文件名称:
动态规划—最短编辑问题—（非常详细分析以及代码）
开发工具:
文件大小: 6kb
下载次数: 0
上传时间: 2011-06-07
详细说明： *问题描述：设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。 * 这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； * (3)将一个字符改为另一个字符。将字符串A变换为字符串B 所用的最少 * 字符操作数称为字符串A到B 的编辑距离，记为 d(A,B)。试设计一个有效 * 算法，对任给的2 个字符串A和B，计算出它们的编辑距离d(A,B)。 * 例如： * 输入第一个字符串： * shao * 输入第二个字符串： * shaod * 最短编辑距离 * 1 (2)本题思路分析 * 定义两个字符串s1 ,s2 * 比较两字符串的某两个相同位置时：(例如s1[i] s2[j] 这时i=j)有三种办法 * 1.把字符ch1变成ch2， 使得s1与s2字符串在该处相同 * 2.删除s1当中的该字符ch1，使得s1与s2字符串在该处相同 * 3.插入某个字符ch2，使得s1与s2字符串在该处相同 运行结果： * 请输入字符串1 * shao * 请输入字符串2 * sha1 * d[1][1]= 0 d[1][2]= 1 d[1][3]= 2 d[1][4]= 3 * * d[2][1]= 1 d[2][2]= 0 d[2][3]= 1 d[2][4]= 2 * * d[3][1]= 2 d[3][2]= 1 d[3][3]= 0 d[3][4]= 1 * * d[4][1]= 3 d[4][2]= 2 d[4][3]= 1 d[4][4]= 1 * * 最短编辑距离为： 1 * 请按任意键继续. . . ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
