第一章算法基礎(chǔ)

目錄向量與矩陣2樹6線性方程組4圖與網(wǎng)絡(luò)分析5圖形變換的矩陣方法3算法基礎(chǔ)1算法基礎(chǔ)Chapter1

學(xué)習(xí)目標(biāo)1.2掌握算法邏輯結(jié)構(gòu)，能用圖表示問題的算法

1.3了解遞歸算法思想及問題中遞歸實(shí)現(xiàn)1.1理解算法的含義、算法特征、算法的表示1.1算法

1.1.1什么是算法

最初算法（Algorism）一詞出現(xiàn)在12世紀(jì)，是用于表示十進(jìn)制算術(shù)運(yùn)算的規(guī)則，18世紀(jì)，算法Algorism演變?yōu)锳lgorithm，算法概念有了更廣的含義，任何定義明確的計(jì)算步驟都可稱為算法，或者說算法是合乎邏輯、簡潔的一系列步驟。現(xiàn)在算法通常指可以用計(jì)算機(jī)來解決某一類問題的程序或步驟。例如，現(xiàn)在有炒菜機(jī)，把制作一道菜的做法編寫成程序，炒菜機(jī)就可以自動(dòng)完成這道菜的烹飪了。做菜的步驟就可視為算法。1.1算法

1.1.2算法的特性

問題不同，解決的思路和采取的方法與步驟有針對(duì)性，對(duì)應(yīng)的算法也各不相同，但各種算法有如下共同之處：首先計(jì)算機(jī)要有操作對(duì)象，通過輸入，給予計(jì)算機(jī)問題所涉及的對(duì)象；最后要能得到運(yùn)行結(jié)果，有輸出；在輸入與輸出之間是具體的方法步驟，這些方法步驟必須是確定的、正確的、有限的、有效的、通用的。因而，運(yùn)行于計(jì)算機(jī)的各種算法有如下特征：1.1算法

1.1.2算法的特性

輸入輸出確定性正確性有限性有效性通用性1.1.2算法的特性算法過程從序列第一項(xiàng)開始，并把序列第一項(xiàng)設(shè)為臨時(shí)最大值max的初始值，接著逐項(xiàng)檢查，如果有一項(xiàng)超過max，就把max更新為這一項(xiàng)的值，檢查到序列的最后一項(xiàng)結(jié)束。算法每進(jìn)行一步要么是比較max和這項(xiàng)的大小，要么是更新max的值，所以每一步操作都是確定的，能保證max是已檢查過的最大整數(shù)，結(jié)果是正確的。如果序列包含n個(gè)整數(shù)，經(jīng)過n-1次比較就結(jié)束，所以算法步驟是有限的、有效的。這個(gè)算法可以用于求任何有限整數(shù)序列問題的最大元素，所以它是通用的。例1.1找出計(jì)算機(jī)軟件專業(yè)錄取的新生中高考總分的最高分。這個(gè)問題等價(jià)于求有限整數(shù)序列中最大值的算法。算法步驟：輸入是軟件專業(yè)所有新生的高考成績輸出是高考最高分1.1算法

1.1.3算法的表示自然語言程序框圖N-S圖偽代碼計(jì)算機(jī)語言又叫流程圖，是由一些規(guī)定的圖形、流程線和文字說明來直觀描述算法的圖形。1、程序框圖例1.2

畫出例1.1的算法的流程圖（圖1-1）

NYNY2、N-S圖流程圖由一些特定意義的圖形、流程線及簡要的文字說明構(gòu)成，它能清晰明確地表示程序的運(yùn)行過程。在使用過程中發(fā)現(xiàn)流程線不一定是必需的，為此，人們設(shè)計(jì)了一種新的流程圖，它把整個(gè)程序?qū)懺谝粋€(gè)大框內(nèi)，這個(gè)大框圖由若干個(gè)小的基本框圖構(gòu)成，這種流程圖簡稱N-S圖，N-S圖是無線的流程圖，又稱盒圖，1973年由美國兩位學(xué)者I.Nassi和B.Shneiderman提出。例1.3例1.1算法的N-S圖（圖1-2）

YN3、偽代碼（Pseudocode）偽代碼是一種介于自然語言與編程語言之間的算法描述語言，讓人便于理解，不依賴于語言的，用來表示程序執(zhí)行過程，而不一定能編譯運(yùn)行的代碼。使用偽代碼的目的是為了使被描述的算法可以容易地以任何一種編程語言實(shí)現(xiàn)。

4計(jì)算機(jī)語言（ComputerLanguage）斯蒂芬-霍金強(qiáng)調(diào)了21世紀(jì)編程語言的重要性，說：“無論你想揭開宇宙的秘密，還是你在第二十一個(gè)世紀(jì)只想追求一個(gè)職業(yè)生涯，基本的計(jì)算機(jī)編程是一個(gè)重要的技能，學(xué)習(xí)吧”。（史蒂芬-霍金，理論物理學(xué)家、宇宙學(xué)家）計(jì)算機(jī)語言種類非常多，總的來說可分為機(jī)器語言、匯編語言、高級(jí)語言。高級(jí)語言包含了很多編程語言。C、C++、C#、Java、VB、VC、FoxPro、Delphi…..2016流行的高級(jí)編程語言SQL全稱是“結(jié)構(gòu)化查詢語言(StructuredQueryLanguage)”，應(yīng)用于大型數(shù)據(jù)庫管理系統(tǒng)。Java是一種計(jì)算機(jī)編程語言，擁有跨平臺(tái)、面向?qū)ο?、泛型編程的特性，廣泛應(yīng)用于企業(yè)級(jí)Web應(yīng)用開發(fā)和移動(dòng)應(yīng)用開發(fā)。JavaScript一種直譯式腳本語言，廣泛用于客戶端的腳本語言，最早是在HTML（標(biāo)準(zhǔn)通用標(biāo)記語言下的一個(gè)應(yīng)用）網(wǎng)頁上使用，用來給HTML網(wǎng)頁增加動(dòng)態(tài)功能。C#是Microsoft公司設(shè)計(jì)，是從C和C++派生來的一種簡單、現(xiàn)代、面向?qū)ο蠛皖愋桶踩木幊陶Z言。Python（英國發(fā)音：/?pa?θ?n）,是一種面向?qū)ο蟮慕忉屝陀?jì)算機(jī)程序設(shè)計(jì)語言。7月20日，IEEE發(fā)布2017年編程語言排行榜：Python高居首位?！?include<stdio.h>intmain(){ inta[100],i,n,max; printf("您要從幾個(gè)數(shù)中尋找最大值：");

scanf("%d",&n); printf("\n請輸入這%d個(gè)數(shù)，兩數(shù)直接用空格隔開\n",n); for(i=0;i<n;i++){ scanf("%d",&a[i]);} max=a[0]; for(i=1;i<=n-1;i++){ if(a[i]>=max){ max=a[i];}} printf("\n這組數(shù)的最大值為：%d\n",max);}例1.1算法的C語言程序運(yùn)行結(jié)果例1.5例1.1算法的MATLAB語言程序

clear;clc;fprintf('請?jiān)?[]"內(nèi)輸入一組數(shù)：');x=input(‘x=');n=length(x);max=x(1);fori=1:nifx(i)>=maxmax=x(i);endendfprintf('max=%d',max);運(yùn)行結(jié)果例1.1算法的MATLAB語言程序演示1.2算法的邏輯結(jié)構(gòu)1.2.1算法的基本邏輯結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)1、順序結(jié)構(gòu)

順序結(jié)構(gòu)是指按順序執(zhí)行完一步后再執(zhí)行下一步的執(zhí)行結(jié)構(gòu)，順序結(jié)構(gòu)在程序框圖中的體現(xiàn)是用流程線將程序框自上而下地連接起來，按順序執(zhí)行算法步驟。AB順序結(jié)構(gòu)

2、選擇結(jié)構(gòu)(條件結(jié)構(gòu))

條件結(jié)構(gòu)在程序框圖中是用判斷框來表示，判斷框內(nèi)寫上條件，兩個(gè)出口分別對(duì)應(yīng)著條件滿足和條件不滿足時(shí)所執(zhí)行的不同指令。條件PAB條件結(jié)構(gòu)NY3、循環(huán)結(jié)構(gòu)

在一些算法中，會(huì)出現(xiàn)從某處開始，按照一定條件，反復(fù)執(zhí)行某一步驟，這就是循環(huán)結(jié)構(gòu)。反復(fù)執(zhí)行的步驟稱為循環(huán)體。循環(huán)結(jié)構(gòu)有三個(gè)要素：循環(huán)變量、循環(huán)體和循環(huán)終止條件。循環(huán)結(jié)構(gòu)必然包含條件結(jié)構(gòu)，循環(huán)結(jié)構(gòu)在程序框圖中是利用判斷框來表示，判斷框內(nèi)寫上條件，兩個(gè)出口分別對(duì)應(yīng)著條件成立和條件不成立時(shí)所執(zhí)行的不同指令，其中一個(gè)要指向循環(huán)體，然后再從循環(huán)體回到判斷框的入口處。循環(huán)結(jié)構(gòu)有兩種類型：當(dāng)型和直到型。3、循環(huán)結(jié)構(gòu)（圖示）循環(huán)體條件PNY條件P循環(huán)體NY直到型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)4、三種基本邏輯結(jié)構(gòu)的N-S圖AB順序結(jié)構(gòu)AB條件P成立不成立當(dāng)循環(huán)條件P成立循環(huán)體A當(dāng)型循環(huán)結(jié)構(gòu)當(dāng)循環(huán)條件P不成立循環(huán)體A直到型循環(huán)結(jié)構(gòu)1.2.2算法舉例

算法分析：

第一步：輸入三個(gè)系數(shù)

a,b,c；

例1.6（a）N-S圖

輸出沒有實(shí)數(shù)根

輸出x

NY

NY例1.6（b）流程圖輸入a,b,c

輸出x

輸出沒有實(shí)數(shù)根NYNY例1.7中國農(nóng)歷60年一大輪回，按天干“甲乙丙丁戊已庚辛壬癸”和地支“子丑寅卯辰巳午未申酉戍亥”循環(huán)排列而成。天干共十個(gè)，公元紀(jì)年也是十年一周期，公元紀(jì)年除以10的余數(shù)（就是公元紀(jì)年的尾數(shù)）與天干之間有一一對(duì)應(yīng)關(guān)聯(lián)（如下表1）余數(shù)4567890123天干甲乙丙丁戊己庚辛壬癸表1

地支共十二個(gè)，地支12年一輪回，用公元紀(jì)年除以12，余數(shù)與地支也有一一對(duì)應(yīng)關(guān)聯(lián)（如表2）余數(shù)45678910110123地支子丑寅卯辰巳午未申酉戌亥表2解：N-S圖輸入年份yearX={甲乙丙丁戊已庚辛壬癸}Y={子丑寅卯辰巳午未申酉戍亥}i=（year-4）除以10的余數(shù)j=（year-4）除以12的余數(shù)S=i+1

t=j+1流程圖輸入年份yearX={甲乙丙丁戊已庚辛壬癸}Y={子丑寅卯辰巳午未申酉戍亥}i=（year-4）除以10的余數(shù)j=（year-4）除以12的余數(shù)S=i+1t=j+1

例1.8設(shè)計(jì)一個(gè)求10！的算法算法分析：第一步：賦初值s=1,i=1

先計(jì)算1×2

1×2的結(jié)果乘以3前3個(gè)數(shù)乘積的結(jié)果再乘以4以此方式進(jìn)行一個(gè)累乘循環(huán)計(jì)算過程

輸入s=1,i=1

s=s*ii=i+1輸出SNY輸入s=1,i=1輸出Ss=s*ii=i+1

例1.8（b）流程圖例1.8（a）N-S圖例1.9用“二分法”設(shè)計(jì)一個(gè)求方程

的近似根的算法。二分法思想二分法是基于根的存在定理，求方程根的近似值的一種算法。二分法思想為：將函數(shù)的零點(diǎn)所在區(qū)間不斷的一分為二，使所得的新區(qū)間不斷變窄，兩個(gè)端點(diǎn)逐步逼近零點(diǎn)，達(dá)到精度要求為止。根的存在定理設(shè)函數(shù)f(x)在閉區(qū)間[a,b]上連續(xù)，且f(a)*f(b)<0，則區(qū)間(a,b)內(nèi)至少有一點(diǎn)c，使得f(c)=0。c稱為函數(shù)f(x)的零點(diǎn)。這個(gè)定理可以幫助我們確定方程根的大致范圍，或判斷方程在某一范圍內(nèi)是否有解。算法分析第一步：輸入……

NYYYNN流程圖1.3遞歸算法小游戲：（漢諾塔或梵塔問題）有3個(gè)基座A、B、C，開始時(shí)A基座上有n個(gè)大小不同盤子，大盤子在下小盤子在上疊在一起，問：要把A基座上的n個(gè)盤子移到C基座上，每次只能移動(dòng)一個(gè)，并且移動(dòng)過程中始終保持大的盤子在下小的盤子在上，能做到嗎？要移動(dòng)幾次？設(shè)n個(gè)大小不同的盤子按規(guī)則移動(dòng)，需要移動(dòng)f(n)次，請動(dòng)手做一做:f(1)=

f(2)=

f(3)=

f(4)=

從移動(dòng)的過程中，你發(fā)現(xiàn)了f(n)的規(guī)律嗎？漢諾塔演示1.3.1什么是遞歸

各種計(jì)算機(jī)高級(jí)語言都有函數(shù)的嵌套調(diào)用和遞歸調(diào)用，什么是遞歸呢？f(n)=2f(n-1)+1就是遞歸定義的函數(shù)，f(n)與f(n-1)本質(zhì)上是相同的函數(shù)。自己調(diào)用自己，稱為遞歸。自己調(diào)用自己的函數(shù)，稱為遞歸函數(shù)。遞歸函數(shù)包括直接遞歸和間接遞歸。

例1.10

1、什么是遞歸與遞歸函數(shù)類似的說法，還有遞歸調(diào)用：在函數(shù)內(nèi)部發(fā)出調(diào)用自身的操作。遞歸算法：直接或者間接地調(diào)用自身的算法。遞歸方法：通過函數(shù)或過程調(diào)用自身將問題轉(zhuǎn)換為本質(zhì)相同但規(guī)模較小的子問題的方法。2、遞歸算法的基本思想與構(gòu)成遞歸算法需要具備的兩個(gè)重要條件：（1）自身調(diào)用的語句，如s(n)=s(n-1)+n；（2）遞歸終止條件（即已解決的基礎(chǔ)問題）。如

s(1)=1。遞歸方法實(shí)際上體現(xiàn)了“以此類推”、“用同樣的步驟重復(fù)”這樣的思想，是算法和程序設(shè)計(jì)中的一種重要技術(shù)。3、

遞歸的邏輯過程

計(jì)算機(jī)執(zhí)行遞歸算法程序時(shí)，反復(fù)進(jìn)行“調(diào)用”與“返回”，先“調(diào)用”，然后“返回”。調(diào)用過程：每一次調(diào)用自身，參數(shù)值在逐漸變小，直到調(diào)用已知條件，即遞歸終止條件，調(diào)用結(jié)束。返回過程：從已知條件出發(fā)，按“調(diào)用”的逆過程，逐步求值返回。計(jì)算機(jī)高級(jí)語言中有返回語句return來指示如何返回。

返回代入

4、

遞歸算法的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：可以用簡單的程序來解決某些復(fù)雜的計(jì)算問題，源程序非常簡潔；有一些算法本質(zhì)上只有遞歸算法。缺點(diǎn)：運(yùn)算量較大，消耗較多的內(nèi)存和運(yùn)行時(shí)間，效率不高。例1.11

遞歸定義的圖形——Koch雪花曲線Koch雪花曲線，Matlab代碼%Koch雪花曲線Matlab代碼如下%Koch雪花曲線clear;t=input('迭代次數(shù)t=');p=[00;100];n=2;A=[cos(pi/3)-sin(pi/3);sin(pi/3)cos(pi/3)];fork=0:2:t;d=diff(p)/3;%差分運(yùn)算，比矩陣p少一行

m=4*n-3;%下一次的節(jié)點(diǎn)數(shù)

q=p(1:n-1,:);%每條線段的起點(diǎn)

p(5:4:m,:)=p(2:n,:);%每條線段的終點(diǎn)

p(2:4:m,:)=q+d;%每段新加入的第一個(gè)節(jié)點(diǎn)

p(3:4:m,:)=q+d+d*A';p(4:4:m,:)=q+2*d;n=m;endplot(p(:,1),p(:,2),'k');axisequalKoch雪花曲線，Matlab實(shí)例演示數(shù)學(xué)中還有許多用相同方法遞歸生成的圖形，如謝爾賓斯基三角形（Sierpinskitriangle）是一種分形，由波蘭數(shù)學(xué)家謝爾賓斯基在1915年提出。*1.3.2遞歸算法C語言程序代碼C語言中，遞歸函數(shù)一般表現(xiàn)形式是遞歸函數(shù)名f（參數(shù)n....）{if(n==初值）結(jié)果=......；else結(jié)果=遞歸表達(dá)式；return結(jié)果；}例1.12用遞歸程序設(shè)計(jì)一段求5的階乘的C語言代碼。

#include<stdio.h>//包含一個(gè)有輸入輸出的頭文件longpower(intn){longf；

//聲明定義變量f的類型if(n==1)f=1;elsef=power(n-1)*n;returnf；}main()//main是程序的主函數(shù){intn;longy;printf(“inputaIntegernumber\n”);scanf(“%d”,&n);y=power(n);printf(“%n!=%d\n”,n,y);}用遞歸計(jì)算階乘，實(shí)例演示例1.13漢諾塔的C語言遞歸算法代碼//將A基座上按從小到大疊在一起的n個(gè)圓盤移動(dòng)到C基座，B做輔助基座viodhanoi(intn,charA,charB,charC){if(n==1)move(A,1,C);//將編號(hào)為1的圓盤從A移到Celse{hanoi(n-1,A,C,B);

);//將A上編號(hào)為1至n-1的圓盤移到B，C作輔助基座move(A,n,C)//將編號(hào)為n的圓盤從A移到Chanoi(n-1,B,A,C);

);//將B上編號(hào)為1至n-1的圓盤移到C，A作輔助基座}}//漢諾塔

#include<stdio.h>voidhanoi(intn,chara,charb,charc){if(n>=1){hanoi(n-1,a,c,b);printf(“%c-->%c\n”,a,c);

hanoi(n-1,b,a,c);}}voidmain(){intn;printf("Inputthenumberofdiskes:\n“);scanf(“%d”,&n);hanoi(n,'A','B','C');}求下面兩個(gè)正整數(shù)的最大公約數(shù)：（1）求25和35的最大公約數(shù)255535718293015335∴25和35的最大公約數(shù)為5∴18和30的最大公約數(shù)為62×3=61.3.3遞歸算法舉例——求最大公約數(shù)（2）求18和30的最大公約數(shù)這是小學(xué)學(xué)過的求兩個(gè)數(shù)的最大公約數(shù)的方法——先用兩個(gè)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來。除了用這種方法外還有沒有其它方法？如何算出8251和6105的最大公約數(shù)？——輾轉(zhuǎn)相除法（歐幾里得算法）1.3.3遞歸算法舉例——求最大公約數(shù)

2、最大公約數(shù)能整除兩個(gè)整數(shù)a，b的最大整數(shù)，稱為這兩個(gè)整數(shù)的最大公約數(shù)，記作gcd(a,b)3、最大公約數(shù)的求法——輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法是公元前300年左右由古希臘數(shù)學(xué)家歐幾里得首先提出的，因而又叫歐幾里得算法。算法基礎(chǔ)……輾轉(zhuǎn)相除法步驟……第一步用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)

8251=6105×1+2146結(jié)論：8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。余數(shù)求8251和6105的最大公約數(shù)的輾轉(zhuǎn)相除法過程第二步對(duì)6105和2146重復(fù)第一步的做法

6105=2146×2+1813

同理：6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。余數(shù)完整的過程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù)思考：從右面的這個(gè)例子中可以看出計(jì)算的規(guī)律是什么？step1：用大數(shù)除以小數(shù)step2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)step3：重復(fù)step1，直到余數(shù)為0練習(xí)：用輾轉(zhuǎn)相除法求225和135的最大公約數(shù)。225=135×1+90135=90×1+4590=45×2顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù)

S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)S1，直到余數(shù)為0輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0才停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q＋r用程序框圖表示出右邊的過程求m除以n的余數(shù)rm=nn=rr=0?是否S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除