結構化程式設計(17)

專案3-愛因斯坦階梯問題

阿爾伯特·愛因斯坦（1879－1955），猶太裔物理學家，諾貝爾物理獎獲得者。他創立了代表現代科學的相對論，並為核能開發奠定了理論基礎，開創了現代科學技術新紀元，被公認為是繼伽利略、牛頓以來最偉大的物理學家。

【問題】

有一次，愛因斯坦給他的朋友出了這樣一道有趣的數學題：有一條長長的階梯，如果每步跨2階，最後剩1階；每步跨3階，最後剩2階；每步跨5階，最後剩4階；每步跨6階，最後剩5階。只有每步跨7階時，才正好到頭，一階也不剩。請問這條階梯至少有多少階？請你編寫一個Scratch程序求解這個問題。

【問題分析】

階梯數n要同時滿足以下5個條件：

【演算法及程式設計】

我們採用窮舉法(枚舉法)來解決該問題。

1.我們用一個變數n來表示階梯數

2.利用Scratch運算積木表示滿足5個條件的積木程式

3.我們使用「重複執行」指令構建一個循環結構，在循環體內讓變數n的值不斷增加，並判斷n的值是否滿足上述5個條件。

由於階梯數是7的整數倍，因此我們調整一下，在循環體內讓變數n每次增加7，這樣就不需要判斷第5個條件了。如果變數n的值同時滿足前4個條件，那麼我們就求得這個問題的解。

完整的參考程式如下：

4.點擊綠旗，執行結果：這條階梯最少有119階。

【思考問題】

通過上面的程序我們已經求得這個問題的解，但是仍然有改進的空間。

回頭再仔細看愛因斯坦階梯問題，我們發現，階梯數依次除以2、3、5、6的餘數分別是1、2、4、5，能同時滿足這四個條件的最小階梯數是29，而2、3、5、6的最小公倍數是30，也就是說，階梯數是2、3、5、6的最小公倍數減去1，這樣才會出現餘數是1、2、4、5的現象。

根據這個發現，我們修改上述程序，讓變數n從29開始，每次遞增30。而要判斷的條件只有一個，就是判斷變數n是否是7的整數倍。

經過改進的程序更為簡潔，完整的參考程式如下：

點擊綠旗運行程序，得到結果：這條階梯最少有119階。

在本文中，我們心算就能求出2、3、5、6的最小公倍數是30，或者用筆算也能很快求出一般數的最小公倍數。但是如果遇到一些大數或很多個數的時候，用口算或筆算就不能很快算出最小公倍數了。這個時候，我們可以編寫程序，藉助計算機來幫助我們求最小公倍數。

通過解決愛因斯坦階梯問題，我們發現數學思維在編程中有著重要的作用，它能使我們的程序更加簡潔、更有效率。