计算思维导论（第2版）课件：算法基础

算法基础对算法的认识算法是计算机科学研究的一个重要领域，也是许多其他计算机科学技术的基础。所谓的算法，不只是数学，也不限于计算机，它是指可复制的，解决问题的一系列步骤。“视代码如诗词，勿要做无所谓的堆砌。”——伊利亚·多尔曼（IlyaDorman）“写代码时，每次都要告诉自己：最后负责维护代码的，会是一个知道你住在哪的变态暴力狂。”——约翰·伍德（JohnWoods）Algorithm问题求解发现问题数学模型数据结构算法设计编程实现231454.1算法和算法描述算法：解决问题的方法和步骤数据结构：数据的存储组织方式

尼古拉斯·沃斯瑞士苏黎世大学Pascal之父数据结构

+算法=程序数据结构：描述数据算法：对数据进行操作#include<stdio.h>intmain(){return0;}“程序=数据结构+算法”的体现inta,b;scanf(“%d%d”,&a,&b);printf(“%d%d”,a,b);c=a;a=b;b=c;定义所需的变量输入数据输出数据处理数据核心之一设计数据结构核心之二设计算法伪控制结构基本操作算法要素算术运算关系运算逻辑运算数据传输顺序结构选择结构循环结构有穷性确定性输入输出可行性算法的特性常量和变量变量是程序运行过程中，取值可以改变的量。它与计算机的内存单元相对应。通常变量名中只能出现数字、字母或下划线，而且变量名的首字符不能是数字。常量是指程序执行过程中其值不发生改变的量。例如，数字、字符串、逻辑性常量True和False。算法描述自然语言描述流程图描述伪代码描述020103交换两个数两碗饭，如何交换？任务：交换两个整数算法描述：

step1：读入两个非负整数a，b的值

step2：将a的值赋值给t

step3：将b的值赋值给a

step4：将t的值赋值给b

step5：输出a，b的值abt优点：简单容易缺点：容易产生二义性图形符号名称含义起止框表示算法的开始或结束处理框表示处理或运算等功能输入/输出框表示进行输入/输出操作判断框根据给定的条件是否满足决定执行两条路径中的某一条路径控制流表示算法执行的路径，箭头代表方向任务：交换两个整数算法：step1：读入两个非负整数a，b的值

step2：将a的值赋值给t

step3：将b的值赋值给a

step4：将t的值赋值给b

step5：输出a，b的值a=1b=2t=aa=bb=toutputa,b顺序结构：传统流程图顺序结构：N-S流程图选择结构：传统流程图选择结构：双分支N-S流程图循环结构：传统流程图循环结构：N-S流程图运算符号说明符号表示示例赋值符号←或=a←5，b=5算术运算符号+、-、*、/、mod（整数取余）、^（乘方）a+b，amod

b，a^b关系运算符号>、>=、<、<=、=、<>（不等于）a>b、a<>b逻辑运算符号and（与）、or（或）、not（非）not（a>=banda>0or

a>0）输入和输出input、output（或read、print）input

a，output

a选择结构如果P成立则A否则B：ifPthenAelseBif

A=B

then

AelseB循环结构当型循环：whilePDoAFor型循环：fori=初值to

终值[stepn]DoAwhilei<=100dos=s+ii=i+1endwhilefori=1to100s=s+iendfor过程（函数）procedureName（）functionName（参数列表）……endprocedureendfunctionprocedurepi（）functionswap（a，b）arccos(-1)c=aendprocedurea=bb=cendfunction任务：交换两个整数算法：

step1：读入两个非负整数a，b的值

step2：将a的值赋值给t

step3：将b的值赋值给a

step4：将t的值赋值给b

step5：输出a，b的值//SwapAlgorithminputa,bt=aa=bb=toutputa,b数组数组就是一组有序数据的集合定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法按照顺序排列的一列数一组有序数据的集合数列数组等差数列、摆动数列、……一维数组、二维数组、……a1,a2,a3…,an一维数组：a[1],a[2],……,a[n]所有数据同一个数据类型所有数据同一个数据类型数据之间有（位置）顺序数据之间有（位置）顺序数据从1开始计算下标数据从0或1开始计算下标定义类型特点格式找规律，写通项公式一次输入，多次使用作用1、下面伪代码输出的结果是：a[5]={1,2,3,4,5}outputa[1]outputa[2]outputa[3+1]outputa[5]12、下列伪代码输出的结果是：a[5]={1,2,3,4,5}s=0fori=1to5s=s+a[i]endforavg=s/5outputavg2453循环遍历数组元素算法分析1）求5个数平均值，可以转5圈进行累加求和2）哪些数大于高于平均值呢？

需要再次使用这5个数，依次和平均值比较3）需用到数组，一次输入，多次使用。任务：高于平均数个数问题求：5个整数中大于平均数的个数，写出伪代码和画出流程图。定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法a[5]=0,s=0,num=0fori=1to5//累加求和求均值inputa[i]s=s+a[i]endforavg=s/5fori=1to5//统计高于均值个数ifa[i]>avgthennum=num+1endifendforoutputnum算法分析1）循环10圈，求出总分、最高分、最低分。2）总分中减去最高分和最低分。3）求去掉最高分和最低分的平均分。任务：体育计分问题

10个评委给运动员打分，去掉一个最高分，去掉一个最低分，求选手最终得分（去掉最高分最低分后的平均分）。定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法a[10]=0,s=0fori=1to10//输入且累加求和inputa[i]s=s+a[i]endfors=s-max–min//计算且输出均值avg=s/_____outputavgmax=_________//求最大最小值min=a[1]fori=2to10if________________thenmax=a[i]ifa[i]<minthenmin=a[i]endfora[i]>maxa[1]8数组&循环数组作用一次输入，多次使用数组示例①统计高于平均值个数②体育计分问题数组特点相同的数据类型数据之间有顺序下标从0或1开始数组的访问循环遍历数组元素生活中的数组①组团旅游②统计购物小票③报菜名34562数组一组有序数据的集合1函数函数就是模块化设计将不同功能的函数搭建在一起构成系统定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法类型系统预定义（三角函数，……）用户自定义主调函数与被调函数：A，B两个函数。A函数调用了B函数，A叫做主调函数，B叫做被调函数。注意事项：（1）函数名（2）函数参数（3）函数返回值过程/函数123456主调函数格式：变量=Name（实参表列）被调函数格式：functionName(形参表列)…endfunctionA函数：…调用B函数…B函数：………1、下面伪代码输出的结果是：

主调函数：a=2b=cube(a)outputb

被调函数：functioncube(x)returnx^3endfunction2、下列伪代码输出的结果是：

主调函数：a=1，b=2c=max（a，b）outputc

被调函数：functionmax（x，y）ifx>ythenreturnxelsereturnyendifendfunction28过程/函数算法分析怎么用户自定义函数呢？1）函数名oddeven2）函数参数：x3）函数返回值：0/1任务：奇偶问题自定义一个函数，功能是判断一个整数是奇数还是偶数，请写出流程图和伪代码。定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法被调函数框架：functionoddeven(x)……endfunction主调函数：flag=oddeven(m)主调函数：inputmflag=odd_even(m)ifflag=0thenoutput"even"elseoutput"odd"endif被调函数：functionodd_even(x)ifxmod2=0thenreturn0elsereturn1endfunction算法分析怎么定义自定义函数呢？1）函数名area2）函数参数：r3）函数返回值：s任务：圆面积问题自定义一个函数，功能是给定一个圆的半径r，求出圆的面积，请写出流程图和伪代码。定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法被调函数框架：functionarea(r)……endfunction主调函数：s=area(r)主调函数：inputrs=____________outputs被调函数：functionarea(r)returnendfunctionarea(r)3.14*r^2函数函数名函数参数函数返回值主调函数与被调函数主调函数：变量=函数（实参）被调函数：function函数名（形参）

…endfunction函数类型系统预定义函数用户自定义函数实参与形参主调函数：实参被调函数：形参生活中的函数①三角函数、指数对数函数②excel函数③底薪+提成的正比例函数34562函数就是模块化设计1时间复杂度需要消耗的时间资源空间复杂度需要消耗的空间资源正确性：准确无误健壮性：容错力强可读性：易理解算法的特征有穷性、确定性可行性、输入和输出算法描述自然语言、流程图、伪代码算法的要素基本操作控制结构发现算法发现问题、数学模型、数据结构（数组等）、算法设计、编程实现（函数等）算法评价时间复杂度、空间复杂度正确性、健壮性、可读性34562什么是算法？解决问题的方法和步骤14.2经典算法枚举法010203040506070809010203040506070809枚举法贪心算法动态规划分治法递推法递归法迭代法查找排序算法策略10回溯法10细数一下你身边的枚举法找出100以内的素数忘记密码？配菜方案（一荤一素一饮品）枚举法：穷举法、暴力法、蛮力法什么是枚举法？根据问题的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到将全部情况验证完毕。枚举法的思想枚举法的设计1）找出枚举范围2）找出约束条件枚举法的实现循环+条件判断任务1：百钱买百鸡鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法鸡雏三，值钱一鸡翁一值钱五鸡母一值钱三设要买x只公鸡，y只母鸡，z只小鸡，列方程：枚举法的设计1）找出枚举范围2）找出约束条件算法分析x+y+z=100①5x+3y+z/3=100②x∈[0,20]y∈[0,33]z∈[0,99]约束条件枚举范围x=01…20y=01…33z=03…99x∈[0,20]y∈[0,33]z∈[0,99]枚举范围指定取值范围内，穷尽所有可能后，选取可行方案的过程枚举法的实现循环+条件判断forx=0to20fory=0to33forz=0to99step3ifx+y+z=100and5x+3y+z/3=100thenoutputx,y,zendforendforendfor任务2：猜字问题雨水淋湿了算术书的一道题，8个数字只能看清3个，第一个数字虽然看不清，但可看出不是1。求其余数字是什么？[□*(□3+□)]2=8□□9定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法任务2：猜字问题雨水淋湿了算术书的一道题，8个数字只能看清3个，第一个数字虽然看不清，但可看出不是1。求其余数字是什么？[□*(□3+□)]2=8□□9定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法1）枚举范围：A：2～9B、C：1～9D、E：0～9算法分析2）约束条件：(A*(B*10+3+C))^2=8009+D*100+E*10forA=2to9forB=1to9forC=1to9forD=0to9forE=0to9if(A*(B*10+3+C))^2=8009+D*100+E*10thenoutputA,B,C,D,Eendforendforendforendforendfor枚举结构特点循环+选择适用范围可能解个数不多的情况算法设计步骤找出枚举范围找出约束条件枚举优缺点优点：直观形象缺点：效率低应用举例①找钥匙②

验钞机验钞③

品酒员品酒34562枚举的概念一一列举，逐个检验1递推法如何求等差数列、等比数列的通项、以及数列和？1）1,3,5,7,9,11,…,？2)1,3,9,27,81,…,？（1）等差：通项：an=a1+（n-1）*d=2n-1求和：S=(a1+an)*n/2=n^2（2）等比：通项：an=a1*q^(n-1)=1*3^(n-1)=3^(n-1)求和：S=a1*(1-q^n)/(1-q)=1*(1-3^n)/(1-3)=-（1-3^n）/2方法：通项公式与求和公式切0刀——1块切1刀——2块切2刀——4块切3刀——7块切4刀——11块?你还能找到通项吗？切蛋糕（垂直切、且要求块数最多）你还能找到通项吗？解决方案：1）相邻项之间的关系ai=ai-1+i（第i刀块数=上一刀块数+本次切的刀数）切蛋糕（要求块数最多）切0刀——1块切1刀——2块切2刀——4块切3刀——7块切4刀——11块?2）用迭加法求通项公式a0=1a1=a0+1……+)an=an-1+n-------------------an=1+（1+2+…+n）=1+n*(n+1)/2010203040506070809010203040506070809枚举法贪心算法动态规划分治法递推法递归法迭代法查找排序算法策略10回溯法10从问题的规模（项数）出发，找到大规模问题与小规模问题之间的关系（或前后项之间的关联），然后根据他们之间的联系逐步求解。这种在规定的初始条件下，找出后项对前项的依赖关系的操作，称为递推。什么是递推？递推公式表示某项和它前面若干项的关系式就叫递推公式。边界条件初始条件称为边界条件。递推法设计递推法实现1）找出递推规律，写出递推公式2）根据初始条件，顺推或逆推1）循环写入数组，非递归求解2）根据递推公式，递归求解递推法分类顺推和逆推两种递推法特点1）问题可以划分成多个状态。2）除初始状态外，其它各状态都可用固定的递推关系式来表示。任务：兔子繁殖问题这是一个古典数学问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第3个月后每个月又生一对兔子。假设所有的兔子不死，问第20月兔子总数为多少？定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法任务：兔子繁殖问题算法分析月数小兔子对数中兔子对数老兔子对数兔子总数110012010131012411135212563238……………定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法任务：兔子繁殖问题算法分析这就是著名的斐波那契数列。1,1,2,3,5,8,13,…递推法设计1）找出递推规律，写出递推公式2）根据初始条件，顺推或逆推递推式：an=an-1+an-2初始条件：a1=1，a2=1a[20]=0,a[1]=1,a[2]=1inputnfori=3tona[i]=a[i-1]+a[i-2]endforoutputa[n]设f(n)函数求Fibonacci递归式：f(n)=f(n-1)+f(n-2)递归出口：n=2orn=1界函数：f(n-1),f(n-2)非递归实现递归实现被调函数functionf(n)ifn=2orn=1thenreturn1elsereturnf(n-1)+f(n-2)endifendfunction主调函数inputnf=f(n)outputf递推式：an=an-1+an-2初始条件：a1=1，a2=1任务：猴子吃桃子猴子第一天摘下若干个桃子，当即吃下了一半，还不过瘾，有多吃了一个。第2天早上又将剩下的桃子吃掉了一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，就只剩下一个桃子了。求第1天共摘了多少个桃子？定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法任务：猴子吃桃子算法分析天数桃子数量10194810722…1?递推法设计1）找出递推规律，写出递推公式2）根据初始条件，顺推或逆推递推式：an-1=(an+1)*2初始条件：a10=1设monkey(n,f)函数求第n天吃桃数量f递推式：monkey(n,f)=monkey(n-1,2*(f+1))递归出口：n>1界函数：monkey(n-1,2*(f+1))被调函数：functionmonkey(n,f)ifn>1thenf=2*(f+1)monkey(n-1,f)endifendfunctiona[10]=1i=10whilei>=2doa[i-1]=2*(a[i]+1)i=i-1endwhileoutputa[1]递推式：an-1=(an+1)*2初始条件：a10=1主调函数：f=1monkey(10,f)outputf非递归实现递归实现算法设计步骤写递推公式顺推或逆推递推优缺点优点：可避开求通项公式的麻烦缺点：递推公式固定递推特点问题可划分为多个状态，除初始状态外，其他均可写递推公式递推实现①循环+数组②递归调用应用举例①猜年龄②

碟中谍、案中案、

环环相扣34562递推的概念前项后项有特定关系1递归法细数一下你身边的递归法文字递归分形图形德罗斯特效应010203040506070809010203040506070809枚举法贪心算法动态规划分治法递推法递归法迭代法查找排序算法策略10回溯法10什么是递归？递推+回溯递归法的思想在调用一个函数的过程中又出现直接或间接地调用该函数本身，称为函数的递归调用。如：sin(sin(30*pi()/180))递归法的设计递归法的实现1）缩小规模：将原问题转换为性质相似的独立子问题2）递归出口：有递归终止的条件递归法三要素条件判断+函数调用1）递归式：递归公式，或递归函数2）递归出口：递归终止条件3）界函数：问题规模变化的函数，保证递归规模向出口靠拢，

类似循环中的步长。functiontell_story()

if(讲话被打断)then

故事结束;else

从前有座山;……;

tell_story();

endifendfunction递归出口递归式任务1：求自然数n的阶乘一个正整数的阶乘是所有小于及等于该数的正整数的积，并且0的阶乘为1。定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法数学定义：n！=1*2*3*……(n-1)*nn！=n*(n-1)!递归法的设计1）缩小规模：独立的相似子问题2）递归出口：递归结束算法分析以n=4为例fact(4)=4*fact(3)fact(3)=3*fact(2)fact(2)=2*fact(1)fact(1)=1fact(1)=1fact(2)=2fact(3)=6fact(4)=24递推回溯递归出口缩小规模主调函数：inputnoutputfact(n)被调函数：functionfact(n)ifn=1thenreturn1elsereurnn*fact(n-1)endifendfunction任务2：走楼梯问题小明走路喜欢蹦蹦跳跳，他最喜欢在楼梯上跳来跳去。但年幼的他一次只能走上一阶或者一下子蹦上两阶。现在一共有N阶台阶，请你计算一下小明从第0阶到第N阶共有几种走法？定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法算法分析设f(n)为小明上楼梯的走法当n=1时，1种走法当n=2时，2种走法f(n)=f(n-1)+f(n-2)n级台阶的走法=先走一级后，n-1级台阶的走法+先走两级后，n-2级台阶的走法递推法（数组实现）：

a[10]={1,2}fori=3to10step1a[i]=a[i-1]+a[i-2]endfor主调函数：inputnoutputf(n)被调函数：

functionf(n)ifn=1thenreturn1elseifn=2thenreturn2elsereurnf(n)=f(n-1)+f(n-2)endifendfunction递归三要素递归式递归出口界函数递归优缺点优点：容易理解缺点：时空代价大算法设计步骤缩小规模找出递归出口递归实现递归调用+条件判断应用举例①繁衍生息（分形）②

购物返券③

冤冤相报何时了34562递归的概念和特点一一递推，回溯1迭代法细数你身边的迭代…版本升级长江后浪推前浪，一代新人换旧人010203040506070809010203040506070809枚举法贪心算法动态规划分治法递推法递归法迭代法查找排序算法策略10回溯法10迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法，即一次性解决问题。什么是迭代法？迭代法设计迭代法实现1）循环结构2）要有循环迭代终止条件1）循环+变量的值替换2）递归求解迭代法特点辗转特性（即翻来覆去地用变量的旧值递推出新的值，新值随即变成旧值）任务：最大公约数问题

请用辗转相除法求两自然数m，n的最大公约数是多少？定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法算法分析设m=14，n=6，最大公约数为2辗转相除法mnr1462620146273算法描述非递归实现inputm,nifm<nthent=m,m=n,n=tendifr=mmodnwhiler<>0dom=nn=rr=mmodnendwhileoutputn递归实现设gcd(m,n)函数递归式：gcd(m,n)递归出口：r=0界函数：gcd(n,r)主调函数：inputm,nifm<nthent=m,m=n,n=tendifgcd(m,n)被调函数：functiongcd(m,n)r=mmodnifr=0thenoutputnelsegcd(n,r)endifendfunction非递归实现任务：兔子繁殖问题

请用迭代法求解斐波那契数列的前20项定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法算法分析1,1,2,3,5,8,13,21,34,55,…设f1=1,f2=1f1=f1+f2=2f2=f1+f2=3…f1=1f2=1outputf1,f2i=1whilei<10dof1=f1+f2f2=f1+f2outputf1,f2i=i+1endwhile定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法迭代法设计迭代法实现1）循环迭代2）要有迭代终止条件1）循环2）递归求解迭代算法的设计循环结构有迭代终止的条件迭代优缺点优点：解决收敛问题的方法缺点：迭代次数可能过多，开销大迭代特点辗转特性（翻来覆去旧值换新值）迭代的实现①循环（非递归）②递归应用举例①家电以旧换新②

长江后浪推前浪34562迭代的概念旧值递推新值1查找法细数一下你身边的查找青玉案∙元夕∙辛弃疾李彦宏∙百度总裁010203040506070809010203040506070809枚举法贪心算法动态规划分治法递推法递归法迭代法查找排序算法策略10回溯法10线性查找：枚举法折半查找：分治法任务1：查找（线性查找）

现有6个数，要求用线性查找法，查找数字6，如果该数不在列表中，则输出"无此数"。定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法264754遍历=枚举6算法分析：算法描述：定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法inputa[6]={2,6,4,7,5,4},i=1fori=1to6ifa[i]=6thenoutput“Findit,itisat"&i&"site.”exitendifendforifi>6thenoutput"NotFindit."查找技术任务2：查找（折半查找）

现有6个数，要求用线性查找法，查找数字6，如果该数不在列表中，则输出"无此数"。定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法264754折半=分治算法分析：定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法1）对数据排序。264754244567244567topmidbottom62）设置bottom=1，top=6。3）设置mid=(1+6)/2=34）bottom=mid+1，top=6244567bottomtopmid算法描述：定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法inputa[6]={2,6,4,7,5,4}，bottom=1，top=6sortamid=(bottom+top)/2whilebottom<=topdoifa[mid]=a[des]thenoutputa[mid]elseifa[des]<a[mid]thentop=mid-1elsebottom=mid+1endifendwhile查找技术查找算法线性查找折半查找查找策略线性=枚举折半=分治排序算法010203040506070809010203040506070809枚举法贪心算法动态规划分治法递推法递归法迭代法查找排序算法策略10回溯法10排序前排序后比较元素大小改变元素位置12AdjustCompare排序技术快速排序法冒泡排序法选择排序法比较排序法插入排序法归并排序希尔排序……选择法冒泡法插入法部分有序空位移动插入被标记的队员归并算法打扑克时，你用到哪些排序？任务：冒泡排序

现有6个数，要求用冒泡排序法进行排序。排序过程定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法冒泡排序8>6j=1j+1869327大数沉底小数上浮i=1任务：冒泡排序

现有6个数，要求用冒泡排序法进行排序。排序过程定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法冒泡排序8<9689327j=2j+1大数沉底小数上浮i=1任务：冒泡排序

现有6个数，要求用冒泡排序法进行排序。排序过程定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法冒泡排序9>3689327j=3j+1大数沉底小数上浮i=1任务：冒泡排序

现有6个数，要求用冒泡排序法进行排序。排序过程定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法冒泡排序9>2683927j=4j+1大数沉底小数上浮i=1任务：冒泡排序

现有6个数，要求用冒泡排序法进行排序。排序过程定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法冒泡排序9>7683297j=5j+1大数沉底小数上浮i=1任务：冒泡排序定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法冒泡排序inputa[6]={8,6,9,3,2,7}fori=1to5forj=1to6-iifa[j]>a[j+1]thent=a[j]a[j]=a[j+1]a[j+1]=tendifendforendforoutputa[6]冒泡排序排序方法比较排序冒泡排序……排序策略大数沉底、小数上浮分治法010203040506070809010203040506070809枚举法贪心算法动态规划分治法递推法递归法迭代法查找排序算法策略10回溯法10一口吃不成胖子，但胖子却是一口一口吃来的切西瓜凡治众如治寡，分数是也；斗众如斗寡，形名是也。十则围之，五则攻之，倍则分之，敌则能战之，不若则能避之。孙子兵法“分而治之”就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。什么是分治法？分治分治，要先分，再治，最后合分：把问题划分为子问题治：递归的求解子问题合：把子问题的解合并称问题的解分治法的步骤functionDivide_Conquer（P）if（P的规模足够小）then

直接求解else

将P分解为P1,P2,…,Pkendiffori=1tokDivide_Conquer（Pi）endforendfunction任务1：二分求幂计算机模拟手工计算2^159=?定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法手工计算2^159，怎么计算？自然是判断指数，如果指数为奇数，则，2^奇数幂=2*2^奇数幂-1，如：2^159=2*2^158，否则，指数为偶数幂，2^偶数幂=4^偶数幂的一半。如：2^158=（2^2）^79=4^79算法分析求解过程2^159=？=2*2^158=2*4^79=2*4*4^78=2*(4*16^39)=……=2*(4*(16*256*(256^2)*(256^2^2^2)^2))functionf(x,n)//求x^nifn=1thenreturnxendififnmod2=1thenreturnx*f(x,n-1)elsereturnf(x^2,n/2)endifendfunction流程图伪代码任务2：有假币16个硬币中，混进了1枚假币。现在知道假币的重量比真币的质量要轻。给你一个天平，请用最快的时间把那个可恶的假币找出来。定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法算法分析方法1：枚举任意取1枚硬币，与其他硬币进行比较，若发现轻者，这那枚为伪币。最多可能有15次比较。算法分析方法2：一次二分法

将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为伪币。最多可能有8次比较。算法分析方法3：多次二分法①②③④算法分析方法4：三分13-23-12-12-2Inputn=16,t=0whilen>1dot=t+1n=(n+2)/3endwhileoutputt流程图伪代码公共子问题分久必合最优子结构计算复杂性问题可以分解成若干个规模较小的相同子问题问题的计算复杂性一般都是随着问题规模的增加而增加，问题规模缩小到一定规模，就可轻易求解了子问题的解可以合并为原问题的解子问题是相互独立的，不包含公共子问题算法设计步骤分解、求解、合成适用范围最优子结构、计算复杂性、分久必合、公共子问题分治结构特点减治分治优缺点优点：降低复杂度缺点：递归效率低应用举例①二分查找②

切西瓜③

还半价34562分治的概念各个击破、分而治之1动态规划010203040506070809010203040506070809枚举法贪心算法动态规划分治法递推法递归法迭代法查找排序算法策略10回溯法10今天你要是进不了前一百，你就进不了重点高中。你进不了重点高中，就进不了重点大学。进不了重点大学，你等于是这辈子完了。决策决策决策小升初中考高考多阶段决策问题多阶段决策过程，是指这样一类的决策问题：由问题的特性，可将过程按时间、空间等标志分为若干个互相联系又相互区别的阶段，在它的每一个阶段都需要做出决策，从而使整个过程达到最好的效果。20世纪50年代，美国数学家Bellman在研究多阶段决策过程的优化问题时，提出了著名的最优化原理。这种优化理论，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，从而创立了解决这类过程优化问题的新方法——动态规划。动态规划dynamicprogramming多阶段决策最短路径问题决策者需要作出时间上有先后之别的多次决策。前一次决策的选择将直接影响到后一次决策，后一次决策的状态取决于前一次决策的结果。决策者关心的是多次决策的最终结果，而不是各决策的即时结果。

阶段———把一个复杂的决策问题按时间或空间特征分解为若干个相互联系的阶段，以便顺序求解。一般用k表示。

状态———每个阶段有若干个状态，表示某一个阶段决策面临的条件或所处的位置。一般用s表示。

决策———就是关于状态的选择，是决策者从给定阶段状态触发对下一阶段状态作出的选择。一般用Xk=XK(SK)表示。表示k阶段，状态Sk时的决策。状态转移方程———————一个状态到另一个状态的转移过程由状态转移过程描述。大多数情况下可以用数学公式表达。指标函数—————分为：阶段函数和过程函数（目标函数）两种。它是全过程或子过程或各阶段上确定数量的函数。如费用、成本、距离、利润、时间等。

最优解————对指标函数求解，称为最优解。阶段变量Step1Step2Step3Step4Step5Step6Step7按时间或空间划分阶段___________按时间或空间确定状态___________状态变量确定决策变量以及决策集合_____________决策变量写出状态转移方程__________确定决策变量取值范围___________状态方程取值范围写出指标函数递推公式___________指标函数由后向前逆序求解__________逆序求解任务：最短路径下图从A点到G点最短路径是哪条？定义所需的变量输入数据输出数据处理数据关键之一设计数据描述关键之二设计算法

阶段———按空间划分阶段。分为6个阶段。K=1,…,6

状态———状态变量可用城市编号。S1={A}，S2={B1,B2}，S3={C1,C2,C3,C4}，S4={D1,D2,D3}，S5={E1,E2,E3}，S6={F1,F2}，S7={G}

决策———决策变量也可用城市编号。X1(S1)=A，X2(S2)=B1，X3(S3)=C2，X4(S4)=D1，X5(S5)=E2，X6(S6)=F2，X7(S7)=G

状态转移方程———————Sk+1=Xk

指标函数—————阶段函数：Vk=(Sk，XK)目标函数：fk（Sk）=min{Vk+fk+1（Sk+1）}

逆序求解—————从k=6开始计算。

逆序求解—————K=6f6(F1)=4，f6(F2)=3K=5f5(E1)=min{3+f6(F1)=7*，5+f6(F2)=8}=7f5(E2)=min{5+f6(F1)=9，2+f6(F2)=5*}=5f5(E3)=min{6+f6(F1)=10，6+f6(F2)=9*}=9K=4f4(D1)=min{2+f5(E1)=9，2+f5(E2)=7*}=7f4(D2)=min{1+f5(E2)=6*，2+f5(E3)=11}=6f4(D3)=min{3+f5(E2)=8*，3+f5(E3)=12}=8

逆序求解—————K=3f3(C1)=min{6+f4(D1)=13*，8+f4(D2)=14}=13f3(C2)=min{3+f4(D1)=10*，5+f4(D2)=11}=10f3(C3)=min{3+f4(D2)=9*，3+f4(D3)=11}=9f3(C4)=min{8+f4(D2)=14，4+f4(D3)=12*}=12K=2f2(B1)=min{1+f3(C1)=14，3+f3(C2)=13*，6+f3(C3)=15}=13f2(B2)=min{8+f3(C2)=18，7+f3(C3)=16*，6+f3(C4)=18}=16

逆序求解—————K=1f1(A)=min{5+f2(B1)=18*，3+f2(B2)=19}=18

最短路径—————AB1C2D1E2F2Ginput阶段变量，状态变量，决策变量，状态数组fori=阶段最大值downto1step-1//倒推每一个阶段forj=状态最小值to状态最大值//枚举阶段i的每一个状态fork=决策最小值to决策最大值//枚举i阶段j状态下的每一种决策

目标函数output最优方案最优子结构问题的最优解所包含的子问题的解也是最优的，称该问题具有最优子结构，即满足最优化原理。最优子结构无后效性某阶段状态一旦确定，该状态以后的过程不会影响以前的状态，只与当前状态有关。无后效性重叠子问题重叠子问题子问题之间是不独立的，一个子问题在下一阶段的决策中可能被多次使用。1）解决复杂问题2）找到全局最优解3）可以得到一组解1）依赖于经验和技巧2）无后效性局限大3）维数灾难动态规划算法步骤阶段、状态决策、状态转移指标函数、最优解动态规划适用条件最优子结构无后效性重叠子问题动态规划算法特点多次决策前一次决策影响后一次决策关心的是总结果，而非即时结果算法实现框架多重循环目标函数逆序求解动态规划优缺点优点：全局最优解缺点：无标准模型

维数灾难34562动态规划的思想多阶段决策1贪心算法010203040506070809010203040506070809枚举法贪心算法动态规划分治法递推法递归法迭代法查找排序算法策略10回溯法10合法抢劫田忌赛马找零钱贪心算法也称贪婪法。顾名思义，是指在求解最优化问题时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解，或者是整体最优解的近似解。现在只有面值分别为1、5和11元的硬币，希望找回总额为15元的硬币，要求硬币数量最少的发放方法11+1+1+1+1=15（五枚）5+5

+5=15（三枚）贪心选择问题最优解可通过一系列贪心策略的选择得到一个问题的最优解包含了它的子问题的最优解最优子结构Step1根据题意选取一种度量标准Step2按照这种度量标准对数据进行排序Step3循环+判断保留可行解舍去无效解贪心策略排序排序排序排序贪心策略价值度量标准容量度量标准单位价值标准……任务：发工资问题财务处发工资，如果每个老师的工资额都知道，最少需要准备多少张人民币，才能在给每位老师发工资的时候都