程序的靈魂算法

第2章程序的靈魂－－算法算法的概念簡(jiǎn)單算法舉例算法的特征怎樣表示一個(gè)算法結(jié)構(gòu)化程序設(shè)計(jì)方法數(shù)據(jù)結(jié)構(gòu)＋算法＝

程序程序＝算法＋數(shù)據(jù)結(jié)構(gòu)＋程序設(shè)計(jì)方法＋語言工具和環(huán)境目標(biāo)理解算法的作用以及特性用自然語言表示算法用流程圖表示算法用c語言表示算法什么是程序

程序一詞來自生活，通常指完成某些事務(wù)的一種既定方式和過程在日常生活中，可以將程序看成對(duì)一系列動(dòng)作的執(zhí)行過程的描述2.1算法的概念一個(gè)程序應(yīng)包括：對(duì)數(shù)據(jù)的描述：在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu)（datastructure）。對(duì)操作的描述：即操作步驟，也就是算法（algorithm）。返回2.1算法的概念一、算法的概念廣義地講：算法是為完成一項(xiàng)任務(wù)所應(yīng)當(dāng)遵照的一步一步的規(guī)則的、精確的、無歧義的描述，它的總步數(shù)是有限的。狹義地講：算法是解決一個(gè)問題采取的方法和步驟的描述二、算法的描述1.日常自然語言2.偽代碼（自然語言與程序設(shè)計(jì)語言相結(jié)合）3.流程圖(傳統(tǒng)流程圖、N—S流程圖）4.程序設(shè)計(jì)語言三、簡(jiǎn)單的算法舉例[例2.1]交換兩個(gè)變量的值算法：⑴a=>t⑵b=>a⑶t=>bNikiklausWirth提出的公式：數(shù)據(jù)結(jié)構(gòu)+算法=程序再進(jìn)一步：程序=算法+數(shù)據(jù)結(jié)構(gòu)+程序設(shè)計(jì)方法+語言工具和環(huán)境

2.1算法的概念做任何事情都有一定的步驟。為解決一個(gè)問題而采取的方法和步驟，就稱為算法。計(jì)算機(jī)算法：計(jì)算機(jī)能夠執(zhí)行的算法。計(jì)算機(jī)算法可分為兩大類：數(shù)值運(yùn)算算法：求解數(shù)值；非數(shù)值運(yùn)算算法：事務(wù)管理領(lǐng)域。算法計(jì)算長(zhǎng)方形的面積問題：1.接收用戶輸入的長(zhǎng)方形長(zhǎng)度和寬度兩個(gè)值；2.判斷長(zhǎng)度和寬度的值是否大于零；3.如果大于零，將長(zhǎng)度和寬度兩個(gè)值相乘得到面積，否則顯示輸入錯(cuò)誤；4.顯示面積。算法：解決問題的具體方法和步驟八皇后問題問題定義：八皇后問題是一個(gè)著名而古老的問題。該問題要求在8×8的國(guó)際象

棋棋盤上放置8個(gè)皇后，使得它們不能相互攻擊，即任意兩個(gè)皇后不能處于同

一行、同一列或者同一斜線上。問有多少種放置的方案？QQQQQQQQQijQijj:行號(hào)i:列號(hào)每行一個(gè)皇后,即每個(gè)j值對(duì)應(yīng)一個(gè)i值。

試探法(1)j=1i=1Qijj:行號(hào)i:列號(hào)每行一個(gè)皇后,即每個(gè)j值對(duì)應(yīng)一個(gè)i值。

試探法(1)j=1i=1(2)j=2i=3，4……，8

i=3QQijj:行號(hào)i:列號(hào)每行一個(gè)皇后,即每個(gè)j值對(duì)應(yīng)一個(gè)i值。

試探法(1)j=1i=1(2)j=2i=3，4……，8

i=3Q(3)j=3i=5，6，7，8

i=5QQijj:行號(hào)i:列號(hào)每行一個(gè)皇后,即每個(gè)j值對(duì)應(yīng)一個(gè)i值。

試探法(1)j=1i=1(2)j=2i=3，4……，8

i=3Q(3)j=3i=5，6，7，8

i=5Q(4)j=4i=2，7，8

i=2QQijj:行號(hào)i:列號(hào)每行一個(gè)皇后,即每個(gè)j值對(duì)應(yīng)一個(gè)i值。

試探法(1)j=1i=1(2)j=2i=3，4……，8

i=3Q(3)j=3i=5，6，7，8

i=5Q(4)j=4i=2，7，8

i=2(5)j=5i=4，8

i=4Q(6)j=6i無法選取

回退一步Qijj:行號(hào)i:列號(hào)每行一個(gè)皇后,即每個(gè)j值對(duì)應(yīng)一個(gè)i值。

試探法(1)j=1i=1(2)j=2i=3，4……，8

i=3Q(3)j=3i=5，6，7，8

i=5Q(4)j=4i=2，7，8

i=2Q(6)j=6i無法選取

回退一步(5)j=5i=4，8

i=8Qijj:行號(hào)i:列號(hào)每行一個(gè)皇后,即每個(gè)j值對(duì)應(yīng)一個(gè)i值。

試探法(1)j=1i=1(2)j=2i=3，4……，8

i=3Q(3)j=3i=5，6，7，8

i=5Q(4)j=4i=2，7，8

i=2(5)j=5i=4，8

i=4Q(6)j=6i無法選取

回退一步(5)j=5i=4，8

i=8(6)j=6i無法選取

回退一步(4)j=4i=2，7，8

i=7依次類推Qijj:行號(hào)i:列號(hào)每行一個(gè)皇后,即每個(gè)j值對(duì)應(yīng)一個(gè)i值。

試探法(1)j=1i=1(2)j=2i=3，4……，8

i=3Q(3)j=3i=5，6，7，8

i=5QQ(4)j=4i=2，7，8

i=7依次類推如何表示一具體方案如何表示一具體方案？intqueen[8];queen[j]j=0,1,2……,7;表示第j+1行皇后放在第queen[j]+1列上,即（queen[i]+1,j+1)放置一個(gè)皇后。QQQQQQQQ皇后放置問題QQQQQQQQ如何表示（queen[i]+1,j+1)放置一個(gè)皇后以后，與該皇后同列、兩個(gè)對(duì)角線不能再放置皇后？intb[8],c[15],d[15];b[j]j=0,1,2……,7;表示第j+1列上已有皇后如果第i+1行、第j+1列上放置一個(gè)皇后，則b[j]=1第j+1列上已有皇后c[i+j]主對(duì)角線上已有皇后d[i-j+7]從對(duì)角線已有皇后算法描述初始化棋盤為第1個(gè)皇后選擇合適位置第2步定義成一個(gè)遞歸函數(shù)try voidtry(inti);該函數(shù)作用是放置第i+1個(gè)（i=0,1……，7）皇后(第i+1行皇后放置）：for(j=0;j<8;j++) /*每個(gè)皇后都有8種可能位置*/

{2-1

如果不存在位置沖突，則

{2-2

位置（i+1,j+1）上放置皇后

2-3

如果第8個(gè)皇后還沒有放置好，則 繼續(xù)放置下一個(gè)皇后/*try(i+1)調(diào)用*/

否則 輸出當(dāng)前解

}

2-4

釋放位置（i+1,j+1）}#include<stdio.h>intqueen[8],b[8],c[15],d[15];int

queennum=0;/*當(dāng)前解的序號(hào)*//*找到一個(gè)解后，輸出當(dāng)前解*/voidprint(){intk;

queennum++;

printf("%d:",queennum);for(k=0;k<8;k++)

printf("\t%d",queen[k]);

printf("\n");}程序源代碼voidtry(inti){ intj; /*每個(gè)皇后都有8種可能位置*/ for(j=0;j<8;j++) {if((b[j]==0)&&(c[i+j]==0)&&(d[i-j+7]==0))

/*判斷位置是否沖突*/ {queen[i]=j;/*擺放皇后*/

b[j]=1;/*宣布占領(lǐng)第j+1行*/

c[i+j]=1;/*占領(lǐng)兩個(gè)對(duì)角線*/d[i-j+7]=1;if(i<7) try(i+1);/*8個(gè)皇后沒有擺完，遞歸擺放下一皇后*/else print();/*完成任務(wù)，打印結(jié)果*/

b[j]=0;/*回溯*/

c[i+j]=0;d[i-j+7]=0;} }}intmain(){ intk; /*數(shù)據(jù)初始化*/ for(k=0;k<15;k++) { if(k<8)b[k]=0;

c[k]=0;

d[k]=0; } try(0); /*從第1個(gè)皇后開始放置*/ return0;}主函數(shù)一、算法(最短路徑問題)：2511214106104131112396581052C1C3D1AB1B3B2D2EC2求從A到E的最短路徑一、算法(最短路徑問題)：2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0一、算法(最短路徑問題)：2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0一、算法(最短路徑問題)：2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1

（C1，D1）D1

（D1，E）E從A到E的最短路徑為19，路線為A→B2→C1→D1→E一、算法(資源分配問題)4萬元資金，如何分配給A、B、C三個(gè)項(xiàng)目，使總效益最大4萬元2萬元1萬元0萬元4萬元2萬元1萬元0萬元4萬元2萬元1萬元0萬元4萬元

x1 A項(xiàng)目 x2 B項(xiàng)目 x3 C項(xiàng)目 x43萬元3萬元3萬元0f2.2簡(jiǎn)單算法舉例[例2.2]求1×2×3×4×5。最原始方法：步驟1：先求1×2，得到結(jié)果2。步驟2：將步驟1得到的乘積2乘以3，得到結(jié)果6。步驟3：將6再乘以4，得24。步驟4：將24再乘以5，得120。這樣的算法雖然正確，但太繁。返回改進(jìn)的算法：S1:使t=1S2:使i=2S3:使t×i,乘積仍然放在在變量t中，可表示為t×i→tS4:使i的值+1，即i+1→iS5:如果i≤5,返回重新執(zhí)行步驟S3以及其后的S4和S5；否則，算法結(jié)束。如果計(jì)算100！只需將S5:若i≤5改成i≤100即可。

如果該求1×3×5×7×9×11，算法也只需做很少的改動(dòng)：S1:1→tS2:3→iS3:t×i→tS4:i+2→tS5:若i≤11,返回S3，否則，結(jié)束。該算法不僅正確，而且是計(jì)算機(jī)較好的算法，因?yàn)橛?jì)算機(jī)是高速運(yùn)算的自動(dòng)機(jī)器，實(shí)現(xiàn)循環(huán)輕而易舉。[例2.3]有50個(gè)學(xué)生，要求將他們之中成績(jī)?cè)?0分以上者打印出來。

如果，n表示學(xué)生學(xué)號(hào)，ni表示第i個(gè)學(xué)生學(xué)號(hào)；g表示學(xué)生成績(jī)，gi表示第i個(gè)學(xué)生成績(jī)，則算法可表示如下：S1:1→iS2:如果gi≥80，則打印ni和gi，否則不打印S3:i+1→iS4:若i≤50,返回S2，否則，結(jié)束。[例2.4]判定2000—2500年中的每一年是否閏年，將結(jié)果輸出。閏年的條件：

能被4整除，但不能被100整除的年份；

能被100整除，又能被400整除的年份；設(shè)y為被檢測(cè)的年份，則算法可表示如下：S1:2000→yS2:若y不能被4整除，則輸出y“不是閏年”，然后轉(zhuǎn)到S6S3:若y能被4整除，不能被100整除，則輸出y“是閏年”，然后轉(zhuǎn)到S6S4:若y能被100整除，又能被400整除，輸出y“是閏年”否則輸出y“不是閏年”，然后轉(zhuǎn)到S6S5:輸出y“不是閏年”。S6:y+1→yS7:當(dāng)y≤2500時(shí),返回S2繼續(xù)執(zhí)行，否則，結(jié)束。[例2.5]求算法可表示如下：S1:sigh=1S2:sum=1S3:deno=2S4:sigh=(-1)×sighS5:term=sigh×(1/deno)S6:term=sum+termS7:deno=deno+1S8:若deno≤100，返回S4；否則，結(jié)束。[例2.6]對(duì)一個(gè)大于或等于3的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。算法可表示如下：S1:輸入n的值S2:i=2S3:n被i除，得余數(shù)rS4:如果r=0，表示n能被i整除，則打印n“不是素?cái)?shù)”，算法結(jié)束；否則執(zhí)行S5S5:i+1→iS6:如果i≤n-1，返回S3；否則打印n“是素?cái)?shù)”；然后算法結(jié)束。S1:輸入n的值S2:i=2S3:n被i除，得余數(shù)rS4:如果r=0，表示n能被i整除，則打印n“不是素?cái)?shù)”，算法結(jié)束；否則執(zhí)行S5S5:i+1→iS6:如果i≤，返回S3；否則打印n“是素?cái)?shù)”;然后算法結(jié)束。改進(jìn)算法可表示如下：2.3

算法的特性有窮性：一個(gè)算法應(yīng)包含有限的操作步驟而不能是無限的。確定性：算法中每一個(gè)步驟應(yīng)當(dāng)是確定的，而不能應(yīng)當(dāng)是含糊的、模棱兩可的。有零個(gè)或多個(gè)輸入。有一個(gè)或多個(gè)輸出。有效性：算法中每一個(gè)步驟應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。返回2.4

怎樣表示一個(gè)算法一、用自然語言表示算法二、傳統(tǒng)流程圖處理框起止框I/O框判斷框流程線連接點(diǎn)1、傳統(tǒng)流程圖中的基本符號(hào)返回2、三種基本結(jié)構(gòu)的表示（1）順序結(jié)構(gòu)條件語句1語句2YN語句1語句2（2）選擇結(jié)構(gòu)條件語句條件語句（3）循環(huán)結(jié)構(gòu)a)當(dāng)型循環(huán)b)直到循環(huán)YNYN三種基本結(jié)構(gòu)的特點(diǎn)：（1）只有一個(gè)入口（2）只有一個(gè)出口（3）不存在死語句（4）不存在死循環(huán)例：畫出從10個(gè)數(shù)中選出最大的數(shù)的流程圖由以上三種基本結(jié)構(gòu)組成的算法結(jié)構(gòu),可以解決任何復(fù)雜的問題。由基本結(jié)構(gòu)所構(gòu)成的算法屬于“結(jié)構(gòu)化”的算法，它不存在無規(guī)律的轉(zhuǎn)向，只在本基本結(jié)構(gòu)內(nèi)才允許存在分支和跳轉(zhuǎn)。N<10Max=AN=1A>=MaxMax=A輸入A開始再輸入給AN=N+1打印Max結(jié)束YNNY四、N—S流程圖將全部算法寫在一個(gè)矩形框內(nèi)，在矩形內(nèi)還可包含其它從屬于它的框三種基本結(jié)構(gòu)的N—S圖表示：語句A語句B語句A語句B條件YN1、順序結(jié)構(gòu)2、選擇結(jié)構(gòu)語句組（3）循環(huán)結(jié)構(gòu)a)當(dāng)型循環(huán)b)直到循環(huán)當(dāng)條件成立語句組直到當(dāng)條件成立例：畫出從10個(gè)數(shù)中選出最大的數(shù)的N—S流程圖輸入A當(dāng)N<=10Max=AN=N+1打印Max輸入AN—S流程圖傳統(tǒng)流程圖N<10Max=AN=1A>=MaxMax=A輸入A開始再輸入給AN=N+1打印Max結(jié)束YNNYA>=MaxYNN-S圖比文字描述直觀、形象、易于理解；比流程圖緊湊易畫，尤其是它廢除了流程線，整個(gè)算法結(jié)構(gòu)是由各個(gè)接納結(jié)構(gòu)按順序組成的。N-S圖中的上下順序就是執(zhí)行時(shí)的順序，即圖中位置在上面的先執(zhí)行，位置在下面的后執(zhí)行。寫算法和看算法只需從上到下進(jìn)行就可以了，十分方便。五、用計(jì)算機(jī)語言表示算法#include

<stdio.h>

main(){intmax,n,a;n=1;

scanf(“%d”,&a);max=a;

while(n<=10){scanf(“%d”,&a);if(max<a)max=a;n++;}

printf(“Max=%d\n”,max);}[例2.7]將例2.1求5!的算用流程圖表示。[例2.8]將例2.2的算用流程圖表示。

[例2.9]將例2.3判定閏年的算用流程圖表示。

用流程圖表示算法直觀形象，比較清楚地顯示出各個(gè)框之間的邏輯關(guān)系。 流程圖對(duì)流程線的使用沒有限制，使得流程圖變得毫無規(guī)律，如同一碗面條(abowlofspaghetti)。[練習(xí)]用N-S圖表示有50個(gè)學(xué)生，要求將他們之中成績(jī)?cè)?0分以上者打印出來。2.4.5

用偽代碼表示算法 偽代碼使用介于自然語言和計(jì)算機(jī)語言之間的文字和符號(hào)來描述算法。[例2.10]打印2000----2500年中的每一年是否是閏年。BEGIN（算法開始）

2000=>ywhiley<=2500{ify被4整除

ify不被100整除printy;”是閏年”

elseify被400整除printy;”是閏年”

elseprinty;”非閏年”

endif

endifelseprinty;”非閏年”

endif

y+1=>y}END（算法結(jié)束）偽代碼書寫格式比較自由，可以隨手寫下去，容易表達(dá)出設(shè)計(jì)者的思想。用偽代碼寫的算法容易修改，容易寫出結(jié)構(gòu)化的算法。但是，用偽代碼寫算法不如流程圖直觀，可能出現(xiàn)邏輯上的錯(cuò)誤。2.4.6

用計(jì)算機(jī)語言表示算法我們的任務(wù)是用計(jì)算機(jī)解題，就是用計(jì)算機(jī)實(shí)現(xiàn)算法；用計(jì)算機(jī)語言表示算法必須嚴(yán)格遵循所用語言的語法規(guī)則。[例2.11]求1×2×3×4×5用C語言表示。main(){

int

i,t; t=1; i=2;

wh