关于 斐波那契数列 的引申
最基本的函数模型是：
/ 0 n=0
f(n)= 1 n=1
\ f(n-1)+(f-2) n>1
我们一般的解法是：
int fun( int n )
{
if ( 0 == n )
{
return0;
}
elseif ( 1 == n )
{
return1;
}
else
{
returnfun(n - 1) + fun(n - 2);
}
}
但是递归在大的数据的情况下可能超时( 特别是在OJ上的时候 )
那么我们想想还可以用：
#include <stdio.h>
int main()
{
long long f[51] = { 0, 1 };
long long n, a0 = 0, a1 = 1;
int i;
for( i = 2; i <= 50 ; i++ )
{
f[i] = a0 + a1; // 此处只要遍历一次就ok
a0 = a1;
a1 = f[i];
}
while( scanf("%d", &n) != EOF ) // 我们可以得到任意的n的 Fibonacci 结果
{
printf("%lld\n", f[n]);
}
return 0;
}
此处还要介绍一个非常好的办法：利用矩阵( 在刷oj的时候想到的 )
Fibonacci 说白了就是一个递推序列，f( n ) = f( n - 1 ) + f( n - 2 );
变形一下有： f( n ) = 1 *f( n - 1 ) + 1 * f( n - 2 );
那么使用矩阵表示就是：( 注意：下面表示的不好看，其实是矩阵表示，见谅！ )
| f( n ) | | 1 1 | | f( n-1 ) |
| f( n-1 ) | = | 1 0 | * | f( n-2 ) |
即：
| f( n ) | | 1 1 | | f( 1 ) |
| f( n-1 ) | = | 1 0 | ^( n-1 ) * | f( 0 ) |就是那个| 1 1 |
| 1 0 | 的n-1次方后 乘以 初始化的两个数就是！
#include <stdio.h>
long long all[71];
void fun( int n )
{
int i;
long long mat[2][2] = { 1, 0, 0, 1 }; // 单位矩阵
long long tmp[2][2];
for( i = 2; i <= n; i++ )
{
tmp[0][0] = mat[0][0];
tmp[0][1] = mat[0][1];
tmp[1][0] = mat[1][0];
tmp[1][1] = mat[1][1];
mat[0][0] = tmp[0][0] + tmp[0][1];
mat[0][1] = tmp[0][0];
mat[1][0] = tmp[1][0] + tmp[1][1];
mat[1][1] = tmp[1][0];
all[i] = mat[0][0] * all[1] +mat[0][1] * all[0];
}
}
int main()
{
int n;
all[0] = 0;
all[1] = 1;
fun( 70 );
while( scanf("%d", &n) != EOF)
{
if( n == 0 )
{
printf("0\n");
}
else if( n == 1 )
{
printf("1\n");
}
else
{
printf("%lld\n",all[n]);
}
}
return 0;
}关于 Fibonacci 的变体：
1》青蛙跳台阶问题:
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析：
当n =1， 只有1中跳法；当n =2时，有2种跳法；当n = 3 时，有3种跳法；当n = 4时，有5种跳法；当n = 5时，有8种跳法
所以还是Fibonacci 序列，只不过初始化为：f(1) = 1; f(2) = 2;
#include <stdio.h>
long long all[71];
void fun( int n )
{
int i;
long long mat[2][2] = { 1, 0, 0, 1 }; // 单位矩阵
long long tmp[2][2];
for( i = 3; i <= n; i++ )
{
tmp[0][0] = mat[0][0];
tmp[0][1] = mat[0][1];
tmp[1][0] = mat[1][0];
tmp[1][1] = mat[1][1];
mat[0][0] = tmp[0][0] + tmp[0][1];
mat[0][1] = tmp[0][0];
mat[1][0] = tmp[1][0] + tmp[1][1];
mat[1][1] = tmp[1][0];
all[i] = mat[0][0] * all[2] +mat[0][1] * all[1];
}
}
int main()
{
int n;
all[0] = 0;
all[1] = 1;
all[2] = 2;
fun( 70 );
while( scanf("%d", &n) != EOF)
{
if( n == 0 || n == 1 )
{
printf("1\n");
}
else
{
printf("%lld\n",all[n]);
}
}
return 0;
}
或者代码为：
（ 下面的代码计算大的数的时候可能超时，不建议 ）
#include <stdio.h>
int count;
void fun( int s, int i, int n )
{
s += i;
if( s == n )
{
count++;
return;
}
else if( s > n )
{
return;
}
else // 此处分叉
{
fun( s, 1, n );
fun( s, 2, n );
}
}
int main()
{
int n;
while( scanf("%d", &n) != EOF)
{
count = 0;
fun( 0, 0, n );
printf("%d\n", count);
}
return 0;
}
2》 跳台阶问题（变态跳台阶）
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法
分析：
/ 1 n=1
f(n)= 2 n=2
\ f(n-1)+(f-2) n>2
#include <stdio.h>
int main()
{
long long f[51] = { 0, 1, 2 };
long long n = 3, sum = 3;
int i;
for( i = 3; i <= 50 ; i++ )
{
f[i] = sum + 1;
sum += f[i];
}
while( scanf("%d", &n) != EOF )
{
printf("%lld\n", f[n]);
}
return 0;
}
3》 矩形覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
分析：
同上!（ 说到底还是其变形 ）
#include <iostream>
using namespace std;
int main()
{
long long f[71];
int i;
int n;
f[0] = 1;
f[1] = 1;
for( i = 2; i <= 70; i++ )
{
f[i] = f[i-1] + f[i-2];
}
while( cin >> n )
{
cout << f[n] << endl;
}
return 0;
}