个人中心
gpt4 book ai didi

Java:计算自己数据类型的Fibonacci

转载 作者：行者123 更新时间：2023-11-30 08:14:10 25 4
gpt4 key购买 nike

<分区>

我必须创建自己的 BigInteger 类实现，称为 GrosseZahl(德语为“BigNumber”)。我已经实现了这些方法:

  • init() 将整数或字符串转换为整数数组。
  • less(GrosseZahl value) 如果此数字小于 value，则返回 true。
  • add(GrosseZahl 求和)
  • mult(GrosseZahl 因子)
  • toString()
  • equals(Object obj)

我必须实现的最后一个方法是计算此 GrosseZahl 的斐波那契数的 fib()。我必须使用辅助方法来递归计算它。

我最终得到了以下代码:

public GrosseZahl fib() {
    GrosseZahl f0 = new GrosseZahl(1);
    GrosseZahl f1 = new GrosseZahl(1);
    GrosseZahl counter = new GrosseZahl(1);

    return this.calcFib(f0, f1, counter);
}

private GrosseZahl calcFib(GrosseZahl f0, GrosseZahl f1, GrosseZahl counter) {
    GrosseZahl f2;

    if (this.equals(counter))
        return f1;

    counter = counter.add(new GrosseZahl(1));

    f2 = f0.add(f1);
    f0 = f1;

    return calcFib(f1, f2, counter);
}

当我用下面的测试类测试该类时，出现堆栈溢出错误。

package java2;

import static org.junit.Assert.*;

import org.junit.Before;
import org.junit.Test;

public class GrosseZahl_Test {

    GrosseZahl i0;
    GrosseZahl s0;
    GrosseZahl i1;
    GrosseZahl s1;
    GrosseZahl i55;
    GrosseZahl s55;
    GrosseZahl i60;
    GrosseZahl s60;
    GrosseZahl i99;
    GrosseZahl s99;
    GrosseZahl i100;
    GrosseZahl s100;
    GrosseZahl i12345;
    GrosseZahl s12345;
    GrosseZahl i47340;
    GrosseZahl s12345678901234567890;
    GrosseZahl s10345678901234567891;

    @Before
    public void setUp() throws Exception {
        i0 = new GrosseZahl(0);
        s0 = new GrosseZahl("0");
        i1 = new GrosseZahl(1);
        s1 = new GrosseZahl("1");
        i55 = new GrosseZahl(55);
        s55 = new GrosseZahl("55");
        i60 = new GrosseZahl(60);
        s60 = new GrosseZahl("60");
        i99 = new GrosseZahl(99);
        s99 = new GrosseZahl("99");
        i100 = new GrosseZahl(100);
        s100 = new GrosseZahl("100");
        i12345 = new GrosseZahl(12345);
        s12345 = new GrosseZahl("12345");
        i47340 = new GrosseZahl(47340);
        s12345678901234567890 = new GrosseZahl("12345678901234567890");
        s10345678901234567891 = new GrosseZahl("10345678901234567891");
    }

    /* ... */

    @Test
    public void testFib() {
        assertEquals("1", new GrosseZahl(0).fib().toString());
        assertEquals("1", new GrosseZahl(1).fib().toString());
        assertEquals("2", new GrosseZahl(2).fib().toString());
        assertEquals("3", new GrosseZahl(3).fib().toString());
        assertEquals("5", new GrosseZahl(4).fib().toString());
        assertEquals("8", new GrosseZahl(5).fib().toString());
        assertEquals("89", new GrosseZahl(10).fib().toString());
        assertEquals("1346269", new GrosseZahl(30).fib().toString());
    }

}

堆栈溢出错误信息:

java.lang.StackOverflowError
    at java.util.regex.Pattern.sequence(Pattern.java:2134)
    at java.util.regex.Pattern.expr(Pattern.java:1996)
    at java.util.regex.Pattern.group0(Pattern.java:2827)
    at java.util.regex.Pattern.sequence(Pattern.java:2051)
    at java.util.regex.Pattern.expr(Pattern.java:1996)
    at java.util.regex.Pattern.compile(Pattern.java:1696)
    at java.util.regex.Pattern.<init>(Pattern.java:1351)
    at java.util.regex.Pattern.compile(Pattern.java:1028)
    at java.lang.String.replaceFirst(String.java:2166)
    at java2.GrosseZahl.init(GrosseZahl.java:38)
    at java2.GrosseZahl.<init>(GrosseZahl.java:25)
    at java2.GrosseZahl.add(GrosseZahl.java:112)
    at java2.GrosseZahl.calcFib(GrosseZahl.java:158)
    at java2.GrosseZahl.calcFib(GrosseZahl.java:163)
    at java2.GrosseZahl.calcFib(GrosseZahl.java:163)
    at java2.GrosseZahl.calcFib(GrosseZahl.java:163)
    /* ... */

更新:我做了一些研究，发现在 calcFib(...) 方法中它总是 0，当我运行测试时 (GrosseZahl_Test)。所以它永远不会等于计数器，所以 if 语句永远不会为真。但为什么 this 总是 0？如果您在 if 语句上方插入 System.out.println(this) 并运行测试，您可以自己测试它:

private GrosseZahl calcFib(GrosseZahl f0, GrosseZahl f1, GrosseZahl counter) {
    GrosseZahl f2;

    System.out.println(this);

    if (this.equals(counter))
        return f1;

    counter = counter.add(new GrosseZahl(1));

    f2 = f0.add(f1);
    f0 = f1;

    return calcFib(f1, f2, counter);
}

如果我使用 less() 方法而不是 equals()，它确实有效:

public GrosseZahl fib() {
    GrosseZahl f0 = GrosseZahl.ONE;
    GrosseZahl f1 = GrosseZahl.ONE;
    GrosseZahl counter = new GrosseZahl(2);

    return this.calcFib(f0, f1, counter);
}

private GrosseZahl calcFib(GrosseZahl f0, GrosseZahl f1, GrosseZahl counter) {
    GrosseZahl f2;

    System.out.println(this);

    if (this.less(counter))
        return f1;

    counter = counter.add(GrosseZahl.ONE);
    f2 = f0.add(f1);
    f0 = f1;

    return calcFib(f1, f2, counter);
}

这是 GrosseZahl 类的所有代码:

package java2;

import java.util.Arrays;

public class GrosseZahl {

    private int[] digits;
    private int length;
    private String value;

    public GrosseZahl(int value) {
        this.value = Integer.toString(value);
        this.init();
    }

    public GrosseZahl(String value) {
        this.value = value;
        this.init();
    }

    private void init() throws NumberFormatException {
        String[] digits;
        String value = this.value;

        if (value.charAt(0) == '-')
            throw new NumberFormatException("Number must be non-negative.");

        if (!value.matches("\\d+"))
            throw new NumberFormatException("Number must only contain digits.");

        value = value.replaceFirst("^0+(?!$)", "");
        digits = value.split("");

        this.length = digits.length;
        this.digits = new int[this.length];

        for (int i = 0; i < this.length; i++) {
            this.digits[i] = Integer.parseInt(digits[i]);
        }
    }

    public boolean less(GrosseZahl value) {
        if (this.length < value.length)
            return true;

        if (this.length == value.length)
            for (int i = 0; i < this.length; i++) {
                if (this.digits[i] < value.digits[i])
                    return true;
                if (this.digits[i] > value.digits[i])
                    return false;
            }

        return false;
    }

    public GrosseZahl add(GrosseZahl summand) {
        GrosseZahl a;
        GrosseZahl b;
        GrosseZahl result;
        StringBuilder number;
        int carry;
        int offset;
        int sum;

        if (!this.less(summand)) {
            a = this;
            b = summand;
        } else {
            a = summand;
            b = this;
        }

        offset = a.length - b.length;
        carry = 0;
        number = new StringBuilder();

        for (int i = a.length - 1; i >= 0; i--) {
            sum = a.digits[i] + carry;

            if (i >= offset)
                sum += b.digits[i - offset];

            if (sum > 9)
                carry = 1;
            else
                carry = 0;

            /*
             * We append the digit because it uses less memory than prepending.
             */
            number.append(sum % 10);
        }

        /*
         * If carry is still one we need to append an one.
         */
        if (carry == 1) {
            number.append(1);
        }

        /*
         * Since we’ve appended the numbers we need to reverse the order.
         */
        result = new GrosseZahl(number.reverse().toString());

        return result;
    }

    public GrosseZahl mult(GrosseZahl factor) {
        GrosseZahl a;
        GrosseZahl b;
        GrosseZahl result;

        a = this;
        b = factor;
        result = new GrosseZahl(0);

        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < b.length; j++) {
                int zeroes = a.length - i + b.length - j - 2;
                int c = a.digits[i] * b.digits[j];

                StringBuilder sum = new StringBuilder();

                sum.append(c);

                for (int k = 0; k < zeroes; k++)
                    sum.append(0);

                result = result.add(new GrosseZahl(sum.toString()));
            }

        return result;
    }

    public GrosseZahl fib() {
        GrosseZahl f0 = new GrosseZahl(1);
        GrosseZahl f1 = new GrosseZahl(1);
        GrosseZahl counter = new GrosseZahl(1);

        return this.calcFib(f0, f1, counter);
    }

    private GrosseZahl calcFib(GrosseZahl f0, GrosseZahl f1, GrosseZahl counter) {
        GrosseZahl f2;

        if (this.equals(counter))
            return f1;

        counter = counter.add(new GrosseZahl(1));

        f2 = f0.add(f1);
        f0 = f1;

        return calcFib(f1, f2, counter);
    }

    @Override
    public String toString() {
        StringBuilder number = new StringBuilder();

        for (int digit : digits)
            number.append(digit);

        return number.toString();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        GrosseZahl other = (GrosseZahl) obj;
        if (!Arrays.equals(digits, other.digits))
            return false;
        if (length != other.length)
            return false;
        return true;
    }

}

25 4 0
文章推荐： Javascript - 将带有参数的函数作为参数传递
文章推荐： java - Array.newInstance 上传递的通用参数的空指针异常
文章推荐： java - 如何处理 powershell 中 $PSScriptRoot 路径中的空格
文章推荐： java - MouseListener - 不适用于 JTextArea
行者123
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com