斐波那契数列(二)

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

【例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≤106),这表示直棒的数量,然后是n个正整数(小于231−1) 用空格隔开。

输出

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

输入样例

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。   

作者:aTeacher原文地址:https://www.cnblogs.com/cs-whut/p/16975148.html

%s 个评论

要回复文章请先登录注册