爱德丝

分类

最新评论

最新留言

标签云

友情链接

浏览计数器

2155

输出斐波那契数列前1000个数

2008-06-12 08:57PM | Comments(9) | Category:algorithms | Tags:Algorithm

一道面试题。各位如果有更好的算法，请告诉我，谢谢。

  1. #include <stdio.h>
  2. #define N 1000
  3.  
  4. int x[N] = {1, 1};
  5. int y[N] = {1, 1};
  6.  
  7. int compare()
  8. {
  9.     if (x[0] - y[0] != 0)
  10.         return x[0] - y[0];
  11.     else
  12.         return x[x[0]] - y[y[0]];
  13. }
  14.  
  15. void printn(int *a)
  16. {
  17.     static int i = 1;
  18.  
  19.     printf("%d: ", i++);
  20.     printf("%d", a[a[0]]);
  21.     for (int j=a[0]-1; j>=1; --j)
  22.     {
  23.         printf("%04d", a[j]);
  24.     }
  25.  
  26.     printf("\n");
  27. }
  28.  
  29. void addto(int *a, int *b)
  30. {
  31.     b[0] = (a[0] > b[0] ? a[0] : b[0]);
  32.     int tmp = 0;
  33.  
  34.     for (int i=1; i<=b[0]; ++i)
  35.     {
  36.         tmp += a[i] + b[i];
  37.         b[i] = tmp % 10000;
  38.         tmp /= 10000;
  39.     }
  40.  
  41.     if (tmp != 0)
  42.     {
  43.         b[0] += 1;
  44.         b[b[0]] = tmp;
  45.     }
  46. }
  47.  
  48. int main()
  49. {
  50.     for (int i=0; i<N; ++i)
  51.     {
  52.         if (compare() < 0)
  53.         {
  54.             printn(x);
  55.             addto(y, x);
  56.         }
  57.         else
  58.         {
  59.             printn(y);
  60.             addto(x, y);
  61.         }
  62.     }
  63.  
  64.     return 0;
  65. }