资源描述：
《算法设计 教学课件 作者 郑宇军 石海鹤 陈胜勇 算法设计（第1章）.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第1章概述1.1问题、算法和程序1.2两个典型问题1.3算法的复杂度分析1.1问题、算法和程序问题：通过输入与输出之间的关系来定义[问题示例]计算自由落体速度输入：物体坠落的起始高度h输出：物体到达地面时的速度v1.1问题、算法和程序问题：通过输入与输出之间的关系来定义算法：将问题的输入转换为输出的计算过程[问题示例]计算自由落体速度输入：物体坠落的起始高度h输出：物体到达地面时的速度v1.1问题、算法和程序问题：通过输入与输出之间的关系来定义算法：将问题的输入转换为输出的计算过程程序：通过程序设计语言对算法的实现[问题示例]计算自由落体速度输入：物体坠
2、落的起始高度h输出：物体到达地面时的速度v[C++程序]doublev=sqrt(2*9.8*h);1.1问题、算法和程序问题：通过输入与输出之间的关系来定义算法：将问题的输入转换为输出的计算过程程序：通过程序设计语言对算法的实现[问题示例]数列求和输入：一个正整数n输出：从1到n的所有正整数之和slets=0;for(inti=1;i≤n;i++)ss+i;lets=n*(1+n)/2;1.2两个典型问题排序问题稳定匹配问题1.2.1排序问题排序：将一组任意顺序的元素按某种顺序排列起来整数数组排序：将所有数按从大到小的顺序排列选择排序过程令i=0;选
3、择A[j]=minA[i..n−1];如A[i]≠A[j]则交换A[i]↔A[j]令i=i+1，当i=n−1时算法结束，否则转第2步[排序问题]输入：任意一个长度为n的数组A输出：这组数的一个重排列A′，其满足A′[0]≤A′[1]≤…≤A′[n−1]1.2.1排序问题[选择排序算法]AlgorithmSelectionSort(A:int[])beginleti=0,n=
4、A
5、;while(i6、,A[j])(A[j],A[i]);ii+1;end1.2.2稳定匹配问题问题实例：n名男青年和n名女青年参加一个相亲会。经过了解，每名男青年在心目中都对所有女青年作了一个排序，而每名女青年同样也对男青年作了排序。问这些男女青年之间怎样才能进行理想的配对。{吕布,刘备,孔明,周瑜,曹操}{貂蝉,大乔,小乔,尚香,阿丑}1.2.2稳定匹配问题匹配：给定两个集合A={a0,a1,…,am−1}和B={b0,b1,…,bn−1}，一个匹配M是指一个AB的有序对的集合，且每个aA和bB最多出现在M的一个有序对中。完美匹配:设M是集合A={a0,a1,…
7、,an−1}到B={b0,b1,…,bn−1}的一个匹配，如果每个aA和bB都恰好出现在M的一个有序对中，那么称M是一个完美匹配。{吕布,刘备,孔明,周瑜,曹操}{貂蝉,大乔,小乔,尚香,阿丑}M1={(吕布,貂蝉),(曹操,阿丑)}1.2.2稳定匹配问题匹配：给定两个集合A={a0,a1,…,am−1}和B={b0,b1,…,bn−1}，一个匹配M是指一个AB的有序对的集合，且每个aA和bB最多出现在M的一个有序对中。完美匹配:设M是集合A={a0,a1,…,an−1}到B={b0,b1,…,bn−1}的一个匹配，如果每个aA和bB都恰好
8、出现在M的一个有序对中，那么称M是一个完美匹配。M1={(吕布,貂蝉),(刘备,大乔),(孔明,小乔),(周瑜,尚香),(曹操,阿丑)}{吕布,刘备,孔明,周瑜,曹操}{貂蝉,大乔,小乔,尚香,阿丑}1.2.2稳定匹配问题不稳定因素：设M是集合A到B的一个匹配，(a,b),(a′,b′)M，如果a偏爱b′大于b，且b′偏爱a大于a′，那么称(a,b′)是M一个不稳定因素。稳定匹配：设M是集合A到B的一个完美匹配，如果M中没有不稳定因素，那么称M是一个稳定匹配。M1={(吕布,貂蝉),(刘备,大乔),(孔明,小乔),(周瑜,尚香),(曹操,阿丑)}1.2
9、.2稳定匹配问题稳定匹配：设M是集合A到B的一个完美匹配，如果M中没有不稳定因素，那么称M是一个稳定匹配。[稳定匹配问题]输入：两个大小为n的集合A和B，以及nn型偏好矩阵PA和PB，它们分别表示A对B以及B对A的偏好排序输出：集合A到B的一个稳定匹配M1.2.2稳定匹配问题算法求解过程对每个aA,选取a最偏爱的一个bB若b还未配对，那么可将a与b配对若b已和另一个a′A配对，且b′偏爱a大于a′，那么可将a与b配对，此时a′变成未配对的若b已和另一个a′A配对，且b′偏爱a′大于a，那么转a下一个偏爱的b当A为空时算法结束，否则转第1步[稳定
10、匹配问题]输入：两个大小为n的集合A和B，以及nn型偏好矩阵PA和PB，它们分
