每個問題的解決方案都始于一個計劃。這個計劃被稱為算法。編寫算法的方法有很多種。有些是非常非正式的,有些是相當正式的數學性質的,還有些是相當圖形化的。將 DVD 播放器連接到電視機的說明就是一種算法。πR2這樣的數學公式是算法的一種特例。只要能很好地描述和檢查計劃的邏輯,形式并不特別重要。
制定算法(計劃)是解決問題的關鍵一步。一旦有了算法,我們就可以用某種編程語言將其轉化為計算機程序。我們的算法開發過程包括五個主要步驟。
第 1 步:獲取問題描述。
這一步比表面看起來要困難得多。在下面的討論中,客戶指的是希望找到問題解決方案的人,而開發人員指的是找到解決問題方法的人。開發人員必須創建一種能夠解決客戶問題的算法。
客戶負責對問題進行描述,但這往往是整個過程中最薄弱的部分。問題描述通常存在以下一種或多種缺陷:(1) 描述依賴于未說明的假設,(2) 描述模棱兩可,(3) 描述不完整,或 (4) 描述存在內部矛盾。這些缺陷很少是由于客戶的粗心造成的。相反,它們是由于自然語言(英語、法語、韓語等)相當不精確這一事實造成的。開發人員的部分責任就是發現問題描述中的缺陷,并與客戶一起彌補這些缺陷。
第 2 步:分析問題。
這一步的目的是確定解決問題的起點和終點。這一過程類似于數學家確定什么是給定的,什么是必須證明的。良好的問題描述會讓這一步更容易完成。
在確定起點時,我們應首先尋求以下問題的答案:
有哪些可用數據?
數據在哪里?
哪些公式與問題有關?
處理數據有哪些規則?
數據值之間存在哪些關系?
在確定終點時,我們需要描述解決方案的特征。換句話說,我們如何知道何時完成?提出以下問題通常有助于確定終點。
我們將獲得哪些新事實?
哪些項目會發生變化?
對這些項目做了哪些修改?
哪些東西將不復存在?
第 3 步:制定高級算法。
算法是解決問題的計劃,但計劃有多個細節層次。通常情況下,最好從包含解決方案主要部分的高級算法開始,而將細節留到以后再處理。我們可以用一個日常的例子來演示高級算法。
問題:我需要給我弟弟馬克寄一張生日賀卡。
分析:我沒有賀卡:我沒有賀卡。我寧愿買一張賀卡,也不愿自己做一張。
高級算法:
去賣賀卡的商店
選擇賀卡
購買賀卡
郵寄賀卡
這種算法在日常使用中是令人滿意的,但它缺少一些細節,而這些細節必須由計算機來執行。這些細節包括以下問題的答案。
"我要去哪家商店?
"我將如何到達那里:步行、開車、騎自行車、乘公共汽車?
"馬克喜歡什么樣的卡片:幽默的、感傷的、俏皮的?"
我們在下一步流程中會考慮到這些細節。
第 4 步:通過添加更多細節來完善算法。
高級算法顯示了解決問題需要遵循的主要步驟。現在,我們需要為這些步驟添加細節,但我們應該添加多少細節呢?不幸的是,這個問題的答案取決于具體情況。我們必須考慮由誰(或由什么)來執行算法,以及這個人(或事)已經知道了多少該怎么做。如果有人要替我購買馬克的生日賀卡,我的指令就必須根據這個人是否熟悉社區里的商店以及購買者對我弟弟賀卡品味的了解程度來調整。
當我們的目標是開發能夠產生計算機程序的算法時,我們需要考慮計算機的能力,并提供足夠的細節,以便其他人能夠使用我們的算法,按照我們算法中的步驟編寫計算機程序。就像生日卡問題一樣,我們需要根據程序員的能力來調整詳細程度。當有疑問時,或者當你正在學習時,細節過多總比細節過少要好。
我們的大多數示例都會在一個步驟中從高級算法過渡到詳細算法,但這并不總是合理的。對于更大、更復雜的問題,我們通常會多次經歷這一過程,并在此過程中開發出中級算法。每一次,我們都會在前一個算法的基礎上增加更多細節,當我們發現進一步完善沒有好處時,就會停止。這種從高級算法逐步過渡到詳細算法的技術通常被稱為逐步細化算法。
第 5 步:審查算法。
最后一步是審查算法。我們在尋找什么?首先,我們需要逐步查看算法,以確定它是否解決了原始問題。一旦我們確信算法確實提供了解決方案,我們就開始尋找其他方面。以下問題是在審查算法時應該提出的典型問題。提出這些問題并尋找它們的答案是培養可應用于下一個問題的技能的好方法。
這個算法是否解決了一個非常具體的問題,還是解決了一個更一般的問題?如果它解決了一個非常具體的問題,是否應該泛化?
例如,一個計算半徑為5.2米的圓的面積的算法(公式π*5.22)解決了一個非常具體的問題,但計算任何圓的面積的算法(公式π*R2)解決了一個更一般的問題。
這個算法是否可以簡化?
計算矩形周長的一個公式是:
長度 + 寬度 + 長度 + 寬度
一個更簡單的公式可以是:
2.0 * (長度 + 寬度)
這個解決方案是否類似于另一個問題的解決方案?它們有什么相似之處?它們有什么不同之處?
例如,考慮以下兩個公式:
矩形面積 = 長 * 寬
三角形面積 = 0.5 * 底邊 * 高度
相似之處:它們都計算面積。它們都將兩個測量值相乘。
不同之處:使用了不同的測量值。三角形公式包含了0.5。
假設:也許每個面積公式都涉及將兩個測量值相乘。
如果你對此還有疑問,或者有更多關于學業輔導方面需求的話,可以添加微信號:hmkt131聯系海馬課堂的Joye老師哦。