【正文】 Gossip: 雙色、三色河內(nèi)塔說(shuō)明雙色河內(nèi)塔與三色河內(nèi)塔是由之前所介紹過(guò)的河內(nèi)塔規(guī)則衍生而來(lái)，雙色河內(nèi)塔的目的是將下圖左上的圓環(huán)位置經(jīng)移動(dòng)成為右下的圓環(huán)位置： 而三色河內(nèi)塔則是將下圖左上的圓環(huán)經(jīng)移動(dòng)成為右上的圓環(huán)：解法無(wú)論是雙色河內(nèi)塔或是三色河內(nèi)塔，其解法觀念與之前介紹過(guò)的河內(nèi)塔是類(lèi)似的，同樣也是使用遞回來(lái)解，不過(guò)這次遞回解法的目的不同，我們先來(lái)看只有兩個(gè)盤(pán)的情況，這很簡(jiǎn)單，只要將第一柱的黃色移動(dòng)至第二柱，而接下來(lái)第一柱的藍(lán)色移動(dòng)至第三柱。那么六個(gè)盤(pán)的情況呢？一樣！首先必須用遞回完成下圖左上至右下的移動(dòng)： 接下來(lái)最底層的就不用管它們了，因?yàn)樗鼈円呀?jīng)就定位，只要再處理第一柱上面的四個(gè)盤(pán)子就可以了，這又與之前只有四盤(pán)的情況相同，接下來(lái)您就知道該如何進(jìn)行解題了，無(wú)論是八個(gè)盤(pán)、十個(gè)盤(pán)以上等，都是用這個(gè)觀念來(lái)解題。雙色河內(nèi)塔 C 實(shí)作 include void hanoi(int disks, char source, char temp, char target) { if (disks == 1) { printf(move disk from %c to %c\n, source, target)。 } else { hanoi(disks1, source, target, temp)。 hanoi(disks1, temp, source, target)。A39。B39。C39。 for(i = disks / 2。 i) { hanoi(i1, source, temp, target)。 printf(move disk from %c to %c\n, source, temp)。 printf(move disk from %c to %c\n, temp, target)。 printf(move disk from %c to %c\n, source, target)。 printf(請(qǐng)輸入盤(pán)數(shù)：)。n)。 return 0。 printf(move disk from %c to %c\n, source, target)。 } else { hanoi(disks1, source, target, temp)。 hanoi(disks1, temp, source, target)。A39。B39。C39。 if(disks == 3) { printf(move disk from %c to %c\n, source, temp)。 printf(move disk from %c to %c\n, source, target)。 printf(move disk from %c to %c\n, temp, source)。 } else { hanoi(disks/31, source, temp, target)。 printf(move disk from %c to %c\n, source, temp)。 hanoi(disks/31, target, temp, source)。 printf(move disk from %c to %c\n, temp, target)。 hanoi(disks/31, source, target, temp)。 printf(move disk from %c to %c\n, target, source)。 printf(move disk from %c to %c\n, source, temp)。 i 0。 } printf(move disk from %c to %c\n,target, source)。 if (i1) { hanoi(i1, temp, source, target)。 } }}int main() { int n。 scanf(%d, amp。 hanoi3colors(n)。} Gossip: 背包問(wèn)題（Knapsack Problem）說(shuō)明假設(shè)有一個(gè)背包的負(fù)重最多可達(dá)8公斤，而希望在背包中裝入負(fù)重范圍內(nèi)可得之總價(jià)物品，假設(shè)是水果好了，水果的編號(hào)、單價(jià)與重量如下所示： 0 李子 4KG NT$4500 1 蘋(píng)果 5KG NT$5700 2 橘子 2KG NT$2250 3 草莓 1KG NT$1100 4 甜瓜 6KG NT$6700 解法背包問(wèn)題是關(guān)于最佳化的問(wèn)題，要解最佳化問(wèn)題可以使用「動(dòng)態(tài)規(guī)劃」（Dynamic programming），從空集合開(kāi)始，每增加一個(gè)元素就先求出該階段的最佳解，直到所有的元素加入至集合中，最后得到的就是最佳解。 逐步將水果放入背包中，并求該階段的最佳解：放入李子 背包負(fù)重 1 2 3 4 5 6 7 8 value ０ ０ ０ 4500 4500 4500 4500 9000 item － － － ０ ０ ０ ０ ０ 放入蘋(píng)果 背包負(fù)重 1 2 3 4 5 6 7 8 value ０ ０ ０ 4500 5700 5700 5700 9000 item － － － ０ 1 1 1 ０ 放入橘子 背包負(fù)重 1 2 3 4 5 6 7 8 value ０ 2250 2250 4500 5700 6750 7950 9000 item － 2 2 ０ 1 2 2 ０ 放入草莓 背包負(fù)重 1 2 3 4 5 6 7 8 value 1100 2250 3350 4500 5700 6800 7950 9050 item 3 2 3 ０ 1 3 2 3 放入甜瓜 背包負(fù)重 1 2 3 4 5 6 7 8 value 1100 2250 3350 4500 5700 6800 7950 9050 item 3 2 3 ０ 1 3 2 3 由最后一個(gè)表格，可以得知在背包負(fù)重8公斤時(shí)，最多可以裝入9050元的水果，而最后一個(gè)裝入的 水果是3號(hào)，也就是草莓，裝入了草莓，背包只能再放入7公斤（81）的水果，所以必須看背包負(fù)重7公斤時(shí)的最佳解，最后一個(gè)放入的是2號(hào)，也就 是橘子，現(xiàn)在背包剩下負(fù)重量5公斤（72），所以看負(fù)重5公斤的最佳解，最后放入的是1號(hào)，也就是蘋(píng)果，此時(shí)背包負(fù)重量剩下0公斤（55），無(wú)法 再放入水果，所以求出最佳解為放入草莓、橘子與蘋(píng)果，而總價(jià)為9050元。 int size。 }。 int main(void) { int item[LIMIT+1] = {0}。 int newvalue, i, s, p。 for(i = 0。 i++) { for(s = a[i].size。 s++) { p = s a[i].size。 if(newvalue value[s]) {// 找到階段最佳解 value[s] = newvalue。 } } } printf(物品\t價(jià)格\n)。 i = MIN。 } printf(合計(jì)\t%d\n, value[LIMIT])。 } Java class Fruit { private String name。 private int price。 = size。 } public String getName() { return name。 } public int getSize() { return size。 final int MIN = 1。 int[] value = new int[MAX+1]。 for(int i = 0。 i++) { for(int s = fruits[i].getSize()。 s++) { int p = s fruits[i].getSize()。 if(newvalue value[s]) {// 找到階段最佳解 value[s] = newvalue。 } } } (物品\t價(jià)格)。 i = MIN。 } (合計(jì)\t + value[MAX])。蒙地卡羅的基本原理為以亂數(shù)配合面積公式來(lái)進(jìn)行解題，這種以機(jī)率來(lái)解題的方式帶有賭博的意味，雖然在精確度上有所疑慮，但其解題的思考方向卻是個(gè)值得學(xué)習(xí)的方式。至于如何判斷所產(chǎn)生的點(diǎn)落于圓內(nèi)，很簡(jiǎn)單，令亂數(shù)產(chǎn)生X與Y兩個(gè)數(shù)值，如果X^2+Y^2等于1就是落在圓內(nèi)。 double x, y。 for(i = 1。 i++) { x = (double) rand() / RAND_MAX。 if((x * x + y * y) 1) sum++。 return 0。解法首先知道這個(gè)問(wèn)題可以使用回圈來(lái)求解，將一個(gè)指定的數(shù)除以所有小于它的數(shù)，若可以整除就不是質(zhì)數(shù)，然而如何減少回圈的檢查次數(shù)？如何求出小于N的所有質(zhì)數(shù)？首先假設(shè)要檢查的數(shù)是N好了，則事實(shí)上只要檢查至N的開(kāi)根號(hào)就可以了，道理很簡(jiǎn)單，假設(shè)A*B = N，如果A大于N的開(kāi)根號(hào)，則事實(shí)上在小于A之前的檢查就可以先檢查到B這個(gè)數(shù)可以整除N。再來(lái)假設(shè)有一個(gè)篩子存放1～N，例如：2　3　4　5　6　7　8　9　10　11　12　13　14　15　16　17　18　19　20　21 ........ N先將2的倍數(shù)篩去：2　3　5　7　9　11　13　15　17　19　21 ........ N再將3的倍數(shù)篩去：2　3　5　7　11　13　17　19　........ N再來(lái)將5的倍數(shù)篩去，再來(lái)將7的質(zhì)數(shù)篩去，再來(lái)將11的倍數(shù)篩去........，如此進(jìn)行到最后留下的數(shù)就都是質(zhì)數(shù)，這就是Eratosthenes篩選方法（Eratosthenes Sieve Method）。 實(shí)作 C include include define N 1000 int main(void) { int i, j。 for(i = 2。 i++) prime[i] = 1。 i*i = N。 j = N。 } } } for(i = 2。 i++) { if(prime[i] == 1) { printf(%4d , i)。 } } printf(\n)。 }  Gossip: 超長(zhǎng)整數(shù)運(yùn)算（大數(shù)運(yùn)算）說(shuō)明基于記憶體的有效運(yùn)用，程式語(yǔ)言中規(guī)定了各種不同的資料型態(tài)，也因此變數(shù)所可以表達(dá)的最大整數(shù)受到限制，例如123456789123456789這樣的 整數(shù)就不可能儲(chǔ)存在long變數(shù)中（例如C/C++等），我們稱(chēng)這為long數(shù)，這邊翻為超長(zhǎng)整數(shù)（避免與資料型態(tài)的長(zhǎng)整數(shù)翻譯混淆），或俗稱(chēng)大數(shù)運(yùn)算。由于使用陣列來(lái)儲(chǔ)存數(shù)值，關(guān)于數(shù)值在運(yùn)算時(shí)的加減乘除等各種運(yùn)算、位數(shù)的進(jìn)位或借位就必須自行定義，加、減、乘都是由低位數(shù)開(kāi)始運(yùn)算，而除法則是由高位數(shù)開(kāi)始運(yùn)算，這邊直接提供加減乘除運(yùn)算的函式供作參考，以下的N為陣列長(zhǎng)度。 for(i = N 1。 i) { c[i] = a[i] + b[i] + carry。 else { // 進(jìn)位 c[i] = c[i] 10000。 } } } void sub(int *a, int *b, int *c) { int i, borrow = 0。 i =