|
由算法得出代碼 本系列一開頭就說明了何謂程序，并說明由于CPU的世界和人們存在的客觀物理世界的不兼容而導致根本不能將人編寫的程序（也就是算法）翻譯成CPU指令，但為了能夠翻譯，就必須讓人覺得CPU世界中的某些東西是人以為的算法所描述的某些東西。如電腦屏幕上顯示的圖片，通過顯示器對不同象素顯示不同顏色而讓人以為那是一幅圖片，而電腦只知道那是一系列數字，每個數字代表了一個象素的顏色值而已。 為了實現上面的“讓人覺得是”，得到算法后要做的的第一步就是找出算法中要操作的資源。前面已經說過，任何程序都是描述如何操作資源的，而C++語言本身只能操作內存的值這一種資源，因此編程要做的第一步就是將算法中操作的東西映射成內存的值。由于內存單元的值以及內存單元地址的連續性都可以通過二進制數表示出來，因此要做的第一步就是把算法中操作的東西用數字表示出來。 上面做的第一步就相當于數學建模——用數學語言將問題表述出來，而這里只不過是用數字把被操作的資源表述出來罷了（應注意數字和數的區別，數字在C++中是一種操作符，其有相關的類型，由于最后對它進行計算得到的還是二進制數故使用數字進行表示而不是二進制數，以增強語義）。接著第二步就是將算法中對資源的所有操作都映射成語句或函數。 用數學語言對算法進行表述時，比如將每10分鐘到車站等車的人的數量映射為一隨機變量，也就前述的第一步。隨后定此隨機變量服從泊松分布，也就是上面的第二步。到站等車的人的數量是被操作的資源，而給出的算法是每隔10分種改變這個資源，將它的值變成按給定參數的泊松函數分布的一隨機值。 在C++中，前面已經將資源映射成了數字，接著就要將對資源的操作映射成對數字的操作。C++中能操作數字的就只有操作符，也就是將算法中對資源的所有操作都映射成表達式語句。 當上面都完成了，則算法中剩下的就只有執行順序了，而執行順序在C++中就是從上朝下書寫，而當需要邏輯判斷的介入而改變執行順序時，就使用前面的if和goto語句（不過后者也可以通過if后接的語句來實現，這樣可以減少goto語句的使用，因為goto的語義是跳轉而不是“所以就”），并可考慮是否能夠使用循環語句以簡化代碼。即第三步為將執行流程用語句表示出來。 而前面第二步之所以還說可映射成函數，即可能某個操作比較復雜，還帶有邏輯的意味，不能直接找到對應的操作符，這時就只好利用萬能的函數操作符，對這個操作重復剛才上面的三個步驟以將此操作映射成多條語句（通過if等語句將邏輯信息表現出來），而將這些語句定義為一函數，供函數操作符使用以表示那個操作。 上面如果未明不要緊，后面有兩個例子，都將分別說明各自是如何進行上述步驟的。 排序 給出三張卡片，上面隨便寫了三個整數。有三個盒子，分別標號為1、2和3。將三張卡片隨機放到1、2、3這三個盒子中，現在要求排序以使得1、2、3三個盒子中裝的整數是由小到大的順序。 給出一最簡單的算法：稱1、2、3盒子中放的卡片上的整數分別為第一、二、三個數，則先將第一個數和第二個數比較，如果前者大則兩個盒子內的卡片交換；再將第一個和第三個比較，如果前者大則交換，這樣就保證第一個數是最小的。然后將第二個數和第三個數比較，如果前者大則交換，至此排序完成。 第一步：算法中操作的資源是裝在盒子中的卡片，為了將此卡片映射成數字，就注意算法中的卡片和卡片之前有什么不同。算法中區分不同卡片的唯一方法就是卡片上寫的整數，因此在這里就使用一個long類型的數字來表示一個卡片。 算法中有三張卡片，故用三個數字來表示。前面已經說過，數字是裝在內存中的，不是變量中的，變量只不過是映射地址而已。在這里需要三個long類型數字，可以借用定義變量時編譯器自動在棧上分配的內存來記錄這些數字，故可以如此定義三個變量long a1, a2, a3;來記錄三個數字，也就相當于裝三張卡片的三個盒子。 第二步：算法中的操作就是對卡片上的整數的比較和交換。前者很簡單，使用邏輯操作符就可以實現（因為正好將卡片上的整數映射成變量a1、a2和a3中記錄的數字）。后者是交換兩個盒子中的卡片，可以先將一卡片從一盒子中取出來，放在桌子上或其他地方。然后將另一盒子中的卡片取出來放在剛才空出來的盒子。最后將先取出來的卡片放進剛空出來的盒子。前面說的“桌子上或其他地方”是用來存放取出的卡片，C++中只有內存能夠存放數字，因此上面就必須再分配一臨時內存來臨時記錄取出的數字。 第三步：操作和資源都已經映射好了，算法中有如果的就用if替換，由什么重復多少次的就用for替換，有什么重復直到怎樣的就用while或do while替換，如上照著算法映射過來就完了，如下： void main() { long a1 = 34, a2 = 23, a3 = 12; if( a1 > a2 ) { long temp = a1; a1 = a2; a2 = temp; } if( a1 > a3 ) { long temp = a1; a1 = a3; a3 = temp; } if( a2 > a3 ) { long temp = a2; a2 = a3; a3 = temp; } } 上面就在每個if后面的復合語句中定義了一個臨時變量temp以借助編譯器的靜態分配內存功能來提供臨時存放卡片的內存。上面的元素交換并沒有按照前面所說映射成函數，是因為在這里其只有三條語句且容易理解。如果要將交換操作定義為一函數，則應如下： void Swap( long *p1, long *p2 ) void Swap( long &r1, long &r2 ) { { long temp = *p1; long temp = r1; *p1 = *p2; r1 = r2; *p2 = temp; r2 = temp; } } void main() void main() { { long a1 = 34, a2 = 23, a3 = 12; long a1 = 34, a2 = 23, a3 = 12; if( a1 > a2 ) if( a1 > a2 ) Swap( &a1, &a2 ); Swap( a1, a2 ); if( a1 > a3 ) if( a1 > a3 ) Swap( &a1, &a3 ); Swap( a1, a3 ); if( a2 > a3 ) if( a2 > a3 ) Swap( &a2, &a3 ); Swap( a2, a3 ); } } 先看左側的程序。上面定義了函數來表示給定盒子之間的交換操作，注意參數類型使用了long*，這里指針表示引用（應注意指針不僅可以表示引用，還可有其它的語義，以后會提到）。 什么是引用？注意這里不是指C++提出的那個引用變量，引用表示一個連接關系。比如你有手機，則手機號碼就是“和你通話”的引用，即只要有你的手機號碼，就能夠實現“和你通話”。 再比如Windows操作系統提供的快捷方式，其就是一個“對某文件執行操作”的引用，它可以指向某個文件，通過雙擊此快捷方式的圖標就能夠對其所指的文件進行“執行”操作（可能是用某軟件打開這個文件或是直接執行此文件等），但如果刪除此快捷方式卻并不會刪除其所指向的文件，因為它只是“對某文件執行操作”的引用。 人的名字就是對“某人進行標識”的引用，即說某人考上大學通過說那個人的名字則大家就可以知道具體是哪個人。同樣，變量也是引用，它是某塊內存的引用，因為其映射了地址，而內存塊可以通過地址來被唯一表明其存在，不僅僅是標識。注意其和前面的名字不同，因為任何對內存塊的操作，只要知道內存塊的首地址就可以了，而要和某人面對面講話或吃飯，只知道他的名字是不夠的。 應注意對某個東西的引用可以不止一個，如人就可以有多個名字，變量也都有引用變量，手機號碼也可以不止一個。 注意上面引入了函數來表示交換，進而導致了盒子也就成了資源，因此必須將盒子映射成數字。而前面又將盒子里裝的卡片映射成了long類型的數字，由于“裝”這個操作，因此可以想到使用能夠標識裝某個代表卡片的數字的內存塊來作為盒子映射的數字類型，也就是內存塊的首地址，也就是long*類型（注意不是地址類型，因為地址類型的數字并不返回記錄它的內存的地址）。所以上面的函數參數類型為long*。 下面看右側的程序。參數類型變成long&，和指針一樣，依舊表示引用，但注意它們的不同。后者表示它是一個別名，即它是一個映射，映射的地址是記錄作為參數的數字的地址，也就是說它要求調用此函數時，給出的作為參數的數字一定是有地址的數字。所謂的“有地址的數字”表示此數字是程序員創建的，不是編譯器由于臨時原因而生成的臨時內存的地址，如Swap( a1++, a2 );就要報錯。之前已經說明，因為a1++返回的地址是編譯器內部定的，就程序邏輯而言，其是不存在的，而Swap( ++a1, a2 );就是正確的。Swap( 1 + 3, 34 );依舊要報錯，因為記錄1 + 3返回的數字的內存是編譯器內部分配的，就程序邏輯上來說，它們并沒有被程序員用某塊內存記錄起來，也就不會有內存。 一個很簡單的判定規則就是調用時給的參數類型如果是地址類型的數字，則可以，否則不行。 還應注意上面是long&類型，表示所修飾的變量不分配內存，也就是編譯器要靜態地將參數r1、r2映射的地址定下來，對于Swap( a1, a2 );就分別是a1和a2的地址，但對于Swap( a2, a3 );就變成a2和a3的地址了，這樣是無法一次就將r1、r2映射的地址定下來，即r1、r2映射的地址在程序運行時是變化的，也就不能且無法編譯時靜態一次確定。 為了實現上面的要求，編譯器實際將會在棧上分配內存，然后將地址傳遞到函數，再編寫代碼以使得好像動態綁定了r1、r2的地址。這實際和將參數類型定為long*是一樣的效果，即上面的Swap( long&, long& );和Swap( long*, long* );是一樣的，只是語法書寫上不同，內部是相同的，連語義都相同，均表示引用（雖然指針不僅僅只帶有引用的語義）。即函數參數類型為引用類型時，依舊會分配內存以傳遞參數的地址，即等效于指針類型為參數。 商人過河問題 3個商人帶著3個仆人過河，過河的工具只有一艘小船，只能同時載兩個人過河，包括劃船的人。在河的任何一邊，只要仆人的數量超過商人的數量，仆人就會聯合起來將商人殺死并搶奪其財物，問應如何設計過河順序才能讓所有人都安全地過到河的另一邊。 給出最弱卻萬能的算法——枚舉法。坐船過河及劃船回來的可能方案為一個仆人、一個商人或兩個商人、兩個仆人及一個商人一個仆人。 故每次從上述的五種方案中選擇一個劃過河去，然后檢查河岸兩側的人數，看是否會發生仆人殺死商人，如果兩邊都不會，則再從上述的五個方案中選擇一個讓人把船劃回來，然后再檢查是否會發生仆人殺死商人，如果沒有就又重新從五個方案中選一個劃過河，如上重復直到所有人都過河了。 上面在選方案時除了保證商人不被殺死，還要保證此方案運行（即過河或劃回來）后，兩岸的人數布局從來都沒有出現過，否則就形成無限循環，且必須合理，即沒有負數。如果有一次的方案選擇失敗，則退回去重新選另一個方案再試。如果所有方案都失敗，則再退回到更上一次的方案選擇。如果一直退到第一次的方案選擇，并且已沒有可選的方案，則說明上題無解。 上面的算法又提出了兩個基本又重要的概念——層次及容器。下面先說明容器。 容器即裝東西的東西，而C++中操作的東西只有數字，因此容器就是裝數字的東西，也就是內存。容器就平常的理解是能裝多個東西，即能裝多個數字。這很簡單，使用之前的數組的概念就行了。但如果一個盒子能裝很多蘋果，那它一定占很大的體積，即不管裝了一個蘋果還是兩個蘋果，那盒子都要占半立方米的體積。數組就好像盒子，不管裝一個元素還是兩個元素，它都是long[10]的類型而要占40個字節。 容器是用來裝東西的，那么要取出容器中裝的東西，就必須有種手段標識容器中裝的東西，對于數組，這個東西就是數組的下標，如long a[10]; a[3];就取出了第四個元素的值。由于有了標識，則還要有一種手段以表示哪些標識是有效的，如上面的a數組，只前面兩個元素記錄了數字，但是卻a[3];，得到的將是錯誤的值，因為只有a[0]和a[1]是有意義的。 因此上面的用數組作容器有很多的問題，但它非常簡單，并能體現各元素之間的順序關系，如元素被排序后的數組。但為了適應復雜算法，必須還要其他容器的支持，如鏈表、樹、隊列等。它們一般也被稱做集合，都是用于管理多個元素用的，并各自給出了如何從眾多的元素中快速找到給定標識所對應的元素，而且都能在各元素間形成一種關系，如后面將要提到的層次關系、前面數組的順序關系等。關于那些容器的具體實現方式，請參考其他資料，在此不表。 上面算法中提到“兩岸的人數布局從來都沒有出現過”，為了實現這點，就需要將其中的資源——人數布局映射為數字，并且還要將曾經出現過的所有人數布局全部記錄下來，也就是用一個容器記錄下來，由于還未說明結構等概念，故在此使用數組來實現這個容器。上面還提到從已有的方案中選擇一個，則可選的方案也是一個容器，同上，依舊使用一數組來實現。 層次，即關系，如希望小學的三年2班的XXX、中國的四川的成都的XXX等，都表現出一種層次關系，這種層次關系是多個元素之間的關系，因此就可以通過找一個容器，那個容器的各元素間已經是層次關系，則這個容器就代表了一種層次關系。樹這種容器就是專門對此而設計的。 上面算法中提到的“再退回到更上一次的方案選擇”，也就是說第一次過河選擇了一個商人一個仆人的方案，接著選擇了一個商人回來的方案，此時如果選擇兩個仆人過河的方案將是錯誤的，則將重新選擇過河的方案。再假設此時所有過河的方案都失敗了，則只有再向后退以重新選擇回來的方案，如選擇一個仆人回來。對于此，由于這里只要求退回到上一次的狀態，也就是人數布局及選擇的方案，則可以將這些統一放在容器中，而它們各自都只依靠順序關系，即第二次過河的方案一定在第一次過河的方案成功的前提下才可能考慮，因此使用數組這個帶有順序關系的容器即可。 第一步：上面算法的資源有兩個：坐船的方案和兩岸的人數布局。坐船的方案最多五種，在此使用一個char類型的數字來映射它，即此8位二進制數的前4位用補碼格式來解釋得到的數字代表仆人的數量，后4位則代表商人的數量。因此一個商人和一個仆人就是( 1 << 4 ) | 1。兩岸的人數布局，即兩岸的商人數和仆人數，由于總共才3+3=6個人，這都可以使用char類型的數字就能映射，但只能映射一個人數，而兩岸的人數實際共有4個（左右兩岸的商人數和仆人數），則這里使用一個char[4]來實現（實際最好是使用結構來映射而不是char[4]，下篇說明）。如char a[4];表示一人數布局，則a[0]表示河岸左側的商人數，a[1]表示左側的仆人數，a[2]表示河岸右側的商人數，a[3]表示右側的仆人數。 注意前面說的容器，在此為了裝可選的坐船方案故應有一容器，使用數組，如char sln[5];。在此還需要記錄已用的坐船方案，由于數組的元素具備順序關系，所以不用再生成一容器，直接使用一char數字記錄一下標，當此數字為3時，表示sln[0]、sln[1]和sln[2]都已經用過且都失敗了，當前可用的為sln[3]和sln[4]。同樣，為了裝已成功的坐船方案作用后的人數布局及當時所選的方案，就需要兩個容器，在此使用數組（實際應該鏈表）char oldLayout[4][200], cur[200];。oldLayout就是記錄已成功的方案的容器，其大小為200，表示假定在200次內，一定就已經得出結果了，否則就會因為超出數組上限而可能發生內存訪問違規，而為什么是可能在《C++從零開始（十五）》中說明。 前面說過數組這種容器無法確定里面的有效元素，必須依靠外界來確定，對此，使用一unsigned char curSln;來記錄oldLayout和cur中的有效元素的個數。規定當curSln為3時，表示oldLayout[0～3][0]、oldLayout[0～3][1]和oldLayout[0～3][2]都有效，同樣cur[0]、cur[1]和cur[2]都有效，而之后的如cur[3]等都無效。 第二步：操作有：執行過河方案、執行回來方案、檢查方案是否成功、退回到上一次方案選擇、是否所有人都過河、判斷人數布局是否相同。如下： 前兩個操作：將當前的左岸人數減去相應的方案定的人數，而右岸則加上人數。要表現當前左岸人數，可以用oldLayout[0][ curSln ]和oldLayout[1][ curSln ]表示，而相應方案的人數則為( sln[ cur[ curSln ] ] & 0xF0 ) >> 4和sln[ cur[ curSln ] ] & 0xF。由于這兩個操作非常類似，只是一個是加則另一個就是減，故將其定義為函數，則為了在函數中能操作oldLayout、curSln等變量，就需要將這些變量定義為全局變量。 檢查是否成功：即看是否 oldLayout[1][ curSln ] > oldLayout[0][ curSln ] && oldLayout[0][ curSln ]以及是否 oldLayout[3][ curSln ] > oldLayout[2][ curSln ] && oldLayout[2][ curSln ] 并且保證各自不為負數以及沒有和原來的方案沖突。檢查是否和原有方案相同就是枚舉所有原由方案以和當前方案比較，由于比較復雜，在此將其定義為函數，通過返回bool類型來表示是否沖突。 退回上一次方案或到下一個方案的選擇，只用curSln--或curSln++即可。而是否所有人都過河，則只用oldLayout[0～1][ curSln ]都為0而oldLayout[2～3][ curSln ]都為3。而判斷人數布局是否相同，則只用相應各元素是否相等即可。 第三步：下面剩下的就沒什么東西了，只需要按照算法說的順序，將剛才的各操作拼湊起來，并注意“重復直到所有人都過河了”轉成do while即可。如下： #include // 分別表示一個商人、一個仆人、兩個商人、兩個仆人、一個商人一個仆人 char sln[5] = { ( 1 << 4 ), 1, ( 2 << 4 ), 2, ( 1 << 4 ) | 1 }; unsigned char curSln = 1; char oldLayout[4][200], cur[200]; void DoSolution( char b ) { unsigned long oldSln = curSln - 1; // 臨時變量，出于效率 oldLayout[0][ curSln ] = oldLayout[0][ oldSln ] - b * ( ( sln[ cur[ curSln ] ] & 0xF0 ) >> 4 ); oldLayout[1][ curSln ] = oldLayout[1][ oldSln ] - b * ( sln[ cur[ curSln ] ] & 0xF ); oldLayout[2][ curSln ] = oldLayout[2][ oldSln ] + b * ( ( sln[ cur[ curSln ] ] & 0xF0 ) >> 4 ); oldLayout[3][ curSln ] = oldLayout[3][ oldSln ] + b * ( sln[ cur[ curSln ] ] & 0xF ); } bool BeRepeated( char b ) { for( unsigned long i = 0; i < curSln; i++ ) if( oldLayout[0][ curSln ] == oldLayout[0][ i ] && oldLayout[1][ curSln ] == oldLayout[1][ i ] && oldLayout[2][ curSln ] == oldLayout[2][ i ] && oldLayout[3][ curSln ] == oldLayout[3][ i ] && ( ( i & 1 ) ? 1 : -1 ) == b ) // 保證過河后的方案之間比較，回來后的方案之間比較 // i&1等效于i%2，i&7等效于i%8，i&63等效于id return true; return false; } void main() { char b = 1; oldLayout[0][0] = oldLayout[1][0] = 3; cur[0] = oldLayout[2][0] = oldLayout[3][0] = 0; for( unsigned char i = 0; i < 200; i++ ) // 初始化每次選擇方案時的初始化方案為sln[0] cur[ i ] = 0; // 由于cur是全局變量，在VC中，其已經被賦值為0 // 原因涉及到數據節，在此不表 do { DoSolution( b ); if( ( oldLayout[1][ curSln ] > oldLayout[0][ curSln ] && oldLayout[0][ curSln ] ) || ( oldLayout[3][ curSln ] > oldLayout[2][ curSln ] && oldLayout[2][ curSln ] ) || oldLayout[0][ curSln ] < 0 || oldLayout[1][ curSln ] < 0 || oldLayout[2][ curSln ] < 0 || oldLayout[3][ curSln ] < 0 || BeRepeated( b ) ) { // 重新選擇本次的方案 P: cur[ curSln ]++; if( cur[ curSln ] > 4 ) { b = -b; cur[ curSln ] = 0; curSln--; if( !curSln ) break; // 此題無解 goto P; // 重新檢查以保證cur[ curSln ]的有效性 } continue; } b = -b; curSln++; } while( !( oldLayout[0][ curSln - 1 ] == 0 && oldLayout[1][ curSln - 1 ] == 0 && oldLayout[2][ curSln - 1 ] == 3 && oldLayout[3][ curSln - 1 ] == 3 ) ); for( i = 0; i < curSln; i++ ) printf( "%d %d\t %d %d\n", oldLayout[0][ i ], oldLayout[1][ i ], oldLayout[2][ i ], oldLayout[3][ i ] ); } 上面數組sln[5]的初始化方式下篇介紹。上面的預編譯指令#include將在《C++從零開始（十）》中說明，這里可以不用管它。上面使用的函數printf的用法，請參考其它資料，這里它只是將變量的值輸出在屏幕上而已。 前面說此法是枚舉法，其基本上屬于萬能方法，依靠CPU的計算能力來實現，一般情況下程序員第一時間就會想到這樣的算法。它的缺點就是效率極其低下，大量的CPU資源都浪費在無謂的計算上，因此也是產生瓶頸的大多數原因。由于它的萬能，編程時很容易將思維陷在其中，如求和1到100，一般就寫成如下： for( unsigned long i = 1, s = 0; i <= 100; i++ ) s += i; 但更應該注意到還可unsigned long s = ( 1 + 100 ) * 100 / 2;，不要被枚舉的萬能占據了頭腦。 上面的人數布局映射成一結構是最好的，映射成char[4]所表現的語義不夠強，代碼可讀性較差。下篇說明結構，并展示類型的意義——如何解釋內存的值。 |
