编程题a ~ y的25个字母,从1位到4位的编码,输出这个编码对应的Index

2024-02-13 03:48

本文主要是介绍编程题a ~ y的25个字母,从1位到4位的编码,输出这个编码对应的Index,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

假定一种编码的编码范围是a-y的25个字母,从1位到4位的编码,如果我们把该编码按字典序排序,形成一个数组如下:
a,aa,aaa,aaaa,aaab,aaac,…,…,b,ba,baa,baaa,baab,baac,… …,yyyw,yyyx,yyyy
其中a的Index为0,aa的Index为1,aaa的Index为2,以此类推。
编写一个函数,输入是任意一个编码,输出这个编码对应的index,如:
输入:baca
输出:16328
题目分析
如果你之前做过另一个题目,“求字符的所有组合,当输入的字符串中含有相同的字符串时,相同的字符交换位置是不同的排列,但是同一个组合。举个例子,如果输入abc,它的组合有a、b、c、ab、ac、bc、abc。” 那么这个题目一出来起码不会觉得特别无从下手,其实就算没做过也不会特别无从下手,因为就是穷举利器嘛(即使写成漂亮的递归,仍然不能摆脱穷举的命运)。
这里自然不是为了分析这个递归穷举法(也许之后我会再单独写一篇阐述一下下)。所以技巧还是需要一些的。将题目要求的字符串排列组合起来,如下图示
在这里插入图片描述
根据排列组合的原理,单独来看每一位字符其可能的组合都是,把4位结合起来看,从第1位到第4位,其可能的排列组合分别是 p n 1 p^1_n pn1 p n 1 ∗ p n 1 p^1_n * p^1_n pn1pn1 p n 1 ∗ p n 1 ∗ p n 1 p^1_n*p^1_n * p^1_n pn1pn1pn1 p n 1 ∗ p n 1 ∗ p n 1 ∗ p n 1 p^1_n * p^1_n*p^1_n * p^1_n pn1pn1pn1pn1和对于每个字符串的index需要拆分开一位一位看。

先来看最末位,即字符串有4位,前3为相同,只有最后一位不同,那么index = index‘+(*p-*p’)。举个例子
p’ 是指向字符串aaaa的最后一位a的指针,p是指向字符串aaab的最后一位b的指针,那么aaab的index就等于aaaa的index‘加上字符b与字符a的距离(即’b‘-’a’)

接下来看倒数第二位,即前2位和最后1位相同,只有倒数第2位不同,那么index = index’ +(*p-p’)( p n 1 p^1_n pn1 + 1)。举个例子
p’ 是指向字符串aaaa的第3位a的指针,p是指向字符串aaba的指针,那么按排列规则,aaaa与aaba之间应该有字符串aaab,aaac,aaad…aaay, aab,再加上aaaa自身,这一系列字符串正好是一个完整的。再来看一个例子,aaaa与aaca,它们之间应该有字符串aaab,aaac,aaad…aaay,aab,
aaba,aabb,aabc…aaby, aac,正好是2倍的 + 1。因此我们可以很容易得出结论,ndex = index’ +(*p-p’) ( p n 1 p^1_n pn1 + 1)
再看第2位,即第1位和最后2位相同,只有第2位不同,那么在这里插入图片描述
举个例子
p’ 是指向字符串aaaa的第3位a的指针,p是指向字符串abaa的指针,那么按排列规则,aaaa与abaa之间应该有字符串aaab,aaac,…aaay, aaba…aaby…aaya…aayy,再加上aaaa自身,这一系列字符串正好是一个完整的 p n 1 ∗ p n 1 + p n 1 p^1_n *p^1_n +p^1_n pn1pn1+pn1

最后就是首位了,即第1位不同,后面的3位相同,那么。举个例子
p’ 是指向字符串aaaa的第3位a的指针,p是指向字符串baaa的指针,那么按排列规则,aaaa与baaa之间应该有字符串aaab,aaac,…aaay, aab,aaba…aaby…ab,aba,abaa,…abyy, ay,aya,ayaa…ayyy,b,ba,baa,再加上aaaa自身,这一系列字符串正好是一个完整的 p n 1 ∗ p n 1 ∗ p n 1 + p n 1 ∗ p n 1 + p n 1 p^1_n * p^1_n*p^1_n +p^1_n *p^1_n +p^1_n pn1pn1pn1+pn1pn1+pn1

综上,mnoq相对于字符串a的index应该是

在这里插入图片描述
分析完毕。输入index反向查找字符串正好是将上面的分析过程反过来,这里不详细记述。

//输入字符串输出index
#include<iostream>
using namespace std;
int main()
{int num=25;string p;cin>>p;int n=3;int index=0;int sum[4]={1};for(int i=1;i<4;i++){sum[i]=num*sum[i-1]+1;}for(int i=0;i<p.length();i++){index=index+(p[i]-'a')*sum[n--];}cout<<index;
}

这篇关于编程题a ~ y的25个字母,从1位到4位的编码,输出这个编码对应的Index的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/704405

相关文章

mybatis的mapper对应的xml写法及配置详解

《mybatis的mapper对应的xml写法及配置详解》这篇文章给大家介绍mybatis的mapper对应的xml写法及配置详解,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,... 目录前置mapper 对应 XML 基础配置mapper 对应 xml 复杂配置Mapper 中的相

使用Java将实体类转换为JSON并输出到控制台的完整过程

《使用Java将实体类转换为JSON并输出到控制台的完整过程》在软件开发的过程中,Java是一种广泛使用的编程语言,而在众多应用中,数据的传输和存储经常需要使用JSON格式,用Java将实体类转换为J... 在软件开发的过程中,Java是一种广泛使用的编程语言,而在众多应用中,数据的传输和存储经常需要使用j

基于Go语言实现Base62编码的三种方式以及对比分析

《基于Go语言实现Base62编码的三种方式以及对比分析》Base62编码是一种在字符编码中使用62个字符的编码方式,在计算机科学中,,Go语言是一种静态类型、编译型语言,它由Google开发并开源,... 目录一、标准库现状与解决方案1. 标准库对比表2. 解决方案完整实现代码(含边界处理)二、关键实现细

Python 异步编程 asyncio简介及基本用法

《Python异步编程asyncio简介及基本用法》asyncio是Python的一个库,用于编写并发代码,使用协程、任务和Futures来处理I/O密集型和高延迟操作,本文给大家介绍Python... 目录1、asyncio是什么IO密集型任务特征2、怎么用1、基本用法2、关键字 async1、async

解决IDEA报错:编码GBK的不可映射字符问题

《解决IDEA报错:编码GBK的不可映射字符问题》:本文主要介绍解决IDEA报错:编码GBK的不可映射字符问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录IDEA报错:编码GBK的不可映射字符终端软件问题描述原因分析解决方案方法1:将命令改为方法2:右下jav

Java并发编程之如何优雅关闭钩子Shutdown Hook

《Java并发编程之如何优雅关闭钩子ShutdownHook》这篇文章主要为大家详细介绍了Java如何实现优雅关闭钩子ShutdownHook,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 目录关闭钩子简介关闭钩子应用场景数据库连接实战演示使用关闭钩子的注意事项开源框架中的关闭钩子机制1.

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

Python使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意