天天看點

《C語言程式設計與實踐(第2版)》——2.8 算法

本節書摘來自華章出版社《c語言程式設計與實踐(第2版)》一書中的第2章,第2.8節,作者:淩雲等著,更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視

2.8.1 算法概念

人們使用計算機,就是要利用計算機來處理各種不同的問題,而要做到這一點,人們就必須事先對各類問題進行分析,确定解決問題的具體方法和步驟,再根據這些步驟,編制一組讓計算機執行的指令(即程式),讓計算機按人們指定的規則有效地工作。這些具體的方法和步驟,其實就是解決一個問題的算法。根據算法,依據某種規則編寫計算機執行的指令序列,就是編制程式,而書寫時所應遵守的規則即為某種語言的文法。由此可見,程式設計的關鍵之一是解題的方法與步驟,即算法。學習進階語言的重點和難點之一就是掌握分析問題、解決問題的方法,鍛煉分析、分解問題并最終歸納整理出算法的能力。與此相對應的,具體語言(如c語言)的文法是工具,是算法的一個具體實作。是以在進階語言的學習中,一方面應熟練掌握該語言的文法——因為它是算法實作的基礎;另一方面必須認識到算法的重要性,加強思維訓練,尋找問題的最優解決方法,以編寫出高品質的程式。

下面通過例2-8來介紹如何設計一個算法。

例2-8 設有一物體從高空墜下,每次落地後都反彈至距離原高度2/3差1m的地方,現在測得第9次反彈後的高度為2m,請編寫程式,求出該物體從多高的地方開始下墜。

問題分析:

此題粗看起來有些無從着手,但仔細分析物體的運動規律後,能找到一些蛛絲馬迹。假設物體墜落時的高度為,設第1~9次反彈的高度依次為h1, … ,h9,現在隻有h9=2是已知的,但我們從物體的反彈規律能找出各反彈高度之間的關系:

《C語言程式設計與實踐(第2版)》——2.8 算法

算法設計:

上面從h9到h0的計算過程,其實是一個遞推過程,這種遞推方法在計算機解題中經常用到。另外,這些遞推運算的形式完全一樣,隻是hi的下标不同而已,是以可以通過循環來處理。為了友善算法描述,我們統一用h0表示上一次的反彈高度,h1表示本次的反彈高度,算法可以較長的描述如下:

《C語言程式設計與實踐(第2版)》——2.8 算法
《C語言程式設計與實踐(第2版)》——2.8 算法

其中第2~5步為循環,遞推計算各次反彈的高度。

上面的示例示範了一個算法的設計過程,即從具體到抽象的過程,具體方法是:

1)弄清解決問題的基本步驟。

2)對這些步驟進行歸納整理,抽象出數學模型。

3)對其中的重複步驟,通過使用相同變量等方式求得形式的統一,然後簡練地用循環解決。

算法的描述方法有自然語言描述、僞代碼、傳統流程圖、n-s圖及pad圖等,自然語言描述簡單、明了,但是由于程式員之間母語的差别,妨礙了他們的正常交流,是以出現了後面四種算法描述形式,下面主要介紹流程圖描述方法。如果讀者對其他描述方法感興趣,可以參考其他資料。

2.8.2 流程圖與算法描述

可以用不同的方法來描述一個算法。常用的方法有自然語言、傳統流程圖、結構化流程圖(n-s圖)和僞代碼等。

其中使用最廣泛的是傳統流程圖。傳統流程圖又稱為程式框圖,是一種傳統的算法表示法,它利用幾何圖形的框來代表各種不同性質的操作,用流程線來訓示算法的執行方向。由于它直覺形象,部分消除了不同國籍程式員之間的交流障礙,是以應用廣泛。

下面首先介紹常見的流程圖符号及流程圖的示例。圖2-2給出了一些常見的流程圖示準符号。

《C語言程式設計與實踐(第2版)》——2.8 算法

圖2-2 常見流程圖符号

起止框。表示算法的開始和結束。一般内部隻寫“開始”或“結束”。

輸入輸出框。表示算法請求輸入輸出需要的資料或算法将某些結果輸出。一般内部常常填寫“輸入……”,“列印 /顯示……”。

判斷框(菱形框)。主要是對一個給定的條件進行判斷,根據給定的條件是否成立來決定如何執行其後的操作。它有一個入口,兩個出口。給定條件成立時在出口處标明“是”或“y”,不成立時标明“否”或“n”。

處理框。表示算法的某個處理步驟,一般内部常常填寫指派操作。

流程線。用于訓示程式的執行方向。

連接配接點。用于将畫在不同地方的流程線連接配接起來。同一個編号的點是互相連接配接在一起的,實際上同一編号的點是同一個點,隻是畫不下才分開畫。使用連接配接點可以避免流程線交叉或過長,使流程圖更加清晰。

注釋框。注釋框不是流程圖中必要的部分,不反映流程和操作,隻是為了對流程圖中某些框的操作做必要的補充說明,以幫助閱讀流程圖的人更好地了解流程圖的作用。

在上述基本流程圖符号的基礎上,我們可以用一個完整的流程圖來描述例2-8的算法。其流程圖如圖2-3所示。

《C語言程式設計與實踐(第2版)》——2.8 算法

圖2-3 例2-8的算法流程圖

習題

2.1 請對感興趣的例子程式進行修改,觀察修改後的程式運作結果。

2.2 請以一兩個生活中的現象為例子,用算法描述圖的方法,描述解決問題的步驟。

2.3 搜集網絡上知名的c語言程式設計網站,關注入門級的c語言問題,并嘗試解決。

2.4 用傳統流程圖表示求解以下問題的算法。

①依次輸入10個數,要求輸出其中最小的數。

②有3個數a、b、c,要求按照從小到大順序輸出。

③求1++++…++。

④判斷一個數n能否同時被3和5整除。

⑤輸出100~200之間的所有素數。

⑥求兩個數m和n的最大公約數。

2.5 輸入一個年份year,判定它是否是閏年,并輸出它是否是閏年的資訊。請用傳統流程圖表示其算法。符合下面兩個條件之一的年份是閏年:

①能被4整除但不能被100整除。

②能被100整除且能被400整除。

繼續閱讀