基礎編程的思考方法

2018-04-23 09:13:08焦華

軟件 2018年3期

焦華

（貴州商學院，貴州貴陽 550014）

0 引言

傳說著名的瑞士計算機科學家尼克拉斯·沃思（Nicklaus Wirth）是憑借一句話獲得圖靈獎的，這句話就是眾所周知的著名公式：“算法+數據結構=程序”，即程序包含了對數據的描述和對操作的描述兩個方面——計算機的操作對象和操作步驟。[1]比如已知三角形的三個邊a、b、c，用海倫公式求三角形的面積。數據的描述是a、b、c、p、s；算法的簡單描述如下（為簡單起見，這里假定輸入的a、b、c滿足兩邊之和大于第三邊）：

Wirth公式對計算機科學的影響程度類似于物理學中愛因斯坦的質能方程“E=MC2”——一個公式揭示了程序的本質。事實上這個公式是 Wirth在1976年寫的一本名著的書名——《Algorithms +Data Structures = Programs》。Wirth被譽為 PASCAL之父，同時也是好幾種編程語言的主設計師，結構化程序設計的思想方法也是Wirth在上世紀70年代提出的。“頂層設計→逐步求精→模塊實現”在當時的程序設計領域引發了一場革命，具有里程碑的意義，完全改變了人們對編程的思維方式。世界的復雜性與人類思維的局限性使得結構化編程方法是解決這一矛盾的有力工具！擴展的Wirth公式是：“算法+數據結構+結構化程序設計方法+語言工具=結構化程序”。因此 1984年獲得的圖靈獎是對 Wirth一系列重大貢獻的回報[2]。

應當說Wirth公式貫穿了過程化程序設計始終，可以將所有的知識點都串起來。比如C語言程序設計包含的內容有：程序設計及C語言、算法——程序的靈魂、順序結構程序設計、分支結構程序設計、循環結構程序設計、用函數實現模塊化程序設計、利用數組處理批量數據、善于利用指針、結構體與共用體、對文件的輸入輸出?？梢钥闯?，這些內容都包含于擴展的Wirth公式中。

未來有眾多的不確定性但不容置疑的是大數據時代已經到來，大數據的世界是程序的世

界！Wirth公式指出，算法是程序的靈魂，從而大數據的世界就是算法的世界！因此有必要對基礎編程的核心——Wirth公式蘊含的思想加以梳理，相關概念和內容進行再認識。

1 W irth公式中相關概念的重述與再認識

計算機有硬件與軟件之分，軟件是程序和程序文檔的總稱，計算機的本質是“執行程序的機器”。由于 Wirth公式揭示了程序的本質，在此重溫其相關術語和內容[3]。

算法（Algorithm）通俗地講，是解決問題的方法與步驟；在數學中，算法通常是指遵照一定的規則解決某一類問題明確的且有效的步驟；在計算機科學中，算法是指解題方案的既準確又完整的描述，是一系列清晰指令的有限序列。算法應當具備正確性、有窮性、可讀性、健壯性、人機交互性等特征。

數據（Data）是客觀事物的符號表示，計算機科學里是指能輸入至計算機且被計算機程序加工處理的符號的總稱。

數據元素（Data Element）是數據的基本單位，計算機程序通常將它作為一個整體加以處理和考慮。

數據結構（Data Structure）是指數據元素自身特征以及它們之間的相互關系（結構）。它有四類基本結構：集合、線性結構、樹型結構、圖或網狀結構。

數據類型（Data Type）是與數據結構密切有關的概念，最先出現在計算機高級語言中，用來刻畫程序操作對象的特性。它是一個值的集合以及定義在該值集上一組操作的總稱。

算法與數據結構的關系：算法依賴于具體的數據結構，數據結構關系到算法的選擇與效益。因此很多時候是先確定數據結構，再確定算法。

程序（Program）是一組計算機能識別和執行的指令序列。編寫程序的人稱為程序員，編寫程序的活動或過程稱為程序設計。

類比實例 1：一盤已做好的美味菜肴比作一個程序，菜譜中需要的食材、佐料相當于數據結構，菜譜中的操作流程相當于算法，廚師相當于程序員，烹飪的過程相當于程序設計。

類比實例 2：一座已建好的雄偉建筑比作一個程序，建筑中需要的鋼筋、水泥、磚瓦等建材相當于數據結構，動工之前的建筑物設計圖相當于算法，設計師及建筑工人相當于程序員，從動工到完工驗收的過程相當于程序設計。

在擴展的Wirth公式中，如果將“數據結構+語言工具”比作人體的組織、器官，那么“算法+結構化程序設計方法”則是人的思想、靈魂。你可以用你的思想去支配你身體的各器官隨意運動。深入下去就是哲學中物質與意識的關系。

2 用流程圖表示算法

程序的概念從“指令序列”轉到“算法+數據結構”，兩者并不矛盾，而是為解決問題必經的具體化歷程。比如線性方程組的求解要用到初等行變換算法；而職工工資收入的高低排列要用到排序算法。算法的表示就是解決具體問題的思路描述[4]。

算法的表示（描述）方法有：自然語言、流程圖、N—S結構圖、PAD問題分析圖、偽代碼、計算機語言等。實際上用計算機語言表示算法就已經是源程序了。

最早描述算法應當是自然語言，雖然這種方式通俗易懂但容易出現歧義，且描述分支和循環極不方便，于是人們發明了流程圖。這是用一些圖框來表示各種操作，圖形表示的算法既直觀形象又易于理解。

實例1：判定2000——2500年中每一個年份是否是閏年，并將結果輸出。

算法的流程圖如下：

一級算法：

圖1 判定閏年的一級算法流程圖[5]Fig.1 Flow chart of first order algorithm for judging leap year

二級求精：

圖2 判定閏年的細化流程圖Fig.2 A thinning flow chart for judging leap year

其實二級求精流程圖可以簡化、不需要分支嵌套，故意復雜化是編程訓練的需要。

實例 2：歐幾里德算法又稱輾轉相除法，用于計算兩個正整數a，b的最大公約數。

歐幾里得算法的流程圖如下[6]：

3 程序（流程）的三種基本結構

在傳統的流程圖中是用流程線來指明各框的執行順序，對流程線的使用無限制，于是亂麻一樣的“面條算法”出現了。為解決這一問題，Bohra和Jacopini在1966年提出了三種基本結構——順序結構、選擇結構、循環結構，用這三種基本結構作為基本單元去搭建的算法稱為結構化算法?？梢宰C明無論多么復雜的流程都可以用三種基本結構排列、組合、嵌套得到（所有非結構化算法可轉化為結構化算法）。色彩學上的三色理論，是指紅、綠、藍這三種顏色相互獨立，但自然界的任何色彩都可以由三種顏色按不同的比例混合而成。順序結構、選擇結構、循環結構相互獨立，雖然人類開發的程序千千萬萬，但任何程序都可用這三種基本結構搭建得到，如同俄羅斯方塊游戲中用七種不同形狀的構件去搭建城墻一樣[7]。

圖3 歐幾里德算法流程圖Fig.3 Flow chart of euclid algorithm

順序結構強調流程的次序，先做什么后做什么很重要，次序不能顛倒。比如一個大學生早晨起床后要做的事：穿衣→洗臉刷牙→整理書包→食堂吃飯→教室上課。如果次序改變為：洗臉刷牙→穿衣→食堂吃飯→回宿舍整理書包→教室上課。這將是糟糕的順序。自然與社會中的時間次序、空間次序、事件次序可以舉出很多例子。

選擇結構也稱為分支結構，在多種選擇（分支）中只能取一種，如同在多岔路口你只能走其中的一條?！斑x擇比努力更重要”表達的就是一旦選定將無法更改，這世界從來沒有“后悔藥”，“機會”錯過就不再有了。

循環結構也稱為重復結構，是指反復執行某一部分操作。循環是天體宇宙的法則。地球每天都在孤獨地旋轉：自轉一圈24小時，形成白天黑夜的交替；公轉一圈365天，形成春夏秋冬的輪回。生活在地球上的人類也因此“日出而作，日落而棲”地重復，感受春花秋月的浪漫、夏日冬雪的無奈……。

“順序不能倒、選擇是唯一、循環有條件”是三種基本結構必須遵循的原則，三種基本結構是自然和社會的法則。在計算機科學中，我們只要定義了三種基本結構的圖形表示，任何復雜問題的算法都可由這三種圖形排列、組合、嵌套得到[8]。

值得一提的是另一種非主流的觀點認為：流程不是三種而是四種基本結構，它將函數的調用回返也作為一種基本結構，這種思考方式可理解為函數的調用回返是和順序、選擇、循環一樣，都是相當重要的結構。

4 用N—S結構圖和PAD問題分析圖表示算法

N—S結構圖也稱為盒圖，是由美國學者I.Nassi和 B.Shneiderman于1973年提出的一種在流程圖中完全去除流程線，所有算法寫在一個矩形框內，在框內還可以包含其他從屬于它的框，即大框套小框、框框排列的形式表達算法。命名為N-S結構流程圖是紀念這兩位學者的（用兩個人姓名的頭一個字母組成）。N—S結構圖特別能表達“自頂向下、逐步細化、模塊化”的編程思想，與中國古代哲學“太極生兩儀、兩儀生四象；四象生八卦、八卦定乾坤。”是相通的[9]。

實例2歐幾里得算法的N—S結構圖如下：

圖4 歐幾里德算法的N—S結構圖Fig.4 N - S structure diagram of euclid algorithm

PAD問題分析圖[problem analysis diagram]是日本日立公司二村良彥等人于 1973年提出的一種表示算法的圖形工具。其優點是PAD圖是二維樹形結構，從上到下的各部分是流程執行順序，而從左往右的展開則代表層次關系。它的特點是結構清晰、易于閱讀、結構化程度高。最左邊縱線是程序的主干線，對應于程序第一層結構，之后每增加一層，PAD圖就向右擴展一條縱線，縱線數就是程序層次數。程序執行時是從PAD圖最左邊主干線的上端結點開始，從上而下、自左往右依次執行，最后終止于最左主干線[2]。

實例2歐幾里得算法的PAD問題分析圖如下：

圖5 歐幾里德算法的PAD問題分析圖Fig.5 PAD problem analysis diagram of euclid algorithm

偽代碼是使用自然語言與計算機語言之間的文字及符號來表示算法。軟件從業人員一般習慣使用偽代碼，這是由于復雜而龐大的問題，畫 N—S結構圖或PAD問題分析圖很費事，使用偽代碼不受約束、自由自在。偽代碼還有容易轉化為真代碼（源程序）的優勢，但表達的流程不清晰、不直觀、尤其對分支與循環描述困難。

傳統流程圖、N—S結構圖、PAD問題分析圖是基礎編程的基本功！是學習程序設計必經的思維訓練歷程！

5 結構化程序設計方法

結構化程序設計是用工程的方法設計程序。其基本思想就是“自頂向下、逐步細化、模塊化編程”，是將問題的求解從抽象逐步具體化的過程。在模塊化分工完成后，即把一個大任務分解為若干個子任務后，對每一個子任務（小模塊）的編碼則是“自下而上、逐步積累”的過程。類比例子是設計房屋，先要“自頂向下、逐步細化”作整體規劃、確定建筑物方案……有了設計圖之后，施工階段則是一磚一瓦“自下而上、逐步積累”完成的[2]。

實例3：輸入兩個自然數a與b，求出它們的最大公約數和最小公倍數。

C語言是函數式的語言，它的特點決定了它是最容易實現結構化編程的優秀語言。在C語言中對一個較復雜的規模較大的問題編程時，代碼通常由一個主函數和若干個其它函數組成。一個函數就是一個程序模塊。主函數可調用其它函數，其它函數也可相互調用，但主函數只能被操作系統調用。同一函數可被一個或多個函數調用任意多次（“代碼重用”）。函數必須先定義后使用，函數之間的關系是相互獨立的、地位是平行的。和“組裝汽車”、“組裝電腦”相類似，結構化編程就是“組裝程序”，而函數就是“組裝程序”的部件。

下面的函數調用回返的樹型模塊圖（方向向右的樹，可旋轉改變方向。）可反映復雜程序的結構脈絡。