斐波那契数列是这样的一个数列:第一第二项的值都为 1;从第三项开始,第n项的值为n-1的值加上n-2的值。形如 1 1 2 3 5 8 13 21 34 55 89......
而我们需要设计一个程序,来输出它的前n(n<=50)项,并且保证每个数之间有空格,行末没有空格。其实很容易就想到了设计一个函数来计算它的第x项,然后输出。比如这样:
#include <stdio.h> long long int F(int n) { long long int s; if(n==1||n==2) s=1; else s=F(n-1)+F(n-2); return s; } main() { int n,i; long long int x; while(scanf("%d",&n)) { for(i=1;i<=n;i++) { x=F(i); if(i==1) printf("%lld",x); else printf("% lld",x); } printf(" "); } }
而这个程序有一个问题,那就是在输出比较靠后的几项的时候是一个一个蹦出来的,这样很容易时间超限。这是为什么呢?因为用了函数!!
在函数运算每一项的时候,都会去递归推导,而当 i 越来越大的时候,程序要用的时间就越来越多。所以我们必须要想个办法,不用函数,而实现推导过程。
所以,有了这个程序:
#include <stdio.h> main() { int n,i; long long int x,y,z; while(scanf("%d",&n)) { y=0; z=1; for(i=1;i<=n;i++) { x=y+z; if(i==1) printf("%lld",x); else printf(" %lld",x); y=z; z=x; } printf(" "); } }
它定义了三个量,x,y,z; x 很明显是当前项的值,z,y是前两项,在输出x后,把 z 的值给了 y,x 的值给了 z,下一次循环开始后,x=z+y;如此往复,实现了推导。
那我是如何实现每个数间有空格,而行末没有空格的呢?
很明显,我在输出第一个数时没有空格,而从第二个数开始,输出格式变为了 :空格+数;
这样就确保了你行末没有空格。