2 vjd vella st vjd_vella_st 于 2015.07.01 11:01 提问

算法实战题:创建摩尔斯电码字典计算第k个答案

题目如下:计算第k个答案
摩尔斯电码字典
在没有电话的时代,摩尔斯电码是无线电传输领域中的一种常用代码。电码以短信号(短点,o)和长信号(长点,-)的不同组合表示各种文字。例如:o—表示英文字母J,而—表示英文字母M。
假设有一本以n个长点和m(n、m<=100)个短点组成的、包含所有信号的字典。例如:n=m=2,就会包含如下信号。
--oo
-o-o
-oo-
o--o
o-o-
oo--
这些信号已按照字典顺序排列好了。-的ASKII码是45,而o的ASCII码是111。因此,按照字典顺序,-在前,o在后。给定n和m时,编写代码计算出此字典的第k(k<=1,000,000,000,000)个信号。例如:上述字典的第四个信号是o--o。
要求使用蛮力法和动态规划法解题。
蛮力法我想的是先建立一个全排列的摩尔斯电码字典,再用折半查找的方式查找k的位置输出值,但问题在于这道题的字典太大,数据极多,如果m,n,k的值较大,估计这样运行下去半天都出不了结果。
动态规划法还没有思路,求大神简要分析一下,有代码就更好了

1个回答

Tiger_Zhao
Tiger_Zhao   Rxr 2015.07.01 11:41

一个信号总共n+m个字符,其中m个为短点(o),字典的信号总数用组合公式C(n+m,m)计算。
如果第一个用长点(-),前半部分数量是L=C(n+m-1,m)个;用k'和L比大小,可以知道k在前半部分还是后半部分。
前半部分,递归:在n-1个长点和m个短点中找第
k个。
后半部分,递归:在n个长点和m-1个短点中找第
k-L+1个(假定k`是自然数序号,从1开始)。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
动态规划之摩尔斯电码字典
有序生成摩尔斯电码字典码。 void generate(int n,int m,string s) { if(n== 0 && m == 0) { printf("%s\n",s.c_str()); return ; } if(n >0) { generate(n-1,m,s+"-"); } if (m>0) { generate(n,m-1,s+"o")
蓝桥杯-9-3摩尔斯电码(java)
算法提高 9-3摩尔斯电码 时间限制:1.0s 内存限制:256.0MB 问题描述   摩尔斯电码破译。类似于乔林教材第213页的例6.5,要求输入摩尔斯码,返回英文。请不要使用"zylib.h",只能使用标准库函数。用' * '表示' . ',中间空格用' | '表示,只转化字符表。   摩尔斯码定
算法提高 9-3摩尔斯电码
问题描述   摩尔斯电码破译。类似于乔林教材第213页的例6.5,要求输入摩尔斯码,返回英文。请不要使用"zylib.h",只能使用标准库函数。用' * '表示' . ',中间空格用' | '表示,只转化字符表。   摩尔斯码定义见:http://baike.baidu.com/view/84585.htm?fromId=253988。 提示   清橙进行评测时,输
蓝桥杯 摩尔斯电码破译 树上的搜索
摩尔斯电码破译。类似于乔林教材第213页的例6.5,要求输入摩尔斯码,返回英文。请不要使用"zylib.h",只能使用标准库函数。用' * '表示' . ',中间空格用' | '表示,只转化字符表。 首先是读入问题,采用scanf一次将所有输入全部放入一个字符组中。然后搜素保存好的字符,输出对应的字母。 问题是,如何判断字符串与字母的对应关系。 观察题中所给表格,发现只存在“-”和“
摩尔斯电码Mrose[C++]
因为某次和朋友聊天中玩到摩尔斯电码...所以想写一个玩一玩...下面就是代码,C++版的,中间有考虑到用一些指针函数STL之类的,但最后还是用了最原始的写法... 基础语法...
算法提高 9-3摩尔斯电码(树上搜索)
时间限制:1.0s 内存限制:256.0MB 问题描述   摩尔斯电码破译。类似于乔林教材第213页的例6.5,要求输入摩尔斯码,返回英文。请不要使用”zylib.h”,只能使用标准库函数。用’ * ‘表示’ . ‘,中间空格用’ | ‘表示,只转化字符表。   摩尔斯码定义见: 提示   清橙进行评测时,输入是以EOF结尾的,而不是换行符。(EOF不是一个字符,“以EOF结尾”
摩尔斯电码模拟器2.8.0
摩尔斯电码模拟器,自动模拟发报,手动发报,导出电文。完全开源,内附源码。MV STUDIO 开源设计工作室
摩尔斯电码练习软件
摩尔斯电码(又译为摩斯电码)是一种时通时断的信号代码,这种信号代码通过不同的排列顺序来表达不同的英文字母、数字和标点符号等。它由美国人艾尔菲德·维尔发明,当时他正在协助Samuel Morse进行摩尔斯电报机的发明(1835年)。
摩尔斯电码练习感想
学习摩尔斯电码有一年多了,进度很慢,真是有点伤心。 最开始是用那个Just learn morse code软件来练习的。这个软件使用一个叫Koch的人主张的方法,就是使用一个较高的速度,从两个字符开始练习,每次正确率到了90%就增加一个新的字母,这样直到学会所有的字母。这个方法据说比使用一个很慢的速度,从所有的字符开始练习要效果好。 这个软件我用了好久,越练越感觉有点问题。它练习的时候需要我
摩尔斯电报码 解码算法 (Python 语言描述)
morseDecodeHelper = [ ' ', 'ET', 'INAM', 'SDRGUKWO', 'HBLZFCP VX Q YJ ', '56 7 8 94 3 2 10' ]def morseDecode(code): result = [] morseList = code.spli