首先应当能看出这是个 斐波那契数列，于是有代码
程序代码：
unsigned fs( unsigned n )
{
unsigned a=0, b=1;
for( unsigned i=0; i!=n; ++i )
{
b = b + a;
a = b - a;
}
return b;
}
然后，题目要求 1≤n≤90，那么当n==90时上面的代码 b = b + a 会不会有溢出呢？只能测试一下
程序代码：
#include <stdio.h>#include <stdlib.h>unsigned fs(
unsigned n )
{
unsigned a=
0, b=
1;
for(
unsigned i=
0; i!=n; ++i )
{
if( b+a<a )
{
printf(
"当 n == %u 时结果溢出\n", n );
exit(
1 );
}
b = b + a;
a = b - a;
}
return b;
}
int main(
void )
{
for(
unsigned n=
0; n<=
90; ++n )
{
printf(
"%u - %u\n", n, fs(n) );
}
}
运行后发现当 n==47 时就发生溢出了。于是将类型改大后再测试
程序代码：
#include <stdio.h>#include <stdlib.h>unsigned long long fs(
unsigned n )
{
unsigned long long a=
0, b=
1;
for(
unsigned i=
0; i!=n; ++i )
{
if( b+a<a )
{
printf(
"当 n == %u 时结果溢出\n", n );
exit(
1 );
}
b = b + a;
a = b - a;
}
return b;
}
int main(
void )
{
for(
unsigned n=
0; n<=
90; ++n )
{
printf(
"%u - %llu\n", n, fs(n) );
}
}
这回没溢出了，很好，于是你有了第一份可提交的代码
程序代码：
#include <stdio.h>
unsigned long long fs( unsigned n )
{
unsigned long long a=0, b=1;
for( unsigned i=0; i!=n; ++i )
{
b = b + a;
a = b - a;
}
return b;
}
int main( void )
{
for( unsigned n=0; scanf("%u",&n)==1 && n!=0; )
printf( "%llu\n", fs(n) );
}
然后题目要求多次输入，你一想，这会不会导致fs重复计算呢？比如先输入40再输入50，当计算f(50)时其实前面的f(40)已经算过了，可是改一改有了第二份可提交的代码
程序代码：
#include <stdio.h>
int main( void )
{
unsigned long long fs[91] = { 1, 1 };
for( unsigned i=2; i!=sizeof(fs)/sizeof(*fs); ++i )
fs[i] = fs[i-2] + fs[i-1];
for( unsigned n=0; scanf("%u",&n)==1 && n!=0; )
printf( "%llu\n", fs[n] );
}
那有没有可能出题者很狡诈，说是n<=90，但他给出的测试用例不是每次都有n==90，没有的话，f(90)就白算了，浪费了运行时间。于是改为只结算到最大的输入数
程序代码：
#include <stdio.h>
int main( void )
{
unsigned long long fs[91] = { 1, 1 };
unsigned m = 2;
for( unsigned n=0; scanf("%u",&n)==1 && n!=0; )
{
for( ; m<=n; ++m )
fs[m] = fs[m-2] + fs[m-1];
printf( "%llu\n", fs[n] );
}
}
