1.1 解決問題

解決問題的方法有很多種。在本章，我們首先要研究的是一個3步走策略，即分析、設計、實現策略。

接下來，我們將通過一個“計算課程成績”的示例來逐一示范這個3步走策略中的各個步驟，看看它們在解決問題過程中所發揮的作用，并以此開始這門課程的學習。

1.1.1 分析（提問、考察、研究）

程序的開發通常始于針對某個問題的研究或分析。這是很顯然的，如果我們想要確定一個程序要執行哪些操作，當然先得理解該程序要解決的問題。如果該問題已經完成了書面化描述，我們就可以從閱讀這個問題開始進入分析步驟了。

在分析一個問題的過程中，做好對程序所需信息數據的命名工作會是很有幫助的。例如，我們可能會被要求計算出特定飛機在特定氣象條件（比如溫度、風向等）下，在指定機場跑道上可以成功起飛時的最大重量。這時，我們就可以在分析問題時將這項要計算的信息命名為maximumWeight，并將計算該信息所需的信息命名為temperature、windDirection等。

雖然這些數據并不代表整個解決方案，但是它們的確表述了問題的某個重要部分。這些數據名稱會是我們編寫程序以及在程序中進行計算工作時要用到的符號，比如可能我們要計算的是飛機在temperature的值為19.0時的maximumWeight?？偠灾@些數據通常都要經過各種形式的操作或處理之后，才能得到我們所期待的結果。在這其中，有些數據得從用戶那里獲取，也有些數據得經過一些相乘或相加的運算，還有些數據得在計算機屏幕上顯示。

在某些時候，這些數據的值會被存儲在計算機的內存中。當程序運行時，相同內存位置上的值是會變化的。另外，這些數據值通常都會有一個類型，比如整數類型、浮點數類型、字符串類型或其他各種存儲類型。對于這種用于在程序運行時存儲這些可變值的內存區塊，我們稱之為變量。

我們將會看到這些數據值施以某種特定行為意義的操作，這些特定的意義有助于我們將數據區分成由計算機顯示的數據（輸出），和計算出結果所需的數據（輸入）。這些變量幫我們總結出了一個程序必須得做的事情。

● 輸入：用戶在解決問題過程中必須提供的信息。

● 輸出：計算機必須顯示的信息。

通常情況下，我們都可以通過回答“給定輸入能得到什么輸出？”這個題目來更好地理解自己要解決的問題。因此，針對待解決的問題來進行舉例往往是一個不錯的思路。下面就是兩個通過變量名的選擇來精準描述其存儲值的問題：

現在來總結一下，我們在分析問題過程中需要：

1．閱讀并理解待解決問題的書面說明。

2．定義用來表示問題答案的數據，以作為輸出。

3．定義用戶為獲取問題答案必須要鍵入的數據，以作為輸入。

4．創建一些問題樣例，以作匯總之用（就像上面做的那樣）。

當然，教材中的問題有時會提供清楚的變量名，以及輸入/輸出時用到的值類型（比如字符串、整數、浮點數等）。如果沒有的話，它們識別起來也往往是相對比較容易的。但在現實中，對于相當規模的問題來說，分析問題這個步驟通常是需要花費大量精力的。

自測題

1-1．請基于英鎊與美元之間的匯率轉換問題，分別為用來存儲用戶輸入值以及程序輸出值的變量賦予有意義的命名。

1-2．針對“從擁有200張CD的播放器中選取一張CD來播放”這個問題，請分別設定用來表示所有CD以及表示用戶所選擇的那張CD的變量名。

問題分析示例

問題：請根據右側的課程成績估算表，用作業項目、期中考試和期末考試這三項的加權值計算出這一門課的成績。

如前所述，問題分析的工作要從理解問題的書面描述開始，然后確定解決該問題所需要的輸入和輸出。在這里，先定義并命名輸出的內容是一個不錯的切入點。因為，輸出內容中通常存儲的就是這個待解決問題的答案，它會驅使我們去深入理解這個待解決的問題。

一旦我們定義好了解決問題所需的數據，并賦予它們有意義的變量名之后，就可以將注意力轉向如何完成任務了。就這個特定的問題而言，它要輸出應該就是實際的課程成績，我們將這個要輸出給用戶的信息命名為courseGrade。然后為了讓這個問題更具有通用性，我們要讓用戶自己輸入產生計算結果所需的值。畢竟如果這個程序可以要求用戶提供所需的數據，那么它以后就可以用來計算多名學生任何一門課程的成績了。在這里，我們將需要用戶輸入的這些數據命名為projects、midterm和finalExam。這樣一來，我們目前就已經完成了問題分析這一步驟中的前3個動作：

1．理解待解決的問題。

2．定義要輸出的信息：courseGrade。

3．定義要輸入的數據：projects、midterm和finalExam。

接下來需要有一個問題樣例，它有助于我們創建一個測試用例（test case），以驗證輸入的數據和程序產生的輸出結果。例如，當projects為74.0、midterm為79.0、finalExam為84.0時，其平均加權值應該為78.0：

        (0.50 × projects) + (0.20 × midterm) + (0.30 × finalExam)
          (0.5 × 74.0)    +    (0.2 × 79.0)    +  (0.30 × 84.0)
              37.0          +       15.8          +       25.2
                                78.0

到這里，問題的分析步驟就算完成了，我們確定了用于輸入/輸出的變量，這有助于我們了解計算機解決方案需要做哪些事，同時還獲得了一個現成的測試用例。

自測題

1-3．請完成對下面問題的分析，這里你可能會需要用到一個準確的計算器。

問題：請基于某項投資的當前價值、投資期限（可能以年為單位）以及投資利率，估算出它的未來價值。在這里，投資利率和投資期限是步調一致的。也就是說，如果投資期限以年為單位，那么這里的投資利率就是年利率（例如8.5%，就是0.085）；如果投資期限以月為單位，那么這里的投資利率就是月利率（例如，如果年利率是9%，那么月利率就是0.075）。其未來價值的計算公式如下：

future value = present value * (1 + rate)periods

1.1.2 設計（模型、思考、計劃、策劃、模式、綱要）

設計這個概念背后所代表的是一系列動作，這其中包括為程序中的每個組件安排具有針對性的算法。而算法則是指我們在解決問題或達成某項目標的過程中所要完成的逐個步驟。一個好的算法必須要：

● 列出程序所要執行的動作。

● 按照恰當的順序列出這些動作。

事實上，我們可以將烤制胡蘿卜蛋糕的過程看成是一個算法：

● 將烤箱預熱至350°F（約180℃）。

● 將每個烤箱模具的側面和底部抹上油。

● 將食材放到一大碗里進行攪拌。

● 將攪拌物倒入每個烤箱模具中，并立即放入烤箱烤制。對于紙杯蛋糕，倒至2/3滿即可。

● 根據相關圖表來進行烤制。

● 將牙簽插入到蛋糕中心，拔出來后依然能干凈就表示蛋糕烤制成功。

如果這些步驟的順序被改變了，廚師可能得到的就是一個滾燙的烤箱模具，里面放了一團雞蛋與面粉的攪拌物。如果省去了其中的某一個步驟，那么廚師也不會烤成蛋糕，或許他只是點了一次火而已。當然，熟練的廚師通常是不需要這種算法的。但是，蛋糕制作原料的銷售商可不能，也不該假設他們的客戶都很熟練。總之，好的算法必須要按照恰當的順序列出恰當的步驟，并且要詳盡到足以完成任務。

自測題

1-4．烤制蛋糕的食譜通常會省略一個非常重要的動作，請指出上述算法中缺少的是什么動作。

通常情況下，算法中所包含的都是一些不涉及太多細節的步驟。例如，“在大碗中攪拌”并不是一個非常具體的動作描述，里面的食材配比是什么呢？如果我們現在的問題是要編寫一個人類能夠理解的蛋糕烤制算法，這個步驟就可以做進一步的改進，使其能指導廚師更好地安排食材配比。比如我們可以將該步驟改成“將牛奶倒入盛有雞蛋與面粉的大碗中攪拌，直至其表面光滑”，或者為面包師將該步驟切分如下：

● 配置好食材中干燥的成分；

● 將食材的液體成分倒入碗中；

● 每次倒入四分之一杯的干成分，將其攪拌至表面光滑。

算法可以用偽代碼來描述，甚至也可以用一種非程序員也能理解的語言來描述。由于偽代碼面向的是人類，而不是計算機，因此用偽代碼描述的算法在程序設計中是很有幫助的。

偽代碼有極強的表達能力。一條偽代碼通常可以表示多條計算機指令。另外，用偽代碼來描述算法可以避免糾纏于標點錯誤或者與特定計算機系統相關的細節。用偽代碼來描述解決方案允許我們將這些細節問題向后推，這可以讓設計變得更容易一些。其實，寫算法就相當于在做計劃，程序開發者也可以用紙和筆來做這些設計，甚至有時可以直接在腦海中完成這些事。

1.1.3 算法模式

解決問題通常需要用戶完成一定的輸入才能計算并顯示出相應的信息。事實上，這種輸入-處理-輸出的動作流是如此的司空見慣，我們甚至可以把它視為一種模式，而且你們會發現這絕對是程序設計中最有用的幾個算法模式之一。

模式可以是任何一種事物形式或設計，它的作用是將某些事物模型化或者提供某種行事指南。而算法模式就是一種用于輔助我們解決問題的指南。以下面的輸入/處理/輸出（Input/Process/Output，IPO）算法模式為例，我們可以用它來輔助解決第一個問題的設計，事實上，IPO模式可以輔助我們解決本書前5章中幾乎所有程序的設計問題。

代碼示例如下：

        int n1, n2, n3;
        float average;

        // Input
        cout << "Enter three numbers: ";
        cin >> n1 >> n2 >> n3;

        // Process
        average = (n1 + n2 + n3) / 3.0;

        // Output
        cout << "Average = " << average;

這是若干種算法模式中的第一種。在后面的章節中，我們會陸續看到Guarded Action、Alternative Action、Indeterminate Loop等其他算法模式。為了有效地使用一個算法模式，我們首先必須得熟記它。將IPO模式注冊在心中，并在開發程序時能想起它，這樣就會讓我們的程序設計變得更容易。例如，如果你在數據中發現了無意義的值，有可能是你將程序的處理步驟放在了輸入步驟之前，或者根本就跳過了輸入步驟。

關于模式在解決其他類型問題時所能提供的幫助，我們可以參考Christopher Alexander在A Pattern Language[Alexander 77]這本書里的一段話：

每個模式描述的都是一個我們所在客觀環境中反復出現的問題，及其解決方案的核心內容，通過這種方式構建的解決方案，可以讓我們用上一百萬次，無須用相同的方式構建兩次解決方案。

盡管Alexander所描述的是用于設計家具、花園、大樓和城鎮的模式，但他描述的模式也適用于計算領域問題的解決。在程序設計的過程中，IPO模式就是會反復出現，并指引著許多問題的解決方案。

1.1.4 算法設計示例

IPO模式也可以用來指導我們解決之前那個課程成績計算問題的算法設計：

當然了，算法的開發通常是一個迭代的過程，模式也只是提供了解決這個問題所必需的動作序列綱要。

自測題

1-5．在閱讀上述算法的3個動作時，你發現其中缺失的動作了嗎？

1-6．在閱讀上述算法的3個動作時，你發現其中有什么不正常的動作嗎？

1-7．如果對調上述算法中前兩個動作的順序，該算法還能正常工作嗎？

1-8．上述算法的描述是否已經足夠支持計算出courseGrade的值了？

很顯然，我們在上面對計算課程成績問題的處理步驟的描述是不夠詳細的，我們還需對它進行進一步的細化。具體來說就是，說清楚在處理過程中如何用輸入數據計算出課程成績。上面的算法中省略了我們在問題書面化描述中提到的加權值，所以我們在第二步中重新細化了處理步驟：

1．從用戶那里獲取projects、midterm、finalExam這3個數據值。

2．計算courseGrade = (projects × 50%) + (midterm × 20%) + (finalExam × 30%)。

3．顯示courseGrade的值。

就像人們常說的那樣，好的藝術家應該知道什么時候該放下畫筆，并決定與此刻完成他的畫作，這對他的成功是至關重要的。同樣地，設計師也必須要知道什么時候該停止設計，那就是我們進入解決問題第三階段——實現階段的好時機。

現在，我們來總結一下到目前為止所取得的進展：

● 待解決的問題得到了充分的理解。

● 所要用到的變量得到了確認。

● 對已知問題樣例的輸出有了了解（78.0%）。

● 已經開發出了一種算法。

1.1.5 實現（完成、操作、使用）

計算機本質上就是一種可編程的、用來存儲、檢索并處理數據的電子設備。事實上，程序員們也可以通過紙和筆來手動執行存儲、檢索與處理數據的動作，以此來模擬算法在電子設備中的執行過程。下面就是一個人工模擬的（非電子的）算法執行過程：

1．從用戶那里檢索到一些示例值并將它們存儲起來：

            projects = 80
            midterm = 90
            finalExam = 100

2．再次檢索這些值并用它們計算出courseGrade的值：

            courseGrade = (0.5 × projects) + (0.2 × midterm) + (0.3 × finalExam)
                            (0.5 × 80.0)    +    (0.2 × 90.0)  +  (0.3 × 100.0)
                                40.0       +       18.0         +      30.0
                                      courseGrade = 88.0

3．將存儲在courseGrade中的值顯示成88%。

1.1.6 一段C++程序

下面，我們要帶你預覽一段完整的C++程序，由于對這里的許多編程語言上的細節問題，我們要到下一章中才會介紹，因此各位也不必期待自己能完全理解這段C++源代碼。在此次此刻，我們只需要讀懂這段源代碼是對之前那個偽代碼算法的實現就可以了。這里有projects、midterm、finalExam三個變量，代表的是用戶的輸入。另外，還有一個名為courseGrade的輸出變量。這里的cout對象，發音是“see-out”，代表的是公共輸出以及程序所產生的輸出。輸入部分用的則是cin對象，發音是“see-in”，代表的是公共輸入。

        /*
         * This program computes and displays a final course grade as a
         * weighted average after the user enters the appropriate input.
         *
         * File name: CourseGrade.cpp
         */
        #include <iostream>    // for cin and cout
        #include <string>      // for string
        using namespace std;  // avoid writing std::cin std::cout std::string

        int main() {
          // Explain what this program does.
          cout << "This program computes a weighted course grade." << endl;

          // Read in a string
          cout << "Enter the student's name: ";
          string name;
          cin >> name;
          // I)nput projects, midterm, and finalExam
          double projects, midterm, finalExam;

          cout << "Enter project score: ";
          cin >> projects;

          cout << "Enter midterm: ";
          cin >> midterm;

          cout << "Enter final exam: ";
          cin >> finalExam;

          // P)rocess
          double courseGrade = (0.5 * projects) +
                              (0.2 * midterm) +
                              (0.3 * finalExam);

          // O)utput the results
          cout << name << "'s grade: " << courseGrade << "%" << endl;
        }

程序會話

下面是該程序計算一次加權課程成績的過程：

        Enter the student's name: Dakota
        Enter project score: 80
        Enter midterm: 90
        Enter final exam: 100
        Dakota's grade: 88%

1.1.7 測試

測試這個重要的過程，可能，可以，并且也應該出現在我們解決問題的所有階段中。這部分的實際工作量很小，但很值得做。只不過，在因為不做測試而遇到問題之前，你可能不會同意我這個觀點?？偠灾瑴y試相關的系列動作可以出現在程序開發的所有階段中：

● 在分析階段中，我們可以通過測試用例確認自己對待解決問題的理解。

● 在設計階段中，我們可以通過測試算法來確定其按照恰當的順序執行了恰當的步驟。

● 在測試過程中，我們可以用幾組不同的輸入數據來運行程序，確認其結果是否正確。

● 請復查待解決問題的書面描述，確認我們運行的程序的確執行了需要執行的操作。

我們應該在針對問題編寫程序之前（而不是之后）準備一個以上的測試用例，然后確定一下程序的輸入值與預估輸出值。比如，之前我們提到的輸入值為80、90和100時，預估輸出值是88%的情況，就屬于這樣的測試用例。當程序最終產生它的輸出時，我們可以拿自己預估的結果與程序實際運行中的輸出進行比對，如果預期輸出與程序輸出對不上，我們就要及時做出相關的調整，因為這種沖突表示該問題示例或程序輸出有錯，甚至有可能是兩者都錯了。

通過若干個測試用例的測試，我們可以有效地避免誤認為只要程序能成功運行并產生輸出，程序就是正確的。顯然，輸出本身也可能會出錯！簡單執行一下程序是無法確保程序正確的。測試用例的作用是確保程序的可行性。

然而，即使進行了詳盡的測試，我們其實也未必能完全保證程序的正確性。E. W. Dijkstra就曾認為：測試只能證明程序中存在錯誤，無法證明其中不存在錯誤。畢竟，即使程序的輸出是正確的，該程序本身也未必就一定正確。但測試還是有助于減少錯誤，并提高程序的可信度。

自測題

1-9．如果程序員預估當上述程序的3個輸入都為100.0時，courseGrade的值也應為100.0，但程序顯示的courseGrade的值卻為75.0，請問是預估輸出和程序輸出中的哪一方出錯了？還是雙方都錯了？

1-10．如果程序員預估當上述程序的輸入projects為80.0、midterm為90.0、finalExam為100.0時，courseGrade的值應為90.0，但程序顯示的courseGrade的值卻為88.0，請問是預估輸出和程序輸出中的哪一方出錯了？還是雙方都錯了？

1-11．如果程序員預估當上述程序的輸入projects為80.0、midterm為90.0、finalExam為100.0時，courseGrade的值應為88.0，但程序顯示的courseGrade的值卻為90.0，請問是預估輸出和程序輸出中的哪一方出錯了？還是雙方都錯了？