集训队作业poi0115解题报告_第1页
集训队作业poi0115解题报告_第2页
集训队作业poi0115解题报告_第3页
全文预览已结束

付费下载

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论