下载文档原格式
几种常见的算法案例分析算法不仅是数学及其应用的重要的组成局部，也是计算机科学的重要根底，其中算法的重要思想在几种常见的算法例案中得以较好的表达。
本文从几种常见算法案例出发，来探究一下算法的内涵。
一、辗转相除法所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数，假设余数不为零，那么将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，那么这时的较小的数就是原来两个数的最大公约数。
例1． 写出求两个正数,()a b a b >的最大公约数的一个算法。
算法设计：第一步：输入两个正整数,()a b a b >；第二步：把a b ÷的余数赋予r ；第三步：如果0r ≠，那么把b 赋予a ，把r 赋予b ，转到第二步；否那么转到第四步；第四步：输入最大公约数b 。
程序框图下列图所示：用伪代码表示：input “a=,b=〞；a,bdo r=mod(a,b)a=bb=rloop until r=0print bend二、更相减损术所谓更相减术，就是对于给定的两个数，以其中较大的数减去较小的数，然后将差和较小的数构成一对新数，再用较大的数减去较小的数，反复执行此步骤，直到差数和较小的数相等，此时相等的两个数就是原两个数的最大公约数。
在我国古代的<<九章算术>>中有这样的描述“约分术曰：可半者半之，不可半者会置分母分子之数，以少减多，更相损减，求其等也，以等数约之。
〞意思是说如果分母、分子都是偶数，那么先除以2；如果不全是偶数，便将分子与分母互减，以少减多，直到得出最大公约数为止，用最大公约数约分子与分母，便可使分数最简。
如果两个数都是偶数，也不除以2，直接求最大公约数。
这是一种多么奇妙的方法啊，我们古代人在许多方面都比西方先进，这是值得我们自豪的。
以上题为例，算法可以这样来设计：第一步：输入两个正整数,()a b a b >；第二步：假设a 不等于b ，那么执行第三步；否那么执行第五步；第三步：把a b -的差赋予r ；第四步：如果b r >，那么把b 的值赋予a ，否那么把r 的值赋予a ，执行第二步； 第五步：输出最大公约数b 。
C++经典问题算法分析分解一、百钱买百鸡问题（枚举算法）★算法分析：1、对百钱买百鸡问题的所有结果进行逐一统计验证（枚举验证）。
2、公鸡最多只能买20只，母鸡最多只能买33只，小鸡最多只能买300只。
3、用for循环进行逐一验证4、对小鸡的费用应用x/3代替x*(1/3)，因为1/3在整型变量下的值为0。
5、需保证小鸡的数量是3的倍数，即x%3==0。
★源代码：图1-1★执行结果：图1-2二、填写运算符问题（枚举算法）★算法分析：1、5个数字需要填入4个运算符。
2、每两个数字之间有4种运算符可以选择。
3、当运算符中填入除号时，右边的被除数不能为0.4、乘除的优先级大于加减的优先级。
5、可以用循环的方法逐一填入各种运算符。
★源代码：图2-1三、汉诺塔问题（递归算法）★算法分析：1、汉诺塔问题可以运用递归算法解决。
2、递归是函数本身调用直接或者间接调用自己的方法。
3、在汉诺塔问题中需要的步骤数是2^n-1。
4、汉诺塔问题步骤解析：（1）把1座上（n-1）个盘子借助3座移动到2座。
（2）把1座上的第n个盘子移动到3座。
（3）把2座上的（n-1）个盘子借助1座移动到3座。
（4）我们假设用h（n，a，b，c）表示把1座n个盘子借助2 座移动到3座。
由此可得出结论：（1）上是h（n，1,3,2）, (2)上是（n-1，2,1,3）★源代码：图3-1 ★执行结果：图3-2 ★形象示例：A B C图3-3★故事缘由：据说古代有一个梵塔，塔内有3个座A、B、C。
A座上有64个圆盘，盘子大小不等，大的在下，小的在上。
有一个和尚想把这64个盘子从A座移动到C 座，但每次只能移动一个圆盘，并在移动过程中始终保持大盘在下，小盘在上。
在移动过程中只能利用B座。
现在需要写出移动的步骤。
这就是汉诺塔问题。
当时这个和尚觉得很难，于是他想，要是有一个人能把前面的63个圆盘移动到B座，自己再把最后一个圆盘移动到C座，那就简单了。
所以他找了另一个和尚来做这件事。
算法解决问题的步骤经典案例算法是解决问题的一种方法和步骤。
经典的案例中，算法一般包括以下步骤：问题定义、问题分析、算法设计、算法分析和算法实现。
下面，我们将介绍几个经典问题案例，并详细说明每个步骤的具体内容。
一、最小生成树问题问题定义：给定一个连通的无向图，每个边都有一个权重，需要找出一棵包含所有顶点但总权重最小的生成树。
问题分析：首先，需要理解连通图和生成树的概念。
然后，要明确最小生成树的定义和目标。
算法设计：可以使用Prim算法或Kruskal算法来解决最小生成树问题。
Prim算法从一个任意的顶点开始，逐步扩展生成树，选择与当前生成树相连的最小权重边。
Kruskal算法则是不断选择权重最小的边，直到生成树包含所有顶点为止。
算法分析：分别分析Prim算法和Kruskal算法的复杂度，比较两个算法的优劣。
算法实现：编写Prim算法和Kruskal算法的代码，并对其进行测试和调试。
二、背包问题问题定义：给定一系列物品和一个固定大小的背包，每个物品都有一个重量和一个价值。
需要确定一个最佳组合，使得背包能够装载最大价值的物品，同时不超过背包的重量限制。
问题分析：需要理解背包问题的定义和背包的限制条件。
可以将其分为01背包问题、完全背包问题和多重背包问题等。
算法设计：对于01背包问题，可以使用动态规划算法来解决。
从第一个物品开始，计算每个物品是否放入背包，使得总价值最大。
对于完全背包问题，也可以使用动态规划算法来解决，但需要考虑每个物品可以重复选择的情况。
对于多重背包问题，可以将其转化为01背包问题来解决。
算法分析：分析背包问题的复杂度，比较不同算法的效率和适用情况。
算法实现：编写动态规划算法来解决背包问题，并对其进行测试和调试。
三、图的最短路径问题问题定义：给定一个加权有向图，需要找到一个顶点到其他所有顶点的最短路径。
问题分析：需要理解最短路径的定义和目标。
可以使用Dijkstra 算法或Bellman-Ford算法来解决最短路径问题。
算法解决实际问题实例算法是计算机科学中的核心概念，它是一套定义了在解决问题时需要遵循的规则和步骤的总称。
算法的应用范围广泛，不仅局限于计算机领域，也包括了其他领域，如数学、物理学、经济学等。
本文将从实际问题的角度出发，介绍几个运用算法解决的实例。
第一个实例是旅行推荐系统。
对于喜爱周游世界的旅行者来说，他们在规划旅行路线时常常会面临以下问题：如何合理安排旅行的目的地，使得既能满足游客对景点的兴趣，又能合理安排时间和交通路线？这个问题通常可以通过图算法来解决。
首先，将每个景点作为图的一个节点，各节点之间的距离作为图的边。
然后，根据用户的兴趣偏好，给每个节点打分。
接下来，通过图搜索算法（如最短路径算法）找出一个或多个满足用户要求的旅行路线。
第二个实例是社交网络中的好友推荐。
随着社交网络的快速发展，人们面临了一个新的问题：如何在广大的网络中找到真正的朋友，而不只是浮于表面的社交关系？这个问题可以通过图算法和机器学习算法来解决。
首先，通过图算法建立社交网络的图模型。
然后，根据用户的行为和社交关系，使用机器学习算法预测用户之间的友谊强度。
最后，根据这一预测结果，推荐给用户潜在的好友。
第三个实例是电商平台的推荐系统。
在电商平台上，为了提高用户的购物体验和销售量，经常会使用推荐系统来推荐给用户可能感兴趣的商品。
推荐系统的核心是通过算法分析用户的历史行为和兴趣，根据这些信息给用户推荐相关的商品。
其中，常用的算法包括协同过滤算法、内容过滤算法和深度学习算法等。
通过这些算法，电商平台可以提高用户购买的满意度，从而提高用户黏性和销售额。
除了上述实际问题，算法还有很多其他的应用。
例如，医疗领域中的疾病诊断和药物设计、金融领域中的股票预测和风险控制、交通领域中的交通流优化和路径规划等。
这些问题都可以通过算法来解决，提高工作效率和精确度。
算法的应用不仅仅局限于计算机领域，也能够为其他科学和工程领域提供帮助。
通过合理地运用算法，可以解决实际问题，提高工作效率和解决方案的可行性。
信息学竞赛中的论与算法应用的实例分析信息学竞赛作为一项智力竞技活动，旨在培养学生的计算思维和解决实际问题的能力。
在竞赛中，论与算法的应用是非常重要的一环。
本文将通过实例分析，探讨论与算法在信息学竞赛中的应用。
一、背包问题背包问题是计算机科学中经典的优化问题之一，也是信息学竞赛中常见的题型。
该问题要求在一个给定容量的背包中，放入一定物品，使得背包中物品的总价值最大化。
通过使用动态规划算法，可以有效解决背包问题。
算法的核心思想是通过迭代计算，根据子问题的最优解推导出更大问题的最优解。
例如，在信息学竞赛中，有一题是求解背包问题，给定一组物品和它们的价值和重量，以及背包的容量。
我们需要选择一些物品放入背包中，使得背包中的物品总价值最大，同时考虑背包的容量限制。
这个问题可以通过动态规划算法进行求解。
我们可以定义一个二维数组dp[i][j]，表示前i个物品放入容量为j的背包中能达到的最大价值。
通过填充这个数组，我们可以逐步推导出最后的结果。
二、最短路问题最短路问题是求解两点之间最短路径的问题，也是信息学竞赛中常见的题型。
在现实生活中，最短路问题有很多应用，比如导航系统、交通规划等。
在信息学竞赛中，通过使用图论算法，可以高效地解决最短路问题。
例如，在一道信息学竞赛题目中，给定一个有向图和起点终点，我们需要求解两点之间的最短路径。
这个问题可以使用迪杰斯特拉算法（Dijkstra's Algorithm）进行求解。
算法的核心思想是通过不断更新起点到各个节点的最短距离，直到找到最短路径。
三、匈牙利算法匈牙利算法是解决二分图最大匹配问题的经典算法，也是信息学竞赛中常见的题型。
在信息学竞赛中，经常需要求解二分图的最大匹配，比如安排任务、分配资源等。
例如，在一道信息学竞赛题目中，给定一个二分图和一些边的限制条件，我们需要求解最大匹配数。
这个问题可以使用匈牙利算法进行求解。
算法的核心思想是通过不断寻找增广路径，直到找到最大匹配。
贪心算法实例分析贪心算法，是一种常见的解决问题的方法，尤其在最优化问题中得到了广泛的应用。
简单来说，贪心算法是建立在选取局部最优解的基础上，通过不断的贪心选择，达到全局最优解的目的。
本文将通过两个实例，介绍使用贪心算法的思路和实现方法。
实例一：零钱兑换问题假设有 n 种不同面值的硬币，每种面值的硬币数量无限，现在需要兑换一个目标值amount 元，求兑换所需的最少硬币数。
例如：有2元、5元、10元、20元、50元、100元六种面值的硬币，需要兑换52元，则兑换最少需要三枚硬币：两枚20元硬币和一枚10元硬币。
思路分析：对于这个问题，我们可以把它看成选择一定数量的硬币使其面值之和等于 amount，且硬币数量最少。
为了使硬币数量最少，我们每次都选取当前面值最大并且小于剩余兑换金额的硬币。
这相当于在每个阶段选择局部最优解，最终得到的就是全局最优解。
实现方法：1. 排序：将硬币面额按从大到小的顺序排列。
2. 贪心选择：从面额最大的硬币开始选取，直到兑换金额为 0 或全部面额都被选择过。
代码示例：```pythondef coinChange(coins, amount):coins.sort(reverse=True) # 排序res = 0for coin in coins:while amount >= coin: # 贪心选择amount -= coinres += 1return res if amount == 0 else -1```实例二：区间调度问题假设有 n 个区间 [start, end]，现在需要选出最多的区间，使得它们没有重叠。
例如：有四个区间[1,3]、[2,4]、[3,6]、[5,7]，选出的最多区间数是 3，即选出[1,3]、[3,6]、[5,7]这三个区间。
思路分析：这个问题可以看成排序和贪心选择问题的复合。
首先，我们将所有区间按照 end 非递减的顺序排序。
然后从第一个区间开始，依次选取与当前区间不重叠且start 大于等于当前区间的所有区间，直到所有区间都被检查完。
实验一递归与分治策略一、实验目的：熟练掌握递归与分治策略的思想并应用其解决实际问题。
二、递归与分治策略思想基本思想:将要求解的较大规模的问题分割成k个更小规模的子问题。
对这k个子问题分别求解。
如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
实验题目(1-2):找出从自然数1,2,…，n中任取r个数的所有组合。
算法思想：当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。
这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。
设函数引入工作数组a[ ]存放求出的组合，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一个组合求出后，才将a[ ]中的一个组合输出。
第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未确定组合的其余元素，继续递归去确定；或已确定了组合的全部元素，输出这个组合。
问题描述：找出从自然数1、2、……、n中任取r个数的所有组合。
例如n=5，r=3的所有组合为：（1）5、4、3 （2）5、4、2 （3）5、4、1（4）5、3、2 （5）5、3、1 （6）5、2、1（7）4、3、2 （8）4、3、1 （9）4、2、1（10）3、2、1分析所列的10个组合，可以采用这样的递归思想来考虑求组合函数的算法。
设函数为void find(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。
当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。
这就将求m个数中取k 个数的组合问题转化成求m-1个数中取k-1个数的组合问题。
设函数引入工作数组a[ ]存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一个组合求出后，才将a[ ]中的一个组合输出。
第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未去顶组合的其余元素，继续递归去确定；或因已确定了组合的全部元素，输出这个组合。
最小长度电路板排列问题问题描述小长度电路板排列问题是大规模电子系统设计中提出的实际问题。
该问题的提法是: 将n块电路板以最佳排列方案插入带有n个插槽的机箱中。
n块电路板的不同的排列方式对应于不同的电路板插入方案。
设B={1，2，…，n }是n块电路板的集合。
集合L={ N1 ，N2 ，…，Nm }是n块电路板的m个连接块。
其中每个连接块Ni 是B的一个子集，且Ni 中的电路板用同一根导线连接在一起。
连接块的长度是指该连接块中第1 块电路板到最后1 块电路板之间的距离。
试设计一个分支限界法找出所给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。
例：如图，设n=8, m=5，给定n块电路板及其m个连接块：B={1, 2, 3, 4, 5, 6, 7, 8}，N1={4, 5, 6}，N2={2, 3}，N3={1, 3}，N4={3, 6}，N5={7, 8};这8块电路板两个可能的排列如图所示：在最小长度电路板排列问题中，连接块的长度是指该连接块中第1 块电路板到最后1 块电路板之间的距离。
例如在左图示的电路板排列中，连接块N4的第1 块电路板在插槽3 中，它的最后1块电路板在插槽6中，因此N4的长度为3。
同理N2的长度为2。
图中连接块最大长度为3。
试设计一个分支限界法找出所给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。
输入数据：第一行有2 个正整数n和m。
接下来的n 行中，每行有m个数。
第k行的第j个数为0 表示电路板k不在连接块j 中，1 表示电路板k在连接块j中。
输出数据为计算出的电路板排列最小长度与相应的排列方式。
Sample Input8 51 1 1 1 10 1 0 1 00 1 1 1 01 0 1 1 01 0 1 0 01 1 0 1 00 0 0 0 10 1 0 0 1Sample Output45 4 3 16 2 8 7可用策略电路板排列问题是NP难问题，因此不大可能找到解此问题的多项式时间算法。
算法设计与分析常见习题及详解⽆论在以后找⼯作还是⾯试中，都离不开算法设计与分析。
本博⽂总结了相关算法设计的题⽬，旨在帮助加深对贪⼼算法、动态规划、回溯等算法的理解。
1、计算下述算法执⾏的加法次数：输⼊：n =2^t //t 为整数输出：加法次数 k K =0while n >=1 do for j =1 to n do k := k +1 n = n /2return k解析：第⼀次循环执⾏n次加法，第⼆次循环执⾏1/2次加法，第三次循环执⾏1/次加法…因此，上述算法执⾏加法的次数为==2n-12、考虑下⾯每对函数 f(n) 和 g(n) ，如果它们的阶相等则使⽤Θ记号，否则使⽤ O 记号表⽰它们的关系解析：前导知识：，因为解析：，因为解析:，因为解析：解析:3、在表1.1中填⼊ true 或 false解析：利⽤上题的前导知识就可以得出。
2=21/4n +n +21n +41...+1n +n −n +21n −21n +41....−1f (n )=(n −2n )/2，g (n )=6n1<logn <n <nlogn <n <2n <32<n n !<n ng (n )=O (f (n ))f (n )=Θ(n ),g (n )=2Θ(n )f (n )=n +2,g (n )=n n 2f (n )=O (g (n ))f (n )=Θ(n ),g (n )=Θ(n )2f (n )=n +nlogn ,g (n )=n nf (n )=O (g (n ))f (n )=Θ(nlogn ),g (n )=Θ(n )23f (n )=2(log ),g (n )=n 2logn +1g (n )=O (f (n ))f (n )=log (n !),g (n )=n 1.05f (n )=O (g (n ))4、对于下⾯每个函数 f(n),⽤f(n) =Θ(g(n))的形式，其中g(n)要尽可能简洁，然后按阶递增序排列它们（最后⼀列）解析：最后⼀个⽤到了调和公式：按阶递增的顺序排列：、、、、、、、、、(n −2)!=Θ((n −2)!)5log (n +100)=10Θ(logn )2=2n Θ(4)n 0.001n +43n +31=Θ(n )4(lnn )=2Θ(ln n )2+3n logn =Θ()3n 3=n Θ(3)n log (n !)=Θ(nlogn )log (n )=n +1Θ(nlogn )1++21....+=n1Θ(logn )=∑k =1nk 1logn +O (1)1++21....+n 15log (n +100)10(lnn )2+3n logn log (n !)log (n )n +10.001n +43n +313n 22n (n −2)!5、求解递推⽅程前导知识：主定理前导知识：递归树：例⼦：递归树是⼀棵节点带权的⼆叉树，初始递归树只有⼀个结点，标记为权重W(n)，然后不断进⾏迭代，最后直到树种不再含有权为函数的结点为⽌，然后将树根结点到树叶节点的全部权值加起来，即为算法的复杂度。
最小长度电路板排列问题问题描述小长度电路板排列问题是大规模电子系统设计中提出的实际问题。
该问题的提法是: 将n块电路板以最佳排列方案插入带有n个插槽的机箱中。
n块电路板的不同的排列方式对应于不同的电路板插入方案。
设B={1，2，…，n }是n块电路板的集合。
集合L={ N1 ，N2 ，…，Nm }是n块电路板的m个连接块。
其中每个连接块Ni 是B的一个子集，且Ni 中的电路板用同一根导线连接在一起。
连接块的长度是指该连接块中第1 块电路板到最后1 块电路板之间的距离。
试设计一个分支限界法找出所给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。
例：如图，设n=8, m=5，给定n块电路板及其m个连接块：B={1, 2, 3, 4, 5, 6, 7, 8}，N1={4, 5, 6}，N2={2, 3}，N3={1, 3}，N4={3, 6}，N5={7, 8};这8块电路板两个可能的排列如图所示：在最小长度电路板排列问题中，连接块的长度是指该连接块中第1 块电路板到最后1 块电路板之间的距离。
例如在左图示的电路板排列中，连接块N4的第1 块电路板在插槽3 中，它的最后1块电路板在插槽6中，因此N4的长度为3。
同理N2的长度为2。
图中连接块最大长度为3。
试设计一个分支限界法找出所给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。
输入数据：第一行有2 个正整数n和m。
接下来的n 行中，每行有m个数。
第k行的第j个数为0 表示电路板k不在连接块j 中，1 表示电路板k在连接块j中。
输出数据为计算出的电路板排列最小长度与相应的排列方式。
Sample Input8 51 1 1 1 10 1 0 1 00 1 1 1 01 0 1 1 01 0 1 0 01 1 0 1 00 0 0 0 10 1 0 0 1Sample Output45 4 3 16 2 8 7可用策略电路板排列问题是NP难问题，因此不大可能找到解此问题的多项式时间算法。
首先考虑分治的方法，因为不同连接块连接了不同的电路板，原问题很难分解成互不相关的子问题，所以不考虑分治法。
其次考虑贪婪法，逐步满足每个连接块的局部最优解，很容易想出并不能得到全局最优解。
使用动态规划方法也没有办法解答这个问题。
可用算法有回溯法和分支限界法。
采用回溯法予以解答。
算法设计考虑采用回溯法系统的搜索问题解空间的排列树，找出电路板的最佳排列。
设用数组B表示输入。
B[i][j]的值为1当且仅当电路板i在连接块Nj中。
设low[i] 表示第i块连接块中最左边的电路板的下标，high[i]表示第i快连接块中最右边的电路板的下标。
回溯法搜索排列树的算法一般可以描述如下：void backtrack(int t) {if (t > n)output(x);elsefor (int i = t; i < n; i++) {swap(x[t], x[i]);if (constraint(t) && bound(t))backtrack(t + 1);swap(x[t], x[i]);}}在这个问题中，output(x)，即所有已经排列好，更新最优排列。
当i<n时，电路板排列尚未完成。
X[1：i]的是当前扩展结点所相应的部分排列，high[i]- low[i] 表示相应的部分最大长度，在当前部分排列之后加入一块未排定的电路板，扩展当前部分排列产生当前扩展结点的一个儿子结点。
对于这个儿子结点，计算新的最大长度。
仅当len<bestd时候，算法搜索相应的子树，否则该子树被剪去。
按上述回溯搜索策略设计的算法如下：实例/执行结果ing namespace std;2.class minBoard{3.public:4. minBoard(int n, int m, int *B);5.int* getBestx(){return bestx;}6.int getMinl(){return minl;}7.private:8.int minl;//最优最大长度9.int nowl;//当前最大长度10.int *low;//low[i]表示第i块连接块中最左边的电路板的下标11.int *high;//high[i]表示第i快连接块中最右边的电路板的下标12.int *x;//当前解向量13.int *bestx;//当前最优解向量14.int *B;//B[i][j] = 1表示第i个电路板在第j个连接块中15.int n;//电路板数量16.int m;//连接块数量17.int t;//递归深度18.void Backtrack(int t);//回溯递归函数19.int caNowl(int t);//计算当前排列的最大长度20.};21.minBoard::minBoard(int n, int m, int *B){22.this->B = B;23.this->n = n;24.this->m = m;25.this->t = 1;26. minl = 0x7fffffff;27. nowl = 0;28. x = new int[n + 1];29. bestx = new int[n + 1];30.for (int i = 1; i <= n; ++i)31. {32. x[i] = i;33. }34. low = new int[m + 1];35. high = new int[m + 1];36.this->Backtrack(t);37.}38.int minBoard::caNowl(int t){39.for (int i = 1; i <= m; ++i){40. low[i] = n + 1;41. high[i] = 0;42. }43.for (i = 1; i <= t; ++i)44. {45.for (int j = 1; j <= m; ++j)46. {47.if (B[(m + 1) * x[i] + j])48. {49.if (low[j] > i)low[j] = i;50.if (high[j] < i)high[j] = i;51. }52. }53.54. }55.int maxt = 0;56.for (int j = 1; j <= m; ++j)57. {58.if (high[j] - low[j] > maxt &&low[j] <= n)59. {60. maxt = high[j] - low[j];61. }62. }63.return maxt;64.65.}66.void minBoard::Backtrack(int t){67.if (t > n)//若能够达到说明满足条件nowl < minl68. {69.//更新最优解70.for (int j = 1; j <= n; ++j)71. {72. bestx[j] = x[j];73. }74. minl = nowl;75. }76.else{77.for (int i = t; i <= n; ++i)78. {79.//产生下一个排列80. swap(x[t],x[i]);81.//记录原始nowl当前最大长度用于恢复82.int reNowl = nowl;83.//计算当前组合的最大长度84. nowl = caNowl(t);85.if(nowl < minl){86. Backtrack(t+1);87. }88.//回溯恢复状态89. swap(x[i],x[t]);90. nowl = reNowl;91. }92. }93.}94.int main(){95.int n,m;96.in>>n>>m;97.int *B = new int[(m + 1)*(n + 1)];98.for (int i = 1; i <= n; ++i)99. {100.for (int j = 1; j <= m; ++j) 101. {102.in>>B[i*(m+1) + j];103. }104. }105. minBoard minB(n,m,B);106.107.out<<"Case #"<<Case<<": "<<minB.getMinl()<<endl;108.for (i = 1; i <= n; ++i)109. {110.out<<minB.getBestx()[i]<<" ";111. }112.out<<endl;113. }114.return 0;115.}输入：8 51 1 1 1 10 1 0 1 00 1 1 1 01 0 1 1 01 0 1 0 01 1 0 1 00 0 0 0 10 1 0 0 1输出45 4 3 16 2 8 7算法分析该问题用回溯法求解，搜索一棵树列树。
最坏情况下有n!个节点，对于剪枝函数caNowl复杂度为O(mn)。
n为电路板数量,m为连接块数量。
所以此问题的总复杂度为O(mn*n!) 。
中位数一、 中位数1. 问题描述 给定一个由n 个互不相同的数组成的集合S ，及一个正整数k n ≤，试设计一个O(n)时间算法找出S 中最接近S 的中位数的k 个数。
2. 设计思路1) 可用策略 对数组排序，然后取(,]22S k S k -+范围内的k 个数。
2) 选用策略1. 找中位数x ；2. 计算S 中各个数与该中位数x 的差值：||i s x -,组成新的非负数集合'S ；3. 查找'S 中k 个小的数对应于集合S 中的元素。
3. 算法设计/描述1. 找中位数x ；2. 计算S 中各个数与该中位数x 的差值：||i s x -,组成新的非负数集合'S ；3. 查找'S 中第k 小的数，记为k x ；4. 查找'S 中所有小于等于k x 的数；5. 根据第4步查找的结果找出在集合S 中对应的数即为S 中最接近S 的中位数的k 个数。
关于第三步,求数组中第k 小的数,线性时间复杂度的具体算法描述如下: 基于快排序思想，步骤如下：1. 随机选择一个支点2. 将比支点大的数，放到数组左边；将比支点小的数放到数组右边；将支点放到中间(属于左部分)3. 设左部分的长度为L,当K < L 时，递归地在左部分找第K 大的数当K > L 时，递归地在有部分中找第(K - L)大的数当K = L 时，返回左右两部分的分割点（即原来的支点），就是要求的第K 大的数4. 实例/执行结果输入：{9,6,4,2,1,5,7,3,8,18,32,14,13},5S k ==输出：5,6,7,8,95. 分析T(n)/S(n)1) 策略1T(n)取决于所采用的排序算法，根据已知的效率比较高的排序算法如归并排序或者堆排序，()T n =(lg )O n n ，()S n =(1)O2) 策略2()S n =()O n第一步，()()T n O n =；第二步，一遍扫描即可，()()T n O n =；第三步，采用STL 中的nth_element 算法，该算法的平均()()T n O n =； 第四步，一遍扫描找出符合要求的数即可，因此()()T n O n =。
