問題求解與程序設(shè)計(jì)問題抽象

1、問題求解與程序設(shè)計(jì)第五講 問題抽象,李文新2004.2 – 2004.6,內(nèi)容提要,Binary codes - 1147討論 – 1063 作業(yè) – 1063,問題描述,給定一個(gè)N位的二進(jìn)制串b1 b2 … bN-1 bN將該串做旋轉(zhuǎn)，即將b1移到bN后面，得到一個(gè)新的二進(jìn)制串：b2 … bN-1 bN b1,問題描述,對(duì)新的二進(jìn)制串再做旋轉(zhuǎn)，得二進(jìn)制串b3 b4 … bN-1 bN

2、 b1 b2重復(fù)旋轉(zhuǎn)操作操作，可得N個(gè)二進(jìn)制串，對(duì)這N個(gè)串排序，可得一個(gè)N*N的矩陣,問題描述,例如：1 0 0 0 1 0 0 0 1 11 1 0 0 00 0 1 1 00 1 1 0 0,,,,,問題描述,對(duì)它們做排序，得矩陣0 0 0 1 10 0 1 1 0 0 1 1 0 0

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

4、示矩陣第一行從左到右的數(shù)值。,問題描述,輸入樣例bincode.in51 0 0 1 0,問題描述,輸出樣例bincode.out0 0 0 1 1,問題描述,限制1 <= N <= 1000,解法一 猜測(cè)法,計(jì)算輸入列中包含 0 的個(gè)數(shù) I生成輸出行：前I個(gè)為0，后N-I個(gè)為1思路：因?yàn)榫仃嚢醋帜感蚺判?，所?應(yīng)該在前面。?該算法不能保證正確，但對(duì)樣例正確?,解法二 窮舉法,生成

5、一個(gè)長度為N的全0序列按規(guī)則將其旋轉(zhuǎn)生成N*N矩陣如果最后一列與輸入相同，則輸出開始的序列。按字母序生成下一個(gè)長度為N的二進(jìn)制序列，goto 2.,解法二 窮舉法,顯然這一算法不是最優(yōu)的，但是它是正確的，因?yàn)樗F舉了全部可能。,解法三 迭代法,初始化一個(gè)N行，最開始是0列的工作矩陣.將輸入列放在當(dāng)前工作矩陣左邊，對(duì)行排序.如果矩陣列數(shù)小于N, goto 2.輸出第一行,解法三 迭代法,例子 （輸入10010

6、） 010 00 100 0000 000 00 000 0010 000 01 001 0111 111 10 110 1000 101 11 011 110,解法三 迭代法,例子 （輸入10010）0001000 0001 10001 0001100010001 0011 00011 001100011

7、0011 0110 00110 0110011001100 1000 11000 1000101100110 1100 01100 11000輸出：00011,解法三 迭代法,分析該算法所需數(shù)時(shí)間是>O(N3)N次迭代，每次要對(duì)一個(gè)N*N的矩陣排序,解法三 迭代法,證明該算法的本質(zhì)是逐一構(gòu)造矩陣的前 I 列對(duì)于I=1,重新排序后顯然成立對(duì)于I<N，如果

8、前I列就是矩陣的前I列，那么把最后一列加到前面，從序列的順序來說，是正確的，重新對(duì)這I+1列排序保證了行順序的正確性。,解法三 迭代法,分析一個(gè)值得注意的現(xiàn)象是：每次排序總是把開頭是0的行按原來的先后次序移到前面，而把開頭是1的行按原來的先后次序移到后面。,解法四 線性算法,算法描述：1.計(jì)算輸入列中0和1的個(gè)數(shù)，并用它們形成第一列.,解法四 線性算法,2. 生成一個(gè)Next數(shù)組，使得數(shù)組中的i個(gè)0指向最后一

9、列第i個(gè)0的行數(shù)，數(shù)組中的第j個(gè)1指向最后一列第j個(gè)1的行數(shù).,解法四 線性算法,3. 從第1行開始，按照Next指引的順序 – 從k到Next[k], 每次把該行最后一列的數(shù)字取出生成第一行的相應(yīng)數(shù)字。,解法四 線性算法,例如 輸入 10010有3個(gè)0，2個(gè)1，所以第1列一定是00011,解法四 線性算法,例如 輸入 100102.生成Next數(shù)組Next

10、10122003300541115104,,,,,,解法四 線性算法,例如 輸入 10010 Next 235143.沿著Next，根據(jù) 輸入列，生成第一行0 0 0 1 1,解法四 線性算法,證明對(duì)于序列（1） b1 b2 … bN-1 bN，左旋一位變成（2） b2 … bN-1 bN b1 ，

11、我們只要知道（1）左旋后得到的（2）在矩陣中是哪一行，就可以根據(jù)該行第一列的值得到 b2，依次類推得到b3 ， b4 ， …,解法四 線性算法,證明假設(shè)矩陣中兩行都以0開始，則它們左旋后，前后次序不變，所以在矩陣中以0開始的第1行，它的左旋后的序列在最后一列的第一個(gè)0的行。對(duì)1開始的行有同樣的性質(zhì)。,解法四 線性算法,證明例如 1 0 0 0 1 1 第1，2，3行以0 20 0

12、 1 1 0 開始，左旋后0 30 1 1 0 0 到最后1列，但 41 0 0 0 1 前后順序不變， 51 1 0 0 0 所以是2，3，5,解法四 線性算法,證明該算法就是利用了這一性質(zhì)，根據(jù)第1列和最后1列，直接算出第1行。,測(cè)試數(shù)據(jù),20 組100 位 全1100位 全0100位 01…01

13、1000位 0…01…1,5位，10位，15位的小數(shù)據(jù)長度為300-1000的隨機(jī)序列 13個(gè),算法分析初步,算法 – 解決問題的計(jì)算方法衡量算法的標(biāo)準(zhǔn)：正確性時(shí)間效率空間效率清晰性 – 實(shí)現(xiàn)的簡單性最優(yōu)性,算法分析初步,正確性完整的算法包括輸入、輸出和從輸入到輸出的處理過程。驗(yàn)證算法的正確性是指證明該算法可以從輸入經(jīng)過算法所描述的過程一定可以到達(dá)預(yù)定的輸出。定理證明正確性簡單驗(yàn)證+幾個(gè)樣例驗(yàn)證,算法分析