首页 > 代码库 > HDU2842之斐波那契亚数列变形，动态规划

HDU2842之斐波那契亚数列变形，动态规划

2024-07-12 18:22:38   218人阅读

1.原题展示：

一根棒子上有n个环(n<=10^9) 第一个环可以随意取下或者放上 如果前k个环都不在棒子上，且第k+1个环在棒子上，则你可以取下或放上第k+2个环 给出n，求最少需要多少步可以取完棒子上的环？

2.思路分析：

如果要把n个环全部拿完，那么我们必须先拿完前n-2个环（只有这样才能拿走第n个环），剩下第n-1个环未拿走。当拿走前n-2个环所花的步骤数目为f(n-2)加上最后一个环，那么所花步数为f(n-2)+1步.对于第n-1个球，如果要拿走它，必须补上前n-2个球，放进去n-2个球所花步数为f(n-2)步。此时棒上共有n-1个环，要全部拿走，则所需步数为f(n-1)步。到这里我们就可以得到递推公式了：f(n)=f(n-2)+1+f(n-2)+f(n-1)=2*f(n-2)+f(n-1)+1.

对于这种递推公式，我们考虑矩阵的快速幂求法，首先我们需要构造出几个基本矩阵。

矩阵init：

1 2 1

1 0 0

0 0 1

矩阵r：（构造有技巧，每次乘init后第一列都会按照f(k-1),f(k-2),1的格式排列，因而保证了递推关系的成立）

2 0 0

1 0 0

1 0 0

所以f(n)为矩阵init^n-2*r的第一个数字。

3.代码如下：

 1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #define size 3 5 #define mod 200907 6 struct Mat 7 { 8 long long num[size][size]; 9 };10 Mat init,r;//定义全局变量；11 void InitMat()//初始化全局变量函数12 {13 int i,j;14 for (i=0;i<size;i++)15 for (j=0;j<size;j++)16 r.num[i][j] = init.num[i][j] = 0;17 r.num[1][0] = r.num[2][0] = init.num[0][0]=init.num[0][2]=init.num[1][0]=init.num[2][2]=1;18 r.num[0][0] = init.num[0][1]= 2;19 }20 21 Mat mul(Mat m,Mat r)//矩阵相乘22 {23 Mat c;24 memset(c.num,0,sizeof(c.num));25 for (int i=0;i<size;i++)26 {27 for (int j=0;j<size;j++)28 {29 c.num[i][j] = 0;30 for(int k=0;k<size;k++)31 c.num[i][j]+=(m.num[i][k]*r.num[k][j])%mod;32 c.num[i][j]%=mod;33 }//矩阵相乘并赋给ans34 35 }36 return c;//返回最后的值37 }38 Mat pow(Mat m,int k)//矩阵的乘方函数39 {40 Mat ans;41 memset(ans.num,0,sizeof(ans.num));//首先置为042 for(int i=0;i<size;i++)43 for(int j=0;j<size;j++)44 if(i==j) ans.num[i][j]=1;//置为单位矩阵45 while(k)46 {47 if(k&1) ans = mul(ans,m);//开始矩阵的乘方48 k >>= 1;49 m = mul(m,m);50 }51 return ans;//返回所求矩阵52 }53 int main()54 {55 int n;56 InitMat();57 while (scanf("%d",&n)!=EOF)58 {59 if(n==1) printf("1\n");60 else if(n==2) printf("2\n");61 else62 {63 Mat multi=pow(init,n-2);64 Mat t=mul(multi,r);65 printf("%lld\n",t.num[0][0]);66 }67 }68 return 0;69 }


联系
我们