集訓(xùn)隊(duì)作業(yè)poi0115解題報(bào)告

1、Poi0115 解題題意描述本題實(shí)際上可看成計(jì)算出將一個(gè)指定的二進(jìn)制串按照一定規(guī)則轉(zhuǎn)化為另一個(gè)長度相同的全 0 二進(jìn)制串所需的最少步數(shù)。算法分析通過粗略分析可知，由于串長 n 相當(dāng)大（最多可達(dá) 1000），用搜索的辦法是肯定行不通的，須另辟蹊徑。為 k 的環(huán)是扣著注意到，題目所給出的移動(dòng)規(guī)則“如果為 1，k1 的所有環(huán)都已經(jīng)被拿掉了，則可以將的，而為k+1 的環(huán)拿掉或扣上”具有明顯的遞歸性。那么，本題的最小移動(dòng)步數(shù)也有遞歸性質(zhì)呢？大家一定都知道一道經(jīng)典遞歸題問題的移動(dòng)是分為三步，遞歸完成的。類似于的移動(dòng)，通過分析發(fā)現(xiàn)，若串中最后一位非 0 位是第t 位，若 t1，則步數(shù)最少的移動(dòng)方式一定按照如

2、下三步完成：1用最少步數(shù)將前 t1 位變成“0001”（第 t1 位為1，其余各位均為 0）的形式；2將第t 位變?yōu)?0；3用最少步數(shù)將前 t1 位變成“0000”。由此可見，移動(dòng)方法也具有遞歸性。為敘述方便，定義F（S1,S2）為按照規(guī)則將串 S1 轉(zhuǎn)化為串S2 所需的最少步數(shù)(S1 與 S2 的長度相同)，Ai =0001；（前 i1 位為 0，第i 為 1） Bi =0000；（長度為 i 且每位都是 0 的串） G（i）=F（Ai ，Bi）下面讓來看一個(gè)具體的例子。記設(shè)輸入的串為“110101”，F(xiàn)(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)顯然，不光是這個(gè)例子，事實(shí)上將任意輸入串 S 轉(zhuǎn)變?yōu)槿?0等長串的 F 值通過如上類似的變形后，都只與 G 的值有關(guān)，那么，應(yīng)該如何求得G 的值呢？對(duì)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）的值可以獨(dú)立計(jì)算。有了 G（i）的值，還需確定哪些是需要累加進(jìn)最后結(jié)果的。這可以通過一個(gè)遞歸過程實(shí)現(xiàn)，具體代碼參見程序。需要的是，由于 n 值很