第1章算法與程序設計

1、算算 法法1 1算法的定義算法的定義所謂算法，是指為解決問題而采用的方法和步驟。所謂算法，是指為解決問題而采用的方法和步驟。隨著信息社會的發(fā)展，計算機已成為人們日常生活和工作中不可缺少的工具。聽音樂、看電影、玩游戲、打字、畫卡通畫、處理數據，計算機幾乎滲透到了人們生活的所有領域，那計算機是怎樣工作的呢？要想弄清楚這個問題，算法的學習是一個開始。在計算機中，利用計算機解決問題的方法和步驟稱為計算機的算法。算算 法法然而不是所有問題計算機都能夠解決，根據圖靈理論：只要能夠分解為有限步驟，并且每一步驟都可以轉化為計算機可以執(zhí)行的程序指令的問題，才是計算機可以解決的問題。這里面包含兩層含義，一是算法的

2、步驟必須是有限的，二是算法最終可以轉化為計算機所執(zhí)行的程序。因此算法設計是程序設計的基礎，算法研究成為了計算機科學的核心課題之一。1 1算法的定義算法的定義算算 法法2 2算法的算法的基本特征基本特征（1）可行性（2）確定性（3）有窮性（4）零到多個輸入（5）至少一個輸出算算 法法3 3算法的算法的組成要素組成要素一個算法通常由兩種基本要素組成：一是對數據對象的運算和操作；二是算法的控制結構（1）對數據對象的運算和操作每個算法實際上是根據題意并結合環(huán)境選擇合適的操作所組成的一組指令序列，因此，計算機算法就是由計算機能處理的操作所組成的指令序列。而指令是計算機可以執(zhí)行的基本操作。算算 法法3 3

3、算法的算法的組成要素組成要素操作離不開運算。在一般的計算機系統中，基本的操作運算有以下4類。 算術運算：主要包括加、減、乘、除等運算。 邏輯運算：主要包括“與”、“或”、“非”等運算。 關系運算：主要包括“大于”、“小于”、“等于”、“不等于”等運算。 數據傳輸：主要包括賦值、輸入、輸出等操作算算 法法3 3算法的算法的組成要素組成要素在編制計算機的算法時通常要考慮很多與方法和分析無關的細節(jié)問題（如語法規(guī)則），因此在設計算法的開始，通常并不直接利用計算機來描述算法，而是用別的描述工具（如流程圖、專門的算法描述語言，甚至用自然語言）來描述算法。但不管用哪種工具來描述算法，算法的設計一般都要從上述

4、4類基本操作運算的考慮，根據題意從這些基本操作運算中選擇合適的操作組成解題的操作序列。算算 法法3 3算法的算法的組成要素組成要素（2）算法的控制結構一個算法的功能不僅取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關。算法中各操作之間的執(zhí)行順序稱為算法的控制結構。算法的控制結構給出了算法的基本框架，它不僅決定了算法中各操作的執(zhí)行順序，而且也直接反映了算法的設計是否符合結構化原則。描述算法的工具通常有自然語言、傳統流程圖、N-S結構化流程圖、算法描述語言等，而流程圖特別是傳統流程圖是初學者最喜歡的算法表示。一個算法一般都可以用順序、選擇、循環(huán)這3種基本控制結構組合而成。我們通過下面的傳統流程

5、圖的示意圖，直觀地來了解這3種結構及圖框。算算 法法3 3算法的算法的組成要素組成要素順序結構：算算 法法3 3算法的算法的組成要素組成要素選擇結構：算算 法法3 3算法的算法的組成要素組成要素循環(huán)結構： (a) (a) 當型循環(huán)當型循環(huán) (b) (b) 直到循環(huán)直到循環(huán)算算 法法3 3算法的算法的組成要素組成要素流程圖常用圖框與符號算算 法法4 4算法算法設計基本方法設計基本方法（1）窮舉法窮舉法是基于計算機特點而進行解題的思維方法。其基本思想是：根據提出的問題列舉所有可能的情況，然后通過一一驗證是否符合整個問題的求解要求，而得到問題的解。因此，窮舉法常用于解決“是否存在”或“有多少種可能”

6、等類型的問題，如求解不定方程的問題。窮舉法雖然是一種比較笨拙而原始的方法，且其運算量比較大，但在有些實際問題中（如尋找路徑、查找、搜索等問題），局部使用窮舉法卻是很有效的，因此，窮舉法是計算機算法中的一個基礎算法。算算 法法4 4算法算法設計基本方法設計基本方法（2）歸納法歸納法是從個別性知識引出一般性知識的推理方法。其基本思想是：通過列舉少量具有代表性的信息，經過分析，最后找出一般性的結論。（3）遞推法所謂遞推，是指從已知的初始條件出發(fā)，逐次推出所要求的各序列結果和最后結果。遞推法在數值計算中是極為常見的。其思想是把一個復雜的龐大的計算過程轉化為簡單過程的多次重復。它是計算機中的一種常用算法

7、。該算法利用了計算機速度快和不知疲倦的機器特點。算算 法法4 4算法算法設計基本方法設計基本方法（4）遞歸法人們在解決一些復雜問題時，為了降低問題的復雜程度（如問題的規(guī)模等），一般總是將問題逐層分解，最后歸結為一些規(guī)模較小的同類簡單的問題。這種將問題逐層分解的過程，實際上并沒有對問題進行求解，而只是當解決了最后那些同類簡單的問題后，再沿著原來分解的逆過程逐步進行綜合，這就是遞歸的基本思想。在工程實際中，有許多問題就是用遞歸來定義的，數學中的許多函數也是用逆歸來定義的。遞歸在計算機程序設計中占據很重要的地位。算算 法法4 4算法算法設計基本方法設計基本方法（5）回溯法回溯法也稱為試探法，它是一種

8、系統地搜索問題的解的方法。其基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。它是工程中既不能用歸納法，又不能用遞推法、遞歸法，也不能進行無限列舉的一類問題所采用的一種方法。對于這類問題，一種有效的方法就是“試”。通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，對于每一步，若試探成功，就得到問題的解，若試探失敗，就逐步回退，換別的路線再進行試探?；厮莘ㄔ谔幚韽碗s數據結構方面有著廣泛的應用。算算 法法想一想想一想 做一做：做一做：1將5個蘋果放入x個籃子里，發(fā)現必有一個籃子的蘋果數不少于3個，用窮舉法求籃子數最多為幾個？2有一位師傅想考考他的兩個徒弟，看誰更

9、聰明一些。他給每人一框花生去剝皮，看看每一?；ㄉ欠穸加蟹垡掳凑l先給出答案。大徒弟費了很大的力氣將花生全部剝完了；二徒弟只撿了幾個飽滿的、幾個干癟的、幾個熟透的、幾個沒熟的、幾個三仁的、幾個兩仁的和幾個一仁的，從總共不過一把花生中可以得出結論，顯然二徒弟比大徒弟聰明，那么二徒弟用的是什么方法？大徒弟用的是什么方法？算算 法法算法表示案例算法表示案例【案例1.1】 互換變量x和變量y的值案例分析：在計算機中，一個變量在內存中均對應相應的存儲單元。而存儲器的性質是：一個存儲單元一次只能存儲一個值，當新值進入時，則原值就被覆蓋。因此不能直接將x的值賦給y，或直接將y的值賦給x，而應借助一個中間

10、變量z過渡。算算 法法算法表示案例算法表示案例【案例1.1】 互換變量x和變量y的值具體算法：算算 法法算法表示案例算法表示案例【案例1.2】 求ax+b=0的解案例分析：對于方程ax+b=0來講，應該分情況討論方程的解。要對一次項系數a和常數項b的取值情況進行分類，分類如下：（1）當a 0時，方程有唯一的實數解 ；（2）當a=0，b=0時，全體實數都是方程的解；（3）當a=0，b 0時，方程無解。算算 法法算法表示案例算法表示案例【案例1.2】 求ax+b=0的解具體算法：算算 法法算法表示案例算法表示案例【案例1.3】 求1+2+100的值案例分析：通常，按照下列過程計算1+2+100的值

11、。第1步 0+1=1第2步 1+2=3第3步 3+3=6第4步 6+4=10第100步 4 950+100=5 050顯然，這個過程中包含重復操作的步驟，可以用循環(huán)結構表示上述計算過程算算 法法算法表示案例算法表示案例【案例1.3】 求1+2+100的值具體算法：算算 法法算法表示案例算法表示案例【案例1.4】 將十進制整數a轉化成二進制數案例分析： 將十進制整數轉化成二進制數的方法是：除2求余反向取。具體算法：C C程序設計程序設計隨著計算機應用領域的不斷深入和發(fā)展，利用計算機解決的問題也越來越多、越來越復雜。要想讓計算機解決一個問題，首先需要把解決問題的方法和步驟設計出來，并且將解決問題所

12、需要的數據合理組織，最后用計算機的語言表示出來，所以有人將程序描述為：程序 = 算法 + 數據結構 + 語言，而編寫程序的過程就稱為程序設計。由此可見，一個程序設計離不開對問題的分析、程序設計的基本方法和程序設計語言C C程序設計程序設計分析問題為了能編寫出解決問題的程序，首先應該分析問題，然后設計算法，組織數據并用高級語言編寫程序指令。分析問題是第一步，也是最重要的步驟，這一步需要做以下幾方面的工作。1明確問題的性質計算機能夠解決的問題不外乎兩類：一類是數值計算問題，一類是非數值計算問題。不管是哪類問題其所用的方法、工具以及輸入/輸出的形式都會有所不同，因此明確問題的性質是分析問題的基礎。C

13、 C程序設計程序設計分析問題2了解解決問題的必要條件這些必要條件包括：程序是否需要與用戶建立聯系，程序是否要處理數據，程序是否有輸出，需要什么樣的結果。如果程序要對數據進行操作，那么還必須知道數據是什么以及這些數據代表什么。如果程序產生輸出結果，還應該知道怎樣產生結果以及以何種形式來輸出結果。3合理分解問題如果問題比較復雜，應該把復雜問題分解為若干子問題，每個子問題只完成一項簡單的功能，并且每個子問題都重復步驟1和2。C C程序設計程序設計C程序設計的基本方法C程序設計的基本方法就是結構化程序設計法。結構化程序設計法也稱為自上而下的設計、逐步細化和模塊化編程，即把問題分解為若干個子問題的方法。

14、在結構化程序設計中，問題被分解為若干較小的問題，然后把所有子問題的解決方法結合在一起來解決整個問題。執(zhí)行結構化程度設計的過程稱為結構化編程。結構化程序設計要求把程序的結構限制為順序、選擇和循環(huán)3種基本控制結構，以便于提高程序的可讀性。采用這種結構開發(fā)出來的程序具有清晰的結構層次，易于理解并便于修改調試。C C程序設計程序設計C程序設計的基本方法1按功能劃分模塊按功能劃分模塊的基本原則是：按照人們解決復雜問題的普遍規(guī)律，使每個模塊都易于理解，同時各模塊的功能盡可能單一，各模塊之間的聯系盡量少，從而保證各模塊的可讀性和可理解性。2按層次組織模塊按層次組織模塊是劃分模塊的最好形式之一。在按層次組織模

15、塊時，一般上層模塊只指出“做什么”，具體“怎么做”由下層模塊精確描述。在圖1.9所示的層次結構中，上層模塊給出任務，最后一層模塊才精確描述“怎么做”。C C程序設計程序設計C語言程序的構成和基本格式1一個簡單的C語言程序案例【案例1.5】 求半徑為2的圓的面積#include stdio.hmain( ) float r，s； /*定義變量r，s*/ r=2； /*給半徑r賦值*/ s=3.14*r*r； /*求出圓面積并放入變量s*/ printf(s=%f，s)； /*輸出圓面積的值*/C C程序設計程序設計C語言程序的構成和基本格式2C語言程序的構成和基本格式C語言程序是由函數構成的。一

16、個C語言程序可以包含若干函數，但必須有且只有一個名為main的主函數，任何一個C語言程序都是從主函數開始執(zhí)行的，即沒有主函數main( )，C語言程序將不能執(zhí)行。C語言程序的每個函數均由函數頭部（如以上程序的main( )）和函數體“ ”組成，函數頭部的圓括號中間可以為空，但這對圓括號不能缺省。C語言的函數體由左花括號“”開始，由右花括號“”結束。函數體包括數據定義部分和執(zhí)行部分。以上程序的第4行是定義部分，第57行是執(zhí)行部分。程序通過執(zhí)行部分向計算機系統發(fā)出操作指令。C C程序設計程序設計C語言程序的構成和基本格式2C語言程序的構成和基本格式不管是定義部分還是執(zhí)行部分，其組成成分均是語句，語句以分號“；”結束，特別要注意：分號“；”是C語句的一個組成成分，不能缺省。定義部分的語句叫做定義語句，在上述程序中只有一個定義語句，該語句的作用就是對程序中所需要的r、s定義并說明它們是float類型。程序的第5行是一條給半徑r賦值的語句，第6行是計算圓面積的值并賦給s的語句，第7行是按照定義的數據格式將s輸出到終端屏幕上的語句。C C程序設計程序設計C語言程序的構成和基本格式2C