Zibonacci遞回，我的解決方案有什么問題？-有解無憂

我遵守了規則，但我仍然得到 n>2 的堆疊溢位。

該函式借鑒了斐波那契數列的思想，但計算結果呈現鋸齒形和鋸齒形，因此得名。所謂的“Zibonacci”系列將由以下規則定義：

Zib(0) == 1;
Zib(1) == 1;
Zib(2) == 2;
Zib(2n 1) == Zib(n)   Zib(n-1) 1, if n>0 (i.e. odd values 3 and higher)
Zib(2n) == Zib(n)   Zib(n 1) 1, if n>1 (i.e. even values 4 and higher).

創建 Zibonacci(num) 函式。

我的解決方案：

function Zibonacci(num){
    // Enter code below
    if(num == 0){
       return 1;
    }
    if(num == 1 || num == 2){
       return num;
    }
    if(num>0 && num%2 != 0){
       return Zibonacci(num)   Zibonacci(num-1) 1;
    }
    if(num>1 && num%2 == 0){
       return Zibonacci(num)   Zibonacci(num 1) 1;
    }
}

Zibonacci遞回，我的解決方案有什么問題？

uj5u.com熱心網友回復：

您首先需要重新制定遞回方程以匯出 Z(n) 而不是 Z(2n 1) 和 Z(2n)：

Zib(n) == Zib((n - 1) / 2) Zib((n - 1) / 2 - 1) 1，如果 n>0（即奇數值 3 或更高）
Zib(n) == Zib(n / 2) Zib(n / 2 1) 1，如果 n>1（即偶數值 4 或更高）。

這導致如下代碼：

function Zibonacci(num){
    if (num == 0) {
       return 1;
    }
    if (num == 1 || num == 2) {
       return num;
    }
    if (num > 0 && num % 2 != 0){
       return Zibonacci((num - 1) / 2)   Zibonacci((num - 3) / 2)   1;
    }
    if (num > 1 && num % 2 == 0) {
       return Zibonacci(num / 2)   Zibonacci((num   2) / 2)   1;
    }
}

for (let i = 0; i < 10; i  ) {
    console.log(i, Zibonacci(i));
}

uj5u.com熱心網友回復：

@trincot 是正確的，您必須根據z(n)重寫遞回方程。您可以對其余部分使用歸納推理-

如果n為負數，則拋出錯誤（可選）
（歸納）n是非負的。如果n小于 3，則回傳max(1,n)
（歸納）n大于 2。如果n為奇數，則回傳z((n - 1) / 2) z((n - 1) / 2 - 1) 1
（歸納）n大于 2 且偶數。回傳z(n / 2) z(n / 2 1) 1

function z(n) {
  if (n < 0)
    throw Error
  else if (n < 3)
    return Math.max(1, n)
  else if (n & 1)
    return z((n - 1) / 2)   z((n - 1) / 2 - 1)   1
  else
    return z(n / 2)   z(n / 2   1)   1
}

for (let i = 0; i < 10; i  )
  console.log(i, z(i))

.as-console-wrapper { min-height: 100%; top: 0; }

我們也可以將z寫成純函式運算式——

const z = n => // n for all n >= 0
  n < 3
    ? Math.max(1, n)                            // base
    : n & 1
      ? z((n - 1) / 2)   z((n - 1) / 2 - 1)   1 // odd
      : z(n / 2)   z(n / 2   1)   1             // even

for (let i = 0; i < 10; i  )
  console.log(i, z(i))

.as-console-wrapper { min-height: 100%; top: 0; }

uj5u.com熱心網友回復：

這是代碼

  function Zibonacci(num){
  if(num <= 1) return num;
  return Zibonacci(num -1)   Zibonacci(num-2);
}
console.log(Zibonacci(6));

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/513458.html

標籤：javascript算法递归斐波那契

上一篇：中序遍歷在創建單獨的函式時起作用，但在創建單個函式時不起作用。為什么？

下一篇：帶有onclick事件的嵌套狀態（反應）