付费下载
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、Poi0115 解题题意描述本题实际上可看成计算出将一个指定的二进制串按照一定规则转化为另一个长度相同的全 0 二进制串所需的最少步数。算法分析通过粗略分析可知,由于串长 n 相当大(最多可达 1000),用搜索的办法是肯定行不通的,须另辟蹊径。为 k 的环是扣着注意到,题目所给出的移动规则“如果为 1,k1 的所有环都已经被拿掉了,则可以将的,而为k+1 的环拿掉或扣上”具有明显的递归性。那么,本题的最小移动步数也有递归性质呢?大家一定都知道一道经典递归题问题的移动是分为三步,递归完成的。类似于的移动,通过分析发现,若串中最后一位非 0 位是第t 位,若 t1,则步数最少的移动方式一定按照如
2、下三步完成:1用最少步数将前 t1 位变成“0001”(第 t1 位为1,其余各位均为 0)的形式;2将第t 位变为 0;3用最少步数将前 t1 位变成“0000”。由此可见,移动方法也具有递归性。为叙述方便,定义F(S1,S2)为按照规则将串 S1 转化为串S2 所需的最少步数(S1 与 S2 的长度相同),Ai =0001;(前 i1 位为 0,第i 为 1) Bi =0000;(长度为 i 且每位都是 0 的串) G(i)=F(Ai ,Bi)下面让来看一个具体的例子。记设输入的串为“110101”,F(110101,000000)=F(11010,00001)+1+G(6-1)F(110
3、10,00001)=F(1101,0001)+1+G(5-1)F(1101,0001)=F(110,000)F(110,000)=F(11,00)F(11,00)=F(1,1)+1+G(2-1)F(1,1)=0将等式相加,整理,得F(110101,000000) = 1+G(6-1)+1+G(5-1)+1+G(2-1)显然,不光是这个例子,事实上将任意输入串 S 转变为全 0等长串的 F 值通过如上类似的变形后,都只与 G 的值有关,那么,应该如何求得G 的值呢?对G(i)的求值过程做一些变形。显然G(1)= 1;G(i+1)= F(Ai+1 ,Bi+1)= F(Bi,Ai)+1+ F(Ai,Bi)= F(Ai,Bi)*2+1= G(i)*2+1所以G(i)= 2n1也就是说,G(i)的值可以独立计算。有了 G(i)的值,还需确定哪些是需要累加进最后结果的。这可以通过一个递归过程实现,具体代码参见程序。需要的是,由于 n 值很
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 金融科技公司数据分析师数据应用与分析能力绩效评定表
- 景区游客集中区域秩序维护指引方案
- 智能制造设备采购资金管理指引
- 电影制片财务管理与进度跟踪绩效表
- 关于新客户服务手册发放通知(6篇)
- 事业单位人事岗2026面试必练考题全真模拟试卷
- 小学英语教资面试结构化2026易错题题库及解析
- 游戏公司策划设计师用户反馈收集与体验优化绩效考核表
- 2026初中物理教资面试试讲历年真题题库及解析
- 2026小学数学教资面试结构化易错题题库及解析
- 蛋糕制作演讲课件
- 7.1 珍视自由 课件(共18张)+内嵌视频
- 2025年甘肃(专升本)英语考试题库(含答案)
- DB45-T 2875-2024 矿山生态修复工程技术规范
- AI赋能小学语文整本书阅读实施方案
- 加气站变更管理制度(3篇)
- 《CATIA-V5R21基础与应用案例教程》(共9章)第七章钣金设计
- 手术部位感染的预防及控制措施
- 油漆店面应急预案
- 2025年四川省内江市专业技术继续教育公需科目考试及答案
- 工程合同外增加项补充协议模板
评论
0/150
提交评论