字典序问题的解决方案

2024-09-03 20:18
文章标签 解决方案 问题 字典

本文主要是介绍字典序问题的解决方案,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

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

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

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

结果输出:
将计算结果输出到文件output.txt.文件共有k行,文件共有k行,每行对应于一个字符串的编码.
  输入文件示例:
    input.txt
   2
   a
   b

输出文件示例:
output.txt
1
2

 

复制代码
#include <iostream>
#include<fstream>
using namespace std;
//计算阶乘
int factorial(int n)
{if (n==0){return 1;}int sum=1;for (int i=1;i<=n;i++){sum*=i;}return sum;
}
//统计n位中取p位的情况个数
int getnp(int p,int n)
{int sum=1;for (int i=n-p+1;i<=n;i++){sum*=i;}return sum/factorial(p);
}
//统计在总位数一样的情况下第p位前有多少
int getp(char a,int p,int n)
{int sum = 0;for (int i = n+1;i<(a-'a'+1);i++){sum += getnp(p-1,(26-i));}return sum;
}
void main()
{int sum=0;int size=0;char buffer[20];ifstream inputfile("D:\\12.txt.txt");ofstream outputfile("1-2out.txt");while(!inputfile.eof()){inputfile.getline(buffer,20);sum=0;size = strlen(buffer);for (int i=1;i<size;i++){sum += getnp(i,26);sum += getp(buffer[i],size-i,buffer[i-1]-'a'+1);}sum += getp(buffer[0],size,0);sum++;outputfile<<sum<<"\n";}outputfile.close();
}
复制代码

如上代码,思想为,例如egh这样的情况,那我们先把只有一位长的情况和两位长的加起来,即为26C1和26C2,然后找出起始位为a,b,c,d的三位单词的情况,它们也排在efg之前,即为25C2,24C2,23C2,22C2(这里需要注意并不是26C2了,因为如果为a开头,那后面两位只能从b以后的数开始选,即25个,b开头的为24个以此类推),然后考虑e开头的,因为在上面的情况过后就是高位以e开头的情况,这个时候需要注意,eah,ebh这样的并不合理,所以我们要将getp(buffer[i],size-i,buffer[i-1]-'a'+1),buffer[i]和buffer[i-1]进行比较即为e和g进行比较然后通过比较只有ef为开头的才合理,然后我们计算从efa到efz,继而到最后一位由于ega,egb这种不存在(通过buffer的比较可知),因此没有其他在eg开头的情况了,即是egh是eg开头的三位数的第一种情况,此时我们的定位工作就完毕了。

这篇关于字典序问题的解决方案的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1133942

相关文章

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

Springboot如何正确使用AOP问题

《Springboot如何正确使用AOP问题》:本文主要介绍Springboot如何正确使用AOP问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录​一、AOP概念二、切点表达式​execution表达式案例三、AOP通知四、springboot中使用AOP导出

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到

解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题

《解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题》:本文主要介绍解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4... 目录未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘打开pom.XM

IDEA Maven提示:未解析的依赖项的问题及解决

《IDEAMaven提示:未解析的依赖项的问题及解决》:本文主要介绍IDEAMaven提示:未解析的依赖项的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录IDEA Maven提示:未解析的依编程赖项例如总结IDEA Maven提示:未解析的依赖项例如

python3如何找到字典的下标index、获取list中指定元素的位置索引

《python3如何找到字典的下标index、获取list中指定元素的位置索引》:本文主要介绍python3如何找到字典的下标index、获取list中指定元素的位置索引问题,具有很好的参考价值,... 目录enumerate()找到字典的下标 index获取list中指定元素的位置索引总结enumerat

Redis分片集群、数据读写规则问题小结

《Redis分片集群、数据读写规则问题小结》本文介绍了Redis分片集群的原理,通过数据分片和哈希槽机制解决单机内存限制与写瓶颈问题,实现分布式存储和高并发处理,但存在通信开销大、维护复杂及对事务支持... 目录一、分片集群解android决的问题二、分片集群图解 分片集群特征如何解决的上述问题?(与哨兵模