回 帖 发 新 帖 刷新版面

主题:大鸟们,小鸟 遇到麻烦了

这道题 真不知道 怎么算啊?说一下算法就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个回复)

沙发

看了题目就头疼,还有就是输入输出例子也太少了,一组怎么好说明情况,这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;
}

板凳

ok , 谢谢大鸟

我来回复

您尚未登录,请登录后再回复。点此登录或注册