天天看點

《C++ 開發從入門到精通》——2.5 算法是程式的靈魂

本節書摘來自異步社群出版社《c++ 開發從入門到精通》一書中的第2章,第2.5節,作者: 王石磊 , 韓海玲,更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

圖檔 1 知識點講解:CD光牒:視訊ppt講解(知識點)第2章算法是程式的靈魂.mp4

任何程式語言都需要進行大量的運算,為達到某個目的以擷取指定的結果,這就需要了解算法的基礎知識。算法是對操作的描述,是程式設計語言實作一種功能的操作方法。任何一門語言都有自己的資料類型,通過資料類型,能夠實作具體的功能。

一個程式應包括對資料的描述和對操作的描述2個部分,其中,“資料的描述”在程式中要指定資料的類型和資料的組織形式,即資料結構(data structure);而“對操作的描述”即操作步驟,也就是算法(algorithm)。

在現實工作中,做任何事情都有一定的步驟。為解決一個問題而采取的方法和步驟,就稱為算法。而計算機領域中的算法被稱為計算機算法,計算機算法可分為如下2類。

數值運算算法:用于求解數值。

非數值運算算法:用于事務管理領域。

看下面的運算。

1×2×3×4×5

上述運算通常需要按照如下步驟來計算。

第1步:先求1×2,得到結果2。

第2步:将步驟1得到的乘積2乘以3,得到結果6。

第3步:将6再乘以4,得24。

第4步:将24再乘以5,得120。

上述過程就是一個算法,雖然過程有點複雜。而在計算機程式中,對上述算法進行了改進,使用如下算法。

第1步:使t=1

第2步:使i=2

第3步:使t×i,乘積仍然放在變量t中,可表示為t×i→t

第4步:使i的值+1,即i+1→i

第5步:如果ileqslant5,傳回重新執行步驟3以及其後的步驟4和步驟5;否則,算法結束。

上述算法方式就是數學中的“n!”公式。

看下面的數學應用題。

問題1:有80個學生,要求将他們之中成績在60分以上者列印出來。

在此設n表示學生學号,ni表示第i個學生學号;cheng表示學生成績,chengi表示第i個學生成績。則對應算法表示如下。

第1步:1→i

第2步:如果chengigeqslant60,則列印ni和chengi,否則不列印。

第3步:i+1→i

第4步:若ileqslant80,傳回步驟2,否則,結束。

問題2:判定1900~2500年中的每一年是否閏年,将結果輸出。

潤年需要滿足的條件如下。

(1)能被4整除,但不能被100整除的年份。

(2)能被100整除,又能被400整除的年份。

在此可以設y為被檢測的年份,則對應算法如下。

第1步:1900→y

第2步:若y不能被4整除,則輸出y“不是閏年”,然後轉到第6步。

第3步:若y能被4整除,不能被100整除,則輸出y“是閏年”,然後轉到第6步。

第4步:若y能被100整除,又能被400整除,輸出y“是閏年”否則輸出y“不是閏年”,然後轉到第6步。

第5步:輸出y“不是閏年”。

第6步:y+1→y

第7步:當yleqslant2500時,傳回第2步繼續執行,否則,結束。

算法的表示方法即算法的描述和外在表現,上節中的算法都是通過語言描述來展現的。除了語言描述外,還可以通過流程圖來描述。

在入場應用中,流程圖的描述格式如圖2-9所示。

《C++ 開發從入門到精通》——2.5 算法是程式的靈魂

圖2-9 流程圖示識說明

例如,有80個學生,要求将他們之中成績在60分以上者列印出來。對上述問題的算法即可使用圖2-10所示的流程圖來表示。

《C++ 開發從入門到精通》——2.5 算法是程式的靈魂

圖2-10 算法流程圖

在日常流程設計應用中,流程圖通常包含如下3種結構。

順序結構:順序結構如圖2-11所示,其中a和b兩個框是順序執行的。即在執行完a以後再執行b的操作。順序結構是一種基本結構。

《C++ 開發從入門到精通》——2.5 算法是程式的靈魂

圖2-11 順序結構

選擇結構:選擇結構也稱為分支結構,如圖2-12所示。此結構中必含一個判斷框,根據給定的條件是否成立而選擇是執行a框還是b框。無論條件是否成立,隻能執行a框或b框之一,也就是說a、b兩框隻有一個,也必須有一個被執行。若兩框中有一框為空,程式仍然按兩個分支的方向運作。

《C++ 開發從入門到精通》——2.5 算法是程式的靈魂

圖2-12 選擇結構

循環結構:循環結構分為兩種,一種是當型循環,一種是直到型循環。當型循環是先判斷條件p是否成立,成立才執行a操作,而直到型循環是先執行a操作再判斷條件p是否成,成立又執行a操作,如圖2-13所示。

《C++ 開發從入門到精通》——2.5 算法是程式的靈魂

圖2-13 循環結構

計算機語言表示算法時,必須嚴格遵循所用語言的文法規則。例如,題目要求計算輸入的任意兩個分數的和,用c++程式設計可以通過如下代碼實作。

至此,和語言相關的算法介紹完畢。此部分内容的目的是讓讀者了解各種數學問題的解決方法,掌握c++的處理流程,為進行後面的學習打下基礎。

繼續閱讀