爱德丝

分类

最新评论

最新留言

标签云

友情链接

浏览计数器

1600

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

爱德丝 posted @ 2008-06-12 08:57PM in algorithms with 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. }

 

Comments Feed

1
Cite 邱焜 posted @ 2008-06-12 09:15PM
Head_small
邱焜

不看你代码``自己找SICP看去，一开始就是Fib


2
Cite 爱德丝 posted @ 2008-06-12 09:24PM
Head_small
爱德丝

SICP 是什么？不好意思，我没有那书。说一说思路吧，谢谢。


3
Cite 邱焜 posted @ 2008-06-21 11:37AM
Head_small
邱焜

1+1=2 1+2=3 2+3=5 3+5=8

i=1
j=1
i+=j
print i
j+=i
print j

这样不是更简单？


4
Cite fanOH posted @ 2008-06-21 01:50PM
Head_small
fanOH

......说啥好呢 胖子


5
Cite 邱焜 posted @ 2008-06-22 12:34AM
Head_small
邱焜

ls是第一个用AStyle的， lz是胖子？


6
Cite 爱德丝 posted @ 2008-06-23 02:23PM
Head_small
爱德丝

邱焜 没有考虑到溢出问题啊，这个是关键。问题本身是很简单的，就如你说的那样


7
Cite 邱焜 posted @ 2008-06-23 08:44PM
Head_small
邱焜

别用int行吗`


8
Cite 爱德丝 posted @ 2008-06-24 12:06AM
Head_small
爱德丝

可以啊，但要输出精确的数值


9
Cite 邱焜 posted @ 2008-06-24 10:05PM
Head_small
邱焜

long long long long int



Login