1、問(wèn)題求解與程序設(shè)計(jì)第五講 問(wèn)題抽象,李文新 2004.2 2004.6,內(nèi)容提要,Binary codes - 1147 討論 1063 作業(yè) 1063,問(wèn)題描述,給定一個(gè)N位的二進(jìn)制串 b1 b2 bN-1 bN 將該串做旋轉(zhuǎn)，即將b1移到bN后面，得到一個(gè)新的二進(jìn)制串： b2 bN-1 bN b1,問(wèn)題描述,對(duì)新的二進(jìn)制串再做旋轉(zhuǎn)，得二進(jìn)制串 b3 b4 bN-1 bN b1 b2 重復(fù)旋轉(zhuǎn)操作操作，可得N個(gè)二進(jìn)制串，對(duì)這N個(gè)串排序，可得一個(gè)N*N的矩陣,問(wèn)題描述,例如： 1 0 0 0 1 0 0 0 1 11 1 0 0 0 0 0 1 1 00 1 1 0 0,問(wèn)題描述,對(duì)它們做排序

2、，得矩陣 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0,問(wèn)題描述,問(wèn)：給定這種矩陣的最后一列， 求出矩陣的第一行。 對(duì)于上面的例子，給出 1 0 0 1 0，要你的程序輸出 0 0 0 1 1。,問(wèn)題描述,輸入文件名：bincode.in 第一行有一個(gè)整數(shù) N 表示二進(jìn)制串的長(zhǎng)度 第二行有N個(gè)整數(shù)，表示矩陣最后一列從上到下的數(shù)值。,問(wèn)題描述,輸出文件名：bincode.out 第一行包括N個(gè)整數(shù)，表示矩陣第一行從左到右的數(shù)值。,問(wèn)題描述,輸入樣例 bincode.in 5 1 0 0 1 0,問(wèn)題描述,輸出樣例 bincode.out 0

3、0 0 1 1,問(wèn)題描述,限制 1 = N = 1000,解法一 猜測(cè)法,計(jì)算輸入列中包含 0 的個(gè)數(shù) I 生成輸出行：前I個(gè)為0，后N-I個(gè)為1 思路：因?yàn)榫仃嚢醋帜感蚺判?，所?應(yīng)該在前面。 該算法不能保證正確，但對(duì)樣例正確,解法二 窮舉法,生成一個(gè)長(zhǎng)度為N的全0序列 按規(guī)則將其旋轉(zhuǎn)生成N*N矩陣 如果最后一列與輸入相同，則輸出開(kāi)始的序列。 按字母序生成下一個(gè)長(zhǎng)度為N的二進(jìn)制序列，goto 2.,解法二 窮舉法,顯然這一算法不是最優(yōu)的，但是它是正確的，因?yàn)樗F舉了全部可能。,解法三 迭代法,初始化一個(gè)N行，最開(kāi)始是0列的工作矩陣. 將輸入列放在當(dāng)前工作矩陣左邊，對(duì)行排序. 如果矩陣列數(shù)小于

4、N, goto 2. 輸出第一行,解法三 迭代法,例子 （輸入10010） 010 00 100 000 0 000 00 000 001 0 000 01 001 011 1 111 10 110 100 0 101 11 011 110,解法三 迭代法,例子 （輸入10010） 0001000 0001 10001 00011 00010001 0011 00011 00110 00110011 0110 00110 01100 11001100 1000 11000 10001 01100110 1100 01100 11000 輸出：00011,解法三 迭代法,分析 該算法所需數(shù)時(shí)間是

5、O(N3) N次迭代，每次要對(duì)一個(gè)N*N的矩陣排序,解法三 迭代法,證明 該算法的本質(zhì)是逐一構(gòu)造矩陣的前 I 列 對(duì)于I=1,重新排序后顯然成立 對(duì)于IN，如果前I列就是矩陣的前I列，那么把最后一列加到前面，從序列的順序來(lái)說(shuō)，是正確的，重新對(duì)這I+1列排序保證了行順序的正確性。,解法三 迭代法,分析 一個(gè)值得注意的現(xiàn)象是：每次排序總是把開(kāi)頭是0的行按原來(lái)的先后次序移到前面，而把開(kāi)頭是1的行按原來(lái)的先后次序移到后面。,解法四 線(xiàn)性算法,算法描述： 1.計(jì)算輸入列中0和1的個(gè)數(shù)，并用它們形成第一列.,解法四 線(xiàn)性算法,2. 生成一個(gè)Next數(shù)組，使得數(shù)組中的i個(gè)0指向最后一列第i個(gè)0的行數(shù)，數(shù)組中

6、的第j個(gè)1指向最后一列第j個(gè)1的行數(shù).,解法四 線(xiàn)性算法,3. 從第1行開(kāi)始，按照Next指引的順序 從k到Nextk, 每次把該行最后一列的數(shù)字取出生成第一行的相應(yīng)數(shù)字。,解法四 線(xiàn)性算法,例如 輸入 10010 有3個(gè)0，2個(gè)1，所以第1列一定是 0 0 0 1 1,解法四 線(xiàn)性算法,例如 輸入 10010 2.生成Next數(shù)組Next 1012 2003 3005 4111 5104,解法四 線(xiàn)性算法,例如 輸入 10010 Next 23514 3.沿著Next，根據(jù) 輸入列，生成第一行 0 0 0 1 1,解法四 線(xiàn)性算法,證明 對(duì)于序列（1） b1 b2 bN-1 bN，左旋一位變

7、成（2） b2 bN-1 bN b1 ，我們只要知道（1）左旋后得到的（2）在矩陣中是哪一行，就可以根據(jù)該行第一列的值得到 b2，依次類(lèi)推得到b3 ， b4 ， ,解法四 線(xiàn)性算法,證明 假設(shè)矩陣中兩行都以0開(kāi)始，則它們左旋后，前后次序不變，所以在矩陣中以0開(kāi)始的第1行，它的左旋后的序列在最后一列的第一個(gè)0的行。對(duì)1開(kāi)始的行有同樣的性質(zhì)。,解法四 線(xiàn)性算法,證明 例如 1 0 0 0 1 1 第1，2，3行以0 20 0 1 1 0 開(kāi)始，左旋后0 30 1 1 0 0 到最后1列，但 41 0 0 0 1 前后順序不變， 51 1 0 0 0 所以是2，3，5,解法四 線(xiàn)性算法,證明 該算法就是利用了這一性質(zhì)，根據(jù)第1列和最后1列，直接算出第1行。,測(cè)試數(shù)據(jù),20 組 100 位 全1 100位 全0 100位 0101 1000位 0011, 5位，10位，15位的小數(shù)據(jù) 長(zhǎng)度為300-1000的隨機(jī)序列 13個(gè),算法分析初步,算法 解決問(wèn)題的計(jì)算方法 衡量算法的標(biāo)準(zhǔn)： 正確性 時(shí)間效率 空間效率 清晰性 實(shí)現(xiàn)的簡(jiǎn)單性 最優(yōu)性,算法分析初步,正確性 完整的算法包括輸入、輸出和從輸入到輸出的處理過(guò)程。驗(yàn)證算法的正確性是指證明該算法可以從輸入經(jīng)過(guò)算法所描述的過(guò)程一定可以到達(dá)預(yù)定的輸出。 定理證明正確性 簡(jiǎn)單驗(yàn)證+幾個(gè)樣例驗(yàn)證,算法分析初步,時(shí)間效率 執(zhí)行該算法所需時(shí)間