计+算+机+常+用+算+法

《计+算+机+常+用+算+法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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。A1∈{1，2}，A2∈{2，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

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

4、填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合条件的即为解。因此可以用枚举法。但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。例2、有四个学生，上地理课时提出我国四大淡水湖的排序如下：甲：洞庭湖最大，洪泽湖最小，鄱阳湖第三；乙：洪泽湖最大，洞庭湖最小，鄱阳湖第二，太湖第三；丙：洪泽湖最小，洞庭湖第三；丁：鄱阳湖最大，太湖最小，洪泽湖第二，洞庭湖第三；对于各个湖泊应处的地位，每个人只说对了一个。根据以上情况，编程序判断各个湖泊应处的地位。[算法分析]：本题是一个逻辑判断题，一般

5、的逻辑判断题都采用枚举法进行解决。四个湖的大小分别可以有4！=24种排列可能，因为24比较小，因此我们对每种情况进行枚举，然后根据给定的条件判断哪些符合问题的要求。源程序例3、最佳游览路线。某旅游区的街道成网格状。其中东西向的街道都是旅游街，南北向的街道都是林阴道。由于游客众多，旅游街被规定为单行道，游客在旅游街上只能从西向东走，在林阴道上则既可从南向北走，也可以从北向南走。阿龙想到这个旅游街游玩，他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之见的街道值得游览的程度，分值是从-100到100的整数，所有林阴道不打分。所有分值不可能全是负分。如图：-50-4736-30

6、-2317-19-34-13-8-42-3-4334-45北南东西输入数据：输入文件是input.txt.文件的第一行是两个整数m和n,之间用一个空格隔开，m表示有多少条旅游街（1≤m≤100），n表示有多少条林阴道（1≤n≤20001）。接下来的m行依次给出了由北向南每条旅游街的分值信息。每行有n-1个整数，依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。输出数据：输出文件是output.txt。文件只有一行，是一个整数，表示你的程序找到的最佳游览线路的总分值。Input.txtOutput.txt36-50–4736–30–2317–19–34–13–

7、8-42–3–4334-4584Lij为第I条旅游街上自西向东第j段的分值（1≤i≤m,1≤j≤n-1）。例如样例中L12=17，L23=-34，L34=34。我们将网格状的旅游区街道以林阴道为界分为n-1个段，每一段由m条旅游街的对应成段，即第j段成为{L1j，L2j，。。。Lmj}（1≤j≤n-1）。由于浏览方向规定横向自西向东，纵向即可沿林阴道由南向北，也可由北向南，而横行的街段有分值，纵行无分值，因此最佳游览路现必须具备如下三个特证：1）来自若干个