計概二 (Ｂ班) 的「難題」 我不小心出了一個不太簡單的習題給數一Ｂ的計概二學生. 當助教找我問解答的時候, 還真的把我嚇了一跳. 一時之間, 我當時只能想出兩個很「暴力」的解法. 但是我 直覺應該有比較優美的解法, 所以當晚堅持作了一個半小時, 得到一個滿意的方法. 這個問題沒有「標準答案」, 只有比較快或比較慢的差別. 因為我發現這是一題難得的 值得花大腦的問題, 而且想試試數學系的新生, 讀了將近一年以後能不能接受這種挑戰. 所以我強迫他們重作這一題, 而且我自己批這一題的作業成績. 看得出來有一些用心 思考過的答案. 但是基本上還是屬於「暴力」的解法. 我覺得很遺憾來不及在課堂上討論這個題目. 現在成績已經送出去了, 忙碌中迫我自己 把一些相關的想法放在這裡. 等九月開學時, 希望你們讀到. 希望同學能藉這個例子, 體會一個「計算法」是如何生成的. 並體會, 數學的訓練, 可以幫助我們想出「比較好」 的計算法. By the way, 我喜歡沒有「標準答案」的問題. 這樣可以看出來一個學生對自己的 期許有多高. 首先, 重述題目: 依序列出只有 2 或 3 為因數的整數. 前幾項是 2 3 4 6 8 9 12 16 18 24 27 32 ... 注意, 有些人誤解題意而想得太簡單. 並非只要有 2 或 3 就好了. 例如 30 = 2 * 3 * 5 就不在考慮之列. 這個問題的困難在於「依序」二字. 以下我們稱這種 2^n * 3^m 的型式的整數為「二三數」. 第一種解法. 先把一大堆二三數算出來, 存在 array 裡面, 再 sort. 但是生成 二三數的順序不是二三數本身的順序. 最容易想到的是把二三數的指數 (n,m) 排序, 例如 (0,1) (1,0) (0,2) (1,1) (2,0) (0,3) (1,2) (2,1) (3,0) ... 再依此生成二三數 3 2 9 6 4 27 18 12 8 ... 這個想法的困難是, 若想要排出前 N 個二三數, 不知道要先造出多少個二三數才夠. 而且計算量頗大. 駱仁山提出一個改良的方法, 減少一些花在 sort 的時間. 我不清楚細節, 但我想 其基本想法仍是排序, 但是比較不「暴力」. 第二種解法. 依整數的順序, 2, 3, 4, 5, 6, ... 一個一個地測驗是否為二三數. 測驗的方法是: mod 2, 若餘零, 表示是 2 的倍數, 將其除 2 後以其商重複此一動, 一直重複作到不餘零為止; 然後把 2 換成 3 再重複作到不餘零為止; 看最後的商, 若是 1, 則表示此數只有2 或 3 為因數, 故驗得一個二三數, 將它存入一個 array. 其實我覺得這個想法比較數學. 但是計算量太大了. 在這個想法之下, 我看到幾個 漂亮的程式. 有一人用 recurrsion 處理上述的測驗, 另有人用 bitwise operation 處理上述對 2 的除法 (忘了他們是誰). 這個想法的最簡單的改善是, 先把 3 的次 方 3, 9, 27, 81 ... 放一邊, 則剩下的二三數必為偶數. 所以只有偶數須要被測驗. 如此測出來的二三數只須再和 3 的次方作一次比較即可排序. 我的第三種解法, 是基於對前面幾個二三數的觀察: 2 3 4 6 8 9 12 16 18 24 27 32 ... 我發現, 除了 3 的次方 (3, 9, 27 ...) 其它的數都是前面的二三數乘二造成的. 例如 2, 3 乘二造成 4, 6; 而 6, 8, 9 乘二造成 12, 16, 18. 但是 4, 6 乘二造成 8, 12, 中間缺了一個三的次方, 9. 所以我的算法是, 簡單地說, 把已經造成的 二三數依序乘二, 造成新的二三數; 而這些新數只要一次比較 (和三的次方比較) 就可以決定其位置. 以下是我的程式: #include main () { int ans[312], N=312, i, cmp=3, index=0, tmp; ans[0]=2; for (i=1; i cmp) { ans[i++] = cmp; ans[i] = tmp; cmp *= 3; } else ans[i] = tmp; ++index; } for (i=0; i= 1. 將 這三個數都除二, 可見和原假設矛盾. 若它倆之間有一個以上的三的次方數, 則 必定是 2^(n+1) * 3^m < 3^k < 3^(k+1) < ..., 但是 3^k 和 3^(k+1) 之間 必夾一個 2 * 3^k. 所以推得它倆之間有一個非三的次方的二三數. 已經證明了 這是不可能的. 再加上一些標準的歸納法語句, 你就可以證明這個算法的正確性.