时间戳

首页 > 解决方案 > 如何从斐波那契数中提取所有值到n？

javascript - 如何从斐波那契数中提取所有值到n？

问题描述

我需要在不使用数组的情况下使用递归编写函数。这会将斐波那契数字的所有值返回到n. n > 0;

function fib(number) {
  if (number === 1) {
    return "0,1,1";
  }
  if (number === 2) {
    return "0,1,1,2,";
  } else {
    let fibList = fib(number - 1);
    return (fibList += `${number - 2 + number - 1},`);
  }
}
console.log(fib(45));

我的代码不能按我的意愿工作，我不知道如何修复它。

n=7 “0, 1, 1, 2, 3, 5 “

n=45 “0, 1, 1, 2, 3, 5, 8, 13, 21, 34”

标签： javascript

解决方案

有点有趣的问题。它有助于使用一些数学理论。可以证明一个数字 ,n是一个斐波那契数当且仅当其中一个5*n**2 + 4或5*n**2 - 4是一个完美的正方形（见此证明）。使用这种特性，很容易直接编写一个递归函数。这是一个 Python 示例，您应该能够将其移植到 JavaScript：

import math

def perfect_square(n):
    return int(math.sqrt(n)) ** 2 == n

def is_fib(n):
    return perfect_square(5*n**2 + 4) or perfect_square(5*n**2-4)

def fibs_below(n):
    if n == 1:
        return "0 1 1"
    elif is_fib(n):
        return fibs_below(n-1) + ' ' + str(n)
    else:
        return fibs_below(n-1)

例如：

>>> fibs_below(45)
'0 1 1 2 3 5 8 13 21 34'

推荐阅读