解環(huán)題目與解題報(bào)告

1、解環(huán)拜特蘭并不總是一個(gè)非常民主的國家，也有一些陰暗的歷史。一個(gè)美好的日子，拜特將軍該國的統(tǒng)帥作了一個(gè)用以結(jié)束長期內(nèi)戰(zhàn)的決定，釋放被關(guān)押的反對派。然而，他并未讓反對派的領(lǐng)袖拜特薩直接自由，而是用一根“拜特鏈”將拜特薩鎖在墻邊.該鏈子由很多環(huán)和固定在墻上柵欄組成。盡管環(huán)并未和柵欄融合在一起，但想除去它們卻非常困難。 “將軍，你為什么要用鏈子將我鎖在墻邊而不讓我自由！”拜特薩大叫道?！鞍萏厮_，你并未完全被鏈子鎖住，我可以坦率的告訴你，你完全可以從柵欄上解下環(huán)?！卑萏貙④姴恢业鼗卮?，同時(shí)他補(bǔ)充說，“但是，你必須在夜里工作，一個(gè)小時(shí)之內(nèi)完成，不能弄出任何聲音，否則，我將按有關(guān)法律制罪?！睘榱藥椭萏厮_！

2、鏈子上的環(huán)按整數(shù)1,2,n進(jìn)行了編號。我們可以按照以下規(guī)則解開環(huán)：只有一個(gè)環(huán)時(shí)可以被連接到柵欄或從柵欄上拆開。 第1號環(huán)總能進(jìn)行連接或拆開 如果1,.,k-1 (1=kn)環(huán)都被拆開，第k個(gè)環(huán)被連接時(shí), 此時(shí)我們能連接或拆開 第k+1個(gè)環(huán). 寫一個(gè)程序：文本文件LAN.IN描述了拜特鏈的構(gòu)成, 計(jì)算拆除拜特鏈上全部環(huán)的最少操作次數(shù), 將結(jié)果寫入文本文件LAN.OUT. 輸入在文本文件LAN.IN 中的第1行有一個(gè)整數(shù)n, 1=n=1000.在第2行有n個(gè)用一個(gè)空格分隔的整數(shù) o1,o2,.,on (每個(gè)都是0或1)，如果 oi=1, 那么第I個(gè)環(huán)和柵欄相連，如果 oi=0, 那么第I環(huán)沒有和柵

3、欄相連。 輸出文本文件 LAN.OUT中只包含一個(gè)整數(shù)，為解開拜特鏈的全部環(huán)的最少操作次數(shù)。輸入示例41 0 1 0輸出示例6解題報(bào)告初步分析為了看清問題的本質(zhì)，我們將題目重述：任意給定一個(gè)01串S，以及下面兩種操作：操作a：將S的第一個(gè)字符取反。操作b：若S1 . i 1 = 00000，Si = 1，那么將Si + 1取反。（1 = i = n 1）同時(shí)給出一個(gè)固定的目標(biāo)串T = 000000。現(xiàn)在需要將初始串S反復(fù)執(zhí)行上述兩種操作，變換到目標(biāo)串T。問：至少需要執(zhí)行多少次操作？譬如S = 1010。執(zhí)行操作b：1110執(zhí)行操作a：0110執(zhí)行操作b：0100執(zhí)行操作a：1100執(zhí)行操作b：

4、1000執(zhí)行操作a：0000共進(jìn)行了6次操作。稍加分析可知：性質(zhì)1 同一種操作不能連續(xù)兩次執(zhí)行。證明 若連續(xù)執(zhí)行同一操作兩次，相當(dāng)于沒執(zhí)行任何操作。所以不能將同一種操作連續(xù)兩次執(zhí)行。根據(jù)性質(zhì)1，我們?nèi)菀椎玫剑盒再|(zhì)2 將S變換到T的操作序列必然是：操作序列1：abab ba或者操作序列2：baba ba（最后執(zhí)行的操作必然是a）那么一種最簡單的算法構(gòu)想就形成了：分別按照上述兩種方法對S進(jìn)行操作，得出所需得操作次數(shù)；取較小值作為答案。然而這種算法的效率十分低下。如果最后的結(jié)果是s，那么它的時(shí)間復(fù)雜度就是O(s)s最大可以達(dá)到2n！于是我不得不尋找新的方法廣泛應(yīng)用于計(jì)數(shù)、以高效而著稱的動(dòng)態(tài)規(guī)劃就成了

5、我們首選的考察對象。動(dòng)態(tài)規(guī)劃模型要將S的每一位都變成0，顯然最后一次執(zhí)行的必須是操作a。故而我們可以將整個(gè)變換過程分解成：S 100000 00000即：將S的后n-1位全變?yōu)?。將S的第1位變?yōu)?。還是從實(shí)例入手：1 010 0101 110 1100 1100 100 1001 1001 000 0000 000圖中左列是S = 1010變到T = 0000的過程。我們?nèi)绻魂P(guān)心它的后n-1位，如右列所示實(shí)際上是把S的后3位變換到“全零”的過程。這正吻合了我們前面的分析。然而后面n-1的變換又直接受到第一位取值的影響。當(dāng)?shù)谝晃粸?時(shí)，后n-1位才能進(jìn)行b操作；當(dāng)?shù)谝晃粸?時(shí)，后n-1位才能

6、進(jìn)行a操作。另一方面，對后n-1位進(jìn)行變換同樣要遵行性質(zhì)2（操作a和b交替出現(xiàn)）。所以對后n-1位執(zhí)行完一次操作a，就必須進(jìn)行一次額外的操作，將原串的第一位取反；類似的，對后n-1位執(zhí)行完一次操作b，也必須進(jìn)行一次額外的操作，將原串中的第一位取反正如上圖中方框匡起來的部分，后n-1位的每個(gè)狀態(tài)都重復(fù)出現(xiàn)了兩次，這是由于這個(gè)原因。設(shè)通過“操作序列1”將S的后i位全部變換到0所需的最少操作次數(shù)是fi, 1；通過“操作序列2”將S的后i位全部變換到0所需的最少操作次數(shù)是fi, 2。那么根據(jù)上文的分析可以列出狀態(tài)轉(zhuǎn)移方程：當(dāng)?shù)趎 - i + 1位是1時(shí)： fi, 1 = fi - 1, 2 * 2 + 1 fi, 2 = fi - 1, 1 * 2當(dāng)?shù)趎 - i + 1位是0時(shí)： fi, 1 = fi - 1, 1 * 2 + 1 fi, 2 = fi - 1, 2 * 2邊界條件： f0, 1 = +，f0, 2 = 0求：minfn, 0, fn, 1。由于結(jié)果可能很大，所以要使用高精度運(yùn)算。整個(gè)算法的時(shí)間復(fù)雜度是O(n)。（不包