原题链接：366：点击打开链接 32：点击打开链接 19：点击打开链接
488 ：点击打开链接。。
看这几个题 都是可以用递归求解。。用递归ac完这几个题后，递归应该 掌握的差不多了。。今天把这4个题总结一下。。这四个题递归调用基本一样，之间只需 稍微改变即可。。
19 擅长排列的小明：
这个貌似只能用递归。。
代码如下：
#include<stdio.h>
#include<string.h>
int n,m;
int ok[15];//
int num[15];//存放
int ac[15];//标记
void f(int l)
{
int a,b;
if(l==m)
{
for(a=0;a<m;a++)
printf("%d",num[a]);
printf("\n");
//return;
}
else
{
for(b=0;b<n;b++)
{
if(ac[b]>0)
{
num[l]=ok[b];
ac[b]--;
f(l+1);
ac[b]++;
}
}
}
}
int main()
{
int a,b,k;
for(a=0;a<10;a++)
ok[a]=a+1;
scanf("%d",&k);
while(k--)
{
scanf("%d%d",&n,&m);
for(a=0;a<=n;a++)
ac[a]=1;
memset(num,0,sizeof(num));
f(0);
}
}
336 D的小L:
这个也可以用next_permutation来求解。递归调用代码就不贴了。代码如下：
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
int a[]={1,2,3,4,5,6,7,8,9};
int k,n,i;
scanf("%d",&k);
while(k--)
{
scanf("%d",&n);
do
{
for(i=0;i<n;i++)
{
printf("%d",a[i]);
}
printf("\n");
}
while(next_permutation(a,a+n));
}
return 0;
}
32 组合数：
先看懂 擅长排列的 小明 再来看这个题 就很随意了。。
#include<stdio.h>
#include<string.h>
int n,m;
int ok[15];//
int num[15];//存放
int ac[15];//标记
void f(int l)
{
int a,b;
if(l==m)
{
for(a=0;a<m;a++)
printf("%d",num[a]);
printf("\n");
}
else
{
if(l==0)
{
for(b=n-1;b>=m-1;b--)
{
if(ac[b]>0)
{
num[l]=ok[b];
ac[b]--;
f(l+1);
ac[b]++;
}
}
}
else
{
for(b=n-1;b>=0;b--)
{
if(ac[b]>0)
{
if(l>=1&&ok[b]<num[l-1])
{
num[l]=ok[b];
ac[b]--;
f(l+1);
ac[b]++;
}
}
}
}
}
}
int main()
{
int a,b,k;
for(a=0;a<10;a++)
ok[a]=a+1;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(a=0;a<=n;a++)
ac[a]=1;
memset(num,0,sizeof(num));
f(0);
}
}
488 素数环 ：
看懂上面两个递归再来看这个貌似很随意了，但这个只用递归可ac不了。会超时滴。处理时有个小规律。。当输入的n%2==1&&n！=1是一定是No Answe。这些情况就不要再递归了。。要不然你就和我一样会悲剧的。。我悲剧了两次。。
代码：
#include<stdio.h>
#include<string.h>
int ac[25]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
int yi[25],sushu[50];
int ok[25]={2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22};
int loop,n;
void f(int i)
{
int a,b;
if(i==n)
{
printf("1 ");
for(a=0;a<n;a++)
printf("%d ",yi[a]);
printf("\n");
loop=1;
}
else
{
for(a=0;a<n;a++)
{
if(i==n-1)
{
if(ac[a]==1&&sushu[1+ok[a]]==0&&sushu[yi[i-1]+ok[a]]==0)
{
yi[i]=ok[a];
ac[a]--;
f(i+1);
ac[a]++;
}
}
else if(i==0)
{
if(ac[a]==1&&sushu[1+ok[a]]==0)
{
yi[i]=ok[a];
ac[a]--;
f(i+1);
ac[a]++;
}
}
else
{
if(ac[a]==1&&sushu[yi[i-1]+ok[a]]==0)
{
yi[i]=ok[a];
ac[a]--;
f(i+1);
ac[a]++;
}
}
}
}
}
int main()
{
int a,b,j=1;
memset(sushu,0,sizeof(sushu));
for(a=2;a<45;a++)
for(b=a+a;b<45;b+=a)
{
if(sushu[b]==0)
sushu[b]=1;
}
while(1)
{
scanf("%d",&n);
loop=0;
if(n==0)
break;
printf("Case %d:\n",j++);
if(n%2&&n!=1) printf("No Answer\n");
else
{
n--;
f(0);
}
}
}