绳圈，找规律动态规划。13省梅森素数，李白打酒,递推，算法训练k好数，递归，动态规划

川长思鸟来 2022-11-14 10:08 132阅读 0赞

### 绳圈 ###

[link][].  
参考博客：https://blog.csdn.net/b1723407539/article/details/107974967

#include<bits/stdc++.h>
     using namespace std;
    double p[102][102];
    int main()
    {
           p[1][1]=1;
        for(int i=2;i<=100;i++){
        
                for(int j=1;j<=i;j++){
        
                   //double a=1/(2.0*i-1)*p[i-1];
                   //double b=(2.0*i-2)/(2.0*i-1)*p[i];
                   p[i][j]=1.0/(2.0*i-1)*(p[i-1][j-1]+(2*i-2)*p[i-1][j]);//二维数组
                }
        }
        double mp=0;
        int ans=0;
        for(int i=1;i<=100;i++){
        
            if(mp<p[100][i]) {
        mp=p[100][i];
            ans=i;
            }
        }
       // for(int i=1;i<=100;i++){
        
        //    if(mp==p[100][i]) {ans=i;
        //    }
        //}
        cout<<ans<<endl;
    return 0;
    }

### 13省梅森素数 ###

2  
11213  
−1 这个数字已经很大(有 30003000 多位)，请你编程求出这个素数的十进制表示的最后 100100 位。

#include <iostream>
    #include <vector>
    using namespace std;
    int main()
    {
        
        vector<int> a(101, 0);
        a[1] = 1;
        for (int i = 1; i <= 11213; ++i) {
        
            int c = 0;
            for (int j = 1; j <= 100; ++j) {
        
                a[j] = a[j] * 2 + c;
                c = a[j] / 10;
                a[j] %= 10;
            }
        }
        a[1] -= 1;
        for (int i = 100; i >= 1; --i) {
        
            cout << a[i];
        }
        return 0;
    }

### 李白打酒,递推 ###

[link][link 1].

#include <stdio.h>
    #include <stdlib.h>
    int fun(int a,int b,int now)
    {
         if(a==0)
    {
        if(b==now)return 1;
    else return 0;
    }
    if(b==0)
    {
        if(a==0&&now==0)return 1;
    else return 0;
    }
    
    return fun(a-1,b,now*2)+fun(a,b-1,now-1);
    }
    int main(int argc, char *argv[])
    {
        
     printf("%d\n",fun(5,10,2));
      return 0;
    }

### 算法训练k好数，递归，动态规划 ###

[link][link 2].  
递归

#include <stdio.h>
    #include <math.h>
    using namespace std;
    long long f(int ly, int i, int k)
    {
        
    	if (ly==1)
    		return 1;
    
    	int j;
    	long long sum=0;
    	for (j=0;j<=k-1;j++)
    		if (fabs(i-j)!=1)
    			sum+=f(ly-1,j,k)%1000000007;
    	
    	return sum;
    }
    
    long long F(int k, int L)
    {
        
    	int i;
    	int sum=0;
    	for ( i=1;i<=k-1; i++ )
    		sum+=f(L,i,k)%1000000007;	
    	return sum%1000000007;
    }
    
    int main()
    {
        
    	int k,L;
    	scanf("%d%d",&k,&L);
    //	printf("%I64d",F(k,L));
    	printf("%lld",F(k,L));
    	return 0;
    }

2.非递归实现  
程序执行效率高，速度快。  
根据递推公式，从第1层开始，逐层往下计算出每一层的值。

#include <stdio.h>
    #include <math.h>
    using namespace std;
    int main()
    {
        
    	int k,L;
    	scanf("%d%d",&k,&L);	
    	long long f[101][100]={
        0};
    	int i;
    	for (i=0;i<k;i++)
    		f[1][i]=1;
    	long long sum;
    	int j,p;
    	for (i=2;i<=L;i++)
    	{
        
    		for (p=0;p<k;p++)
    		{
        
    			sum=0;
    			for (j=0;j<=k-1;j++)
    			if (fabs(p-j)!=1)
    				sum+=f[i-1][j]%1000000007;
    			
    			f[i][p]=sum%1000000007;
    		}
    	}
    	sum=0;
    	for (i=1;i<k;i++)
    		sum+=f[L][i];
    	printf("%I64d",sum%1000000007);
    	return 0;
    }

[link]: https://www.lanqiao.cn/problems/709/learning/
[link 1]: https://www.lanqiao.cn/problems/703/learning/
[link 2]: http://lx.lanqiao.cn/problem.page?gpid=T13