信息学奥赛一本通(C++版) 第二部分 基础算法 第四章 递归算法

时间:2021-03-21 08:55:29

信息学奥赛一本通(C++版) 第二部分 基础算法 第四章 递归算法

http://ybt.ssoier.cn:8088/

//1315 【例4.5】集合的划分
//http://blog.csdn.net/sinat_34943123/article/details/51434717此文介绍得不错,摘抄如下:
//【算法分析】
//先举个例子,设S={1,2,3,4},k=3,不难得出S有6种不同的划分方案,即划分数S(4,3)=6,具体方案为:
//{1,2}∪{3}∪{4} {1,3}∪{2}∪{4} {1,4}∪{2}∪{3}
//{2,3}∪{1}∪{4} {2,4}∪{1}∪{3} {3,4}∪{1}∪{2}
//考虑一般情况,对于任意的含有n个元素a1 ,a2,……,an的集合S,放入k个无标号的盒子中去,划分数为S(n,k),我们很难凭直觉和经验计算划分数和枚举划分的所有方案,必须归纳出问题的本质。其实对于任一个元素an,则必然出现以下两种情况(分类讨论):
//1、{an}是k个子集中的一个(即{an}是一个子集合),于是我们只要把a1,a2,……,an-1 划分为k-1子集,便解决了本题,这种情况下的划分数共有S(n-1,k-1)个;
//2、{an}不是k个子集中的一个(即an是一个子集合中的元素,该子集合中除了an,还有其它元素),则an必与其它的元素构成一个子集。则问题相当于先把a1,a2,……,an-1 划分成k个子集,这种情况下划分数共有S(n-1,k)个;然后再把元素an加入到k个子集中的任一个中去,共有k种加入方式,这样对于an的每一种加入方式,都可以使集合划分为k个子集,因此根据乘法原理,划分数共有k * S(n-1,k)个。
//综合上述两种情况,应用加法原理,得出n个元素的集合{a1,a2,……,an}划分为k个子集的划分数为以下递归公式:S(n,k)=S(n-1,k-1) + k * S(n-1,k) (n>k,k>0)。
//(探讨边界情况,0,1)
//下面,我们来确定S(n,k)的边界条件,首先不能把n个元素不放进任何一个集合中去,即k=0时,S(n,k)=0;也不可能在不允许空盒的情况下把n个元素放进多于n的k个集合中去,即k>n时,S(n,k)=0;再者,把n个元素放进一个集合或把n个元素放进n个集合,方案数显然都是1,即k=1或k=n时,S(n,k)=1。
//因此,我们可以得出划分数S(n,k)的递归关系式为:
//S(n,k)=S(n-1,k-1) + k * S(n-1,k) (n>k,k>0)
//S(n,k)=0 (n<k k==0)
//此文代码简单,但分析过程复杂。
//int容易溢出,采用long long,提交,测试点5,答案错误
//将long long改成int,提交,AC,直接怀疑测试数据有问题, 2017-11-7

#include <stdio.h>
int S(int n,int k){
    if(n<k||k==0)return 0;
    if(n==k||k==1)return 1;
    return S(n-1,k-1)+k*S(n-1,k);
}
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    printf("%d",S(n,k));
    return 0;
}

//1316 【例4.6】数的计数(Noip2001)
//提交,未通过,测试点10:运行超时
//洛谷里 P1028 数的计算 发现数据有更新,除了原有5个数据外,又增加了15个数据,提交,这15个数据全是TLE
//看来,递归是没用了,要递推。采用递归编写的代码,获得以下数据
//n ans
//1 1
//2 2
//3 2
//4 4
//5 4
//6 6
//7 6
//8 10
//9 10
//10 14
//11 14
//发现i是奇数a[i]=a[i-1],i是偶数a[i]=a[i-1]+a[i/2];
//这总方法,属于纯模拟的递推
//从编程角度,该题递归比递推容易理解

#include <stdio.h>
int a[1100];
int main(){
    int n,i;
    scanf("%d",&n);
    a[1]=1,a[2]=2;
    for(i=3;i<=n;i++)
        if(i%2==1)a[i]=a[i-1];//奇数
        else a[i]=a[i-1]+a[i/2];//偶数
    printf("%d",a[n]);
    return 0;
}

以下代码为,提交,未通过,测试点10:运行超时
#include <stdio.h>
int cnt=1;//1表示加上自己本身
void f(int k){
    int i;
    if(k==0)return;
    for(i=1;i<=k/2;i++)cnt++,f(i);
}
int main(){
    int n;
    scanf("%d",&n);
    f(n);
    printf("%d",cnt);
    return 0;
}


//1198 逆波兰表达式
//此文排版很不错,让人有阅读的想法,http://blog.csdn.net/c20180630/article/details/52683055
//阅读上文,让人感到了递归地威力,太强了。
//样例通过,提交AC
#include <stdio.h>
#include <stdlib.h>
double f(){
    char a[20];
    scanf("%s",a);
    switch(a[0]){
        case '+':return f()+f();
        case '-':return f()-f();
        case '*':return f()*f();
        case '/':return f()/f();
        default:return atof(a);
    }
}
int main(){
    printf("%f\n",f());
    return 0;


//1199 全排列
#include <stdio.h>
#include <string.h>
char s[10],b[10];
int n,vis[10];
void dfs(int step){
    int i;
    if(step==n){
        b[step]='\0';
        printf("%s\n",b);
    }
    for(i=0;i<n;i++)
        if(vis[i]==0){
            vis[i]=1;
            b[step]=s[i];
            dfs(step+1);
            vis[i]=0;
        }
}
int main(){
    memset(vis,0,sizeof(vis));
    scanf("%s",s);
    n=strlen(s);
    dfs(0);
    return 0;
}
 
//1200 分解因数
//确实有点象 1318 【例5.3】自然数的拆分
//样例通过,提交AC 2017-11-22 17:25
//基本确认 1200 分解因数 与  1318 【例5.3】自然数的拆分 写法一致 
#include <stdio.h>
int a[32768],cnt,b;
void f(int d,int step){
    int i,ans=1,j;
    for(i=1;i<=step-1;i++)ans*=a[i];
    if(ans>b)return;
    if(ans==b){
        cnt++;
        return;
    }
    for(i=a[step-1];i<=b;i++)
        if(d%i==0){
            d/=i,a[step]=i,f(d,step+1),d*=i;
        }
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        cnt=0;
        scanf("%d",&b);
        a[0]=2;
        f(b,1);
        printf("%d\n",cnt);
    }
    return 0;
}

//1201 菲波那契数列
#include <stdio.h>
int f(int n){
    if(n==1)return 1;
    if(n==2)return 1;
    return f(n-1)+f(n-2);
}
int main(){
    int n,i,x;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&x);
        printf("%d\n",f(x));
    }
    return 0;
}
//1202 Pell数列
//数据范围有问题,1≤k<1000000递归必定超时
//果然提交未通过,放弃递归,用循环来处理
//1189 Pell数列
#include <stdio.h>
int a[1000100];
int main(){
    int n,k,i;
    a[1]=1,a[2]=2;
    for(i=3;i<=1000000;i++)
        a[i]=(2*a[i-1]+a[i-2])%32767;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&k);
        printf("%d\n",a[k]);
    }
    return 0;
}
//1203 扩号匹配问题
//感觉此题挺奇怪的,跟一般的题目思路不一样
//http://blog.csdn.net/xtzmm1215/article/details/8634748此文代码写得简洁
//研究了该代码,发现核心是在栈中存储 左括号 的位置, 右括号 不进栈,直接进行'?' 处理
//样例通过,提交AC 2017-11-22 22:02
#include <stdio.h>
#include <string.h>
char a[110],b[110];
int stack[110],top=0;
int main(){
    int i,j,len;
    while(scanf("%s",a)!=EOF){
        len=strlen(a);
        for(i=0;i<len;i++)
            if(a[i]=='(')
                top++,stack[top]=i,b[i]=' ';
            else if(a[i]==')')
                if(top)top--,b[i]=' ';
                else b[i]='?';
            else b[i]=' ';
        while(top)b[stack[top]]='$',top--;
        b[len]='\0';
        printf("%s\n%s\n",a,b);
    }
    return 0;
}


//1204 爬楼梯
#include <stdio.h>
int f(int n){
    if(n==1)return 1;
    if(n==2)return 2;
    return f(n-1)+f(n-2);
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF)
        printf("%d\n",f(n));
    return 0;
}

//1205 汉诺塔问题
//没有头绪,搜索了一下,没想到代码这么短
//http://blog.csdn.net/yanyanwenmeng/article/details/77417672思路写得不错,摘抄如下
//注意是移到中间的杆b上。可以这样看:
//1. 先把a中(n-1)个盘移到c中;
//2. 把a中剩余的一个盘移到b中;
//3. 将c中(n-1)个盘移到b上。
//可以出在 阅读程序 写结果,或者 完善程序 中
//样例通过,提交AC  2017-11-23 21:26
#include <stdio.h>
void Han(int n,char a,char c,char b){
    if(n==1){
        printf("%c->%d->%c\n",a,n,b);
        return ;
    }
    Han(n-1,a,b,c);
    printf("%c->%d->%c\n",a,n,b); //该句是程序调试写出来的,而不是理解写出来的 该句是最后才写出的
    Han(n-1,c,a,b);
}
int main(){
    int n;
    char a,b,c;
    scanf("%d %c %c %c",&n,&a,&b,&c);
    Han(n,a,c,b);
}


//1206 放苹果 递归
//1192 放苹果
//http://www.cnblogs.com/dongsheng/archive/2012/08/15/2640468.html此文介绍得不错,摘抄如下:
//8    解题分析:
//9         设f(m,n) 为m个苹果,n个盘子的放法数目,则先对n作讨论,
//10         当n>m:必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响。即if(n>m) f(m,n) = f(m,m)  
//11         当n<=m:不同的放法可以分成两类:
//12         1、有至少一个盘子空着,即相当于f(m,n) = f(m,n-1);  
//13         2、所有盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即f(m,n) = f(m-n,n).
//14         而总的放苹果的放法数目等于两者的和,即 f(m,n) =f(m,n-1)+f(m-n,n)
//15     递归出口条件说明:
//16         当n=1时,所有苹果都必须放在一个盘子里,所以返回1;
//17         当没有苹果可放时,定义为1种放法;
//18         递归的两条路,第一条n会逐渐减少,终会到达出口n==1;
//19         第二条m会逐渐减少,因为n>m时,我们会return f(m,m) 所以终会到达出口m==0.
//该题可以放在阅读程序写结果
//觉得很奇怪,算法没问题,反复看题,也觉得没问题,再看未通过理由,发现格式错误
//原来是小错误啊,修改,提交AC。
#include <stdio.h>
int f(int m,int n){
    if(m==0||n==1)return 1;
    if(m<n)return f(m,m);
    return f(m,n-1)+f(m-n,n);
}
int main(){
    int m,n,i,j,k;
    scanf("%d",&k);
    for(i=1;i<=k;i++){
        scanf("%d%d",&m,&n);
        printf("%d\n",f(m,n));//此处写成printf("%d",f(m,n));
    }
    return 0;
}


//1207 求最大公约数问题
#include <stdio.h>
int gcd(int a,int b){//a>b
    if(b==0)return a;
    return gcd(b,a%b);
}
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    if(a>b)printf("%d",gcd(a,b));
    else printf("%d",gcd(b,a));
    return 0;
}

//1208 2的幂次方表示
//此文代码与本人极其相似,唯一不同就是此文代码成功了,http://www.cnblogs.com/bofengyu/p/4477355.html
//思路,先打印2(7)+2(3)+2(0)
//再对7 3 0进行处理,本人这里没静下心,怎么编也编不出,参考了上述代码,发现离成功只有一步
//不过,相比 洛谷  P1010 幂次方 http://blog.csdn.net/mrcrack/article/details/61625530
//已经有了长足的进步
//该题是边编写边调试的典范。2017-11-7 18:51
//抽空,还是要独立再进行编写一次。
#include <stdio.h>
void f(int n,int step){
    if(n==0)return;
    f(n/2,step+1);
    if(n%2==1){
        if(n/2!=0){
            printf("+");
        }
        if(step==1)printf("2");//此处添加
        else{
            printf("2(");
            if(step==0)printf("0");
            else f(step,0);
            printf(")");
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    f(n,0);
    return 0;
}

//1209 分数求和
//该题比较简单
//基本思路,先统分,分子求和,之后用GCD求最大公约数即可
//提交,未通过,测试点3,4,7,9答案错误
//读题,发现“p,q均不超过10。” 明白了,可以等于10,而之前的处理是按1-9进行的,马上进行修改
//提交AC。2017-11-7 20:35
#include <stdio.h>
int a[20],b[20];
long long gcd(long long a,long long b){//a>=b
    if(b==0)return a;
    return gcd(b,a%b);
}
int main(){
    int n,k=0,i;
    long long son=0,mother=1,y;
    char s[20];
    scanf("%d",&n);
    while(n--){
        scanf("%d/%d",&a[k],&b[k]);
        k++;
    }
    for(i=0;i<k;i++)mother*=b[i];
    for(i=0;i<k;i++)son+=mother*a[i]/b[i];
    y=gcd(mother,son);
    mother/=y,son/=y;
    if(mother==1)printf("%lld",son);
    else printf("%lld/%lld",son,mother);
    return 0;
}
//1210 因子分解
//此题思路 与 1200 分解因数 十分接近
//样例通过,提交AC 2017-11-222 18:51
//exit(0);//退出递归 有一个问题,除了此法,还有其他方法能退出递归吗?突然想到,不要回溯,即可 ,真是佩服自己,这个想法有突破
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int a[110],n,d[110];
void f(int b,int step){//犯了严重的错误,将d[110]写成b[110],请注意,要调用外部的数据,名字不能与b重名
    int i,ans=1,k=0;
    for(i=1;i<=step-1;i++)ans*=a[i];
    if(ans>n)return;
    if(ans==n){
        memset(d,0,sizeof(d));
        for(i=1;i<=step-1;i++)
            d[a[i]]++;
        for(i=1;i<=n;i++){
            if(d[i]){
                k++;
                if(k==1){//第一个数字打印
                    printf("%d",i);
                    if(d[i]>1)printf("^%d",d[i]);
                }else{
                    printf("*%d",i);
                    if(d[i]>1)printf("^%d",d[i]);
                }
            }
        }
        //exit(0);//退出递归 有一个问题,除了此法,还有其他方法能退出递归吗?突然想到,不要回溯,即可 ,真是佩服自己,这个想法有突破
    }
    for(i=a[step-1];i<=n;i++)
        if(b%i==0)b/=i,a[step]=i,f(b,step+1);//删除 b*=i 不要回溯
}
int main(){
    scanf("%d",&n);
    a[0]=2;
    f(n,1);
    return 0;
}  


//1211 判断元素是否存在
//样例通过,提交,未通过
//测试点2,3,4,6,8,10答案错误
//http://www.cnblogs.com/huashanqingzhu/p/7745662.html代码启发很大
//提供一组测试数据
//输入:
//0 7
//输出:
//YES
//提交,未通过,一看,测试数据未删除,修改,提交AC 2017-11-7 21:41
#include <stdio.h>
int k;
int f(int x){
    if(x==k)return 1;
    if((x-1)%3==0&&(x-1)%2==0)return f((x-1)/3)||f((x-1)/2);//漏了此行
    if((x-1)%3==0)return f((x-1)/3);
    if((x-1)%2==0)return f((x-1)/2);
    return 0;
}
int main(){
    int x;
    scanf("%d,%d",&k,&x);
    if(f(x))printf("YES");
    else printf("NO");
    return 0;
}

2017-11-23 21:30 AC 该章节内容