第1章 算法及其設(shè)計基礎(chǔ),教學(xué)目的和要求 了解算法描述的基本要求和目的，掌握用自然語言方式、流程圖方式、盒圖(N-S圖)、 偽代碼方式、PAD圖方式和計算機(jī)語言方式來描述一個算法。 重點： 流程圖方式、盒圖(N-S圖)、PAD圖方式。 難點： 完整地用盒圖(N-S圖)來描述一個算法。,1.1 引言,程序設(shè)計方法首先強(qiáng)調(diào)的是設(shè)計，其次才是實現(xiàn)（寫出程序代碼）。其核心是將程序設(shè)計過程分為兩部分。 第一部分集中于問題及其解法或算法，與任何特定的計算機(jī)或計算機(jī)語言無關(guān)。 第二部分集中于選擇某一種程序設(shè)計語言，把算法表達(dá)給特定的計算機(jī)。,1.2 算法的概念,廣義地說，為解決一個問題而采取的方法和步驟，就稱為“算法”。 你想查看計算機(jī)CPU，首先必須將計算機(jī)斷電，拆除連線，打開機(jī)箱，然后按下夾子解除夾口，最后取出CPU進(jìn)行查看。 復(fù)制文件，首先要尋找所要復(fù)制的文件，然后選中，再進(jìn)行復(fù)制，最后移動到需要的地方進(jìn)行粘貼。,計算機(jī)算法的分類： 本書所講述的算法只限于計算機(jī)算法，即計算機(jī)能執(zhí)行的算法。在設(shè)計一個計算機(jī)算法時，應(yīng)當(dāng)考慮到計算機(jī)能否執(zhí)行。 計算機(jī)算法可分為兩大類別：數(shù)值運(yùn)算算法和非數(shù)值運(yùn)算算法。 數(shù)值運(yùn)算的目的是求數(shù)值解，例如求方程的根，求一個函數(shù)的定積分等，都屬于數(shù)值運(yùn)算范圍。 非數(shù)值運(yùn)算包括的面十分廣泛，最常見的是用于事務(wù)管理領(lǐng)域，例如圖書檢索、人事管理等。目前，計算機(jī)在非數(shù)值運(yùn)算方面的應(yīng)用遠(yuǎn)遠(yuǎn)超過了在數(shù)值運(yùn)算方面的應(yīng)用。,1.3 算法的特性,一個算法應(yīng)該具有以下幾個特性： 有窮性 確定性 輸入 輸出 有效性,1.3 算法的特性,1）有窮性 一個算法應(yīng)包含有限的操作步驟，而不能是無限的。 但是要注意，“有窮性”往往指“在合理的范圍之內(nèi)”。如果讓計算機(jī)執(zhí)行一個歷時幾百年才結(jié)束的算法，這雖然是有窮的，但超過了合理的限度，人們也不把它視做有效算法。究竟什么算“合理限度”，并無嚴(yán)格標(biāo)準(zhǔn)，由人們的常識和需要而定。,確定性 算法中的每一個步驟，必須是確切定義的，而不應(yīng)當(dāng)含糊不清或模棱兩可的。即算法的含義應(yīng)當(dāng)是唯一的，而不應(yīng)當(dāng)產(chǎn)生“歧義性”。 例如，某人只說請您“復(fù)制文件”或查看計算機(jī)的CPU，是不確定的，因為此人沒有說明復(fù)制哪一個文件或查看哪一臺計算機(jī)的CPU。,1.3 算法的特性,輸入 所謂輸入是指在執(zhí)行算法時需要從外界取得必要的信息。 例如，讓計算機(jī)來完成“將N個正數(shù)按從小到大的次序排列”時，就需要輸入N個正整數(shù)。一個算法可以有多個輸入，也可以沒有輸入。,1.3 算法的特性,輸出 算法執(zhí)行過程中往往會產(chǎn)生一些數(shù)據(jù)，它們在算法執(zhí)行之后被保存下來或傳遞給算法的調(diào)用者，這些數(shù)據(jù)被稱為算法的輸出。 一個算法可以有多個輸出，沒有輸出的算法是沒有意義的。 例如，計算機(jī)來完成“將N個整數(shù)按從小到大的次序排列”的算法時，輸出的整數(shù)將是一組“從小到大的次序排列的N個整數(shù)”。,1.3 算法的特性,有效性 一個算法應(yīng)該是具有現(xiàn)實意義的，如果算法中含有不能實現(xiàn)的某一個步驟，則這個所謂的“算法”無法解決問題，因此，不能稱為算法。 算法貫穿于程序設(shè)計的始終，希望讀者對算法給予很大的重視，在解決一個問題之前應(yīng)當(dāng)首先構(gòu)造出一個好的算法。在本書各章中都貫穿這一原則。,1.3 算法的特性,1.4 算法的結(jié)構(gòu),1966年，計算機(jī)科學(xué)家Bohm和Jacopini的研究表明，任何簡單或復(fù)雜的算法都可以由下述3種基本控制結(jié)構(gòu)組成。 1）順序結(jié)構(gòu) 2) 選擇結(jié)構(gòu) 3) 循環(huán)結(jié)構(gòu),1）順序結(jié)構(gòu),這是最簡單的一種基本結(jié)構(gòu)。順序結(jié)構(gòu)中的各個部分是按書寫順序依次執(zhí)行的。例如某個算法中可能出現(xiàn)下列形式的一組操作： 操作 1 操作 2 操作 3 如果這樣一組操作的執(zhí)行順序與操作出現(xiàn)的前后順序相同，即先進(jìn)行“操作1”，然后進(jìn)行“操作2”，再后進(jìn)行“操作3”，那么這段算法的結(jié)構(gòu)就是順序結(jié)構(gòu)。,2) 選擇結(jié)構(gòu),這種結(jié)構(gòu)也稱為分支結(jié)構(gòu)，它表示操作的處理步驟出現(xiàn)了分支，它需要根據(jù)某一特定的條件選擇其中的一個分支執(zhí)行。例如下述算法描述片段： 如果 成立 則執(zhí)行 否則執(zhí)行 和 之間構(gòu)成了一種選擇關(guān)系，兩個操作中哪一個將被執(zhí)行是通過對 的判斷來控制的。,3) 循環(huán)結(jié)構(gòu),循環(huán)結(jié)構(gòu)是指被重復(fù)執(zhí)行的一個操作集合。例如下述算法描述片段： 重復(fù)執(zhí)行 直到 不成立 這段描述指出 將被反復(fù)運(yùn)行多次，直到 不成立為止。,注意： 通過上述三種基本控制結(jié)構(gòu)可以看到，它們有一個共同的特點，即：只有一個入口且只有一個出口，并且操作不會出現(xiàn)死循環(huán)。,1.5 算法的描述,算法的描述具有重要意義，描述一個算法的目的在于使其他人能夠利用算法解決具體問題。 算法的描述方式?jīng)]有統(tǒng)一規(guī)定，本書將介紹常用的自然語言、流程圖、N-S圖、PAD圖、偽代碼以及計算機(jī)語言等六種描述算法的方式。 注意： 不論是哪類方式，對它們的基本要求都是能提供對算法的無歧義的描述，以便使我們能夠?qū)⑦@種描述很容易轉(zhuǎn)換成計算機(jī)高級語言（程序）。,1.5.1 自然語言方式,自然語言就是人們?nèi)粘Ｊ褂玫恼Z言，可以是漢語、英語或其他任何形式的語言。,算法可以表示如下： 第1步 使sign=1（sign代表數(shù)值的符號） 第2步 使sum1（sum代表累加和變量） 第3步 使deno=2（deno代表分母變量） 第4步 sign(-1)*sign（求級數(shù)中各項的符號，它的值為l或-1） 第5步 termsign*(1/deno) （term代表級數(shù)中的某一項） 第6步 sum=sum+term 第7步 deno=deno+l 第8步 若deno20，轉(zhuǎn)去執(zhí)行第4步以及其后的各個步驟；否則 執(zhí)行第9步 第9步 打印sum的值（即所求之總和） 第10步 算法結(jié)束,例1.1 求,例1.2 用選擇排序法，將N個正整數(shù)數(shù)列按照從小到大 的順序排列。 選擇排序法基本思想：在選擇排序方法中，第一步在N個元素中選出最小元素，將其與第一個元素交換。第二步從剩下的N-1個元素中選出最小元素，將其與第二個元素交換，如此下去，直到剩下最后兩個元素。,輸入：將N個正整數(shù)放置在數(shù)組aN中。 第1步 使i=1 第2步 若iN-1，執(zhí)行第3步；否則轉(zhuǎn)第10步 第3步 使k=i，順次執(zhí)行第4步 第4步 使j=i+1，順次執(zhí)行第5步 第5步 若jN，執(zhí)行第6步；否則轉(zhuǎn)第8步 第6步 若ajak，則置k為j，然后順次執(zhí)行第7步；否則 直接執(zhí)行第7步 第7步 使j=j+1，轉(zhuǎn)第5步 第8步 若i!=k交換ai和ak的值(置t為 ai,ai為 ak， ak為 t )，順次執(zhí)行第9步；否則直接執(zhí)行第9步 第9步 使i=i+1，轉(zhuǎn)第2步 第10步 輸出a1aN 第11步 算法結(jié)束,算法可以表示如下：,自然語言方式的優(yōu)缺點： 用自然語言表示通俗易懂，但文字冗長，容易出現(xiàn)歧義性。 用自然語言描述的算法通用性差。例如，用漢語描述的算法只適合于懂得漢語的人，而用英語描述的算法也只能適合于懂得英語的人。 基于上述原因，除了很簡單的問題以外，一般不用自然語言描述算法。,1.5.2 流程圖方式,流程圖是20世紀(jì)40年代末出現(xiàn)的一種描述算法或程序的工具，其特點是用一些圖框表示各種類型的操作，用線表示這些操作的執(zhí)行順序。,圖例中各結(jié)點的意義：,端點符：表示算法由此開始或結(jié)束。 處理框：表示一般的處理功能，應(yīng)在框中對該功能進(jìn)行簡單標(biāo)記和說明。 判斷框：表示判斷操作，應(yīng)該在框中標(biāo)明判斷條件。此框具有兩個或兩個以上出口，在每個出口處標(biāo)明出口的條件。 預(yù)定義功能框：代表未詳細(xì)說明的一個或一組操作，通常用來表示調(diào)用一個已知的算法或函數(shù)，框中標(biāo)明這個算法或函數(shù)的名字或入口地址。 連接符：表示連結(jié)點，框中標(biāo)有數(shù)字。當(dāng)流程圖較復(fù)雜或分布在多張紙上時，用連接符表示各圖之間的聯(lián)系，相同符號的連接符是相互連接的（如圖1.2所示）。 注釋框：注釋框不反映流程和操作，只是為了對流程圖中某些框的操作做必要的補(bǔ)充說明，以幫助閱讀流程圖的人更好地理解流程圖的作用。,端點符,處理框,輸入輸出框,預(yù)定義功能框,判斷框,流程線,連接符,圖 1.1 流程圖常用圖形符號,使用流程圖表示的順序型、選擇型、當(dāng)型循環(huán)和直到型循環(huán)等四種基本控制結(jié)構(gòu)如圖1.3所示。,條件,處理2,處理1,順序結(jié)構(gòu),處理2,處理,N,當(dāng)型循環(huán),直到型循環(huán),選擇結(jié)構(gòu),處理,條件,條件,Y,Y,N,處理,圖 1.3 四種基本控制結(jié)構(gòu),N,Y,使用流程圖表示的順序型、選擇型、當(dāng)型循環(huán)和直到型循環(huán)等四種基本控制結(jié)構(gòu)：,例1.3 求,的流程圖如圖1.4所示,例1.4 將N個正整數(shù)數(shù)列按照從小到大的順序排列的算法用流程圖表示。,流程圖描述算法的不足之處?,隨意地使用箭頭控制算法的執(zhí)行流程，從而造成算法的層次結(jié)構(gòu)混亂。 降低了程序的可讀性和可維護(hù)性。 不適于自頂向下、逐步求精的程序開發(fā)方式。,使用程序流程圖描述算法，具有簡捷、直觀、使用方便的特點。,流程圖特點:,1.5.3 盒圖(N-S圖)方式,出于要有一種不允許違背結(jié)構(gòu)化程序設(shè)計思想的圖形工具的考慮，1973年美國學(xué)者Nassi和Shneiderman提出了一種新的流程圖形式,稱為盒圖（box diagram）,又稱為N-S圖。 在這種流程圖中，完全去掉了帶箭頭的流程線。全部算法寫在一個矩形框內(nèi)，在該框內(nèi)還可以包含其他的從屬于它的框。 N-S圖十分適合描述結(jié)構(gòu)化程序或算法的結(jié)構(gòu)化實現(xiàn)，能夠較好地反映算法和程序的層次結(jié)構(gòu)，可讀性好，具有自頂向下逐步求精的特征。,N-S 圖基本符號以及控制結(jié)構(gòu)的描述方法,例1.5 求,圖 1.7 N-S圖描述,的N-S圖表示。,例1.6 將N個正整數(shù)數(shù)列按照從小到大的順序排列的N-S圖描述,1.5.4 PAD圖方式,PAD圖是問題分析圖（problem analysis diagram）的英文縮寫，1973年由日本日立公司的二才 良彥等提出，是另一種可以用于算法和程序描述的圖形工具。 PAD圖用二維樹型結(jié)構(gòu)的圖來表示程序的控制流，即可以用于表示程序中操作的邏輯順序，也可用于表示數(shù)據(jù)結(jié)構(gòu)，是一種結(jié)構(gòu)化程序設(shè)計描述工具，適用于自頂向下、逐步求精的程序開發(fā)方法。,PAD圖的符號及控制結(jié)構(gòu)如圖1.9和表1.1所示。,表1.1 PAD圖的圖形符號,例1.7求,的PAD圖描述算法,例1.8 將N個正整數(shù)數(shù)列按照從小到大的順序排列。,圖1.11 PAD圖描述,1.5.5 偽代碼方式,偽代碼(pseudo code)就是程序設(shè)計語言的控制結(jié)構(gòu)和其他一些元素的速記符號。一般來說，偽代碼的語法規(guī)則分為“外層語法”和“內(nèi)層語法”。 外層語法類似于一般編程語言控制結(jié)構(gòu)的關(guān)鍵字，比較嚴(yán)格。 內(nèi)層語法則是靈活自由的，可以用自然語言，也可用程序設(shè)計語言，或使用自然語言與程序設(shè)計語言的混合體，以便使用于不同工程項目的需要。 偽代碼不用圖形符號，因此書寫方便、格式緊湊，也比較好懂，便于轉(zhuǎn)換成計算機(jī)高級語言(即程序)。,1) 層次,算法的書寫應(yīng)該具有層次，下面的一層采用縮進(jìn)方式，同層次的縮進(jìn)相同，例如： X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X,本書偽代碼構(gòu)成元素和書寫規(guī)則如下：,2) 注釋,其形式是由()括起來的中文或英文字符串。 3) 3種控制結(jié)構(gòu) (1) 順序結(jié)構(gòu) 書寫格式如下： ,(2) 分支結(jié)構(gòu),有以下兩種書寫格式： 格式1： if() then else 格式2： if() then 多重選擇的格式如下： ，執(zhí)行 ，執(zhí)行 ，執(zhí)行,（3）循環(huán)結(jié)構(gòu),有以下三種書寫格式： 格式l：do while() 格式2：while() do 格式3：for to 步長 ,4) 調(diào)用算法,書寫方式如下： 調(diào)用() 5) 需要標(biāo)明算法的“BEGIN(開始)”和“END(結(jié)束)”點。,例1.9 求,BEGIN sign=1（sign代表數(shù)值的符號） sum=1（sum代表累加和變量） deno=2（deno代表分母變量） while deno20 sign=(-1)*sign（求級數(shù)中各項的符號,它的值為l或-1） term=sign*1/deno（term代表級數(shù)中的某一項） sum=sum+term deno=deno+1 print sum（所求之總和） END,例1.10 將N個正整數(shù)數(shù)列按照從小到大的順序排列。,BEGIN for i=1 to N-1 (每循環(huán)一次在未排序元素中找出一個最小的元素進(jìn)行排序) k=i for j=i+1 to N（查找未排序元素中的最小的元素） if( ajak) then k=j if( ik ) then t=ai; ai=ak; ak=t; END,偽代碼書寫格式比較自由，可以隨手寫下去，容易表達(dá)出設(shè)計者的思想。 用偽代碼寫的算法很容易修改，例如增加一行、刪除一行或?qū)⒑竺婺骋徊糠终{(diào)到前面某一位置，都是很容易做到的。 用偽代碼很容易寫出結(jié)構(gòu)化的算法。 用偽代碼寫算法不如流程圖和N-S圖直觀，可能會出現(xiàn)邏輯上的錯誤。,1.5.6 計算機(jī)語言方式,前幾節(jié)我們用自然語言方式、偽代碼方式、流程圖方式、N-S圖方式、PAD圖等5 種不同的方式描述了算法，用計算機(jī)語言（包括低級語言和高級語言）編寫的程序也是算法的表示形式。 用計算機(jī)語言表示算法必須嚴(yán)格遵循所用語言的語法規(guī)則，這是與其它描述方式不同的。本書中將用C程序設(shè)計語言表示算法。,例1.11 求,main() int sign=1; float deno=2.0,sum=1.0,term; clrscr(); while(deno=20) sign=-sign; /* 求級數(shù)中各項的符號,值為l或-1 */ term=sign/deno; /* term代表級數(shù)中的某一項 */ sum=sum+term; deno=deno+1; printf(“sum=%fn“,sum); 程序運(yùn)行結(jié)果： sum=0.668771,#define N 10 main() int i,j,k,t; int aN; printf(“input %d number:n“,N); for(i=0;iN;i+) printf(“a%d=“,i); scanf(“%d“, ,例1.12 將N個正整數(shù)數(shù)列按照從小到大的順序排列。,程序運(yùn)行結(jié)果： input 10 number: a0=13 a1=19 a2=22 a3=55 a4=66 a5=88 a6=11 a7=77 a8=55 a9=1 1 11 13 19 22 55 55 66 77 88,我們可以直接使用某種程序設(shè)計語言（如C程序設(shè)計語言或C+程序設(shè)計語言）來描述算法，不過直接使用程序設(shè)計語言不是很容易，而且不太直觀，并常常需要借助注釋才能使人看明白。,1.6 關(guān)于計算機(jī)算法的評價,關(guān)于一個計算機(jī)算法的好壞可用下面幾個指標(biāo)來衡量： 1）程序的可讀性好 2）提高收斂速度 3）節(jié)省計算時間 4）節(jié)省存儲空間 5）增強(qiáng)數(shù)值穩(wěn)定性,1）程序的可讀性好 在早期使用程序設(shè)計語言編程的時候，尤其是在使用匯編語言編程的時候，人們有這樣一種認(rèn)識，那就是程序只是給機(jī)器執(zhí)行的，而不是供人閱讀的。基于這一想法，人們往往采用一些編程技巧，從而造成算法難以理解，編程更加困難，程序不易閱讀，也不便于程序的測試和維護(hù)。 20世紀(jì)70年代初，人們開始注意在編寫程序時注意應(yīng)該使程序具有良好的風(fēng)格。這樣使得今后有人閱讀這個程序時能比較方便地沿著你的思路去理解程序的功能，從而使程序的可讀性增強(qiáng)，方便了測試與維護(hù)。,2）提高收斂速度 對于一個迭代過程來說，理論上講需要無限多步的計算才能得到某個量的真值，實際操作中采用的方法是根據(jù)精度要求決定是否停止進(jìn)一步的計算。所以計算時間既與選定的方法有關(guān)，還與要求達(dá)到精度有關(guān)，用計算量來評估并不適宜。,3）節(jié)省計算時間 盡管現(xiàn)在計算機(jī)的運(yùn)算速度極快，但是對于一些復(fù)雜的大規(guī)模問題求高精度數(shù)值解來說，最后折算成所需要進(jìn)行的四則運(yùn)算次數(shù)也是相當(dāng)多的，所需要的計算時間也很多。通常我們使用機(jī)器完成一次浮點數(shù)的乘法或除法運(yùn)算連同一次加法或減法運(yùn)算的計算量作為評估計算量的計量單位。 現(xiàn)在由于CPU的運(yùn)算速度以及數(shù)據(jù)總線的位數(shù)都得到了明顯的改善，因此，這個問題的重要性現(xiàn)在已經(jīng)大大降低了。但是，對于一些問題而言，設(shè)計算法時應(yīng)該考慮節(jié)省計算的時間。,4）節(jié)省存儲空間 節(jié)省存儲空間有兩層含義，第一層含義是指算法簡單，因而程序就短，程序本身所占用的存儲空間便少；另一層含義是指所需要保留的中間結(jié)果比較少，這樣就可以省下為了保留中間結(jié)果所需要的額外的存儲空間。 自20世紀(jì)90年代以來，計算機(jī)的機(jī)器字長，數(shù)據(jù)總線的位數(shù)，以及存儲器的容量等都得到了明顯的改善。因此，這個問題的重要性現(xiàn)在已經(jīng)大大降低了。,5） 增強(qiáng)數(shù)值穩(wěn)定性 對于某個數(shù)值算法，如果輸入數(shù)據(jù)的誤差，在計算過程中不斷擴(kuò)大而難以得到控制，則稱該算法是數(shù)值不穩(wěn)定的，否則是數(shù)值穩(wěn)定的。 如果某算法在一定的條件下才是穩(wěn)定的，則稱該算法是條件穩(wěn)定（相對穩(wěn)定）的；若在任何條件下，某算法是穩(wěn)定的，則稱該算法是無條件穩(wěn)定（絕對穩(wěn)定）的。 誤差的傳播能否得到控制，是誤差分析的重要內(nèi)容，也是衡量一個算法優(yōu)劣的一個重要標(biāo)志，可以用算法的數(shù)值穩(wěn)定性表示誤差傳播的控制。,1.7 常用算法設(shè)計及其實現(xiàn),下面我們將介紹幾種典型的方法，這些方法有一定的使用價值，但更重要的是為了使初學(xué)者容易理解算法，從而逐步掌握根據(jù)算法編寫程序的方法。,1.7.1 排序算法及其實現(xiàn),排序是將一個無序的數(shù)據(jù)序列按照某種順序（升序或降序）重新排列的過程。例如，將一批雜亂無序的學(xué)生成績按高分到低分的順序排列。,1.7 常用算法設(shè)計及其實現(xiàn),例 1.13 用冒泡排序法將N個正整數(shù)，按照從小到大的順序排序。 冒泡排序法基本思想是將相鄰兩個數(shù)比較，把大數(shù)往后移，如圖1.12所示的過程就是冒泡處理的形象過程。,6 6 6 6 6 6 6 8 8 8 4 4 4 4 4 4 4 8 7 7 7 7 7 7 7 8 2 2 2 2 2 2 2 8 5 5 5 5 5 5 5 8 第1次 第2次 第3次 第4次 第5次 結(jié)果 6 6 4 4 4 4 4 4 6 6 6 6 7 7 7 7 2 2 2 2 2 2 7 5 5 5 5 5 5 7 第1次 第2次 第3次 第4次 結(jié)果 圖1.12 冒泡排序法第一趟比較和第二趟比較的示意,值得注意的是: 如果在一趟比較中沒有數(shù)據(jù)的交換，說明所有的數(shù)據(jù)都已經(jīng)從小到大排好了序，因此可以提前退出循環(huán)。為此，程序中設(shè)置exchange為交換標(biāo)志，在一趟比較中數(shù)據(jù)進(jìn)行了交換exchange置為1，沒有進(jìn)行數(shù)據(jù)交換exchange置為0，即可退出循環(huán)。其N-S圖，如圖1.13所示。,圖 1.13 N-S圖描述,#include #define N 6 main() int i,j,t,exchange; int aN+1; /* aN用于存放 */ printf(“input %d number:“,N); for(i=0;iaj+1) /* 順序不符合要求時交換位置 */ t=aj; aj=aj+1; aj+1=t; exchange=1; if (!exchange) break; /* 若所有的元素都已排好序，則退出循環(huán) */ for(i=0;iN;i+) printf(“%4d“,ai); printf(“n“); ,程序運(yùn)行結(jié)果： input 6 number: 6 8 4 7 2 5 6 8 4 7 2 5 2 4 5 6 7 8,1.7.2 查找算法及其實現(xiàn),在處理大量數(shù)據(jù)時，經(jīng)常要按某種方法找出所需的數(shù)據(jù)，這個過程稱為查找。 例如，在學(xué)生成績中查找某位學(xué)生的成績等。查找方法很多，下面將以例1.14為例介紹常用的順序查找法。,例 1.14 編寫一個程序，在給定的數(shù)組a中查找用戶輸入的值，并提示相應(yīng)的查找結(jié)果。 順序查找法基本思想是：從數(shù)組第一個元素開始，順序掃描數(shù)組，依次將掃描元素和給定值x相比較，若當(dāng)前掃描元素與x相等，則查找成功；若掃描結(jié)束后，仍未找到等于x的元素，則查找失敗。,例 1.14 編寫一個程序，在給定的數(shù)組a中查找用戶輸入的值，并提示相應(yīng)的查找結(jié)果。,#define N 10 main() int a=6,3,9,8,1,5,4,10,2,7; int i=0,x; printf(“input x=“); scanf(“%d“, ,程序運(yùn)行結(jié)果： input x=8 find 8 it position is :a3=8 input x=99 99 not been found,1.7.3 窮舉算法及其實現(xiàn),在循環(huán)算法中，窮舉法是具有代表性的基本算法，窮舉的基本思想是，對問題的所有可能狀態(tài)一一測試，直到找到解或?qū)⑷靠赡軤顟B(tài)都測試過為止。,例 1.15 編寫一個程序，求這樣四位數(shù)：該四位數(shù)的千位上的數(shù)字和百位上的數(shù)字都被擦掉了，知道十位上的數(shù)字是1，個位上的數(shù)字是2，又知道這個數(shù)如果減去7就能被7整除，減去8就能被8整除，減去9就能被9整除。 設(shè)這個數(shù)為n=abl2，則n=lOOO*a+lOO*b+lO+2，且有0a9，0b9。,main() int n,a,b; for(a=1;a=9;a+) for(b=0;b=9;b+) n=1000*a+100*b+10+2; if(n-7)%7=0 程序運(yùn)行結(jié)果： n=1512