logo

您所在位置网站首页 > 海量文档  > 计算机 > 软件编程

字符变换教案.ppt 17页

本文档一共被下载: ,您可全文免费在线阅读后下载本文档。

  • 支付并下载
  • 收藏该文档
  • 百度一下本文档
  • 修改文档简介
全屏预览

下载提示

1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值,立即自动返金币,充值渠道很便利
特别说明: 下载前务必先预览,自己验证一下是不是你要下载的文档。
  • 上传作者 爱是你我(上传创作收益人)
  • 发布时间:2019-05-15
  • 需要金币100(10金币=人民币1元)
  • 浏览人气
  • 下载次数
  • 收藏次数
  • 文件大小:542.5 KB
下载过该文档的会员
你可能关注的文档:
* * * * * * * * * * * * * [题一] 字符变换(NOIPG2)? 问题描述: 已知有两个字串A$,B$及一组字串变换的规则: A1$→B1$ A2$→B2$ ……… 规则的含义为:在A$中的子串A1$可以变换为B1$、A2$可以变换为B2$…..。 例如:A$ =‘abcd’ B$=‘xyz’ 变换规则为: ‘abc’→‘xu’ ‘ud’→‘y’ ‘y’→‘yz’ 则此时,A$可以经过一系列的变换变为B$,其变换的过程为: ‘abcd’→‘xud’→‘xy’→‘xyz’ 共进行了三次变换,使得A$变换为B$。 输入: 输入文件名为A.in。文件格式如下: A$,B$ A1$ → B1$ A2$ → B2$ 变换规则 ……… 所有字符串长度的上限为255。 输出:输出文件名为A.out。若在30步(包含30步)以内能将A$变换为B$,则向A.out输出最少的变换步数;否则向A.out输出‘ERROR!’。 问题简述: 给定一起始状态S、最终状态T及一些可行操作集P,使用最少的操作步数把S转变为目标集合T。 分析: 这是一个典型的状态空间搜索问题。这类问题可用广度优先搜索算法解决。 步骤: 1. 将备选队列初始化为起始状态S; 2. 在备选队列中取出所需操作步骤最少的一个状态R; 3. 对于P中的每一个操作Pi: 3.1 对R应用Pi得到Q; 3.2 若Q未被扩展,则把Q加入备选队列; 3.3 若Q=T,则输出步数并退出; 3.4 若操作步数大于指定步数上限,则输出“No Answer”并退出; 4. 转步骤2。 应用广度优先搜索算法的基本框架编写程序,判重时采用将已产生的状态扫描一遍的方法,耗费了大量时间。此外,由于最坏情况下字串的每一个位置都有10种变换方法,状态数呈指数级增长,空间问题也没有得到很好的解决。 分析题目,可得到以下事实:设有规则{A}?{B},则本问题也可等价于求从目标串通过规则{B}?{A}转变成初始串的最少变换次数。例如样例,由abcd?xud?xy?xyz,也就是由xyz?xy? xud?abcd。基于此,我们考虑使用双向搜索,即对串和目标串分别利用规则{A}?{B}和{B}?{A}进行变换,直至二者得到一个相同的串为止,因此采用双向搜索。 实践证明,双向搜索大大减少了扩展出的状态。 单向搜索 双向搜索 测试点 产生状态数 测试点 产生状态数 1 10 1 5 2 34 2 24 3 6 3 6 4 21 4 20 5 5549 5 330 判重时,采用hash表来完成对状态的存储和检索。字串St的hash函数H(St)为字串的每一位字符的ASCII码值的和除以255的余数。 例如,H(‘abcd’)=(97+98+99+100) mod 255=139。用数组que来存储状态。 [题二] 聪明的打字员 Swap 0 Swap1 Up Dpwn Left Right 1 2 3 4 5 6 输入样例: 123456 654321 (初始密码) (目标密码) 输出样例: 11(密码的最少击键次数) [题三] 栅栏 (fence)? 问题描述: Farmer John在农场周围建造栅栏。他定出农场的形状,并打上了木桩。他手头上有一些不同长度的木板,将木板切割成几段(忽略损耗)。例如,一块9米的木板可以切成一块4米的和一块5米的,也可以切成三块3米的。 Farmer John需要一些指定长度的横栏,他希望能利用商店里的木板切割出尽可能多的他所需要的横栏(这些长度可以重复)。? 输入格式:第一行一个整数N(1<=N<=50),表示商店里的木板数。以下N行,每行一个正整数表示商店里木板的长度。接着是一个整数R,表示需要切割出的横栏数,以下R行每行一个正整数表示这些横栏的长度。 输出格式:一个整数,表示能切割出的最大横栏数。 输入样例: 4 30 40 50 25 10 15 16 17 18 19 20 21 25 24 30 输出样例: 7 优化: 1.? 采用二分法枚举最多能切出 的横栏数,作为搜索目标; 2.? 按长度从小到大的顺序。 [题四] 旅游路线? 问题描述: 一正方形小镇被划分

发表评论

请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
用户名: 验证码: 点击我更换图片

2010-2013 max.book118.com在线文档投稿赚钱网. All Rights Reserved 蜀ICP备08101938号