时间戳

首页 > 解决方案 > 这个递归算法的名称？

java - 这个递归算法的名称？

问题描述

作业 - 编写两个 Java 程序！

第一个使用递归算法。

第二个使用非递归算法。

他们必须确定一个列表（任意长度）是否具有以下模式：

单元格[0] = 2;

单元格[1] = 2squared = 4;

单元格[3] = 4squared = 16;

该模式是单元格 [n+1] 的任何值都等于单元格 [n] 中的值的平方。

例如：2、4、16、256、65536、4294967296

问题：

谁能给我一个代码示例，好吗？

提前致谢！

标签： javalistalgorithmrecursion

解决方案

Here is one way to do it using BigInteger. But even then, I limited the number of terms to 8 as they get quite large.

Iterative call.

BigInteger[] terms = iterative(8);
for (BigInteger b : terms) {
    System.out.println(b);
}
System.out.println("Sequence array for iteration is " + 
(validate(terms) ? "valid" : "invalid"));

Prints

2
4
16
256
65536
4294967296
18446744073709551616
340282366920938463463374607431768211456
Sequence array for iterative is valid

Recusive call

terms = recursive(8);
for (BigInteger b : terms) {
    System.out.println(b);
}
System.out.println("Sequence array for recursion is " + 
(validate(terms) ? "valid" : "invalid"));

Prints

2
4
16
256
65536
4294967296
18446744073709551616
340282366920938463463374607431768211456
Sequence array for recursion is valid

Validation method

public static boolean validate(BigInteger[] terms) {
    for (int i = 1; i < terms.length; i++) {
        if (!terms[i].equals(terms[i-1].pow(2))) {
            return false;
        }
    }
    return true;
}

The iterative approach.

  • simply initialize the first term to Biginteger.TWO.
  • then iterate over the list raising each previous term to the power of 2.
public static BigInteger[] iterative(int n) {
   if (n < 1) {
        throw new IllegalArgumentException("n must be > 0");
    }
    BigInteger[] terms = new BigInteger[n];
    terms[0] = BigInteger.TWO; // 2^2^0 = 2;
    for (int i = 1; i < n; i++) {
        terms[i] = terms[i-1].pow(2);
    }
    return terms;
}

The recursive approach.

Although it can be done without a helper method using one is more straightforward and efficient.

  • allocate the array based on n
  • initialize the 0th element to 2.
  • return immediately if n == 1
  • otherwise, invoke the helper method.
public static BigInteger[] recursive(int n) {
    if (n < 1) {
         throw new IllegalArgumentException("n must be > 0");
    }
    BigInteger[] terms = new BigInteger[n];
    terms[0] = BigInteger.TWO;
    if (n == 1) {
        return terms;
    }
    return recursiveHelper(terms, n);
}
  • recursively call the method until n == 2
  • then simply assign the n-1 element the value in n-2 raised to the power of 2
  • then return the terms.
private static BigInteger[] recursiveHelper(BigInteger[] terms, int n) {
     if (n > 2) {
        recursiveHelper(terms,n-1);
     }
     terms[n-1] = terms[n-2].pow(2);
     return terms;
}

推荐阅读