UC知道算法 字典序问题
来源：百度知道 编辑：UC知道 时间：2024/06/05 06:41:26
´问题描述：
在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表 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的升序字符串，计算出它在上述字典中的编码。
´数据输入：
输入数据由文件名为input.txt的文本文件提供。文件的第一行是一个正整数 k，表示接
下来共有 k行。接下来的k行中，每行给出一个字符串。
´结果输出:
将计算结果输出到文件output.txt中。文件共有 k 行，每行对应于一个字符串的编码。
输入文件示例 输出文件示例
input.txt output.txt
2
a
b
1
2
#include<stdio.h>
#include<string.h>
const int N = 10;
int ans[N]; //ans[i]存放数字i出现的次数
char str[N]; //输入的数字
int a[N],len; //a[i]为10^i，len为数字的长度
void solve(long n) //统计数字n
{
long m=n+1;
memset(ans,0,sizeof(ans));
int j,i;
for(i=0;i<len;i++)
{
int x=str[i]-'0';
int t=(m-1)/a[len-i-1];
ans[x]+=m-t*a[len-i-1];//自左往右到i位数字不变条件下，i位为x的数字个数
t=t/10;
j=0;
while(j<x)
{
ans[j]+=(t+1)*a[len-i-1];//统计当前位置为j出现的个数
j++;
}
while(j<N) //统计当前位置为j的数目
{
ans[j]+=t*a[len-i-1];
j++;
}
ans[0]-=a[len-i-1];//消去前导0
}
for(i=0;i<N;i++)
printf("%d\n&quo