下载文档原格式
常用算法设计方法第1节计算机算法概述 (1)1.1算法的五个特性 (1)1.2算法设计的要求 (1)1.3算法效率的度量 (1)第2节各种常规算法 (2)2.1迭代法 (2)2.2穷举搜索法 (3)2.3递推法 (3)2.4递归法 (3)2.5分治法 (4)2.5.1 分治法思想 (4)2.5.2 分治法时间复杂度计算 (5)2.6动态规划法 (7)2.7回溯法 (8)2.8贪心法 (9)2.9分支限界法 (10)2.10概率算法 (10)2.11字符串的模式匹配 (11)第3节附录部分 (12)3.1使用递推法求N的阶乘程序代码 (12)第1节 计算机算法概述计算机算法是对特定问题求解步骤的描述，它是指令的有限序列。
为解决某问题的算法与为该问题编写的程序含义是相同的。
常用的表示算法的语言有：自然语言、流程图、盒图、程序设计语言和伪代码。
1.1 算法的五个特性1. 有限性：算法必须在执行有限条指令之后结束，每条指令执行的时间也必须是有限的。
2. 确定性：算法中每一条指令必须有确切的含义，读者和计算机在理解时不会产生二义性，并且在相同条件下，相同的输入只能得到相同的输出。
3. 可行性：算法能把问题真正的解决。
即不能是理论正确但无法在计算机上实现的算法。
4. 输入：一个算法有零个或多个输入。
1.2 算法设计的要求1. 正确性：算法应当满足具体问题的需求。
2. 可读性：算法应该能让人读懂，能被计算机运行。
3. 健壮性：算法应该具有容错处理能力，不容易被击垮。
4. 高效率与低存储量要求：效率指程序的执行时间（越短越好），算法要占用计算机一定的存储量（越小越好）。
1.3 算法效率的度量1. 时间复杂度根据不同的输入，将算法的时间复杂度分为三种情况：(1) 最佳情况：使算法执行时间最少的输入。
一般不进行算法在最佳情况下的时间复杂度分析。
(2) 最坏情况：使算法执行时间最多的输入。
一般会进行算法在最坏时间复杂度的分析，因为最坏情况是在任何输入下运行时间的一个上限，而且对于某些算法来说，最坏情况是相当频繁的。
填空题：1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性有穷性可行性 0个或多个输入一个或多个输出2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低。
3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。
5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解6.动态规划算法的基本思想是将待求解问题分解成若干子问题_，先求解子问题，然后从这些子问题的解得到原问题的解。
7.以深度优先方式系统搜索问题解的算法称为回溯法。
8.0-1背包问题的回溯算法所需的计算时间为o(n*2n),用动态规划算法所需的计算时间为o(min{nc,2n})。
9.动态规划算法的两个基本要素是最优子结构和重叠子问题。
10.二分搜索算法是利用动态规划法实现的算法。
11.一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有时间复杂性和空间复杂性之分。
12.出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同。
13.动态规划算法有一个变形方法备忘录方法。
这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。
14、这种不断回头寻找目标的方法称为回溯法。
15、直接或间接地调用自身的算法称为递归算法。
16、 记号在算法复杂性的表示法中表示渐进确界或紧致界。
17、由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
18、建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。
19、下列各步骤的先后顺序是②③④①。
①调试程序②分析问题③设计算法④编写程序。
20、最优子结构性质的含义是问题的最优解包含其子问题的最优解。
拉斯维加斯算法范文拉斯维加斯算法最早由László Babai于1979年提出，该算法的目的是解决组合优化问题，如图论中的Traveling Salesman Problem（TSP，旅行商问题）。
TSP是一个NP困难问题，即在给定一组城市和每对城市间的距离，找到一条旅行路径，使得旅行的总距离最小且每个城市只能访问一次。
通常来说，解决NP困难问题无法在多项式时间内获得最优解，因此在实践中我们需要采用近似算法或者随机算法。
拉斯维加斯算法是一种随机算法，其在每次运行时采用了不同的随机数选择，但保证在有限时间内能够找到一个最优解。
拉斯维加斯算法的基本思想是：通过不断重复运行算法，并在每次运行中应用不同的随机数选择，直到找到一个满足条件的解。
在TSP问题中，每次运行时，算法会随机选择一个起点城市，并依据一定规则选择下一个城市。
直到访问了所有城市，算法会回到起点城市，结束运行，并记录下该次运行所得到的旅行路径总距离。
重复运行数次后，选择总距离最小的路径作为算法的输出。
拉斯维加斯算法的主要优点是能够保证在有限时间内找到一个最优解。
然而，其缺点是运行时间不确定，因为每次运行所需的时间是不确定的，且多次运行的总时间也无法预测。
因此，拉斯维加斯算法在实际应用中通常用于对问题进行初步探索，或者用于小规模问题的求解。
除了TSP问题，拉斯维加斯算法还可以应用于其他各种组合优化问题，如图着色、子集求和等。
在这些问题中，算法也会根据问题的特定要求，选择不同的随机数选择规则，以确保找到一个满足条件的解。
总的来说，拉斯维加斯算法在组合优化问题的求解中具有一定的优势。
虽然其运行时间不确定，但其能够在有限时间内找到一个最优解的特性，使得它在实际应用中具有一定的价值。
通过不断重复运行，并结合随机数选择，拉斯维加斯算法能够在保证解的正确性的前提下，尽可能寻找到一个最优解。
对比舍伍德算法、拉斯维加斯算法、蒙特卡洛算法的适用范围以及它们的优缺点。
一、舍伍德算法：•特点舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。
当一个确定性算法在最坏情况下的计算复杂性与其在平均惜况下的计算复杂性有较大的差别时，可在这个确定性算法中引入随机性将它改造成一个舍伍徳算法，消除或减少问题的好坏实例间的这种差别。
舍伍德算法的精髓不是避免算法的最坏悄形行为，而是设法消除这种最坏悄形行为与特定实例之间的关联性。
舍伍德算法不会从整体上或平均的改善问题求解的时间复杂度，但可以对一些特别耗时的特定输入改善至较适中的时间复杂度。
设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)o设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A 所需的平均时间为_ 艺© O)“小卞厂这显然不能排除存在xGXn使得tA(x)»tA(n)的可能性。
希望获得一个概率算法B,使得对问题的输入规模为n的每一个实例均有心⑴二几何+心)这就是舍伍德算法设计的基本思想。
当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。
•适用范围：1.快速排序算法2.线性时间选择算法上述两算法选择合适的划分基准，舍伍德算法随机地选择一个数组元素作为划分基准，这样既能保证算法的线性时间平均性能，乂避免了计算拟中位数的麻烦。
3.搜索有序表利用数组的小标的索引性质，可以设讣一个随机化搜索算法，以改进算法的搜索时间复朵性。
即随机抽取数组元素若干次，从较近搜索元素x的位置开始做顺序搜索。
4.跳跃表在跳跃表中随机增加附加指针，以及在该结点处应随机增加指针。
二、拉斯维加斯算法：•特点：拉斯维加斯算法不会得到不正确的解。
一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。
与蒙特卡罗算法类似，拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。
但对所求解的问题，用同一个拉斯维加斯算法反复求解多次，可以使得求解失效的概率任意小。
拉斯维加斯活动流程及规则一、游戏介绍俄罗斯转盘俄罗斯转盘由0到36个数字组成，红黑两色，单双（赔率为1：1） 0为绿色庄赢通吃由1到12分为小门，并分为红小门和黑小门,13到24为中门，并分为红中门和黑中门，25到36为大门，并分为红大门和黑大门（赔率为1：5），1到36为特码（赔率为1：30）21点（两张牌）1. 庄家闲家各发牌两张，庄家不可以补牌，闲家最多可补一张牌2. 2到10的牌所代表的点数即为其牌面的数目；J、Q、K视为10点；A有两种算法，11或1，A计为11时是软牌（如：A、6点数和为软17），A计为1时是硬牌（如：A、6、Q总点数为硬17）骰盅比大小1、10以下为小，11以上为。
（赔率为1：1）2、三个骰当中有两一样的为对。
（赔率为1：8）3、任意豹子（赔率为1：14）4、单调豹子（赔率为1：150）5、其它详见面板二、游戏流程及规则1、兔子女郎登记来宾信息并发放游戏筹码。
新客户发送：1000元筹码老业主发送（凭房号和姓名）：2000元筹码入会客户发送（凭会员卡）：3000元筹码2、客人拿到筹码后就可开始游戏 21点\俄罗斯转盘\骰盅比大小3、游戏一天分为三个时段第一时间段 10:00—12:00第二时间段 12:30—15:00第三时间段 15:30— 18：004、每个时段结束后，由荷官负责统计筹码，并收回筹码，由贵公司人员发放礼品。
5、每个时段结束后，全部客户手上筹码收回，重新登记开始。
6、每个时间段的奖品：第一名二名礼品为: 合金仿真遥控宝马车一辆(大小1:14) 宝马公司授权制造的第二名三名礼品为: 合金仿真遥控法拉利一辆(大小1:24)第三名四名礼品为: 合金仿真甲壳虫一辆(大小1:18)每个客户参与都能获得参与奖一份靓车一辆 (大小1:32 )营销客服部 2011年6月16日。
量子Monte Carlo模拟法量子Monte Carlo法是目前计算多粒子凝聚态系统的最精确的方法。
一个有N个相互作用的电子的系统，需要3N维的Schrodinger方程才能求解。
这看起来根本做不到，因此才有了独立电子近似的能带论等近似理论。
然而，以随机行走为基础的量子Monte Carlo模拟，恰是直接求解多体Schrodinger方程的方法，它通过对多体试验波函数进行抽样，进而优化，获得系统的性质。
要想深入的掌握几种常用的量子Monte Carlo模拟法，需要一定的数学储备。
这里只用积分，也可以对它有所理解。
需要指出的是，量子Monte Carlo模拟法并没有很多物理图像，而是由很多技术细节组成，使得计算效率增加，精度提高等等。
由于技术细节相对枯燥，所以本文主要是介绍量子Monte Carlo的思想，就是从无到有，如何一步一步利用随机抽样，计算多体系统的性质。
一、赌博和随机模拟为什么赌博的原理能成为解决量子多体物理的基础？举个例子就知道了。
在拉斯维加斯，赌大小是最简单的玩法。
想必大家都知道，简述如下：同时掷三个骰子，如果点数之和<=9算小，>=10为大。
这样看来，胜负概率相等，赌场没太有赚头（见注1），所以又加了一条，三个骰子数值相等时，庄家赢。
就是这小小的1/36的概率差，保证了押注次数足够多时，庄家必胜。
投骰子次数足够多，可以保证庄家获胜；对波函数投骰子次数足够多，也可以保证系统的态趋向于真正的基态。
两者的共同点，就是辛钦定理。
二、Monte Carlo法Monte Carlo法就是用统计来模拟事件的方法。
一个简单的例子是求圆周率pi，如图1. 如果想知道圆周率pi，可以在二维平面上边长为R的方块内，均匀撒点。
然后计算点的坐标到正方形中心的距离。
如果距离小于R，则点在圆内，反之点在圆外。
圆周率可以从落在圆内的点的数目和总的点数目的比得到。
那么点恰好落在圆周的时候，算是圆内还是圆外呢？其实没有影响。
1、二分搜索算法是利用（A分治策略）实现的算法。
2、下列不是动态规划算法基本步骤的是（A找出最优解的性质）。
3、最大效益优先是（A分支界限法）的一搜索方式。
4、在下列算法中有时找不到问题解的是（B拉斯维加斯算法）。
5. 回溯法解旅行售货员问题时的解空间树是（A子集树）。
6．下列算法中通常以自底向上的方式求解最优解的是（B动态规划法）。
7、衡量一个算法好坏的标准是（C 时间复杂度低）。
8、以下不可以使用分治法求解的是（D 0/1背包问题）。
9. 实现循环赛日程表利用的算法是（A分治策略）。
10、下列随机算法中运行时有时候成功有时候失败的是（C 拉斯维加斯算法）11．下面不是分支界限法搜索方式的是（D深度优先）。
12．下列算法中通常以深度优先方式系统搜索问题解的是（D回溯法）。
13.备忘录方法是那种算法的变形。
（B动态规划法）14．哈弗曼编码的贪心算法所需的计算时间为（BO（nlogn））。
15．分支限界法解最大团问题时，活结点表的组织形式是（B最大堆）。
16．最长公共子序列算法利用的算法是（B动态规划法）。
17．实现棋盘覆盖算法利用的算法是（A分治法）。
18.下面是贪心算法的基本要素的是（C贪心选择性质）。
19.回溯法的效率不依赖于下列哪些因素（D确定解空间的时间）20.下面哪种函数是回溯法中为避免无效搜索采取的策略（B剪枝函数）21、下面关于NP问题说法正确的是（BP类问题包含在NP类问题中）22、蒙特卡罗算法是（B概率算法）的一种。
23.下列哪一种算法不是随机化算法（C动态规划算法）24. （D最优子结构性质）是贪心算法与动态规划算法的共同点。
25. 矩阵连乘问题的算法可由（B动态规划算法）设计实现。
26. 分支限界法解旅行售货员问题时，活结点表的组织形式是（A最小堆）。
27、Strassen矩阵乘法是利用（A分治策略）实现的算法。
29、使用分治法求解不需要满足的条件是（A子问题必须是一样的）。
拉斯维加斯算法
拉斯维加斯算法是一种基于随机数来寻找最优解的算法，它成功的在几何问题和最优化问题中取得了巨大的成功。
拉斯维加斯算法也称为"抛硬币算法"，拉斯瓦格斯算法或者孤立搜索算法，因为它采用的是抛硬币的概率性策略。
此外，拉斯维加斯算法可以用于随机旅行商问题，插入过程以及排序等问题。
拉斯维加斯算法的基本思想是以一定的搜索树进行搜索，从节点到节点移动，以改变搜索空间状态，根据一定的概率搜索然后返回最优解。
算法开始以某种概率开始产生领域的搜索空间，然后迭代开始不断增大采样空间的概率，直至找到最优解或最佳解。
拉斯维加斯算法的优势在于当前最优解的不断搜索和确定，缺点是搜索空间过大时耗费时间较长，可能需要过多的迭代来搜索最优解。
但是在许多问题，拉斯维加斯算法仍然是有效的，因为它的灵活性和成本低廉，在几乎所有的环境下都能发挥作用。
总之，拉斯维加斯算法是一种比较实用的最优解搜索方法，它的根本是通过概率的方法迭代搜索解决多变量优化问题，它的适用性范围比较广，是常用的一种最优解搜索算法。
