1.3 算法的描述工具

算法是為解決某個特定問題而采取的確定且有限的步驟，算法的描述工具也多種多樣。本節主要介紹利用自然語言、圖形和計算機語言的描述方法。

1.3.1 自然語言

采用自然語言對算法的描述稱為偽代碼。所謂偽代碼是指用自然語言和指令語句（不要求絕對正確的語句）結合起來描述算法的一種方式。

這種方式的特點是比畫流程圖省時省力，轉換為程序容易，但是清晰度層次性不如流程圖。偽代碼描述算法沒有統一規定，寫出來只要自己或別人能看懂就行。如已知圓的半徑求圓的面積，算法可以描述為：

（1）輸入半徑r；

（2）計算面積：s=3.14*r2；

（3）輸入面積：s。

1.3.2 圖形

圖形的描述方法通常有兩種：傳統的流程圖和NS流程圖。

1. 傳統流程圖

傳統流程圖是描述算法的一種常用工具，是由如圖1-8 中所示的幾種基本框和方向線組成。

由這些框和方向線組成的流程圖來表示算法，允許任意轉向，形象直觀，簡單方便。但是，用這種流程圖描述復雜的算法時，所占篇幅較多，勾畫費時費力，且描述復雜問題時不易閱讀。

2. N-S流程圖

N-S流程圖是由美國學者I.Nassi和B. Shneiderman于1973年提出來用于描述算法的一種形式。算法的每一步都用一個矩形框來描述。把一個個的矩形框按執行的先后次序連接起來就構成了一個完整的算法描述。N-S流程圖的特點是取消了流程線，禁止任意轉向，描述復雜算法時和傳統流程圖相比所占篇幅要少得多，勾畫時也省時省力，層次性、易讀性要好于傳統流程圖。

N-S流程圖常用的矩形框如圖1-9、圖1-10、圖1-11和圖1-12所示。

順序結構框：先執行a塊語句，再執行b塊語句。

條件結構框：如果條件P成立（滿足），則執行a塊；如果條件P不成立（不滿足），則執行b塊。

循環結構框1：當給定條件滿足執行a塊一次，再次判斷給定條件P是否滿足，如果滿足，則再次執行a塊一次。如此往復直到給定條件不滿足為止。

循環結構框2：先執行a塊一次，判斷給定條件是否滿足，如果滿足，則再次執行a塊一次。如此往復直到給定條件不滿足為止。

1.3.3 計算機語言

采用計算機語言對算法進行的描述，也就是計算機程序。采用計算機語言描述算法的關鍵是養成一種良好的程序書寫風格。程序書寫風格是程序設計人員在長期編程過程中所養成的一種書寫程序的習慣。養成好風格的目的是為了閱讀、修改程序的方便；好風格的程序可以減少程序的錯誤。要養成良好的程序書寫風格需要從以下幾個方面入手：結構化編碼、程序的清晰性、變量和表達式、輸入和輸出、程序的效率、程序注釋。

1. 結構化編碼

結構化編碼應遵循的原則是使用順序、選擇和循環三種基本結構來表示程序的邏輯結構；每種結構只能有一個入口和一個出口；復雜結構應是三種基本結構的組合；語言中沒有的控制結構，應采用前后一致的方法來表示和模擬；嚴格控制GOTO語句的使用。

2. 程序的清晰性

保持程序的清晰性需要注意以下幾個方面：簡單明了地說明你的意圖；培養好的書寫程序的方式：一個語句占一行；利用空格和空行增加清晰性；采用鋸齒（縮進）形式書寫。使程序按自頂向下方式閱讀；避免使用then if和空else結構；把與判定相聯系的動作盡可能地緊挨著判定；使用使程序更簡單的數據表示方法；使用子程序，實現模塊化程序設計；每一個模塊應能做好一件事情；讓機器去干苦活。

3. 變量和表達式

程序中大量地使用變量和表達式，對變量和表達式的書寫應注意：

（1）變量名的選擇。變量名要有自說明性；不要用相似的變量名；不要有變量的多義性；對變量要先定義后使用；對重要變量作注釋說明。

（2）表達式的書寫。盡量少用中間變量；注意使用括號保持運算的順序；注意浮點運算的誤差；不要單獨進行浮點數相等的比較；注意整數的運算（i/2*2）；注意復合條件式的書寫。

4. 輸入和輸出的原則

輸入和輸出的原則主要有：輸入的有效性校驗；用文件尾或終止標志結束輸入，而不用記數終止輸入；使輸入容易準備，輸出容易解釋；采用統一輸入格式；把輸入和輸出局限在子程序內；確信在使用之前，變量已經賦值。

5. 程序的效率

在保證程序的效率上要注意：使用標準函數；使用公共表達式；程序要先保證正確，再求運行速度；使程序清晰比運行快更重要；讓編譯程序去做簡單的優化。

6. 程序注釋

程序注釋可以提高程序的可讀性，便于以后對程序的修改和完善。程序注釋分為序言性注釋和描述性注釋。序言性注釋是指出現在程序首部的注釋，主要用于描述有關模塊功能的描述；界面描述：調用形式、參數等；重要變量的使用與限制；開發歷史：作者、復查修改日期等。描述性注釋是指對程序的功能和狀態進行的描述，它出現在被描述程序段的前后。

注釋使用的原則是：注釋應與程序一致；注釋應提供一些從程序本身得不到的東西；對程序段注釋，一般不對一個語句注釋。

1.3.4 算法描述舉例

【例1-1】求前N個自然數的和。

分析：用計算解決這個問題，首先考慮這N個自然數存放在哪？其和存放在哪？其次，考慮這N個自然數如何輸入到計算機中；再次，考慮求和問題；最后考慮如何把和顯示出來。

用自然語言描述：

（1）給出N的值；

（2）設求和變量S的初值為0；

（3）由x產生第1個自然數1；

（4）把x加到S中；

（5）x=x+1產生下一個自然數；

（6）如果x小于等于N就轉到（4），否則，執行（7）；

（7）輸出S。

用N-S圖描述如圖1-13所示。

用流程圖描述如圖1-14所示。

用C語言描述如下：

    #include "stdio.h"
    main()
    {
        int  x,n,s;                  /＊ 定義變量 ＊/
        printf("N=");                /＊ 提示輸入N ＊/
        scanf("%d",&n);              /＊ 從鍵盤輸入N的值 ＊/
        x=1;
        while(x<=n)                  /＊ 前N個自然數求和 ＊/
        {
            s=s+x;
            x=x+1;
        }
        printf("1+2+…+%d=%d\n",n,s); /＊ 打印和 ＊/
    }