信息学奥赛一本通（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时，所有苹果都必须放在一个盘子里，所以返回１；
//17 当没有苹果可放时，定义为１种放法；
//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 该章节内容