斐波那契问题

斐波那契数列，指的是这样一个数列：1、1、2、3、5、8、13、21...，除第1，2位的数为1外，其他数为前两位数字的相加之和。

1.斐波那契数列与经典兔子繁殖问题

一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么在有1个月大的一对兔子的条件下一年以后可以繁殖多少对兔子？

我们可以分析一下。

第一个月一对兔子A生出一对小兔B。

第二个月还是原来的一对兔子A生出一对小兔C。

第三个月A生出一对小兔D,B生出一对小兔E。

第四个月A生出一对小兔F，B生出一对小兔G，C生出一对小兔H。

依次类推......如下表所示：

月份	1	2	3	4	5	6	7	8	9	10	11	12
每个月新出生的兔子对数	1	1	2	3	5	8	13	21	34	55	89	144

 

 

一年后繁殖的兔子对数量为:1+1+2+3+5+8+13+21+34+55+89+144

2.C语言使用递归来实现斐波纳契数列

long fibonacci(int n);

#include <stdio.h> #include <stdlib.h> #include "fibonacci.h"


int main(void) { int n; long result; scanf("%d",&n); result=fibonacci(n); printf("%ld",result); return EXIT_SUCCESS; } long fibonacci(int n) { if( n>0 && n<=2 ) return 1; else
        return fibonacci(n-1)+fibonacci(n-2); }

递归带来的好处是使算法变得更加简明，可读性高。然而，使用递归也带来了额外的内存开销.可以考虑使用迭代实现斐波那契。

3.C语言使用迭代来实现斐波那契数列

#include <stdio.h> #include <stdlib.h> #include "fibonacci.h"


int main(void) { int n; long result; scanf("%d",&n); result=fibonacci(n); printf("%ld",result); return EXIT_SUCCESS; } long fibonacci(int n) { long result,previous_result,temp; result = previous_result =1; while(n>2) { temp = result; result += previous_result; previous_result = temp; n -= 1; } return result; }

原先自己的第一个思路是使用一个long数组存放斐波那契数列，在最后的第n位再把前两项的数字相加返。但这样做的话会浪费掉很多用不到的数组内存，所以改进为使用3个变量，一个记录前一个结果，一个记录当前结果,一个做为中间的temp变量，作为一个交换的介体。

4.斐波那契查找

斐波那契数列又称为黄金分割数列。为什么叫做黄金分割数列呢？理由是当n趋近于无穷大的时候，后一项和前一项的比值越来越接近黄金分割1.618.  3/2=1.5，5/3=1.666，8/5=1.6，13/8=1.625...

数学背景：数字0.618…更为数学家所关注，它的出现，不仅解决了许多数学难题(如：十等分、五等分圆周；求18度、36度角的正弦、余弦值等)，而且还使优选法成为可能。优选法是一种求最优化问题的方法。如在炼钢时需要加入某种化学元素来增加钢材的强度，假设已知在每吨钢中需加某化学元素的量在1000—2000克之间，为了求得最恰当的加入量，需要在1000克与2000克这个区间中进行试验。通常是取区间的中点(即1500克)作试验。然后将试验结果分别与1000克和2000克时的实验结果作比较，从中选取强度较高的两点作为新的区间，再取新区间的中点做试验，再比较端点，依次下去，直到取得最理想的结果。这种实验法称为对分法。但这种方法并不是最快的实验方法，如果将实验点取在区间的0.618处，那么实验的次数将大大减少。这种取区间的0.618处作为试验点的方法就是一维的优选法，也称0.618法。实践证明，对于一个因素的问题，用“0.618法”做16次试验就可以完成“对分法”做2500次试验所达到的效果。因此大画家达·芬奇把0.618…称为黄金数。

#include <stdio.h>
#define MAX_SIZE 30
int fibonacci(int n); int main (void) { /*准备工作*/
    int n,i,key; printf("Please input n:"); scanf("%d",&n); int list[MAX_SIZE]; printf("Please input your sorted array:"); for(i=1 ; i<=n ;i++) { scanf("%d",&list[i]); } printf("Please input the key:"); scanf("%d",&key); /*比较找到不小于n的斐波那契数的位置*/
    int k = 1; while(n>fibonacci(k)) { k++; } /*在n的个数不足找到的斐波那契数，用list【n】补齐*/
    for(i=n+1; i<=fibonacci(k); i++) { list[i]=list[n]; } /*定义key的位置*/
    int pos = -1; int low,high,mid; low = 1; high = n; while(low <= high) { mid =low + fibonacci(k-1) -1; if(key < list[mid]) { high=mid - 1; k = k-1; } else if(key > list[mid]) { low=mid + 1; k = k-2; } else { if(mid<n) { pos = mid; break; } else { pos = n; break; } } } printf("The result position is %d.",pos); return 0; } int fibonacci(int n) { int result,previous_result,temp; result = previous_result = 1; while(n>2) { temp=result; result+=previous_result; previous_result=result; n--; } return result; }

 对斐波那契查找可能存在两个比较难理解的地方。

(1)

/*在n的个数不足找到的斐波那契数，用list【n】补齐*/
for(i=n+1; i<=fibonacci(k); i++) { list[i]=list[n]; }

由于斐波那契查找是基于斐波那契数列的查找，要求有序表的个数必须是存在于斐波那契数列中的数，所以在数不足的情况下，如n=10，fibonacci(7)=13 > 10，必须将有序表的个数扩增到等于斐波那契数，则list[11]=list[12]=list[13]=list[n]。

(2)

if(key < list[mid]) { high=mid - 1; k = k-1; } else if(key > list[mid]) { low=mid + 1; k = k-2; }

在key<list[mid] 的情况下 k=k-1，ket > list [mid] 的情况下 k=k-2。这又是为什么呢？

对于斐波那契查找，分割是从mid =low + fibonacci(k-1) -1 开始的，现在数组的长度为fibonacci(k)，mid 将数组分为两个部分，前一部分为[1,mid]，长度为fiboncaai(k-1)，则后一部分的长度为fibonacci(k)-fibonacci(k-1)，根据斐波那契的性质，f(k) - f(k-1) = f(k-2)，则后一部分的长度为fibonacci(k-2)，所以当key > list[mid] 的时候 k = k - 2。

斐波那契的时间复杂度也为O(log n)，相对与择半查找进行加法与除法运算(mid=(low + high)/2 )，斐波那契查找只是最简单加减法运算( mid = low + fibonacci(k-1) -1 )，在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率。