主题:大鸟们,小鸟 遇到麻烦了
w904922993
[专家分:0] 发布于 2011-08-05 16:25:00
这道题 真不知道 怎么算啊?说一下算法就ok了, 不必写代码的 问题描述:
在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A 由26 个小
写英文字母组成A={a,b,…,z}。该字母表产生的升序字符串是指字符串中字母按照从左到
右出现的次序与字母在字母表中出现的次序相同,且每个字符最多出现1 次。例如,
a,b,ab,bc,xyz 等字符串都是升序字符串。现在对字母表A 产生的所有长度不超过6 的升序
字符串按照字典序码如下。
1 2 … 26 27 28 …
a b … z ab ac …
对于任意长度不超过6 的升序字符串,迅速计算出它在上述字典中的编码。
编程任务:
对于给定的长度不超过6 的升序字符串,编程计算出它在上述字典中的编码。
a 的ascall 97
数据输入:
输入数据由文件名为input.txt的文本文件提供。
文件的第一行是一个正整数k,表示接下来共有k 行。
接下来的k行中,每行给出一个字符串。
结果输出:
程序运行结束时,将计算结果输出到文件output.txt 中。文件共有k 行,每行对应于一
个字符串的编码。
输入文件示例 输出文件示例
input.txt
2
a
b
output.txt
1
2 [size=4][/size]
回复列表 (共2个回复)
沙发
fragileeye [专家分:1990] 发布于 2011-08-06 22:43:00
看了题目就头疼,还有就是输入输出例子也太少了,一组怎么好说明情况,这ACM题目害死人啊。大家都没太多时间花在这样的题目上,毕竟都有自己的事情忙,所以即使别人会lz也不一定得到回答。下次请发点短小的问题。。。废话不多说了。我就粗略地写了下,可能有些错,但思路行的通。
主要思路就是:先得到字符串的长度len,在根据rec[len - 1] ~ rec[len]中找以缩短编码计算范围。
上代码吧,
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXLINE 20
#define NUM 7
long rec[NUM] = {0, 26, 351, 2600, 14950, 65780, 230230};
//别问我这些数怎么来的 ,rec[i] = C26(i)+..C26(1),这是i个字符组合最大时的编码值(z,yz,xyz,wxyz)
long getcode(char *str);
int main(int argc, char *argv[])
{
FILE *fpin, *fpout;
char ar[NUM],ch;
int line, i, k, ct;
long rt[MAXLINE];
if((fpin = fopen("input.txt", "r")) == NULL)
{
fprintf(stderr, "can't open file input.txt\n");
exit(EXIT_FAILURE);
}
memset(ar, 0, sizeof(ar));
fscanf(fpin, "%d\n", &k);
ct = line = 0;
while(line < k) //读取元素
{
if(fscanf(fpin, "%s", ar))
{
line++;
rt[ct] = getcode(ar);
if(rt[ct] == 0)
{
fprintf(stderr, "can't find code of the string!\n");
}
else
{
ct++;
}
}
else
{
fprintf(stderr, "error in reading file!\n");
exit(EXIT_FAILURE);
}
}
fclose(fpin);
if((fpout = fopen("output.txt", "w")) == NULL)
{
fprintf(stderr, "can't open file output.txt\n");
exit(EXIT_FAILURE);
}
else
{
printf("succeed in getcode, please open file output.txt to check!\n");
}
for(i = 0; i < ct; i++)
{
fprintf(fpout, "%ld\n", rt[i]);
}
fclose(fpout);
return 0;
}
long getcode(char *ar)
{
int index, len, jdex, range, flag;
char str[NUM];
memset(str, 0, sizeof(str));
len = strlen(ar);
if(ar[len - 1] == '\n') //若读取回车换行,则将去掉字符'\n',str长度-1
{
ar[len - 1] = '\0';
len--;
}
range = rec[len - 1] + 1;
index = 0;
str[index] = 'a';
while(1)
{
if(index == len - 1 && strcmp(str, ar) == 0)
{
return range;
}
else
{
if(index == len - 1)
{
range++;
}
else
{
index++;
str[index] = str[index - 1] + 1;
continue;
}
}
while(str[index] == 'z' && index > 0)
{
index --;
}
if(index == 0 && str[index] == 'z')
{
break;
}
else
{
str[index]++;
}
}
return 0;
}
板凳
w904922993 [专家分:0] 发布于 2011-08-07 17:36:00
ok , 谢谢大鸟
我来回复