NYOJ366 D的小L 和 NYOJO32 组合数 和 NYOJ19 擅长排列的小明 和 NYOJ488 素数环 【递归】

原题链接：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);
		}
	}
}