北京大学计算概论课件第七讲-算法

第七讲

算法北京大学信息学院2013年10月2026/5/14北京大学2主要内容了解算法的基本概念掌握描述算法的三种基本结构学会算法的流程图描述介绍几种基本算法难、有意思、数学、编程的基础2026/5/14北京大学31算法的基本概念计算机是一个计算工具，它本身不能主动帮助我们做任何事情，需要我们告诉它如何进行计算。程序设计就是要告诉计算机如何进行计算的。这与我们中学时代的数学解题过程是一样的，只不过描述的手段有所变化而已。2026/5/14北京大学41算法的基本概念1984年图灵奖获得者瑞士科学家尼克劳斯·沃斯（NiklausWirth，Pascal语言的发明者和结构化程序设计创始者）1976年出版了《算法+数据结构=程序设计》一书，提出了著名的公式：“程序＝数据结构＋算法”。程序：刻画现实世界，解决现实世界中的问题程序设计语言：实现的工具算法：问题的解的描述数据结构：现实世界的数据模型程序就是在数据的某些特定的表示方式和结构的基础上对抽象算法的具体表述。一行行代码、语言2026/5/14北京大学51算法的基本概念算法的定义设计程序的目的是为了求解问题，为解决一个问题所采取的方法和步骤，就称为“算法”算法是一个由一组严格定义的动作组成的过程，给定一个出始状态，这个过程能够结束在一个确定终止状态。大多数算法都可以用程序实现。常用算法一般都被实现为算法库，供程序员调用。算法的基本思想如何把大象关在冰箱里?分3步：第一步：打开冰箱门;第二步：把大象推进冰箱;第三步：关上冰箱门;2026/5/14北京大学71算法的基本概念一个实例：找出一组正整数中的最大的数2026/5/14北京大学81算法的基本概念逐步求解，定义算法的动作S1:设Largest为第一个数S2:若第二个数比Largest大，则设Largest为第二个数S3:若第三个数比Largest大，则设Largest为第三个数S4:若第四个数比Largest大，则设Largest为第四个数S5:若第五个数比Largest大，则设Largest为第五个数2026/5/14北京大学91算法的基本概念算法动作精化S0:设Largest为0S1:若当前数比Largest大，则设Largest为当前数S2:若当前数比Largest大，则设Largest为当前数S3:若当前数比Largest大，则设Largest为当前数S4:若当前数比Largest大，则设Largest为当前数S5:若当前数比Largest大，则设Largest为当前数2026/5/14北京大学101算法的基本概念算法范化从N个正整数中找出最大数的通用算法循环结构S0:设Largest为0，当前位置p为0S1:若当前数比Largest大，则设Largest为当前数S2:若p比N小，则p增加1，并返回S1；否则返回Largest2026/5/14北京大学111算法的基本概念算法的基本性质通用性：即适用于某一类问题中的所有个体，而不只是用来解决一个具体的问题。有效性：即应有明确的步骤一步一步地引导计算的进行。确定性：即每个步骤都是机械的、有明确定义的动作，不需要计算者临时动脑筋。有限性：对满足算法要求的输入数据，算法应在有限多步内结束，并给出明确的计算结果。离散性：算法的输入数据及输出数据都应是离散的符号。2026/5/14北京大学121算法的基本概念算法的基本要求正确易维护（可读，易修改）方便使用高效速度快运行时间少，时间复杂度低占用内存少，空间复杂度低算法的效率可以测试，用大量输入数据测量运行的时间和占用的内存，通过比较判别和选择效率高的算法。更重要的是可以在编程前进行分析和估计（算法分析），即理论的计算，给出事前的判断。高斯，查字典2026/5/14北京大学131算法的基本概念不了解施加于数据上的算法就无法决定如何构造数据；反之，算法的结构和选择却常常在很大程度上依赖于作为基础的数据结构。简而言之，程序的构成（算法）与数据结构是两个不可分割地联系在一起的问题。2026/5/14北京大学142描述算法的三种基本结构计算机科学家已经证明，只使用如下三种结构，就可以描述任何算法，且算法结构优良顺序结构（Sequence）分支结构（Decision）循环结构（Repetition）每一种基本结构分别只有一个入口和一个出口2026/5/14北京大学152.1顺序结构顺序结构：动作（语句）序列，顺序执行，每个动作只执行一次，各动作对执行结果产生的影响是独立的动作1动作2动作3…动作n动作1动作2动作3…动作n2.1顺序结构按部就班先来后到循序渐进接连不断起床刷牙吃早饭上课吃中饭午休上课吃晚饭晚自习洗漱睡觉2026/5/14北京大学16现实生活中的示例2026/5/14北京大学172.2分支结构分支结构：根据条件判断执行什么动作（序列），最多只有一个动作（序列）被执行如果条件成立则动作（或动作序列）1否则动作（或动作序列）2分支结束条件成立？动作（序列）1动作（序列）2是否2.2分支结构如果分数达到一本线录取到一本大学如果分数达到二本线录取到二本大学如果分数达到三本线录取到三本大学如果分数达到专科线录取到专科学校否则落榜选择二选一条条道路通罗马如果明天天晴小明就去郊游否则就在家里看书2026/5/14北京大学18现实生活中的示例2026/5/14北京大学192.3循环结构循环结构：重复执行一系列动作当条件成立做动作1动作2…动作n循环结束处条件成立？动作1动作n…是否2.3循环结构周而复始转圈轮回（第几周）如果小于20周如果是周一到周五上课否则休息放寒假2026/5/14北京大学20现实生活中的示例一个循环结构示例：

求1~1000的平方和S←0j←1S←S+j*jj←j+1j>1000打印SYesNo三种基本控制结构可相互组合和嵌套使用，形成更为复杂的控制，完成各种复杂的工作。开始结束2026/5/14北京大学223用流程图表示算法算法是让人来理解的，因此需要有效的算法表示机制自然语言表示法伪代码表达法流程图表示法2026/5/14北京大学233用流程图表示算法流程图显示了程序的流程判断结构。通常包含如下符号：开始和结束流程线输入和输出处理（动作）条件判断开始/结束处理（动作）流程线输入/输出条件判断2026/5/14北京大学243用流程图表示算法判断x>0y=xy=-xYesNo2026/5/14北京大学253用流程图表示算法循环k<10动作k=k+1YesNo动作k=0吃蟹黄汤包理解算法结构问题1：吃过吗？口诀：轻轻提,慢慢移,先开窗,再喝汤。吃一只蟹黄汤包的“算法”顺序很重要：将包子从蒸笼中轻轻提起，andthen将包子慢慢移动到面前的小碟子中，andthen在包子的正上方咬开一个小口，andthen通过小口吸食包子里的汤(当心别烫着)，andthen将包子送入口中。完成！问题2：你如何确保过程无误？假如我们认为在步骤4和5执行前要确保前面的结果是正确的，可以在相应的地方设个“监视哨”–“guard”。问题3：但是我们并不只是吃一只，那怎么办呢？策略一：控制数量假如规定吃8只：开始设一个计数器，并将其值设定为0。吃一只汤包计数器值加1，并判断其是否为8否是结束注意：计数器的初始值策略二：吃饱为止是否已饱？是否问题4：如果即使饱了，也希望至少品尝一只，该怎么办？有人知道饱不饱，但有人不知道！开始要吃汤包的人不到5岁吗？是选用策略1选用策略2否结束问题7：如果要判断的不止是两种可能，那怎么办？分类定量控制开始要吃汤包的人不到5岁吗？否参数设为2是结束要吃汤包的人不到60岁吗？参数设为8是参数设为4否选用策略1(带参数)2026/5/14北京大学343用流程图表示算法判断闰年能被4整除且不能被100整除；能被400整除2026/5/14北京大学353流程图表示算法判断闰年能被4整除且不能被100整除；能被400整除用C语言实现算法2026/5/14北京大学364.1基本算法–

日期判断问题：给定年月日，判断该日是这年的第几天。求解按月累加天数区分大、小月区分闰年、平年初始化：total=0,i=1开始total=total+31i<month？N结束Yi=i+1输入：year,month,dayi是大月？i是小月？total=total+30YNYNyear是闰年？total=total+29total=total+28total=total+day输出：total4.1基本算法–

日期判断（Ｃ语言实现）2026/5/14北京大学38intyear,month,day,total,i;scanf(“%d%d%d”,&year,&month,&day);total=0;for(i=1;i<month;i++){if(i==1||i==3||i==5||i==7||i==8||i==10||i==12){total=total+31;}if(i==4||i==6||i==9||i==11){total=total+30;}if(i==2){if((year%4==0&&year%100!=0)||year%400==0)total=total+29;elsetotal=total+28;}}total=total+day;2026/5/14北京大学394.1基本算法-求平方根求一个数的平方根：

x=迭代公式

x1=1xn+1=(xn+a/xn)/2

迭代计算，直到xn+1–xn的绝对值小于误差要求，例如小于0.00001，即保留小数点后5位。开始初始化：x2=1x1=x2x2=(x1+a/x1)/2x2-x1的绝对值

小于0.00001？N结束Y输出x2输入数a2026/5/14北京大学404.1基本算法-求平方根(C语言实现)2026/5/14北京大学414.1基本算法–

素数判定与

歌德巴赫猜想问题：判定一个数是否为素数求解除2之外，偶数都不是素数对于一个奇数P，看它是否能被某个大于1，小于P的奇数整除，如果存在，则P不是素数，否则P就是素数初始化：isPrime=ture,i=3开始p能否被２整除？N结束Yi=i+2输入：pi<half？p能否被i整除？YNYNP等于２吗？half=pisPrime=falseYNisPrime=falsehalf=p/2half=sqrt(p)输出isPrime2026/5/14北京大学43intisPrimeNumber(intp){ inti,half,isPrime＝1; if(p%2==0){ if(p==2){ returnisPrime; }isPrime=0; returnisPrime; }

half=p;//half=p/2; for(i=3;i<=half;i=i+2){ if(p%i==0){ isPrime=0; break; } } returnisPrime;}4.1基本算法–

素数判定与

歌德巴赫猜想2026/5/14北京大学444.1基本算法–

素数判定与

歌德巴赫猜想歌德巴赫猜想：任何大于6的偶数都能分成两个奇素数之和问题分析对一个偶数N，把它分解成两个奇数的和分别验证这两个数是否为素数，如果都是，则N满足歌德巴赫猜想初始化：i=3开始结束i=i+2输入：ni<=half？i和n-i是否都为素数？YYNhalf=n/2N4.1基本算法–

素数判定与

歌德巴赫猜想输出：n为素数i和

n-i之和2026/5/14北京大学46判断一个偶数是否满足歌德巴赫猜想4.1基本算法–

素数判定与

歌德巴赫猜想voidGoldbachConjecture(intn){ inthalf=n/2;//求出半数n/2待用

inti;//循环变量

intisPrime1,isPrime2;//临时变量

for(i=3;i<=half;i=i+2) { isPrime1=isPrimeNumber(i); isPrime2=isPrimeNumber(n-i); if(isPrime1&&isPrime2) { printf("%d=%d+%d\n",n,i,n-i); break; } }}2026/5/14北京大学474.2基本算法–

排序排序（Sort）是指对一些数据的重新组织，使得数据由大到小（降序）或者由小到大（升序）存储。排序是很一种基本的要求。我们所感兴趣的是如何寻找到一个好（计算速度快或占用内存少）的办法来进行排序。选择排序冒泡排序2026/5/14北京大学484.2排序——选择排序选择排序，Selectionsort选身高，第一第二。。。==从余下的选最高数据列表被分为两个子列表：已排序和未排序。找到未排序列表中值最小（或最大）的元素，并把它和未排序列表中的第一个元素进行交换。2026/5/14北京大学494.2选择排序——示例（续）2026/5/14北京大学504.2选择排序——示例2026/5/14北京大学514.2选择排序——算法、程序初始化：wall=0开始找到未排序列表中的最小元素与未排序列表中

第一个元素交换是否还有

未排序元素？N结束Ywall=wall+1/*先假设A[i]是最小的*/2026/5/14北京大学524.2排序——冒泡排序冒泡排序，Bubblesort数据列表被分为两个子列表：已排序和未排序。未排序列表中最小（或最大）的元素通过冒泡的形式（从后往前冒泡）从未排序列表中交换到已排序列表中。2026/5/14北京大学534.2冒泡排序——示例比较比较并交换冒泡的过程2026/5/14北京大学544.2冒泡排序——示例（续）2026/5/14北京大学554.2冒泡排序——示例（续）2026/5/14北京大学564.2冒泡排序——算法、程序初始化：wall=0开始还有未排序的数？N结束Y交换相邻数还有未冒泡的数？比较相邻数YNYN4.2基本算法–

排序演示：排序舞2026/5/14北京大学572026/5/14北京大学584.2基本算法–

排序各种排序方法简介：就地排序算法（不增加新的存储空间）1、插入排序法（InsertSort）将一个数插入到序列中的合适位置。2、选择排序法（SelectionSort）每次把最小（大）的元素交换到最前面。3、冒泡排序法（BubbleSort比较并交换相邻的元素，直到所有元素都被放到合适的位置。4、堆排序（HeapSort）一种效率非常高，但原理较复杂的排序方法。5、快速排序算法（QuickSort）一种通常情况下效率非常高，但原理较复杂的排序2026/5/14北京大学594.3基本算法–

搜索搜索（Search）是利用给出的关键值，在一个数据集合或数据序列中找出与关键值匹配的一个或一组数据的过程。顺序查找：最简单的查找算法。从数据序列的第一个数据开始，逐个与关键值比较，直到找到一个或所有的匹配数据为止（也可能找不到）。顺序查找不要求待查找的数据序列已经排好序。但当待查找数据序列中数据比较多时，顺序查找的效率将十分低。二分查找：二分查找可以提高查找效率，但要求待查找的数据序列已经排好序。以序列