下载文档原格式
第三章 蛮力法1.选择排序SelectionSort(A[0..n-1])for i=0 to n-2 domin=ifor j=i+1 to n-1 doif A[j]<A[min]min=jswap A[i] and A[min]2.冒泡排序BubbleSort(A[0..n-1])// 输入：数组A，数组中的元素属于某偏序集// 输出：按升序排列的数组Afor i=0 to n-2 dofor j=0 to n-2-i doif A[j+1]<A[j] swap A[j] and A[j+1]3.改进的冒泡算法ALGORITHM BubbleSortImproved( A[0,…,n –1] )// 冒泡排序算法的改进// 输入：数组A，数组中的元素属于某偏序集// 输出：按升序排列的数组Afor i ← 0 to n – 2 doflag ← Truefor j ← 0 to n – 2 – i doif A[j+1] < A[j]swap(A[j], A[j+1])flag ← False// 如果在某一轮的比较中没有交换，则flag为True，算法结束returnif flag = True4. 顺序查找算法算法 SwquentialSearch2(A[0...n],k)//顺序查找算法的实现，它用了查找键来作限位器//输入：一个n个元素的数组A和一个查找键K//输出：第一个值等于K的元素的位置，如果找不到这样的元素就返回 -1A[n]<--ki<--0while A[i]!=K doi<--i+1if i<n return iElse return -15. 蛮力字符串匹配算法 BruteForceStringMatch(T[0...n-1],P[0...m-1])//该算法实现了蛮力字符串匹配代表一段文本//输入：一个n个字符的数组T[0...n-1]// 一个m个字符的数组P[0..m-1]代表一个模式//输出：如果查找成功的话，返回文本的第一个匹配字串中第一个字符的位置， // 否则返回-1For i<--0 to n-m doj<--0While j<m and P[j]=T[i+j]doj<--i+1If j=m return ireturn -1合并排序最差Θ(nlog2n)快速排序最优Θ(nlog2n)最差Θ(n2)平均Θ(1.38nlog2n)选择排序 Θ(n2)冒泡排序 Θ(n2)插入排序最差Θ(n2)最优 Θ(n)平均 Θ(n2)第四章 分治法合并排序算法 MergeSort(A[0..n-1] )排序 // 递归调用mergesort来对数组 A[0...n-1]// 输入：一个可排序数组A[0..n-1]// 输出：非降序排列的数组A[0..n-1]if n > 1n/2 -1]copy A[0.. n/2 -1] to B[0..n/2 -1]copy A[ n/2 ..n-1] to C[0..MergeSort( B )MergeSort( C )Merge( B,C,A )两个数组合并的算法算法 Merge(B[0..p-1],C[0..q-1],A[0..p+q-1])//将两个有序数组合并成一个有序的数组和C[0...q-1]//输入：两个有序数组B[0...p-1]//输出：A[0..p+q-1]中已经有序存放了B和C中的元素 i=0,j=0,k=0;while i<p and j<q do≤C[j]if B[i]A[k]=B[i], i=i+1elseA[k]=C[j], j=j+1k=k+1if i=pcopy C[j..q-1] to A[k..p+q-1]elsecopy B[i..p-1] to A[0..p+q-1]快速排序算法QuickSort(A[l..r])// 使用快速排序法对序列或者子序列排序或者序列本身A[0..n-1]// 输入：子序列A[l..r]// 输出：非递减序列Aif l < rs ← Partition( A[l..r] )QuickSort( A[l..s-1] )QuickSort( A[s+1..r] )//s是中轴元素/基准点，是数组分区位置的标志实现分区的算法Partition( A[l..r] )// 输入：子数组A[l..r]// 输出：分裂点/基准点pivot的位置p ← A[l]i ← l; j ← r+1repeat≥ prepeat i ←i + 1until A[i]≤ prepeat j ← j – 1 until A[j]swap( A[i], A[j] )≥ juntil iswap( A[i], A[j] )swap( A[l], A[j] )return j折半查找BinarySearch( A[0..n-1], k )// 输入：已排序大小为n的序列A，待搜索对象k// 输出：如果搜索成功，则返回k的位置，否则返回-1 l=0,r=n-1;While l≤rmid= (l+r)/2if k = A[mid] return midelse if k < A[mid] r=m-1else l=m+1return -1Strassen矩阵Strassen方法M1=A11(B12-B22)M2=(A11+A12)B22M3=(A21+A22)B11M4=A22(B21-B11)M5=(A11+A22)(B11+B22)M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12)第五章 减治法插入排序ALGORITHM InsertionSort( A[0..n-1] )// 对给定序列进行直接插入排序// 输入：大小为n的无序序列A// 输出：按非递减排列的序列Afor i ← 1 to n-1 dotemp ← A[i]j ← i-1while j ≥ 0 and A[j] > temp doA[j+1] ← A[j]j ← j –1A[j+1] ←temp深度优先查找算法 BFS（G）//实现给定图的深度优先查找遍历//输入：图G=<V,E>//输出：图G的顶点，按照被DFS遍历第一次访问到的先后次序，用连续的整数标记，将V中的每个顶点标记为0，表示还“未访问”count =0//记录这是第几个访问的节点标记为 unvisitedmark each vertex with 0//∈ V dofor each vertex vif v is marked with 0dfs(v)dfs(v)//递归访问所有和v相连接的未访问顶点，然后按照全局变量count的值//根据遇到它们的先后顺序，给它们附上相应的数字count = count + 1mark v with countv dofor each vertexw adjacent toif w is marked with 0dfs(w)广度优先BFS(G)/实现给定图的深度优先查找遍历//输入：图G=<V,E>//输出：图G的顶点，按照被BFS遍历第一次访问到的先后次序，用连续的整数标记，将V中的每个顶点标记为0，表示还“未访问”count =0mark each vertex with 0for each vertex v∈ V dobfs(v)bfs(v)//递归访问所有和v相连接的未访问顶点，然后按照全局变量count的值//根据遇到它们的先后顺序，给它们附上相应的数字count = count + 1mark v with countinitialize queue with vwhile queue is not empty doa = front of queuefor each vertex w adjacent to a doif w is marked with 0count = count + 1mark w with countadd w to the end of the queueremove a from the front of the queue拓扑排序第六章 变治法Gauss消去法GaussElimination(A[1..n], b[1..n])// 输入：系数矩阵A及常数项 b// 输出：方程组的增广矩阵等价的上三角矩阵for i=1 to n doA[i][n+1] =b[i]for j= i+1 to n dofor k = i to n+1 do– A[i][k]*A[j][i]/A[i][i]A[j][k] = A[j][k]堆排序堆排序主要包括两个步骤：对于给定的数组构造相应的堆。
算法笔记_004：8枚硬币问题【减治法】⽬录1 问题描述（1）实验题⽬在8枚外观相同的硬币中，有⼀枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相⽐较轻还是较重。
可以通过⼀架天平来任意⽐较两组硬币，设计⼀个⾼效的算法来检测这枚假币。
（2）实验⽬的1）深刻理解并掌握减治法的设计思想并理解它与分治法的区别；2）提⾼应⽤减治法设计算法的技能。
3）理解这样⼀个观点：建⽴正确的模型对于问题的求解是⾮常重要的。
（3）实验要求1）设计减治算法实现8枚硬币问题；2）设计实验程序，考察⽤减治技术设计的算法是否⾼效；3）扩展算法，使之能处理n枚硬币中有⼀枚假币的问题。
（4）实现提⽰假设⽤⼀个数组B[n]表⽰硬币，元素B[i]中存放第i枚硬币的重量，其中n-1个元素的值都是相同的，只有⼀个元素与其他元素值不同，则当n=8时即代表8枚硬币问题。
由于8枚硬币问题限制只允许使⽤天平⽐较轻重，所以，算法中只能出现元素相加和⽐较的语句。
2 解决⽅案2.1 减治法原理叙述在说减法法原理之前，我们先来简单看看分治法原理：分治法是把⼀个⼤问题划分为若⼲⼦问题，分别求解⼦问题，然后再把⼦问题的解进⾏合并得到原问题的解。
⽽减治法同样是把⼤问题分解成为若⼲个⼦问题，但是这些⼦问题不需要分别求解，只需求解其中的⼀个⼦问题，也⽆需对⼦问题进⾏合并。
换种说法，可以说减治法是退化的分治法。
减治法原理正式描述：减治法（reduce and conquer method）将原问题的解分解为若⼲个⼦问题，并且原问题的解与⼦问题的解之间存在某种确定关系，如果原问题的规模为n，则⼦问题的规模通常是n/2 或n-1。
2.2 8枚硬币规模解法求解思路：（1）⾸先输⼊8枚硬币重量，存放在⼀个长度为8的⼀维数组中。
（2）定义a,b,c,d,e,f,g,h⼋个变量，分别对应⼀枚硬币的重量。
然后把这8枚硬币分成三组，分别为abc(abc = a+b+c)、def(def =d+e+f)、gh。
蛮力法、分治法、减治法三种方法的理解和处理问题的类型的归纳一、蛮力法蛮力法是一种基础且直接的问题解决策略，通常用于寻找问题的答案或解决方案。
其核心理念在于，通过逐一检查所有可能的解决方案，从而找到问题的答案或找到最佳的解决方案。
在蛮力法中，我们通常需要投入较多的时间和计算资源，尤其是在面对大规模或复杂的问题时。
蛮力法的应用范围广泛，包括但不限于以下几种类型的问题：1. 排序问题：例如，对一个数组进行排序，我们可以使用蛮力法，通过比较每对元素并交换它们的位置，使得整个数组有序。
2. 查找问题：例如，在排序数组中查找一个特定的元素，我们可以使用蛮力法，逐一检查数组中的每个元素直到找到目标元素。
3. 组合与排列问题：例如，计算给定集合的所有可能排列或组合，我们可以使用蛮力法，通过逐一排列或组合所有可能的元素组合得到答案。
二、分治法分治法是一种将复杂问题分解为更小、更易于处理的子问题的方法。
通过将问题分解为独立的子问题，我们可以分别解决每个子问题，然后将这些解决方案组合起来，形成原始问题的解决方案。
这种方法在处理复杂问题时非常有效，因为它可以降低问题的复杂性，使我们可以更有效地解决问题。
分治法的应用范围广泛，包括但不限于以下几种类型的问题：1. 排序问题：例如，归并排序就是一种使用分治法的排序算法，它将一个大列表分解为两个小列表，对这两个小列表分别进行排序，然后合并它们以得到有序列表。
2. 搜索问题：例如，二分搜索是一种使用分治法的搜索算法，它将搜索空间一分为二，每次迭代都排除一半的元素，直到找到目标元素或确定元素不存在。
3. 图问题：例如，Dijkstra的算法就是一种使用分治法的图搜索算法，它将图分解为最短路径树，然后通过搜索每个子图的最短路径来解决整个图的最短路径问题。
三、减治法减治法是一种通过减少问题的规模或复杂性来解决问题的方法。
其核心理念在于，通过消除或减少问题的某些部分或特性，从而降低问题的复杂性或规模，使得问题更容易解决。
生成组合对象的算法（减治法）下面将详细介绍生成组合对象的减治法算法：1.定义问题：首先需要明确所要生成的组合对象的特征和属性。
例如，如果生成组合对象是包含固定数量的不同颜色的气球，那么问题的定义就是生成所有可能的气球颜色组合。
2.划分子问题：接下来，需要将问题划分为更小的子问题。
对于生成组合对象的问题，可以将其分解为生成单个组合对象的子问题。
在上述例子中，可以将其划分为生成单个气球颜色的子问题。
3.设计基本情况：在减治法中，需要定义一个基本情况，当问题的规模达到基本情况时，可以直接解决问题。
在上述例子中，当只有一个气球需要生成时，就可以直接生成所有可能的颜色。
4.减小问题规模：使用递归方法将问题规模逐渐减小。
在上述例子中，可以通过迭代每种颜色的气球来生成组合对象。
每次迭代，都解决一个气球颜色的子问题，并将其与其他已生成的气球组合。
5.合并子问题：将解决子问题的结果合并为整体解决方案。
在上述例子中，可以将每个气球颜色子问题的解合并为组合对象的解。
通过将每种颜色的气球与已生成的组合对象组合，可以生成所有可能的组合对象。
6.返回解决方案：最后，返回所有生成的组合对象作为最终的解决方案。
减治法的关键是确定如何划分子问题，并设计适当的方法来减小问题规模和合并子问题的解。
对于生成组合对象的问题，子问题的划分可以根据组合对象的特征和属性进行确定。
递归方法的使用可以确保问题规模不断减小，直到达到基本情况。
需要注意的是，生成组合对象可能会涉及到大量的计算和存储。
为了提高算法的效率，可以考虑使用剪枝等技术来减少不必要的计算和存储。
总结：生成组合对象的减治法算法通过将问题划分为较小的子问题，并逐步减小问题规模和合并子问题的解决方案来解决复杂问题。
这种算法的关键是确定子问题的划分和适当的规模减小和合并方法。
减治法是解决生成组合对象问题的一种有效方法，可以根据具体问题的特征和属性进行具体的实现。
第一章测试1【判断题】(10分)一个问题的同一实例可以有不同的表示形式A.错B.对2【判断题】(10分)同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。
A.错B.对3【判断题】(10分)问题的两个要素是输入和实例。
A.对B.错4【单选题】(10分)算法与程序的区别是（）A.有穷性B.确定性C.输出D.输入5【单选题】(10分)解决问题的基本步骤是（）。
（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明A.(3)(1)(5)(4)(2)B.(3)(4)(1)(5)(2)C.(1)(2)(3)(4)(5)D.(3)(1)(4)(5)(2)6【单选题】(10分)下面说法关于算法与问题的说法的是（）。
A.算法是一种计算方法，对问题的每个实例计算都能得到正确答案。
B.证明算法不正确，需要证明对任意实例算法都不能正确处理。
C.如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。
D.同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。
7【多选题】(10分)下面关于程序和算法的说法正确的是（）。
A.算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。
B.程序总是在有穷步的运算后终止。
C.程序是算法用某种程序设计语言的具体实现。
D.算法是一个过程，计算机每次求解是针对问题的一个实例求解。
8【多选题】(10分)最大独立集问题和（）问题等价。
A.最大团B.稳定匹配问题C.区间调度问题D.最小顶点覆盖9【多选题】(10分)给定两张喜欢列表，稳定匹配问题的输出是（）。
A.完美匹配B.最大匹配C.稳定匹配D.没有不稳定配对10【单选题】(10分)问题变换的目的有（）。
(1)复杂变简单(2)未知变已知(3)隐式变显式(4)难解变易解（5）以上都是。
A.（5）B.（1）C.（2）D.（3）E.（4）11【单选题】(10分)按照霍纳法则，计算p(x)=a n x n+a n-1x n-1+…+a1x1+a0的数量级为____。
第3章 算法思维3.3 算法思想简介20世纪中期以后，随着计算机的出现、发展，算法广泛地运用于种类问题的求解，成为计算机科学的灵魂，涌现出精彩纷呈的算法。
3.3.1 蛮力法蛮力法也称穷举法，其基本思想是采用一定的策略，将待解决问题的所有可能列出来，找出问题的解。
《算经》中的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？该问题的解决方案是：设公鸡为x 只，母鸡为y 只，小鸡为z 只；则x 的取值范围为0到20，y 的取值范围为0到33，z 的取值范围为0到100，当然z 应该为3的倍数；这样总共有21×34×34，即24276种组合方案，其中满足条件x +y +z =100，并且5x +3y +z /3=100的组合就是问题的解。
[百钱百鸡VB 伪代码] p 1tep 3d (5x+3y+z/3=100)Then 采用的关键技术是描述，算法设计时应避免重复试探，时间复杂度较高，效率较低，分而治之N }，其 中某段的和定义为1 设序列A 中有素，其最大段和为maxsum ；序列A 的开始位置为left ，结束位置为right 序列A left 和A rigth ，序列A left 的最大子段和为leftsu 相同，即用递归进一步分解子序列A left 和A left 中，其值为leftsum ；也有可能处在子序For x=0 To 20 Step 1 For y=0 To 33 Ste For z=0 To 100 S If (x+y+z=100)An Print x;y;z End If Next x Next y Next x蛮力法但现在的计算机有超强的计算能力，仍是直接解决问题的一种常用思路。
3.3.2 分治法分治法的基本思想是将一个难以直接解决的大问题划分成一些规模较小的子问题，，其求解过程通常由划分、求解子问题和合并3个阶段组成，如图3-8所示。
第5章减治法（Decrease and Conquer）减治法的基本思想规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间具有关系：（1）原问题的解只存在于其中一个较小规模的子问题中；（2）原问题的解与其中一个较小规模的解之间存在某种对应关系。
由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。
2减治法的基本思想一旦建立了这种关系，就可以从顶至下（递归），也可以从底至上（非递归）的来运用Example, n!A top down (recursive) solutionA bottom up (iterative) solution3减治法的类型减治法有三种变种：1)减去一个常量2)减去一个常数因子3)减去的规模是可变的gcd（m, n）4减（一）治技术a problem of size nsubproblemof size n-1a solution to thesubprobleme.g., n!a solution tothe original problem5减(半) 治技术a problem of size nsubproblemof size n/2a solution to thesubprobleme.g., Binary searcha solution tothe original problem67典型的分治法subproblem 2 of size n /2subproblem 1 of size n /2a solution to subproblem 1 a solution to the original problema solution to subproblem 2a problem of size ne.g., mergesort减治与分治的区别考虑以下指数问题: 计算a n减一法Bottom-up: iterative (brute Force) Top-down:recursive分治法:减常因子法:a n= a*a*a*a*...*aa n= a n-1* a if n > 1= a if n = 1a n= a ⎣n/2 ⎦* a ⎡n/2⎤if n > 1= a if n = 1a n = (a n/2 ) 2if n is even and positive= (a(n-1)/2 ) 2 * a if n is odd and > 1 = a if n = 1O (log2n) O (n log2n)89111)2/(0)(>=⎩⎨⎧+=n n n T n T 所以，通常来说，应用减治法处理问题的效率是很高的，一般是O (log 2n)数量级。
减治法核⼼数学式：1. f(n) = f(n-1) + F; 应⽤：插⼊排序；⽣成排序/⼦集2. f(n) = f(n/2) + F; 应⽤：假币问题；俄式乘法3. f(n) = f(n-k) + F; 应⽤：查找第k⼤/⼩的元素实现思路：考虑对于元素数量为n的集合的执⾏结果，如何⽤数量为n-1、n/2或者n-k的集合的执⾏结果来表⽰实现⽅法：迭代和递归都可以/** 减治法* 主要思路：* 基于减治法f(n) = f(n-1)...的思路，可以想象，* 对于长度为n的序列，它的所有⼦集，是它前⾯n-1元素所构成⼦集* 都加最后⼀个元素* 例⼦:* "abcd"全部⼦集是"abc"全部⼦集中的元素都加⼀个'd'*/list<string> jianzhi(const string &str, int cursor) {if (0 == cursor) {list<string> subs;subs.add(""):return subs;}list<string> all_subs = jianzhi(str, cursor - 1);for(list<string>::iterator iter = all_subs.begin();iter != all_subs.end();iter++) {*iter += str[cursor];}return all_subs;}/** 第k⼤/⼩的问题*/// 减治法，每次迭代缩⼩需要查找的范围int findKmost(array[0, n], k) {pivot = getPivot(array[0,n]);index = surePivotPos(array[0, n], pivot);if (index == k-1)return pivotelse if (index > k-1)return findKmost(array[0, index], k)elsereturn findKmost(array[index, n], k-index)}。
分治算法选择题
关于分治算法的选择题较多，比如：
1. 求众数：
问题描述：给定一个大小为n的数组，找到其中的众数。
众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例1：输入：[3，2，3]，输出：3
示例2：输入：[2，2，1，1，1，2，2]，输出：2
题解：对数组排序，由于众数大于n/2，则n/2+1处一定是该众数。
又由于索引从0开始，即索引n/2为众数。
算法时间复杂度O（nlogn）。
2. 分治法的适用条件是什么？
答案：A.问题可以分解为规模较小的子问题；B.小规模子问题可解；C.子问题可合并为问题的解；D.子问题相互独立。
3. 分治法的设计思想是什么？
答案：A.大事化小，各个击破，分而治之。
4. 每次都将问题分解为原问题规模的一半进行求解，称为什么法？
答案：A.二分法。
5. 分治法一般在每一层递归上有哪三个步骤？
答案：A.分解、解决、合并。
6. 减治法是什么？
答案：A.把一个问题转化成一个子问题来解决，从子问题的解得到原问题的解。
7. 分治法将原问题分解为若干个什么规模的子问题？
答案：A.规模较小、相互独立、完全相同。
如需更多关于分治算法的选择题及答案，可以咨询专业算法人士获取更多资源。
