算法实现题——字典序问题（C实现）

系统管理员 2024-03-26 18:25 58阅读 0赞

**问题描述：**在数据加密和数据压缩中常需要对特殊字符进行编码。给定字母表A由26个小写英文字母组成，即A=\{a,b,…,z\}，该字母表产生的升序字符串是指字符串中，字母从左往右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1次。例如，a、b、ab、bc、xyz等字符串都是升序字符串。现对字母表A产生的所有长度不超过6的升序字符串按照字符字典序排列并编码如下。

对于任意长度不超过6的升序字符串，迅速计算出它在上述字典中的编码。

**算法设计：**对于给定的长度不超过6的升序字符串，计算它在上述字典中的编码。

**数据输入：**输入数据由文件名为input.txt.的文本文件提供。文件的第1行是一个正整数k，表示接下来有k行。在接下来的k行中，每行给出一个字符串。

**结果输出：**将计算结果输出到文件output.txt。文件有k行，每行对应一个字符串的编码。

#include<stdio.h>
 #include<string.h>
 int combine(int m,int n){//计算组合数的函数
 double sum1=1;
 double sum2=1;
 if(m>n){ 
 return 0;
 }
 else{
 for(int i=1;i<=n-m;i++){//计算(n-m)!
 sum1*=i;
 }
 for(int i=m+1;i<=n;i++){//计算n!/m!
 sum2*=i;
 }
 }
 return sum2/sum1;
 }
 //计算升序字符串编码，
 int count(char str[],int low){//计算与输入字符串同位数，
 int sum=0;
 int len=strlen(str);
 char high=str[0];
 for(int i=low+1;i<=high-'a';i++){//low用于存储上一位高位到达的字母位置，便于下一位运算时，从该高位的第二位开始进行
 sum+=combine(len-1,26-i);
 }
 if(len>1){
 sum+=count(&str[1],high-'a'+1);//递归运算，将下一位作为最高位穿入，进行后边位置的计算
 }
 return sum;
 }
 int main(){
 freopen("input.txt","r",stdin);
 freopen("output.txt","w",stdout);
 int n;
 scanf("%d",&n);
 while(n--){
 int sum=1;
 char str[10];
 scanf("%s",str);
 for(int i=1;i<=strlen(str)-1;i++){
 sum+=combine(i,26);//计算在输入字符串位数之下的所有排列可能性
 }
 sum+=count(str,0);
 printf("%d\n",sum);
 }
 return 0;
 }

（1）事先在程序所在路径建立两个题目所需的txt文件

![140acd33b50f4deaa58808527e896718.png][]

（2）根据题目要求，在input.txt中输入2 a b，进行测试

![bc312f3b9bcc4b4e9e9060028e929feb.png][]

（3）运行程序

![e3fcac4d6bfe42f7bf36e504d6014c65.png][]

（4）待程序运行成功后，查看output.txt文件，是否运行成功

![12cc0264351a452195430c0acf80fdc2.png][]

这样，这个题目就完美解决啦~

[140acd33b50f4deaa58808527e896718.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/deb07f3c993445e59523eb8e7fbfd6ad.png
[bc312f3b9bcc4b4e9e9060028e929feb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/3ebf2cedf0c64947a48a6e3dc58e7a08.png
[e3fcac4d6bfe42f7bf36e504d6014c65.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ce6d87187cbc40d08a21a315ef875c63.png
[12cc0264351a452195430c0acf80fdc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/44b01756ceb145899a70d3a97be7e73f.png