算法训练未名湖边的烦恼（找零排队，递归）非递归（递归，数学hermite多项式物理概念）s01串(递归）

痛定思痛。 2022-11-01 05:45 194阅读 0赞

### 算法训练 未名湖边的烦恼 ###

[题目链接][Link 1].  
问题描述  
　　每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。  
　　每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）  
输入格式  
　　两个整数，表示m和n  
输出格式  
　　一个整数，表示队伍的排法的方案数。  
样例输入  
3 2  
样例输出  
5  
数据规模和约定  
　　m,n∈［0,18］  
　　问题分析  
【关键字】找零 排队 ，递归  
【思路】递归设计要点，  
①设函数f(m,n)表示m个人还，n个人租有的排队个数。递归设计要点  
分以下情况讨论  
②若m=0 结果是0  
③m<n 结果是0  
④n=0 结果是1  
⑤n<m 若第m+n个人是还，则前面还的人是m-1个,租的是n个  
若第m+n个人是租，则前面还的人是m个,租的是n-1个  
结果是两种情况和。

#include<bits/stdc++.h>
    using namespace std;
    int f(int m,int n){
        
        if(m==0||m<n) return 0;
        else if(n==0) return 1;
        else return f(m-1,n)+f(m,n-1);
    
    }
    int main(){
        
        int m,n;
        cin>>m>>n;
        cout<<f(m,n);
    return 0;}

### 算法训练 6-1 递归求二项式系数值 ###

[题目链接][Link 2].  
问题描述

样例输入  
一个满足题目要求的输入范例。  
3 10  
样例输出  
与上面的样例输入对应的输出。

数据规模和约定  
　　输入数据中每一个数的范围。  
　　例：结果在int表示时不会溢出。  
【关键字】递归  
【思路】根据题目公式的简单递归，注意数学知识，细节，案例中 3是k,10是n

#include<bits/stdc++.h>
    using namespace std;
    int c(int k,int n){
        
        if(k==0||k==n) return 1;
        else return c(k,n-1)+c(k-1,n-1);
    
    }
    int main(){
        
        int k,n;
        cin>>k>>n;
        cout<<c(k,n);
    
    return 0;}

### 算法训练 非递归 ###

[题目链接][Link 3].  
问题描述  
　　当x>1时，Hermite多项式的定义见第二版教材125页。用户输入x和n，试编写“非递归”函数，输出对应的Hermite多项式的值。其中x为float型，n为int型。  
输入格式  
　　x n  
输出格式  
　　对应多项式的值  
样例输入  
一个满足题目要求的输入范例。  
例：  
3.6 4  
样例输出  
与上面的样例输入对应的输出。  
例：  
2077.31  
数据规模和约定  
　　x>1  
　　n为自然数  
【思路】不了解埃尔米特多项式原理的，上百度  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTc0Mw_size_16_color_FFFFFF_t_70]

#include<bits/stdc++.h>
    using namespace std;
    float fac(float x,float n){
        //物理上的
         if(n==0) return 1;
         if(n==1) return 2*x;
         else
            return (float) (2.0 * x * fac(x, n - 1) - 2.0 * (n - 1) * fac(x, n - 2));
    }
    int main(){
        
        float x,n;
        cin>>x>>n;
        if(n<5)
           printf("%.2f",fac(x,n));
        else
            printf("%.3f",fac(x,n));
    
    return 0;}

### 算法训练 s01串 ###

[题目链接][Link 4].  
问题描述  
　　s01串初始为"0"  
　　按以下方式变换  
　　0变1，1变01  
输入格式  
　　1个整数(0~19)  
输出格式  
　　n次变换后s01串  
样例输入  
3  
样例输出  
101  
数据规模和约定  
　　0~19  
【关键词】注意细节，if里面的判断==  
【思路】递归

#include<bits/stdc++.h>
    using namespace std;
    int n;
    char s[1000020];
    void f(char s[],int len,int cnt)
        {
          if(cnt==n){
        
           for(int i=0;i<len;i++){
        
            printf("%c",s[i]);
           }
    
           return ;
              }
         for(int i=0;i<len;i++){
        
            if(s[i]=='0') s[i]='1';
            else {
        
                s[i]='0';
                for(int j=len;j>i;j--){
        
                    s[j]=s[j-1];//往后挪动,腾出空位插
                }
                s[i+1]='1';
                len++;
                i++;
            }
         }
         f(s,len,cnt+1);
    
        }
    int main(){
        
    
        cin>>n;
        s[0]='0';
        f(s,1,0);
    return 0;}

[Link 1]: http://lx.lanqiao.cn/problem.page?gpid=T303
[Link 2]: http://lx.lanqiao.cn/problem.page?gpid=T399
[Link 3]: http://lx.lanqiao.cn/problem.page?gpid=T733
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTc0Mw_size_16_color_FFFFFF_t_70]: /images/20221024/0bedbb5a868245718681504bcd8e160f.png
[Link 4]: http://lx.lanqiao.cn/problem.page?gpid=T366