计算思维实践之路(四)

          什么是斐波那契数列？F_n+1=F_n+F_n-1，这个数列中的每个数字都是前两项数之和，如果是以1，1开头的自然数数列，1，1，2，3，5，8，13，21，34，55，89……这些数字被称为斐波那契数。同时，这个数列中还暗含着黄金比例，如果用数列中的每一个数字去除它后面的数字，数字越大，结果就越趋近于1.618，也就是我们平常所说的黄金比例。    
       科学家发现，一些植物的花瓣、萼片、果实的数目以及排列的方式上，都有一个神奇的规律，它们都非常符合著名的斐波那契数列。例如：蓟，它们的头部几乎呈球状。在右图中，你可以看到两条不同方向的螺旋。我们可以数一下，顺时针旋转的（和左边那条旋转方向相同）螺旋一共有13条，而逆时针旋转的则有21条。此外还有菊花、向日葵、松果、菠萝等都是按这种方式生长的。

     

      有些花瓣的数量和花序的排列确实体现出了斐波那契数列，但是大多数植物的花瓣和叶片排列并不会遵循这个原则。之所以出现斐波那契数和黄金比例的角度，都是能最有效利用空间的模型，而在不需要考虑空间使用的情况下，就会随机分布了，是否出现特别的数列，都与植物对生存环境的适应有密切关系。
      俺老猪用递归代码实现斐波那契：
           例6 递归代码实现斐波那契

#include<stdio.h>
int fibonacci(int n) {
	if(n==1||n==2)//递归终止条件
		return 1;
	else//递归通式
		return (fibonacci(n-1)+fibonacci(n-2));
}
int main() {
	int n;
	printf("请输入1个整数：");
	scanf("%d",&n);
	printf("第%d个斐波那契是%d\n",n,fibonacci(n));
	return 0;
}

            经常见到的其衍生题。比如一次登一个或两个台阶，问登n个台阶有多少种可能？青蛙一次跳一下或两下，问跳n下有几种可能？铺地砖问题等等都是使用斐波那契数列解决。

                 俺老孙试一试这个问题
       例7 一次登一个或两个台阶，问登n个台阶有多少种可能？

#include <stdio.h>
#include <stdlib.h>
static int step[128];
static int m = 1;
int count(int n);
void cout(int n,int t);
int main()
{
	int a,n;
	while(1) {
		printf("请输入需要登上的台阶数量：");
		scanf("%d",&n);
		a = count(n);
		printf("登上%d个台阶共有%d种方法！分别如下：\n",n,a);
		cout(n,0);
		m=1;
	}
	return 0;
}
int count(int n)
{
	if(n == 1)
		return 1 ;
	if(n == 2)
		return 2 ;
	else
		return count(n - 1) + count(n - 2) ;
}
void cout(int n,int t)
{
	int i,j;
	if(n<0)
		return ;
	if(n == 0)
	{
		printf("第%d种方法：",m);
		for(j=0; j<t; j++)
			printf("%d ",step[j]);
		m++;
		printf("\n");
	}
	else
	{
		for(i=1; i<=2; i++)
		{
			step[t] = i;
			cout(n-i,t+1);
		}
	}
}

 

                      

         
                   例8 骨牌铺方格 在2×n的一个长方形方格中，用一个1× 2的骨牌铺满方格,输入n ，输出铺放方案的总数。例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：
      

                        

             Input

                输入数据由多行组成，每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。

            Output

          对于每个测试实例，请输出铺放方案的总数，每个实例的输出占一行。

          Sample Input

1 3 2

         Sample Output

1 3 2

            假设用arr[i]表示2*i的方格一共有组成的方法数，我们知道arr[1]=1;arr[2]=2;

       现在假设我们已经知道了arr[i-1]和arr[i-2],求arr[i],所谓arr[i],不过是在2*（i-1）的格子后边加上一格2*1的方格罢了，骨牌在这一格上横着放，竖着放，如果前面i-1块已经铺好，则第i块只有一种铺法，就是竖着放，如果要横着放，也只有一种铺法，不过要求前面i-2块已经铺好！

       因此arr[i]=arr[i-1]+arr[i-2];

#include<iostream>
using namespace std;
int main() {
    __int64 arr[51];
	int num;
	arr[1]=1;
	arr[2]=2;
	for(int i=3; i<=50; i++)
		arr[i]=arr[i-1]+arr[i-2];
	while(scanf("%d",&num)!=EOF) {
		printf("%I64d\n",arr[num]);
	}
	return 0;
}