我怎样才能让我的迭代算法工作？

Question

我正在使用公式 T_n = T_{n - 1} + T_{n 编写迭代算法- 3} 导致序列 { 0, 1, 2, 2, 3, 5, 7, 10, 15, 22, 32, 47, 69, 101 } 等。我不确定该怎么做，但这是我尝试过的：

    public long calculate(long n) {

    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2){
        return 2;
    }
    int firstValue = 1;
    int secondValue = 1;
    int thirdValue;
    



    for (int i = 2; i < n; i++) {
        thirdValue = firstValue;
        firstValue += secondValue;
        secondValue = thirdValue;


    }

    return firstValue;

我想我必须使用某种 forthValue 但不确定如何使用。希望得到一些建议。

Answer 1

对我来说，你的公式看起来像

n = 2n-4

但数字不匹配。

Answer 2

您不能无限期地添加 forthValue 之类的变量 - 要解决此类问题，您可以使用 recursion

所以这看起来像这样：

public class Test {

    public long calculate(long n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2){
            return 2;
        }
        return calculate(n - 1) + calculate(n - 3);
    }
    public static void main(String[] args) {

        Test testClass = new Test();

        for (int i=0; i < 10; i++) {
            System.out.println(testClass.calculate(i));
        }

    }
}

Answer 3

我做了一个JavaScript对应的，但是你当然可以专注于算法。您的 forthValue 可以是每次迭代的 result (firstValue + thirdValue) 并且在 一次迭代完成后 ，我们交换这样的值：-

thirdValue 变为 secondValue

secondValue 变为 firstValue

firstValue 变为 result

以下将起作用：-

//n = n-1 + n-3

function calculate(n) {

    if (n <= 0) {
        return [0];
    }
    if (n == 1) {
        return [0,1];
    }
    if (n == 2){
        return [0,1,2];
    }
    
    let firstValue = 2
    let secondValue = 1
    let thirdValue = 0;
    let result = 0;
    

   const output = [0,1,2];
  
    for (let i = 3; i < n; i++) {
       result = firstValue + thirdValue;
       output.push(result);
       thirdValue = secondValue
       secondValue = firstValue
       firstValue = result;
    }
    return output
    }
    
    let result = calculate(15);
    console.log(result);

另一种方法，如果我们无论如何都要有一个 output 数组，可以使用它来查找下一个值，如下所示：-

//n = n-1 + n-3

function calculate(n) {

    if (n <= 0) {
        return [0];
    }
    if (n == 1) {
        return [0,1];
    }
    if (n == 2){
        return [0,1,2];
    }
    
   
   const output = [0,1,2];
  
    for (let i = 3; i < n; i++) {
       output.push(output[i-3]+output[i-1]);
    }
    return output
    }
    
    let result = calculate(15);
    console.log(result);

Answer 4

(n - 1) + (n - 3) -> 2n - 4 并且作为迭代算法很容易实现，但是看到你的代码我不确定那是你的想法。

public long calculate(long n) {
    long sum = 0;
    for (int i = 0; i < n; i++) {
        sum = 2 * sum - 4;
    }
    return sum;

}

我怎样才能让我的迭代算法工作？

How can I get my iterative algorithm to work?

java

iteration

algorithm