跳至正文

Jam的计数法 解题报告

  • OI路程

这题我用的深搜,写来写去都觉得特别麻烦,干脆把从a到b的所有可能都计算出来,然后判断是否比输入的大,是就输出,让计数器加一,到五就退出程序,等下还优化试下,先把这个的代码贴上来。

C语言:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int a, b;
int n;
char tmp[27];
char str[27];
int count;

void srch(int now)
{
 int i;
 if(now == n + 1){
 if(strcmp(tmp + 1, str + 1) > 0){
 count++;
 printf(%s\\n, tmp + 1);
 if(count == 5){
 exit(0);
 }
 }
 return ;
 }
 for(i = tmp[now - 1] + 1; i <= b; i++){
 tmp[now] = i;
 srch(now + 1);
 }
}

int main(void)
{
 int i;
 scanf(%d%d%d\\n, &a, &b, &n);
 a += \'a\' - 1;
 b += \'a\' - 1;
 scanf(%s, str + 1);
 strcpy(tmp + 1, str + 1);
 *tmp = a - 1;
 srch(1);
 return 0;
}

它有可修改的余地,我还想想。
把开始的时候处理一下,速度会明显快些,代码如下:
C语言: Jam的计数法 改进版.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int a, b;
int n;
char tmp[26];
char str[26];
int count;

void srch(int now, int start)
{
 int i;
 if(now == n){
 if(strcmp(tmp, str) > 0){
 count++;
 printf(%s\\n, tmp);
 if(count == 5){
 exit(0);
 }
 }
 return ;
 }
 for(i = start; i <= b; i++){
 tmp[now] = i;
 srch(now + 1, i + 1);
 }
}

int main(void)
{
 int i;
 scanf(%d%d%d\\n, &a, &b, &n);
 a += \'a\' - 1;
 b += \'a\' - 1;
 scanf(%s, str);
 srch(0, a);
 return 0;
}

发表评论

您的电子邮箱地址不会被公开。