Chinaunix

标题: Fibonacci数列C语言算法问题 [打印本页]
作者: mcmay    时间: 2013-03-28 17:54
标题: Fibonacci数列C语言算法问题
    请各问各位前辈，用C语言编一个程序计算出斐波那契数列的第N位数，如果不用递归算法而是用循环的话，应该如何实现呢（最好也不用数组）？我想了一个下午都没有任何进展，请各位帮忙看看。感激不尽！
   下面我做了个函数调用的测试，但关键部位还是想不出来。
  1. #include <stdio.h>

  3. unsigned long test_fibonacci(int n);


  6. int main(void)
  7. {
  8.     int n;
  9.    
  10.     printf("Enter a positive integer (q to quit): ");
  11.     while(scanf("%d", &n) == 1)
  12.     {
  13.         printf("\nThe %dth number in the fibonacci numbers is %lu",
  14.                n, test_fibonacci(n));
  15.         printf("\nEnter a positive integer (q to quit): ");
  16.     }
  17.     puts("\nDone!");

  19.     return 0;
  20. }

  22. unsigned long test_fibonacci(int n)
  23. {
  24.     int i, sum = 0;

  26.     if(n <= 2)
  27.         sum = 1;
  28.     else
  29.         for(i = 2; i <= n; i++)
  30.         {
  31.         }

  33.     return sum;
  34. }
复制代码
作者: windoze    时间: 2013-03-28 18:37
搞个数组，把每个算过的值都存起来。
贴个python的循环程序
  1. f=[0,1]
  2. for n in range(2, 10):
  3.         f.append(f[n-1]+f[n-2])
  4. print f[-1]
复制代码
作者: mcmay    时间: 2013-03-28 18:43
windoze 发表于 2013-03-28 18:37
搞个数组，把每个算过的值都存起来。
贴个python的循环程序

谢谢你，丰衣足食。用数组来存储有其可取之处，不过很难确定数组的大小，因为不知程序的使用者想制定斐波那契数列中的哪一位，所以最好能够避免使用数组。
请各位继续不吝赐教！多谢！
作者: pmerofc    时间: 2013-03-28 18:43
提示: 作者被禁止或删除 内容自动屏蔽
作者: mcmay    时间: 2013-03-28 18:49
pmerofc 发表于 2013-03-28 18:43
回复 1# mcmay


你好，pmerofc。就是说，比如：1 1 2 3 5 8 13 21 ...，如果N = 3就是2，N = 6就是8，等等。谢谢！
作者: windoze    时间: 2013-03-28 18:53
本帖最后由 windoze 于 2013-03-28 18:53 编辑

回复 3# mcmay

其实这个问题远比你想象的麻烦，首先，只要你用的是递推公式，把N之前的所有项都算一遍是不可避免的，如果你不存中间结果，那将会是一个O(2^n)复杂度的算法；其次，算不了多少个你就会发现用int之类的类型存不下了，还得搞个大整数的库神马的。
作者: pmerofc    时间: 2013-03-28 20:00
提示: 作者被禁止或删除 内容自动屏蔽
作者: folklore    时间: 2013-03-28 20:45
这个很简单吧
  1. #include <stdio.h>

  3. unsigned long fibonacci(unsigned long N){
  4.         unsigned long ar[] ={0UL,1UL,1UL,2UL};
  5.         unsigned long iAnswer =0;
  6.         for(iAnswer =1UL;iAnswer <N;iAnswer++){
  7.                 ar[(iAnswer +1)&0x03UL] =ar[(iAnswer -1)&0x03UL] +ar[iAnswer&0x03UL];       
  8.         }
  9.         return ar[iAnswer&0x03UL];
  10. }

  12. int main(void){
  13.         for(unsigned long iN =1;iN <20; iN++){
  14.                 printf("%ld ",fibonacci(iN));
  15.         }
  16.         return 0;
  17. }
复制代码
作者: pmerofc    时间: 2013-03-28 21:03
提示: 作者被禁止或删除 内容自动屏蔽
作者: mcmay    时间: 2013-03-28 21:31
听君一席话，胜读十年书。楼上几位的点拨让我茅塞顿开！尤其是pmerofc和folklore两位仁兄的代码解析，迭代法在此又展神威。还请folklore说一下代码中“&0x03UL”是什么，我有些看不明白。好像是将数组元素个数往后延展，不过不知如何达到这个功能的，看起来有点像汇编的样子。
作者: folklore    时间: 2013-03-28 21:45
回复 10# mcmay


   x &0x03UL就是 x %4， 目的是让数组成为”环形数组“， 也就是数组元素可以循环往复使用。

用x &0x03UL的目的是避免*/运算，
使用环形数组是为了避免使用特别的逻辑， 这样程序就一目了然了， 因为代码要表达的逻辑和算法理论的逻辑严格一致
作者: mcmay    时间: 2013-03-28 21:54
folklore 发表于 2013-03-28 21:45
回复 10# mcmay

受教了！关于环形数组我还没有学到过，是C99里新加进去的内容吗？在哪里可以学到这些扩展知识？多谢！
作者: folklore    时间: 2013-03-28 22:10
回复 12# mcmay


    环形数组是程序实现的，不是语言特性。
你应当会注意到
  1. for(int i =0;i<100;i++){
  2.     printf("%d ",i%4);
  3. }
复制代码
会输出：
0 1 2 3 0 1 2 3 0 1 2 3 ....
作者: mcmay    时间: 2013-03-29 09:05
folklore 发表于 2013-03-28 22:10
回复 12# mcmay

这样一说就明白了，谢谢folklore兄！不过，我八卦多问一句，像你以及楼上几位这样处理这个问题的知识和经验从何而来？是以前见到过类似情形还是系统地学过的算法中包含了对这个问题的处理方法？
作者: folklore    时间: 2013-03-29 22:26
回复 14# mcmay


    没有什么方法， 只好说： 多写，没想 了



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2