前言 明天就是擁抱情人節，情侶們會在公開的場合擁抱，向世人宣告你倆的愛意，也讓這個寒冷的冬天變得格外溫馨。到了年底依然能熱情擁抱，也見證了兩人情意如昔。 今天子川就給大家帶來就是的利用Python製作表白神器，記得發給自己的心儀對象。廢話不多說直接開整~ 開發工具 Python版本： 3.6 相關模 ...
斐波那契數列在很多問題上得到了應用。下麵通過一些具體的實例加以說明。
【例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。
