Sicily 1343 Jam的计数法 (SOJ 1343)「递归」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/134

原题地址:点击打开链接

原本以为要用全排列字典序的相关知识,特意查资料,找到之前一直看不明白的全排列与序号之间的关系转换的内容,全部看懂后着手写题,发现用不到,或者说我不知道怎么样,不过木有关系,因为查资料学到不少东西,关于全排列的字典序序号以及排列本身的关系,我专门写了一篇博客,感觉会比网上能容易搜出来的博客要好一点,链接是:字典序序号与排列的关系【全排列与序号换算方法】

这题不难,很容易想到解法,但是想到好的解法却不容易,所以我没有想到好的解法,数据量很小,所以暴力递归就过了。

——————正文——————

思路是比较简单的,每一层递归就对于一个位,用for循环改变其值即可,要注意当前的值必须大于或等于上一个值。在初始情况下,每一层的for循环初始值应该为输入的字符串中对应位置的值,但是每一个位置经过一次递归后,就应该让for循环的初始值为前一个值+1,例如:

1 3 2

ad

那么对于ad,最右边的字符d的下一个字符应该是e,即下一个字符串是ae

对于ae,最右边的字符e下一个字符就是c了,为什么呢?因为e已经是最大的字母,这个时候a要变成b,然后e就变成 b+1

注意这一点,递归就很好写,代码如下:

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<memory.h>
bool reset[50];  //reset[i]=true则应该从s[i-1]+1开始,否则从s[i]开始 
char s[50];
int slen;
int mi,ma,n;     //对应题目中的s,t,w 
int cnt;
void compute(int depth,int p)  //p为前一位的值 
{
	if(depth==slen)
	{
		if(cnt++)
  		{ 
		  for(int i=0;i<slen;++i)
		   printf("%c",s[i]);
	      printf("\n");
		}
		return;
	}
	
	int bound;
	if(!reset[depth])
	  bound=s[depth];
	else
	  bound=p+1;

	for(int i=bound;i<=(ma+'a'-1)&&cnt<=5;i++)
	{
		s[depth]=i;
		compute(depth+1,i);
	}
	reset[depth]=true;
}
int main()
{
	//freopen("in","r",stdin);
	//freopen("out","w",stdout);
    while(scanf("%d%d%d",&mi,&ma,&slen)!=EOF)
    {
      scanf("%s",s);
	  cnt=0;
	  memset(reset,0,sizeof(reset));
      compute(0,0);     
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注