第一章算法基础

目录向量与矩阵2树6线性方程组4图与网络分析5图形变换的矩阵方法3算法基础1算法基础Chapter1

学习目标1.2掌握算法逻辑结构，能用图表示问题的算法

1.3了解递归算法思想及问题中递归实现1.1理解算法的含义、算法特征、算法的表示1.1算法

1.1.1什么是算法

最初算法（Algorism）一词出现在12世纪，是用于表示十进制算术运算的规则，18世纪，算法Algorism演变为Algorithm，算法概念有了更广的含义，任何定义明确的计算步骤都可称为算法，或者说算法是合乎逻辑、简洁的一系列步骤。现在算法通常指可以用计算机来解决某一类问题的程序或步骤。例如，现在有炒菜机，把制作一道菜的做法编写成程序，炒菜机就可以自动完成这道菜的烹饪了。做菜的步骤就可视为算法。1.1算法

1.1.2算法的特性

问题不同，解决的思路和采取的方法与步骤有针对性，对应的算法也各不相同，但各种算法有如下共同之处：首先计算机要有操作对象，通过输入，给予计算机问题所涉及的对象；最后要能得到运行结果，有输出；在输入与输出之间是具体的方法步骤，这些方法步骤必须是确定的、正确的、有限的、有效的、通用的。因而，运行于计算机的各种算法有如下特征：1.1算法

1.1.2算法的特性

输入输出确定性正确性有限性有效性通用性1.1.2算法的特性算法过程从序列第一项开始，并把序列第一项设为临时最大值max的初始值，接着逐项检查，如果有一项超过max，就把max更新为这一项的值，检查到序列的最后一项结束。算法每进行一步要么是比较max和这项的大小，要么是更新max的值，所以每一步操作都是确定的，能保证max是已检查过的最大整数，结果是正确的。如果序列包含n个整数，经过n-1次比较就结束，所以算法步骤是有限的、有效的。这个算法可以用于求任何有限整数序列问题的最大元素，所以它是通用的。例1.1找出计算机软件专业录取的新生中高考总分的最高分。这个问题等价于求有限整数序列中最大值的算法。算法步骤：输入是软件专业所有新生的高考成绩输出是高考最高分1.1算法

1.1.3算法的表示自然语言程序框图N-S图伪代码计算机语言又叫流程图，是由一些规定的图形、流程线和文字说明来直观描述算法的图形。1、程序框图例1.2

画出例1.1的算法的流程图（图1-1）

NYNY2、N-S图流程图由一些特定意义的图形、流程线及简要的文字说明构成，它能清晰明确地表示程序的运行过程。在使用过程中发现流程线不一定是必需的，为此，人们设计了一种新的流程图，它把整个程序写在一个大框内，这个大框图由若干个小的基本框图构成，这种流程图简称N-S图，N-S图是无线的流程图，又称盒图，1973年由美国两位学者I.Nassi和B.Shneiderman提出。例1.3例1.1算法的N-S图（图1-2）

YN3、伪代码（Pseudocode）伪代码是一种介于自然语言与编程语言之间的算法描述语言，让人便于理解，不依赖于语言的，用来表示程序执行过程，而不一定能编译运行的代码。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言实现。

4计算机语言（ComputerLanguage）斯蒂芬-霍金强调了21世纪编程语言的重要性，说：“无论你想揭开宇宙的秘密，还是你在第二十一个世纪只想追求一个职业生涯，基本的计算机编程是一个重要的技能，学习吧”。（史蒂芬-霍金，理论物理学家、宇宙学家）计算机语言种类非常多，总的来说可分为机器语言、汇编语言、高级语言。高级语言包含了很多编程语言。C、C++、C#、Java、VB、VC、FoxPro、Delphi…..2016流行的高级编程语言SQL全称是“结构化查询语言(StructuredQueryLanguage)”，应用于大型数据库管理系统。Java是一种计算机编程语言，拥有跨平台、面向对象、泛型编程的特性，广泛应用于企业级Web应用开发和移动应用开发。JavaScript一种直译式脚本语言，广泛用于客户端的脚本语言，最早是在HTML（标准通用标记语言下的一个应用）网页上使用，用来给HTML网页增加动态功能。C#是Microsoft公司设计，是从C和C++派生来的一种简单、现代、面向对象和类型安全的编程语言。Python（英国发音：/ˈpaɪθən）,是一种面向对象的解释型计算机程序设计语言。7月20日，IEEE发布2017年编程语言排行榜：Python高居首位。……#include<stdio.h>intmain(){ inta[100],i,n,max; printf("您要从几个数中寻找最大值：");

scanf("%d",&n); printf("\n请输入这%d个数，两数直接用空格隔开\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这组数的最大值为：%d\n",max);}例1.1算法的C语言程序运行结果例1.5例1.1算法的MATLAB语言程序

clear;clc;fprintf('请在"[]"内输入一组数：');x=input(‘x=');n=length(x);max=x(1);fori=1:nifx(i)>=maxmax=x(i);endendfprintf('max=%d',max);运行结果例1.1算法的MATLAB语言程序演示1.2算法的逻辑结构1.2.1算法的基本逻辑结构顺序结构选择结构循环结构1、顺序结构

顺序结构是指按顺序执行完一步后再执行下一步的执行结构，顺序结构在程序框图中的体现是用流程线将程序框自上而下地连接起来，按顺序执行算法步骤。AB顺序结构

2、选择结构(条件结构)

条件结构在程序框图中是用判断框来表示，判断框内写上条件，两个出口分别对应着条件满足和条件不满足时所执行的不同指令。条件PAB条件结构NY3、循环结构

在一些算法中，会出现从某处开始，按照一定条件，反复执行某一步骤，这就是循环结构。反复执行的步骤称为循环体。循环结构有三个要素：循环变量、循环体和循环终止条件。循环结构必然包含条件结构，循环结构在程序框图中是利用判断框来表示，判断框内写上条件，两个出口分别对应着条件成立和条件不成立时所执行的不同指令，其中一个要指向循环体，然后再从循环体回到判断框的入口处。循环结构有两种类型：当型和直到型。3、循环结构（图示）循环体条件PNY条件P循环体NY直到型循环结构当型循环结构4、三种基本逻辑结构的N-S图AB顺序结构AB条件P成立不成立当循环条件P成立循环体A当型循环结构当循环条件P不成立循环体A直到型循环结构1.2.2算法举例

算法分析：

第一步：输入三个系数

a,b,c；

例1.6（a）N-S图

输出没有实数根

输出x

NY

NY例1.6（b）流程图输入a,b,c

输出x

输出没有实数根NYNY例1.7中国农历60年一大轮回，按天干“甲乙丙丁戊已庚辛壬癸”和地支“子丑寅卯辰巳午未申酉戍亥”循环排列而成。天干共十个，公元纪年也是十年一周期，公元纪年除以10的余数（就是公元纪年的尾数）与天干之间有一一对应关联（如下表1）余数4567890123天干甲乙丙丁戊己庚辛壬癸表1

地支共十二个，地支12年一轮回，用公元纪年除以12，余数与地支也有一一对应关联（如表2）余数45678910110123地支子丑寅卯辰巳午未申酉戌亥表2解：N-S图输入年份yearX={甲乙丙丁戊已庚辛壬癸}Y={子丑寅卯辰巳午未申酉戍亥}i=（year-4）除以10的余数j=（year-4）除以12的余数S=i+1

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

例1.8设计一个求10！的算法算法分析：第一步：赋初值s=1,i=1

先计算1×2

1×2的结果乘以3前3个数乘积的结果再乘以4以此方式进行一个累乘循环计算过程

输入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用“二分法”设计一个求方程

的近似根的算法。二分法思想二分法是基于根的存在定理，求方程根的近似值的一种算法。二分法思想为：将函数的零点所在区间不断的一分为二，使所得的新区间不断变窄，两个端点逐步逼近零点，达到精度要求为止。根的存在定理设函数f(x)在闭区间[a,b]上连续，且f(a)*f(b)<0，则区间(a,b)内至少有一点c，使得f(c)=0。c称为函数f(x)的零点。这个定理可以帮助我们确定方程根的大致范围，或判断方程在某一范围内是否有解。算法分析第一步：输入……

NYYYNN流程图1.3递归算法小游戏：（汉诺塔或梵塔问题）有3个基座A、B、C，开始时A基座上有n个大小不同盘子，大盘子在下小盘子在上叠在一起，问：要把A基座上的n个盘子移到C基座上，每次只能移动一个，并且移动过程中始终保持大的盘子在下小的盘子在上，能做到吗？要移动几次？设n个大小不同的盘子按规则移动，需要移动f(n)次，请动手做一做:f(1)=

f(2)=

f(3)=

f(4)=

从移动的过程中，你发现了f(n)的规律吗？汉诺塔演示1.3.1什么是递归

各种计算机高级语言都有函数的嵌套调用和递归调用，什么是递归呢？f(n)=2f(n-1)+1就是递归定义的函数，f(n)与f(n-1)本质上是相同的函数。自己调用自己，称为递归。自己调用自己的函数，称为递归函数。递归函数包括直接递归和间接递归。

例1.10

1、什么是递归与递归函数类似的说法，还有递归调用：在函数内部发出调用自身的操作。递归算法：直接或者间接地调用自身的算法。递归方法：通过函数或过程调用自身将问题转换为本质相同但规模较小的子问题的方法。2、递归算法的基本思想与构成递归算法需要具备的两个重要条件：（1）自身调用的语句，如s(n)=s(n-1)+n；（2）递归终止条件（即已解决的基础问题）。如

s(1)=1。递归方法实际上体现了“以此类推”、“用同样的步骤重复”这样的思想，是算法和程序设计中的一种重要技术。3、

递归的逻辑过程

计算机执行递归算法程序时，反复进行“调用”与“返回”，先“调用”，然后“返回”。调用过程：每一次调用自身，参数值在逐渐变小，直到调用已知条件，即递归终止条件，调用结束。返回过程：从已知条件出发，按“调用”的逆过程，逐步求值返回。计算机高级语言中有返回语句return来指示如何返回。

返回代入

4、

递归算法的优缺点

优点：可以用简单的程序来解决某些复杂的计算问题，源程序非常简洁；有一些算法本质上只有递归算法。缺点：运算量较大，消耗较多的内存和运行时间，效率不高。例1.11

递归定义的图形——Koch雪花曲线Koch雪花曲线，Matlab代码%Koch雪花曲线Matlab代码如下%Koch雪花曲线clear;t=input('迭代次数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;%差分运算，比矩阵p少一行

m=4*n-3;%下一次的节点数

q=p(1:n-1,:);%每条线段的起点

p(5:4:m,:)=p(2:n,:);%每条线段的终点

p(2:4:m,:)=q+d;%每段新加入的第一个节点

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实例演示数学中还有许多用相同方法递归生成的图形，如谢尔宾斯基三角形（Sierpinskitriangle）是一种分形，由波兰数学家谢尔宾斯基在1915年提出。*1.3.2递归算法C语言程序代码C语言中，递归函数一般表现形式是递归函数名f（参数n....）{if(n==初值）结果=......；else结果=递归表达式；return结果；}例1.12用递归程序设计一段求5的阶乘的C语言代码。

#include<stdio.h>//包含一个有输入输出的头文件longpower(intn){longf；

//声明定义变量f的类型if(n==1)f=1;elsef=power(n-1)*n;returnf；}main()//main是程序的主函数{intn;longy;printf(“inputaIntegernumber\n”);scanf(“%d”,&n);y=power(n);printf(“%n!=%d\n”,n,y);}用递归计算阶乘，实例演示例1.13汉诺塔的C语言递归算法代码//将A基座上按从小到大叠在一起的n个圆盘移动到C基座，B做辅助基座viodhanoi(intn,charA,charB,charC){if(n==1)move(A,1,C);//将编号为1的圆盘从A移到Celse{hanoi(n-1,A,C,B);

);//将A上编号为1至n-1的圆盘移到B，C作辅助基座move(A,n,C)//将编号为n的圆盘从A移到Chanoi(n-1,B,A,C);

);//将B上编号为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');}求下面两个正整数的最大公约数：（1）求25和35的最大公约数255535718293015335∴25和35的最大公约数为5∴18和30的最大公约数为62×3=61.3.3递归算法举例——求最大公约数（2）求18和30的最大公约数这是小学学过的求两个数的最大公约数的方法——先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来。除了用这种方法外还有没有其它方法？如何算出8251和6105的最大公约数？——辗转相除法（欧几里得算法）1.3.3递归算法举例——求最大公约数

2、最大公约数能整除两个整数a，b的最大整数，称为这两个整数的最大公约数，记作gcd(a,b)3、最大公约数的求法——辗转相除法辗转相除法是公元前300年左右由古希腊数学家欧几里得首先提出的，因而又叫欧几里得算法。算法基础……辗转相除法步骤……第一步用两数中较大的数除以较小的数，求得商和余数

8251=6105×1+2146结论：8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。余数求8251和6105的最大公约数的辗转相除法过程第二步对6105和2146重复第一步的做法

6105=2146×2+1813

同理：6105和2146的最大公约数也是2146和1813的最大公约数。余数完整的过程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0显然37是148和37的最大公约数，也就是8251和6105的最大公约数思考：从右面的这个例子中可以看出计算的规律是什么？step1：用大数除以小数step2：除数变成被除数，余数变成除数step3：重复step1，直到余数为0练习：用辗转相除法求225和135的最大公约数。225=135×1+90135=90×1+4590=45×2显然45是90和45的最大公约数，也就是225和135的最大公约数

S1：用大数除以小数S2：除数变成被除数，余数变成除数S3：重复S1，直到余数为0辗转相除法是一个反复执行直到余数等于0才停止的步骤，这实际上是一个循环结构。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q＋r用程序框图表示出右边的过程求m除以n的余数rm=nn=rr=0?是否S1：用大数除以小数S2：除数变成被除