斐波那契数列在很多问题上得到了应用。下面通过一些具体的实例加以说明。

【例1】钢管切割

问题描述

给一根长度为n的钢管，问最多能切割成几段钢管，使得截成的钢管互不相等且均不能构成三角形。

输入

输入文件的第一行包含整数T（1≤T≤10） ，表示测试用例的数量。

每个测试用例包含一行，包括整数N（1≤N≤1018）表示钢管的长度。

输出

对于每个测试用例，输出一行，一个整数表示它可以切割成的最大段数。

输入样例

1

6

输出样例

3

        （1）编程思路。

        本题是斐波那契数列的典型应用。

        下面先以长度为150的钢管切割为例进行说明。

        由于形成三角形的充要条件是任何两边之和大于第三边，因此不构成三角形的条件就是存在两边之和不超过另一边。而要将钢管切割出的段数更多，则开始应尽可能切割出满足要求的长度最短的钢管，因此开始可以切割出一根长度为1和一根长度为2的两根钢管（切割出的钢管长度互不相同），第3根钢管的长度应该是3（为了使得切割的段数最大，因此要使剩下来的钢管尽可能长，因此每一根钢管总是前面的相邻2根钢管长度之和），之后依次为：1、2、3、5、8、13、21、34、55，以上各数之和为 142，与 150 相差 8，因此可以取最后一段钢管长度为 63，这时段数达到最大为 9。

       在这个示例中，142是斐波那契数列的前项和，我们要把150超出142的部分加到最后的一个数上去，如果加到其他数上，就有3根钢管可以构成三角形了。

        （2）源程序。

#include <stdio.h>
int main()
{
    long long f[110]={0,1,2},fsum[110]={0,1,3};
    int i;
    for (i=3; i<100; i++)
    {
        f[i] = f[i-1] + f[i-2];
        fsum[i] = fsum[i-1] + f[i];
    }
    int t;
    scanf("%d",&t);
    while (t--)
    {
        long long n;
        scanf("%lld",&n);
        for (i=1; i<100; i++)
        {
            if (fsum[i] == n)
            {
                break;
            }
            else if (fsum[i]>n)
            {
                i--;
                break;
            }
        }
        printf("%d\n",i);
    }
    return 0;
}

        将上面的源程序提交给HDU题库 HDU 5620 KK's Steel  （http://acm.hdu.edu.cn/showproblem.php?pid=5620），可以Accepted。

【例2】三角形

问题描述

给定n根直棒，能否在这n根直棒中找出3根棒子组成一个三角形。

输入

输入有多个测试用例。

每个测试用例都以包含整数n的行开始（1≤n≤10⁶），这表示直棒的数量，然后是n个正整数（小于2³¹−1） 用空格隔开。

输出

每个用例输出“YES”或“NO”表示可以或不能用三根直棒组成一个三角形。

输入样例

4

1 2 3 4

输出样例

YES

          （1）编程思路。

         由例1可知，三角形的三边关系定理和斐波那契数列存在着一定的联系。由于斐波拉契数列级别增长很快，因此若n>=50，肯定可以找到3根直棒组成三角形。

         如果不能组成三角形，输入数的个数 n< 50。将这n个数从小到大排序，排序后，再遍历这n个数，若存在相邻两个数的和大于之后的1个数，即存在a[i-2]+a[i-1]>a[i]，则这3根直棒可以组成三角形。

        （2）源程序。

#include <stdio.h>
int main()
{
    int n;
    while (scanf("%d",&n)!=EOF)
    {
        int i,j;
        int flag = 0;
        if (n < 50)
        {
            int a[50];
            for (i = 0; i < n; i++)
               scanf("%d", &a[i]);
            for (i=0;i<n-1;i++)
                for (j=0;j<n-1-i;j++)
                   if (a[j]>a[j+1])
                   {
                      int tmp;
                      tmp=a[j]; a[j]=a[j+1]; a[j+1]=tmp;
                   }
            for (i = 0; i < n - 2; i++)
               if (a[i]+a[i+1]>a[i+2]) { flag = 1; break; }
        }
        else
        {
            int x;
            for (i = 0; i < n; i++)
               scanf("%d", &x);
            flag = 1;
        }
        if (flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

      将上面的源程序提交给HDU题库 HDU 6512 Triangle  （http://acm.hdu.edu.cn/showproblem.php?pid=6512），可以Accepted。

【例3】不包含相邻1的序列

问题描述

给定正整数n，确定在长度为n的0、1序列中不包含相邻1的序列的数量。例如，对于n＝3，答案是5（序列000、001、010、100、101满足要求，而011、110、111是不满足要求的）。

输入

第一行包含测试用例的数量。

对于每一个测试用例，在一行中单独给定一个小于45的正整数。

输出

每个测试用例的输出都以包含“Scenario #i：”的行开始，其中i是从1开始的测试用例数。然后输出一行，其中包含没有相邻1的n位序列个数。用空行终止方案的输出。

输入样例

2

3

1

输出样例 

Scenario #1:

5

 

Scenario #2:

2

        （1）编程思路。

        设a[i]表示长度为i的0、1序列中不包含相邻1的序列的数量，在长度为 i 的序列后面再加上1位可以构成长度为 i+1 的序列。若后面添加0，直接添加在长度为i的序列后面即可，有a[i]种序列；若后面添加1，则前面只能为0，即在长度为i-1的合法序列后面添加“01”，有a[i-1]种序列。 因此，a[i+1]=a[i]+a[i-1]。也就是斐波那契数列。

        （2）源程序。

#include <stdio.h>
int main()
{
    long long a[50];
    a[1] = 2;
    a[2] = 3;
    int i;
    for (i=3; i<=45; i++)
    {
        a[i]=a[i-1]+a[i-2];
    }
    int t,n;
    scanf("%d",&t);
    for (i=1;i<=t;i++)
    {
        scanf("%d",&n);
        printf("Scenario #%d:\n",i);
        printf("%lld\n\n",a[n]);
    }
    return 0;
}

      将上面的源程序提交给北大POJ 题库POJ 1953 World Cup Noise （http://poj.org/problem?id=1953），可以Accepted。

【例4】合并相邻的1        

问题描述

给定一个仅包含“1”的字符串；可以将两个相邻的“1”合并为“2”，或将“1”保留在那里。这样，可能会得到很多不同的结果。例如，给定1111，可以得到1111、121、112、211、22。现在，你的工作是找到你可以得到的结果总数。

输入

第一行是数字n，表示测试用例的数量。接下来是n行，每行都有一个由“1”组成的字符串。序列的最大长度为200。

输出

输出包含n行，每行输出可以获得的结果数。

输入样例

3

1

11

11111

输出样例

1

2

8

        （1）编程思路。

      设a[i]表示由i个1组成的字符串可以获得的结果数。当字符串长度增加到 i+1 时，最后一个1不参与合并，就单独保留在那里，可以得到的结果数为a[i]；若最后1个1要参与合并，则只能与其前面的1个1合并，结果相当于在长度为i-1的字符串后面加了一个2，可以得到的结果数为a[i-1]。因此，a[i+1]=a[i]+a[i-1]。同样也就是斐波那契数列。但由于题目给定的n最大为200。结果超过了长整数能表示的范围，因此需要采用高精度计算。

        （2）源程序。

#include <stdio.h>
#include <string.h>
#define MOD 100000000
struct BigNumber
{
   int len;
   int num[205];
};
int main()
{
    struct BigNumber  f[205];
    memset(f[1].num,0,sizeof(f[1].num));
    memset(f[2].num,0,sizeof(f[2].num));
    f[1].len=f[2].len=1;
    f[1].num[0]=1;  f[2].num[0]=2;
    int i,j;
    for (i=3;i<=200;i++)
    {
        memset(f[i].num,0,sizeof(f[i].num));
        f[i].len = f[i-1].len;
        int cf=0;
        for (j=0;j<f[i].len;j++)
        {
           int num=f[i-1].num[j]+f[i-2].num[j]+cf;
           f[i].num[j]=num%MOD;
           cf=num/MOD;
        }
        if (cf!=0)  f[i].num[f[i].len++]=cf;
    }
    int t;
    scanf("%d",&t);
    while (t--)
    {
        char s[205];
        scanf("%s",s);
        int n=strlen(s);
        printf("%d",f[n].num[f[n].len-1]);
        for (i=f[n].len-2;i>=0;i--)
            printf("%08d",f[n].num[i]);
        printf("\n");
    }
    return 0;
}

        将上面的源程序提交给HDU题库 HDU 1865 1sting （http://acm.hdu.edu.cn/showproblem.php?pid=1865），可以Accepted。

 【例5】最大和

问题描述

给定一个由n个正整数构成的序列A，每次从序列中选取两个数相加后，将新数加入序列A中。问这样操作k次后，序列A中所有数的和最大为多少?

输入

输入包括多个测试用例。每个测试用例第一行包含两个整数n和k（2≤n≤100000，1≤k≤1000000000)，第二行包含n个元素ai（1≤ai≤100000），表示序列A。

输出

对于每个测试用例，输出序列A的最大总和（mod 10000007）。

输入样例

3 2

3 6 2

输出样例

35

         （1）编程思路。

        要使序列中所有整数的和最大，每次操作时要选序列当前最大和次大的数相加，然后加入序列中。

        设序列当前最大数和次大数分别为a，b，则操作第1、2、3、4、5…次操作加入的数分别为a+b、2a+b、3a+2b、5a+3b、8a+5b…，可以推出第k次a和b的系数为fib(k+1)、fib(k)。

        序列新添加的数之和为 a*(fib[2]+fib[3]+..fib[k+1]) + b*(fib[1]+fib[2]+..fib[k])。

        根据 (fib[1]+fib[2]+..fib[k]) = fib[k+2]-1，用矩阵快速算出fib[k+2]后计算即可。

        （2）源程序。 

#include <stdio.h>
#define MODNUM 10000007
struct Matrix {
      long long s11 , s12 , s21 , s22 ;
};
typedef struct Matrix matrix;
matrix f(matrix a,matrix b)
{
      matrix p ;
      p.s11 = (a.s11*b.s11 + a.s12*b.s21)%MODNUM;
      p.s12 = (a.s11*b.s12 + a.s12*b.s22)%MODNUM;
      p.s21 = (a.s21*b.s11 + a.s22*b.s21)%MODNUM;
      p.s22 = (a.s21*b.s12 + a.s22*b.s22)%MODNUM;
      return p ;
}
matrix quickpow(matrix p,long long n)    // 采用递归的方法实现矩阵快速幂运算
{
      matrix q ;
      q.s11 = q.s22 = 1 ;                                     // 初始化为单位矩阵
      q.s12 = q.s21 = 0 ;
      if (n == 0)
           return q ;
      q = quickpow(p,n/2);
      q = f(q,q);
      if (n%2)
           q = f(q,p);
      return q ;
}
int main()
{
      long long k ;
      int n,i;
      while (scanf("%d%lld",&n,&k)!=EOF)
      {
          long long ans=0,a=0,b=0,x,i;
          for (i=1;i<=n;i++)
          {
              scanf("%lld",&x);
              ans=(ans+x)%MODNUM;
              if (a<=x)
              {
                  b=a;  a=x;
              }
              else if (b<x)
                b=x;
          }
          matrix p ;
          p.s11 = p.s12 = p.s21 = 1 ;
          p.s22 = 0 ;
          p = quickpow(p,k+2);
          long long x1,x2,res;
          x1=p.s11-1;
          x2=p.s21-1;
          res=(x1*a)%MODNUM+(x2*b)%MODNUM;
          res=(res-a+MODNUM)%MODNUM;
          ans=(ans+res)%MODNUM;
          printf("%lld\n",ans);
      }
      return 0;
}

         将上面的源程序提交给HDU题库 HDU 5171 GTY's birthday gift （http://acm.hdu.edu.cn/showproblem.php?pid=5171），可以Accepted。