javascript 斐波那契

JavaScript05

javascript 斐波那契,第1张

斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）

运行结果如下：

i=0j=1k=0Fibonacci(0)=0

i=1j=0k=1Fibonacci(1)=1

i=2j=1k=1Fibonacci(2)=1

i=3j=1k=2Fibonacci(3)=2

i=4j=2k=3Fibonacci(4)=3

......

i数列的序号，这个程序会打印的数列长度为50

j存放的是F(n-2)的结果

k 存放的是F(n-1)的结果

每次循环时，先获取 F(n) = j+k ，然后将F(n-1)付给 j (j=k) 对应的下次循环的F(n-2) ,

将F(n)付给 k (k=fib) 对应的下次循环的F(n-1) 。

当第一次进入时，F(n) = j+ k = 0 + 0 = 0

当第二次进入时，F(n) = j + k = 1 + 0 =1然后 j=1 ,k = 1

当第三次进入时，F(n) = j + k = 1 + 1 = 2然后 j=1 ,k = 2

当第四次进入时，F(n) = j + k = 1 + 2 = 3然后 j=2 ,k = 3

当第五次进入时，F(n) = j + k = 2 + 3 = 5然后 j=3 ,k = 5

......

动态规划算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。

其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立。即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解。

[0,1,1,2,3,5,8,13...]

递归写发

第一种方法可以在优化，因为不需要列出数组，只需要有前两值即可

题目出一个金额，和硬币面值。答：凑成这个金额所需的 最少的硬币个数