斐波那契數列在很多問題上得到了應用，下面通過一些具體的實體加以說明，
【例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） 用空格隔開，
輸出
每個用例輸出“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，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/540125.html
標籤：其他
上一篇：【腳本專案原始碼】Python制作藝術簽名生成器，打造專屬你的個人藝術簽名
下一篇：python模擬股票的資料分析