我必须创建自己的 BigInteger 类实现，名为 GrosseZahl(德语“BigNumber”的意思)。我已经实现了这些方法:
-
init()将整数或字符串转换为整数数组。 -
less(GrosseZahl value)如果该数字小于值，则返回 true。 -
add(GrosseZahl summand) -
mult(GrosseZahl factor) -
toString() -
equals(Object obj)
我必须实现的最后一个方法是 fib()，它计算这个 GrosseZahl 的斐波那契数。我必须使用辅助方法来递归计算它。
我最终得到了以下代码:
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)
/* ... */
更新:我做了一些研究，发现当我运行测试( 0 )时，这始终是 calcFib(...) 方法中的 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;
}
}
最佳答案
在 Java 中，您可以操作两种类型的逻辑空间:使用 new 关键字分配的堆；以及使用 new 关键字分配的堆。和堆栈。要执行 Java 中的任何指令，必须将操作数压入堆栈，操作完成后，结果将替换堆栈上的操作数。对于每个方法调用，您都将参数插入堆栈，直到方法返回为止，这些参数不会被删除。
上面的问题是您尝试在方法 java2.GrosseZahl#calcFib/3 中递归地使用堆栈。处理这个问题的常见方法是将算法转换为使用堆空间，堆空间有更多的可用空间。
关于Java:计算自己的数据类型的斐波那契数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29630801/