经典c++编程实例

这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡： # i=1;i=i; if(j10,9,7,8-10,7,9,8-7,10,9,8(交换 3次 ) 第二轮： 7,10,9,8-7,10,8,9-7,8,10,9(交换 2 次 ) 第一轮： 7,8,10,9-7,8,9,10(交换 1次 ) 循环次数： 6 次 交换次数： 6 次 其他： 第一轮： 8,10,7,9-8,10,7,9-8,7,10,9-7,8,10,9(交换 2次 ) 第二轮： 7,8,10,9-7,8,10,9-7,8,10,9(交换 0 次 ) 第一轮： 7,8,10,9-7,8,9,10(交换 1次 ) 循环次数： 6 次 交换次数： 3 次 上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+.+成公式就是 1/2*(n。现在注意，我们给出 若存在一常量 K 和起点 当 n=，有 f(n) i=0;0,8,7-8,10,9,7-7,10,9,8(交换 3次 ) 第二轮： 7,10,9,8-7,9,10,8-7,8,10,9(交换 2 次 ) 第一轮： 7,8,10,9-7,8,9,10(交换 1次 ) 循环次数： 6 次 交换次数： 6 次 其他： 第一轮： 8,10,7,9-8,10,7,9-7,10,8,9-7,10,8,9(交换 1次 ) 第二轮： 7,10,8,9-7,8,10,9-7,8,10,9(交换 1 次 ) 第一轮： 7,8,10,9-7,8,9,10(交换 1次 ) 循环次数： 6 次 交换次数： 3 次 从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样也是1/2*(n，所以算法的复杂度仍然是 O(n*n)。由于我们无法给出所有的情况，所以只能直接 告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。 现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下）这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中选择最小的与第二个交换，这样往复下去。 # i=0;i =9 =8 =4()10,9,8,7-()10,9,8,7-()7,9,8,10(交换 1次 ) 第二轮： 7,9,8,10-7,9,8,10()-()7,8,9,10(交换 1次 ) 第一轮： 7,8,9,10-()7,8,9,10(交换 0次 ) 循环次数： 6 次 交换次数： 2 次 其他： 第一轮： 8,10,7,9-()8,10,7,9-()8,10,7,9-()7,10,8,9(交换 1次 ) 第二轮： 7,10,8,9-()7,10,8,9-()7,8,10,9(交换 1次 ) 第一轮： 7,8,10,9-()7,8,9,10(交换 1次 ) 循环次数： 6 次 交换次数： 3 次 遗憾的是算法需要的循环次数依然是 1/2*(n。所以算法复杂度为 O(n*n)。 我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以 f(n) i=1;i=0) & ( & =0 & =0 & =0 & =0 & =0 & =0 & =0 & =0 & =0 & 9,10,8,7(交换 1次 )(循环 1 次 ) 第二轮： 9,10,8,7-8,9,10,7(交换 1次 )(循环 2 次 ) 第一轮： 8,9,10,7-7,8,9,10(交换 1次 )(循环 3 次 ) 循环次数： 6 次 交换次数： 3 次 其他： 第一轮： 8,10,7,9-8,10,7,9(交换 0次 )(循环 1 次 ) 第二轮： 8,10,7,9-7,8,10,9(交换 1次 )(循环 2 次 ) 第一轮： 7,8,10,9-7,8,9,10(交换 1次 )(循环 1 次 ) 循环次数： 4 次 交换次数： 2 次 上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，因为其循环次数虽然并不固定，我们仍可以使用 上面的结果可以看出，循环的次数 f(n) a,n) i=0;i!=n;i+) i,j; i = j = 2; /求中间值 i& (j; if(递归右半边 if(i) i, , = 10,9,8,7,6,5,4; ); i=0;i 1; 1; t; /正向的部分 i=i= if(i x, if( x ; = 9; = 5; = 3; = 1; k,s,w; i=0;i=0) & (w n) i=n,j, ，退出循环 i=0;j+1) j; j=j+1; j+1= ! a7=32,43,22,52,2,10,30; a,7); i=0;i0;2) /设定步长 i=i =0&vjvj+ j-= /比较相距 逆 序 互 换 vj; vj=vj+ vj+ /帕斯卡恒等式为 C(n,k)=C(C(k) n,r) if( ; if(r=1|r=，我们有 C(n,1)=C(n,n n; if(r=0|r=n)/根据组合定义，我们有 C(n,0)=C(n,n)=1 ; r)+ /选择法对数组排序的函数模板 , T i,j; i=0;j) i; i=j; j= /冒泡法对数组排序的函数模板 *d,n) i,j; T t; i=0;idj+1) t=dj; dj=dj+1; dj+1=t; /插 入法对数组排序的函数模板 A, n) i, j; T i = 1; i =0& , T 0, 1; 1; 将 236进制数与 10进制数相互转换 /将 236进制数转换成 10进制数 i=0, ; i) i=0 & i=A & i=a & i # m,n,i=1,j,k=1,o; 请输入总共的人数 ,记为 n n); %d,&n); n+1; n+1; 请输入几号出圈 ,记为 m n); %d,&m); n*n); i # # # ; # 0; TR UVgtxy N; i,j; i=0;iN;) i,j,; i=0;igtij; igtij & gtij0) gtij; ) i=0;i # # # ; # 0; TR UVgtxy N; i,j; i=0;iN;) i=0;igtij; iUi+Vjij & Ui+Vjij0) i+Vjij; ) i=0;i /考虑覆盖情况 d = () 1; s = () 1; = 4 ) /循环展开，提高执行效率 * * * * * * * * = 4; * * 4 ) *d+ = *s+; *d+ = *s+; *d+ = *s+; *d+ = *s+; = 4; *d+ = *s+; 出现次数相当频繁 1常用的算法设计方法： 代法 举搜索法 推法 归法 婪法 治法 态规划法 溯法 算法基础部分 : 算法是对 特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。 算法具有以下 5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量 。 所以对应的算法设计的要求： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 迭代法： 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为 f(x)=0，用某种数学方法导出等价的形式 x=g(x)，然后按以下步 骤执行： （ 1）选一个方程的近似根，赋给变量 （ 2）将 后计算 g(并将结果存于变量 （ 3）当 差的绝对值还小于指定的精度要求时，重复步骤（ 2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的 认为是方程的根。上述算法用 【算法】迭代法求方程的根 始近似根； x1= x0=g( /*按特定的方程计算新的近似根 */ 方程的近似根是 %fn”， 迭代算法也常用于求方程组的根，令 X=（ ， 设方程组为： xi=) (I=0， 1， 则求方程组根的迭代算法可描述如下： 【算法】迭代法求方程组的根 i=0; yi-xi)； i=0;i a,b,c,d,e,f; a=1;a # # 1000 a ,k)/已知 !,求出 k！在 b,m=a0,i,j,r,b=( ) (m+1); i=1;i0; %d” ,ai); nn” ); an,k; n: “ ); %d” ,&n); a0=1; a1=1; a,1); k=2; 写成递归函数有： n) n=0) 0; n=1) 1; n1) 递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为 n）的求解推到比原问题简单一些的问题（规模小于 n）的求解。例如上例中，求解 n)，把它推到求解 也就是说，为计算 n)，必须先计算 而计算 又必须先计算 依次类推，直至计算 )和 )，分别能立即得到结果 1和 0。在递推阶段，必须要有终止递归的情况。例如在函数 ，当 和 0的情况。 在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到 )和 )后，返回得到 )的结果，在得到了 结果后，返回得到 n)的结果。 在编写递归函数时要注意，函数中的局部变量和参数只是局限于当前调用层，当递推进入“简单问题”层时 ，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。 由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。例如上例计算斐波那契数列的第 n)应采用递推算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第 【问题】背包问题 问题描述：有不同价值、不同重量的物品 从这 案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。 设 、 品的价值分别为 、 用递归寻找物品的选择方案。设前面已有了多种选择的方案，并保留了其中总价值最大的方案于数组 ，该方案的总价值存于变量 前正在考察新方案，其物品选择情况保存于数组 。假定当前方案已考虑了前 在要考虑第 前方案已包含的物品的重量之和为 此，若其余物品都选择是可能的话，本方案能达到的总 价值的期望值为 法引入 当一旦当前方案的总价值的期望值也小于前面方案的总价值 续考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比 方案不会被再考察，这同时保证函数后找到的方案一定会比前面的方案更好。 对于第 （ 1）考虑物品 种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后，继续递归去考虑其余物品的选择。 （ 2）考虑物品 i 不被选择，这种可能性仅当不包含物品 大的方案的情况。 按以上思想写出递归算法如下： 品 i，当前选择已达到的重量和，本方案可能达到的总价值 /*考虑物品 (包含物品 i 是可以接受的 ) 将物品 i # N 100 ,; aN; n; i,tw, k; /*考虑物品 i 包含在当前方案中的可能性 */ tw+aii # N 100 ; aN; k,n; ; i,tw, i; ii a,n) i,k,f; tw,tv,; .0,k=0;k=0) f=itw=itv=if) : i; tw+aii # * * n, i, *a; * * *j; *p, *q; 输入箱子容积 n” ); %d” ,& 输入物品种数 n” ); %d” ,&n); A=()n); 请按体积从大到小顺序 输入各物品的体积：” ); i=0;i; j=j!=j=j-j-ai) j= j=(); j-i; j- j; j; j-; j-ai; q=j-q!=q-q=q- q= p-j-j-p; p-q-p; 共使用了 % 各箱子装物品情况如下：” ); j=i=1;j!=j=j-i+) 第 %2d 只箱子，还剩余容积 %4d，所装物品有； n” ,I,j- p=j-p!=p=p- %4d” ,p-); n” ); 治法 1分治法的基本思想 任何一个可以用计算机求解的问题所需的计算时间都与其规模 题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于 n=1时，不需任何计算； n=2时，只要作一次比较即可排好序； n=3时只要作 3次比较即可，。而当n 较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。 分治法的设计思想是，将一个难以 直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 如果原问题可分割成 k 个子问题（ 1表示具有， 中，约定 v0= 若 线段 将多边形分割 成凸的两个子多边形 和 。多边形的三角剖分是一个将多边形分割成互不重迭的三角形的弦的集合 T。图 1 是一个凸多边形的两个不同的三角剖分。 (a) (b) 图 1 一个凸多边形的 2个不同的三角剖分 在凸多边形 中，各弦互不相交且弦数已达到最大，即 中的弦必与 一个有 好有 凸多边形最优三角剖分的问题是：给定一个凸多边形 P=以及定义在由多边形的边和弦组成的三角形上的权函数。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。 可以定义三角形上各种各样的权函数。例如：定义 ( | +| +| ，其中， | 是点 应于此权函数的最优三角剖分即为最小弦长三角剖分。 （ 1）最优子结构性质 凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸（ n+1）边形 P=的一个最优三角剖分 1 k 个部分权的和，即三角形 多边形 的权和 的权之和。可以断言由 为若有 或 的更小权的三角剖分，将会导致 T 不是最优三角剖分的矛盾。 （ 2）最优三角剖分对应的权的递归结构 首先，定义 ti， j（ 1 即最优值。为方便起见，设退化的多边形 具有权值 0。据此定义，要计算的凸（ n+1）边多边形 t1， n。 ti， j的值可以利用最优子结构性质递归地计算。由于退化的 2顶点多边形的权值为 0，所以 ti， i=0， i=1， 2， n 。当 j一 i 1时，子多边形 至少有 3个顶点。由最优于结构性质， ti， j的值应为 ti， k的值加上 tk+1， j的值，再加上 在 i k 此， ti， j可递归地定 义为： （ 3）计算最优值 下面描述的计算凸（ n+1）边形 P=的三角剖分最优权值的动态规划算法入是凸多边形 P=的权函数，输出是最优值 ti， j和使得 ti， k+tk+1， j+（ 到最优的位置（ k=） si， j， 1 i j n 。 ， w)； n=pi=1 to n ti,i:=0; to n do i=1 to do j=i+ti,j= ; k=i to do q=ti,k+tk+1,j+ ( if ti， j的同时，还在 si， j中记录了此最优三角剖分中与边（或弦） 此，利用最优子结构性质并借助于 si， j， 1 i j n ，凸（ n+l）边形 P=的最优三角剖分可容易地在 (n)时间内构造出来。 溯法 回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。 1、回溯法 的一般描述 可用回溯法求解的问题 P，通常要能表达为：对于已知的由 n 元组（ ， 成的一个状态空间 E=（ ， i=1， 2， n，给定关于 ，要求 的全部约束条件的所有 中 |有限， i=1， 2， n。我们称 的全部约束条件的任一 的一个解。 解问题 对 的全部约束，若满足，则为问题 但显然，其计算量是相当大的。 我们发现，对于许多问题，所给定的约束集 ， 足 D 中仅涉及到 ， 所有约束意味着 j（ 此，对于约束集 ，一旦检测断定某个 ， 反 ， 一个约束，就可以肯定，以（ ， 前缀的任何 ， ， 不会是问题 而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。 回溯法首先将问题 P 的 n 元组的状态空间 E 表示成一棵高为 n 的带权有序树 T，把在 E 中求问题 中搜 索问题 可以这样构造： 设 的元素可排成 ) ， ) ， xi(， |=i=1， 2， n。从根开始，让 层的每一个结点都有 儿子。这 从左到右的次序，分别带权 (1) ， (2) ， (， i=0， 1， 2， 这种构造方式， E 中的一个 ， 应于 ， 之亦然。另外，对于任意的 0 i E 中 ， 一个前缀 ， 应于 条边的权分别为 x1， 之亦然。特别， ，对应于 因而，在 的一个解等价于在 求从 ， 足约束集 自然的 一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀 1元组（ 前缀 2元组（ ，前缀 x1， ，直到 i= 在回溯法中，上述引入的树被称为问题 的状态结点；树 的一个解状态结点；树 的全部约束的任意一个叶子结点被称为问题 对应于问题 支定界法： 分支限界法： 这是一种用于求解组合优化 问题的排除非解的搜索算法。类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。 算法思想：分枝定界（ 另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对 个活节点有且仅有一次机会变 成 一个节点变为 生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个 活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。 有两种常用的方法可用来选择下一个 然也可能存在其他的方法）： 1) 先进先出（ F I F O） 即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活 节点表的性质与队列相同。 2) 最小耗费或最大收 益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找 一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个 的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个 2几个重要的算法程序 排序 堆排序也是选择排序的一种，其特点是，在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果。 堆的定义 : 堆是满足下列性质的数列 ， 或 若将此数列看成是 一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左 /右子树不空时，根结点的值小于 (或大于 )左 /右子树根结点的值。 由此，若上述数列是堆，则 别称作小顶堆或大顶堆。 堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。具体作法是：先建一个“大顶堆”，即先选得一个关键字为最大的记录，然后与序列中