緣起:

大概 12 月初吧，我聽我同學說，我們系上的大一生，好像惹怒了基礎程設的老師 (葉老師)，所以老師就把期中考的題目出很難，結果似乎一片慘，之後大一生他們的班導就希望能加強他們的程式能力，所以請我那位同學每個禮拜一的時候在 407 教室開個類似讀書會的活動，跟他們分享寫程式的技巧，讓有志於提升自己程式能力的大一生來一起學習。

那位同學有找我來幫忙做教學 (當志工)，做關於他們期中考與每個禮拜 python 題目的詳解，我覺得很有趣，而且也想教別人東西，所以就答應了。

上個禮拜一，我第一次教學，雖然先前有把那些題目都寫好，不過因為沒做好教學的準備，所以教得零零落落的，尤其是最後一個題目，當下完全不知該怎麼跟他們解釋我的想法，所以就只能跟他們說，這題就留到下次再講。

我覺得他們期中考的題目裡，比較有挑戰性的題目就算它了，所以就想說，為這個題目寫個教學好了，寫完之後也能拿去教他們。

題目:

簡單來說，他給你一個 1000 位長的數字，要你求最大的 n 個相鄰的位數相乘的值。他給你

7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450

這樣長的一串 1000 位長的數字，如果他給你的輸入值是 4，那麼答案會是 5832，因為在這 1000 位數裡，有 4 個相鄰的數字 9、9、8、9 (你可以用 Ctrl +f 搜尋 9989 在哪)，相乘出來的數字會是最大的。對於使用者輸入的一個整數 n ( n <= 1000 吧 ?)，我們都要能找出在那 1000 位裡 n 個相鄰的位數相乘的最大值。

最直觀的解法:

ㄟ...，沒錯，其實寫這樣就對了，暴力破解法，直接用兩個 for 迴圈，外層的控制起始點，內層的迴圈計算從起始點到後 N-1 位數字的相乘值，用 product 計錄乘出來的結果。那個 1000 位的數字我們把它當字串做記錄，方便直接用陣列索引的方式直接取某位的值，要記得用 int() 來把字串轉成數字。我們還用一個叫 max 的變數記錄最終的結果，初始值設 0 ，在外層的 for 迴圈的最後判斷，如果 product 的結果有比 max 還大，那我們就用 product 的值取代 max 的值，這樣一值做到結束，max 的值就會是所有成積裡最大的一個，答案就出來了。

暴力破解法雖然簡單，但也有一個問題，雖然在這題目上可能看不太出來，那就是很耗時。我們在這裡再多加一個變數，每次 for 迴圈執行一次時我們就給它加一，最後再把它給輸出，看看會有什麼結果。

加上這幾行

輸入為 4 的結果

輸入為 5 的結果

輸入為 13 的結果

可以看到，我們輸入的數字每增加 1，count 的次數大概就會增加 1000，看起來好像還好，但如果我們的那個數字是 10000000 位的數字，那麼我們輸入的數字每增加 1 ，for 迴圈會做的次數就大概會增加 10000000 次，這可不是個小數字。就算你的電腦每秒可以跑 10000000 次 for 迴圈，當我們輸入的數字給你增加個 1000，你不就要再多等約 1000 秒才能得到答案了嗎 ? 可見這題其實還有比暴力破解更好的解法。