课外资料计算机常用算法

《课外资料计算机常用算法》由会员分享，可在线阅读，更多相关《课外资料计算机常用算法（35页珍藏版）》请在金锄头文库上搜索。

1、计 算 机 常 用 算 法,7、动态规划,1、穷举法（枚举法）,2、递归法,3、回溯法,4、模拟法,6、分治法,5、贪心法,枚举法穷举法,枚举法（通常也称为穷举法）是指在一个有穷的可能的解的集合中，枚举出集合中的每一个元素，用题目给定的约束条件去判断其是否符合条件，若满足条件，则该元素即为整个问题的解；否则就不是问题的解。枚举的思想往往是最容易想到的一种解题策略，枚举法从本质上说是一种搜索的算法，但适用枚举法解题必须满足下列条件：,1）可预先确定解元素的个数n,且问题的规模不是特别大；,2）对于每个解变量A1，A2，。An的可能值必须为 一个连续的值域。,枚举法的算法流程：设ai1为解变量Ai

2、的最小值；aik为解变量的最大值；其中1 i n. A1 a11,a12,a1K A2 a21,A22,A2K Ai ai1,Ai2,AiK An an1,An2,AnK 我们称解变量为枚举变量。例如某问题的枚举变量有三个： A1， A2， A3。,A11，2， A22，3，4， A3 5，6，7 则问题的可能解为（ A1 ，A2， A3 ） （1，2，5），（1，2，6），（1，2，7），（1，3，5）， （1，3，6），（1，3，7），（1，4，5），（1，4，6）， （1，4，7），（2，2，5），（2，2，6），（2，2，7）， （2，3，5），（2，3，6），（2，3，7），（2，4

3、，5）， （2，4，6），（2，4，7） 在上述18个可能解的集合中，满足问题给定的检验条件的解元素即为问题的解。,枚举法的优化方法： 1）减少枚举的变量，在使用枚举法之前，先考虑一下解元素之 间的关联，将一些非枚举不可的解元素列为枚举变量，其他元素通过计算得出解元素的可能值。,例1、巧妙填数。 将19这9个数字填入到9个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三个三位数是第一行的2倍，第三行的三位数是第一行的三倍，应怎样填数。如图,2）减少枚举变量的值域,3）分解约束条件，将拆分的约束条件嵌套在相应的循环体间。,本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！

4、=362880种方案，在这些方案中符合条件的即为解。因此可以用枚举法。,但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。,递归法,一个函数、过程、概念或数学结构，如果在其定义或说明内部直接或间接地出现有其本身的引用，或者是为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态这种用自己来定义自己的方法，称之为递归或者是递归定义。 在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。子程序直接调用自己，称为直接递归；嵌套关系的子程序a和b,内层的b调用外层的a,是间接递归；平级

5、关系的子程序a和b,其中a调用了b,b又调用了a,这也是间接递归。,数学函数式递归,例1、阶乘n!=1*2*3*（n-1）*n,算法分析：要求n!,只需求出(n-1)!,因为n!=n*(n-1)!,要求出(n-1)!,只需求出(n-2)!,因为(n-1)!=(n-1)*(n-2)!,所以可得到阶乘的递归定义式：,例2、斐波那契数列0，1，1，2，3，5，8，13，21，34，55，,从第三项开始，每一项是前两项的和，其递归定义式为：,求此数列第n项。,例3、楼梯共有n层台阶，上楼可以一步走一层，也可以一步走两层。编程序计算上n层台阶共有多少种走法？,回溯法,回溯是重要的算法之一，有一些问题，要

6、求找到一组解，或要求找到一个满足某些限制的最优解。对于解决这样的问题，可以通过使用彻底的搜索方法来解决。然而，彻底搜索的运算量很大，有时大到计算机承受不了的程度。彻底的搜索，要进行大量的比较，大量的舍弃，以大量的运算，大量的时间为代价。因此，用穷举法解某些实际问题是不现实的，回溯算法为我们提供了一个好方法，使用回溯法可以大大减少实际的搜索。例如，迷宫问题，八皇后问题，骑士周游世界问题。,算法思想： 通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索往前试探，若试探成功，就得到解，若试探失败，就逐步往回退，换别的路线再往前试探。实际上是广度与深度搜索结合的搜索，深度搜索过程中碰到条件不满

7、足，则退回上一层，在每一层上也进行全面的搜索。,关键：找到回溯的条件。,求解八皇后问题： 在n*n个方块排成n行n列的棋盘上，如果两个皇后位于同一行、同一列或同一对角线上，则称它们互相攻击。现在要求找出使棋盘上n个皇后互不攻击布局。,列号：（8，2，4，1，7，5，3，6）,分析： 为了找出互不攻击的布局，需要对n*n个方案进行检查，将有攻击的布局剔除掉。这是一种穷举法。但这种方法对于较大的n，其工作量会急剧的增大，而逐一列举是没有必要的。,算法：由于在第一行上的皇后在第一列，则第二行上的皇后就不可能在第一列。首先将每一行上安置一个皇后，并假设第i个皇后在第i行上，用一个一维数组queen1n

8、用于记录安放皇后的过程中随时记录第i行上的皇后所在的列号。由此可知，在这种情况下，实际上已经剔除了两个皇后在同一行的可能性。因此，在安置每一行上的皇后时，只需考虑每两个皇后不能在同一列或同一对角线上的可能性。,从第一行（即i=1）开始布局。 设前i-1行上的皇后已布局好，即它们互不攻击。现考虑安排第i行上皇后位置，使之与前i-1行上的皇后也互不攻击。为了实现这一点，可以从第i行皇后的当前位置开始向右搜索。,引进集合a,b,c分别表示各列、各条右对角线和各条左对角线上是否放置了皇后。在同一右对角线上，i-j是常量。在同一左对角线上，i+j是常量。第i行第j列上放皇后在第i-j条右对角线和第i+j

9、条左对角线上。能放皇后时为真，不能放皇后时为假。数组queen存放各行皇后所在的列号。,随机数的介绍 在自然界和日常生活中,许多现象具有不确定的性质,有些问题甚至很难建立数学模型,或者很难用计算机建立递推,递归,枚举,回溯法等算法.在这种情况下,一般采用模拟策略.在对实际问题中的随机现象进行数学模拟时,利用计算机产生的随机数是必不可少的,由于用计算机产生的随机数总是受字长的限制,其随机的意义要比实际问题中真实的随机变量稍差,因此,通常将计算机产生的随机数称为伪随机数.,TURBO.PASCAL的系统中有两个产生伪随机数的单元: Randomize过程伪随机数发生器初始化, Random(ran

10、ge)函数产生一个范围在0 xrange的伪随机数x，range和x都为word类型.,模拟法,模拟法: 就是模拟某个过程,通过改变数学的各种参数,进而观察变更这些参数所引起过程状态的变化.一般题目给定或者隐含某一概率.设计者利用随机函数和取整函数设定某一范围的随机值,将符合概率的随机值作为参数.然后根据这一模拟的数学模型展开算法.,模拟策略的关键: 是如何按照概率的要求确定随机值的范围.这个随机值设计得好,模拟效果就好.,例一: 甲乙两人抓n个棋子,谁抓最后一个谁赢.每一次只能抓一个或两个,但不能为零个.甲方为计算机,对弈方为乙(由随机数替代).设计一个程序使计算机尽可能赢. 输入:棋子数n

11、,先下手的方k(k=b对方先下;k=a,计算机先下). 输出:游戏过程.一行表示一步:现有棋子数,被抓走的棋子数.最后一行为赢方的名字.,这个问题的算法核心是:要置对方于死地,必须使余下的棋子是1+2=3的整数倍.因此,当甲方处在棋子数是3的倍数时要小心等待.一旦对方错一步,赶紧控制余下棋子数为3 的倍数.设: b乙方抓走的棋子数.每一次轮到乙方抓时,则随机产生b(1+random(2). a- 甲方抓走的棋子数.轮到甲方抓时,若剩余的棋子数非3的整数倍,则应使抓掉后是3的整数倍.若剩余的棋子数为3的整数倍,则随机产生a(1+random(2).,练习： 假设有一堆小石子，二人轮流去取，谁拿走

12、最后一颗石子便输。先让甲规定石子总数N以及每次最多取多少颗数k（n=2*k+1），甲每次取a颗, （N,k,a均为随机数），乙怎样取赢的可能性最大？设甲为计算机产生的随机数，乙为由你编的计算机程序。,贪心法是从问题的某一个初始解出发,向给定的目标推进.但不同的是 ,推进的每一步不是依据某一固定的递推式,而是做一个当时看似最佳的贪心选择,不断地将问题实例归纳为更小的相似的子问题,并期望通过所做的局部最优选择产生出一个全局最优解. 背包问题：在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有n 种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为c，物品i 需占用wi 的空间，价值

13、为pi。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。如何选择量度标准才能找到最优解？,找零钱问题：一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币。(求解所用方法即为贪心算法）,分治策略指的是分而治之的方法。当我们处理大规模问题时，求解可能比较困难，对于这类问题，我们可以将原问题分解成规模较小而结构与原问题相似的子问题，然后递归地解决这些子问题，最后由这些小问题的解构造出原问题的解。因此一个问题能否用分治法解决，关键是看该问题算法能

14、否将原问题分成n个规模较小而结构与原问题相似的子问题。递归地解决这些子问题，然后合并其结果就得到原问题的解。当n=2时的分治法又称二分法。,分治策略一般分为三个步骤： 1、分解：将要解决的问题划分成若干个规模较小的同类问题。 2、求解：当子问题划分得足够小时，用较简单的方法解决。 3、合并：按原问题的要求，将子问题的解逐层合并成原问题的解。,使用分治策略的问题常常要借助递归的结构，逐层求解，当问题规模达到某个简单情况时，解容易直接得出，而不必继续分解。其过程大致如下：,分 治 策 略,If 问题不可分 then begin 直接求解； 返回问题的解； else begin 从原问题中划分出含1

15、/n运算对象的子问题1； 递归调用分治法过程，求出解1； 从原问题中划分出含1/n运算对象的子问题2； 递归调用分治法过程，求出解2； 从原问题中划分出含1/n运算对象的子问题n； 递归调用分治法过程，求出解n； 将解1、解2、解n组合成整个问题的解； end;,例1、求一组数中的最大值和最小值。,算法分析：假设数据个数为n，存放在数组A1n中。可以直接 进行比较。 min:=a1;max:=a1; for i:=2 to n do if aimax then max:=ai else if aimin then min:=ai,使用分治策略：把n(n2)个数据先分成两组，分别求最大值、最小值

16、，然后分别将这两组的最大值和最小值进行比较，求出全部元素的最大值和最小值。 若分组后元素个数还大于2，则再次分组，直至组内元素小于等于2。,使用这一算法，比较次数为2（n-1）。若n=10，则比较18次。,动态规划是对最优化问题的一种新的算法设计方法。在实际生活中，有这样的一类问题，它们的活动过程可以分为若干个阶段，而且在任意一个阶段x，过程在阶段x以后的行为，仅依赖于x阶段的过程状态，而与x之前过程如何达到这种状态的方式无关，这样的过程就构成一个多阶段决策过程。由此提出了解决这类问题的“最优化原理”，创建了最优化问题的一种新的算法设计方法-动态规划。,动态规划解题方法是一种高效率的解题方法，可以解决相当大的信息量，其时间复杂度通常为O(n2)、O(n3)等。它适用的原则是优化原则，它可以将整体优化分解为若干个局部优化。,动态规划算法,动态规划算法的一般模式： 1）划分阶段：按照问题