斐波那契数列在股市中的使用方法（斐波那契数列（二））

时间2025-05-03 04:26:48分类IT科技浏览3733

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

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

【例1】钢管切割

问题描述

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

输入

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

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

输出

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

输入样例

输出样例

（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）源程序。

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

【例2】三角形

问题描述

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

输入

输入有多个测试用例。

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

输出

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

输入样例

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位序列个数。用空行终止方案的输出。

输入样例

输出样例

Scenario #1:

Scenario #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行，每行输出可以获得的结果数。

输入样例

11111

输出样例

（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

输出样例

（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 GTYs birthday gift （http://acm.hdu.edu.cn/showproblem.php?pid=5171），可以Accepted。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。