首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 计算机考试 > 软件考试 > 复习指导 >

判断句子是不是魔法咒语的算法

2008-12-15 来源:3COME考试频道 
判断一个句子是否为咒语(由魔法词组成) 解法:回溯法

    描述如下:
  "话说有个魔法字典,其中记录了一些魔力单词(字符串),如果一个句子(也是字符串)可以被完全分解为若干魔力单词的拼接,那么这个句子就是一条咒语。假设我们可以用常数时间查询魔力字典是否包含一个特定的单词,那么现在给你一个句子,让你写一个程序判断这个句子是否一条咒语。用动态规划可以解哦。"
  其中跟贴的有人说到需要先列出“状态转移方程”,我不太懂,不过觉得这个问题倒是可以用回溯法尝试一下。
  代码如下:
  #coding: utf-8
  #2008-8-21, Neil Chen
  # 判断一个句子是否为咒语(由魔法词组成)
  # 解法:回溯法
  # 魔法词典
  magic_words = [’m’, ’foo’, ’bar’, ’boo’, ’barr’, ’jac’, ’j’ ’c’]
  # 是否为魔力单词
  def is_magic_word(word):
  return word in magic_words
  # 是否为咒语
  def is_spell(sentence):
  # 最终如能成功分割为魔法单词,则句子中会出现 n 个分隔点,
  # 现尝试用回溯法来找出这些点的位置
  split_points = [1]
  n = len(sentence)
  while True:
  # 判断最后两个分隔点之间的单词是否为魔力单词,否则将该位置增加1,继续尝试
  is_magic = False
  while split_points[-1] <= n:
  if len(split_points) == 1:
  start = 0
  else:
  start = split_points[-2]
  # 得到最后两个分隔点之间的单词
  word = sentence[start : split_points[-1]]
  if is_magic_word(word):
  is_magic = True
  break
  else:
  split_points[-1] += 1
  # 最后一个分隔点之前都是魔力单词
  if is_magic:
  # 已经到达末尾,成功了
  if split_points[-1] == n:
  return True
  # 增加下一个分隔点位置,继续分割
  else:
  split_points.append(split_points[-1] + 1)
  # 最后一个分隔点无论怎样选都不能组成一个魔力单词,则需要回溯到上一个分隔点
  else:
  # 退无可退!表示这个句子不是咒语
  if len(split_points) == 1:
  return False
  # 退回到上一个分隔点
  else:
  split_points.pop()
  # 将回溯到的位置加一,重新进入下一次循环尝试
  split_points[-1] += 1
  #=== 测试代码 ===
  if __name__ == ’__main__’:
  print is_magic_word(’foo’) # True
  print is_magic_word(’fo’) # False
  print is_spell(’morning’) # False
  print is_spell(’hello’) # False
  print is_spell(’foo’) # True
  print is_spell(’bar’) # True
  print is_spell(’barfoombarmjac’) # True
  以上代码已经实现了这个算法。(不过有个小小的问题,如果字符串里含有中文,则不能正确判断,这是因为 python 中 len() 函数判断中文为双字节造成的,等有时间再改进这个)。

 

3COME考试频道为您精心整理,希望对您有所帮助,更多信息在http://www.reader8.cn/exam/


(作者:考试大 编辑:kind887)
热点排行