[程式設計] UVa 13178 - Is it multiple of 3? 以及工程師心態
題目說明
Is it multiple of 3 是 UVa 上的題目，算是簡單題，但要求在 1 秒內得到結果。它的翻譯可以看一下 lucky 貓的說明。
乍看之下，這題蠻難的。
簡單來說，就是給一個數字，看看它是不是 3 的倍數。
這題難在於數字會很大，直覺看來，是不可能在 1 秒內得到結果。
我們先來看看這題數字的規則：
題目會給一個數字 n，然後你要湊出對應的數字 x，接著判斷 x 是不是 3 的倍數。
底下是範例
所以你可以推出來，當 n = 99 時，數字是有多大了 (如下圖囉)
 |
| n == 99 時，x 的值 |
暴力法解題
一開始沒有頭緒，所以先用暴力法試試看！拆出一個數中的所有數字，然後加起來，看是不是3的倍數。
例如
123456，那就拆成 1+2+3+4+5+6 ==> 21
因為 21 可以被 3 整除，所以123456 是 3 的倍數。
程式碼如下。第8到12行是最關鍵的部分，就是將每一個位數拆出來，並加總。
但前述的程式碼中的 x 是給定好的。
這當然不符合題目要求。題目要的，是給一個 n 產生一個 x。
所以我們可以稍微修改一下，先讀入一個 n，然後由 1 開始走訪到 n，產生 x。程式碼如下囉。
上面的程式碼中，第 7 - 16 行的部分，就是算 12345...n 的每一位數的加總。
如果 n 是 6，就會算 123456 的每一位數加總。
這基本上就算達到題目的要求了。
因為題目要求 n 小於等於 10 的 9 次方，所以我們就用這個極限值去測吧，測的結果會發現，要好久的時間。一定會超過一秒！
這表示題目中一定有什麼地方是我們沒有破解的。
尋找規律
那怎麼辦？就想法子找出這些數字有沒有存在什麼規律囉。寫程式方便就在這兒，我們就直接改程式碼，模擬 n = 1, 2,...,10 時，所有數字的結果。程式碼如下：
程式碼的輸出如下圖
 |
| n = 1,2,3,...,10 時的結果 |
看圖就知道，結果是一個 NO，YES，YES 的循環。
所以給一個 n，我們只要判斷 (n-1) % 3 有沒有等於 0，那就知道對應的 x 值是否為 3 的倍數了。
這一定是對的嗎？
看到這兒，一定有人會問，你確定這樣的判斷一定是對的嗎？
嗯，事實上，我們可以跑 n = 1,2,...,10^9試試看。會發現一直存在這樣的規律，所以致少在題目要求的數值範圍內，這個規律都是存在的。
心得
最後說說心得。
這題是可以透過嚴謹的證明，證出不管數字到多大，都會存在「NO, YES, YES」這樣的規律。我們只要使用
「在整數序列中，每隔 3 個數字，就會出現一個 3 個倍數！」
這樣的想法來證明！
但其實解題不是證明，我們沒有必要那麼「搞剛」。
記得之前在網路上看到一則「工程師 VS 科學家」的文章，裏面有一句話我蠻喜歡的：
「科學家求的是真理。工程師追求的是現實」。
這意思是說，我們工程師只要「覺得是對的」，即使我們不知道「背後的真理」，捲起袖子「硬幹」下去就對了。
事實上好多的發明都是在這樣的心態下產生的。舉例來說，燈泡就是在這樣的想法下產生的。
愛迪生當初可不是全盤理解了「碳化的竹絲」的所有化學特性，才把它用來當燈泡的發光材料的。他當初就是不斷地實驗，直接硬幹下去，才找到了這個材料。致於為什麼碳化的竹絲很適合當發光材料，它的物理，以及化學特性為何？我想愛迪生應該不會很關心才對。
而解題，這種工程師心態蠻受用的！
留言
張貼留言