计算机算法总结

算法 1.穷举法 穷举法，又称暴力算法，即列举问题解空间所有可能情况，并逐个测试，从而找出符合问题条件的解。这份通常是一种费时算法，人工手动求解困难，但计算机的出现使得穷举法有了用武之地。例如:密码破译通常用的是穷举法，即将密码进行逐个推算直到找到真正的密码为止。理论上讲，穷举法可以破解任何一种密码，但对于一个长度为n位的密码，其可能的密码有2^n种。可见，当n较大时穷举法将成为一个NP难度问题。 典型例题 【百钱买百鸡问题】公元5世纪末，中国古代数学家张丘建在他的《算经》中提到了著名的“百钱买百鸡”问题:鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？ :设鸡翁、鸡母、鸡雏的个数各为x、y、z,百钱买百鸡问题可以用如下方程式示: 5x+3y+z/3=100 x+y+z=100 1<=x<20,1<=y<33,3<=z<100,z mod3=0 对于百钱买白鸡问题，很容易用穷举法对x、y、z的取值，判断方程（1）、（2）及z mod3=0是否成立，若成立，则是问题的一个解。 百钱买白鸡问题求解算法: //百钱买白鸡问题穷举算法 //设鸡翁、鸡母、鸡雏的个数分别为x、y、z for（x=1;x<20;x++） for（y=1;y<33;y++） for（z=3;z<100;z++） if（x+y+z= =100）and（5x+3y+z/3==100）and（z mod 3==0） writeln（x,y,z） 上述算法是一个三重循环，最内层的条件判断需要执行19*32*97次，即58976。在条件判断中，利用了整数的求模运算，如果将鸡雏的个数设为3z，可以避免该项判断，且可减少内重循环次数。即: for（z=1;z<34;z++） if（x+y+3z==100）and（5x+3y+z==100） writeln（x,y,3z） 【 0-1背包问题1】给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，背包的容量为Wm。应如何选择装入背包的物品，使得装入背包的物品总价值最大？ 分析:所谓0-1背包问题，是指在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。另外，不能将物品i装入背包多次，也不能只装入部分的物品i。0-1背包问题是一种组合优化的NP完全问题，最容易想到的就是穷举法。 0-1背包问题求解的穷举算法。 //设数组w[0…n–1]存储n件物品的重量，数组c[0…n-1]存储 //n件物品的价值，数组b[0…n-1]为标识数组，若物品i未选 //择，则b[i-1]=0，否则b[i-1]=1 cmax=0 for（i=1;i<=2^n-1;i++） { b[0..n-1]=将i转化为n位的二进制字符串 tempw=求和b[j]*w[j] tempc=求和b[j]*c[j] If（tempwcmax） { tempb=b[0..n-1]; cmax=tempc; } } 输出最佳

方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载

tempb[0..n-1],cmax 结束 2.递推法 递推算法是一种根据递推关系进行问题求解的方法。递推关系可以抽象为一个简单的数学模型，即给定一个数的序列a0,a1,…,an若存在整数n0，使当n>n0时，可以用等号（或大于号，小于号）将an与其前面的某些项ai(0=3,n∈N*)。写一算法求斐波那契数列第10项的值。 分析:从斐波那契数列的定义可知，数列的第一项为一，第二项也为一，递推关系是当前项等于前二项之和。因此，通过顺推可以得到f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3,f(5)=f(3)+f(4)=5，以此类推，可以得到f(10)的值。 求斐波那契数列的顺推算法: //求斐波那契数列第十项的值并输出 f[1]=1 f[2]=2 n=3 while（n<=10） { f[n]=f[n-1]+f[n-2] n=n+1 } write(f[10]) 3.递归法 在问题求解思想上，递推是从已知条件出发，一步步递推出未知项，直到问题的解。递归也是递推的一种，只不过它是对待解问题的递推，直到把一个复杂的问题递推为简单的易解问题，然后再一步步返回，从而得到原问题的解。 【斐波那契数列算法2】利用递归思想写出求斐波那契数列的递归算法。 分析：在问题求解中，求解同一个问题的方法通常不止一个。根据递归法的思想，由斐波那契数列递推公式可以很容易地写出递归算法，伪代码描述如下。 求斐波那契数列递归算法: //函数fib返回第n(n>=1)个斐波那契数列的值 int fib(int n) { if(n ==1) return(1) else if(n ==2) return(2) else return (fib(n-1)+fib(n-2)) } 【Hanoi塔问题】Hanoi塔问题（Tower of Hanoi Problem）递归算法。 分析：可以把问题用初始状态和目标状态来表达，问题求解就是要找出搬移的次序和所有的中间状态。 Hanoi塔问题递归算法: //n为盘子数目 //三根柱子from、to和temp分别表示起始柱子、目标柱子和临时柱子 void hanoitower(n,from,to,temp) { if(n>0) { //把from柱子上的n-1个盘子搬移到temp柱子上，用to柱做临时柱子 hanoitower(n-1,from,temp,to); movedisk(from,to); //把temp柱子上的n-1个盘子搬移到to柱子上，用from柱做临时柱子 hanoitower(n-1,temp,to,from); } } 4.回溯法 试探-失败返回-再试探的问题求解方法称为回溯法，回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法中通过构造约束函数，可以大大提升程序效率，因为在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。 【八皇后问题】八皇后问题是十九世纪著名数学家高斯于1850年提出的。问题是：在8*8的棋盘上摆放8个皇后，使其不能互相攻击，即任意的两个皇后不能处在同意行，同一列，或同意斜线上。可以把八皇后问题拓展为n皇后问题，即在n*n的棋盘上摆放n个皇后，使其任意两个皇后都不能处于同一行、同一列或同一斜线上。 分析：显然，每一行可以而且必须放一个皇后，所以n皇后问题的解可以用一个n元向量X=（x1,x2,.....xn）表示，其中，1<= i<= n且1<= xi<= n，即第n个皇后放在第i行第xi列上。 由于两个皇后不能放在同一列上，所以，解向量X必须满足的约束条件为:xi≠ xj;若两个皇后的摆放位置分别是（i,xi）和（j,xj），在棋盘上斜率为-1的斜线上，满足条件i-j=xi-xj;在棋盘上斜率为1的斜线上，满足条件i+j=xi+xj; 综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量X必须满足的约束条件为: |i-xi|≠ |j-xj| 八皇后问题求解的回溯算法: //试探第i个皇后，即第i行要放置的皇后位置 void queen(int i) { for(j=0;j<8;j++)        //从第0列开始从左到右依次试探可能的位置 { if(a[j]==0&&c[i+j]==0 //如果无冲突 { q[i,j]=’Q’;        //(i,j)放皇后，即第i行的皇后放在第j列 a[j]=1;          //在j列标记 b[i-j+7]=1;      //(i,j)所在的主对角线做标记 c[i+j]=1;        //(i,j)所在的从对角线做标记 if(i<7)queen(i+1); //如果行还没有遍历完，进入下一行 else输出当前的摆放方案,即q数组; //当前列摆放了皇后，要继续试探当前行下一个可能的位置，此时需要 //将当前列恢复为没有摆皇后的状态，尝试下一个可能的摆放方案 q[i,j]=’*’; a[j]=0; b[i-j+7]=0; c[i+j]=0; }//end if }//end for } 5.迭代法 迭代法又称辗转法，是一种不断用变量的旧值递推新值的过程，是用计算机解决问题的一种基本方法。迭代法也是一种编程技术方法，它运用了递推的思想方法，利用计算机运算速度快、适合做重复性操作的特点，重复执行一组指令，不断从变量的一个值推出它的下一个值。 【辗转相除法】使用辗转相除法求两数的最大公约数。 分析：辗转相除法, 又称欧几里德算法，是求两个正整数之最大公因子的算法。它是已知最古老的算法之一, 最早可追溯至公元前300年。它首次出现于欧几里德的《几何原本》中，而在中国则可以追溯至东汉出现的《九章算术》。 设两数为a、b(a>b），求a和b最大公约数(a，b）的步骤如下：用b除a，得a÷b=q......r1(0≤r1）。若r1=0，则（a，b)=b；若r1≠0，则再用r1除b，得b÷r1=q......r2 (0≤r2）.若r2=0，则（a，b)=r1，若r2≠0，则继续用r2除r1，……如此下去，直到能整除为止。其最后一个非零除数即为（a，b）。 法1：求两数的最大公约数的辗转相除法减法实现: //辗转相除法求两数a和b的最大公约数g int gcd(a,b) { while(a!=0&&b!=0) { if(a>b) a=a-b          /*迭代*/ else b=b-a;        /*迭代*/ } if(a!=0) return a else return b } 法2：求两数的最大公约数的辗转相除法模拟实现: //辗转相除法求两数a和b的最大公约数g int gcd(a,b) { t=a%b; while(t!=0) { a=b;            /*迭代*/ b=t;            /*迭代*/ t=a%b; } return b } 【解一元非线性方程】用迭代法求一元非线性方程f(x)=0的解 分析：当f(x)是超越函数或高次多项式时，f(x)=0称为非线性方程，此类方程除少数情形外，只能求近似解。求解非线性方程的最简单的方法是二分法（Bisection method），又称二分区间法。其基本思想是设f(x)在区间[a,b]上为连续函数，如果f(a)?f(b)<0，则f(x)在区间[a,b]上至少有一个根。如果f(x)在区间[a,b]上是单调的，则f(x)在区间[a,b]上只存在一个实根，如右图所示。 求方程f(x)=0在区间[a,b]内的根的迭代算法: Step1:求a,b的中点坐标x=a+b/2。 Step2:计算f(x)。 Step3:若|f(x)|<ε(ε为一个指定的极小值，用来控制求解精度，例如10^-4)，则转Step6,否则继续下面的迭代运算。 Step4:修改有根区间 4.1若f(x)与f(a)同号，说明x更接近方程的根，此时a←x,b不变； 4.2若f(x)与f(b)异号,此时a不变，b←x； Step5:转Step1 Step6:输出x，即方程的近似解。 Step7:结束。 6.分治法 在求解复杂问题时，分治法的基本思想是把一个复杂的问题分成若干相对独立而规模较小的子问题，如果某个子问题还比较复杂，再把子问题分成更小的子问题，直到分解后的每个子问题都可以简单的直接求为止，然后通过逐个解决这些较小的子问题而得到原问题的解，即各个击破，分而治之。许多问题可以通过分治法求解，典型的有归并排序算法，折半查找等。 分治法所能解决的问题一般具有以下几个特征： 1) 该问题的规模缩小到一定的程度就可以容易地解决 2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 3) 利用该问题分解出的子问题的解可以合并为该问题的解； 4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 【例题】给定一个长度为n的整数数组，编写一个求出其最大值和最小值的分治算法。 分析：当数组中只有1个数时，可以直接给出结果；如果有两个数，则一次比较即可得出结果。当n>2时，可以将数组分成两个元素个数较小的数组，分别求解它们的最大值和最小值，最后比较两个数组的解来得到原问题的解，这样就分而治之了。 求数组中最大值和最小值的分治算法: #include void minmax(int array[], int begin, int end, int &min, int &max, int &count) { int mid = (begin + end)/2; if (begin == end) { count++; if (array[mid] < min) { min = array[mid]; } else { if (array[mid] > max) max = array[mid]; count++; } return; } minmax(array, begin, mid, min ,max, count); minmax(array, mid + 1, end, min ,max, count); } void main() { int array[10] = {9,8,7,6,5,4,3,2,1,0}; int min = array[0], max = -1, count = 0; minmax(array, 0,9,min,max,count); printf("min = %d, max = %d, count = %d\n", min,max,count); } 7.贪心法 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 基本思路： 1.建立数学模型来描述问题 ⒉把求解的问题分成若干个子问题。 ⒊对每一子问题求解，得到子问题的局部最优解。 ⒋把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 【0-1背包问题2】有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品 A B C D E F G 重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg 价值 10$ 40$ 30$ 50$ 35$ 分析：用贪心算法解背包问题的基本步骤是，首先计算每种物品单位重量的价值Vi/Wi，然后依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超出C，则选择单位重量价值次高的物品，并尽可能多的装入背包。依此策略一直进行下去，直到背包装满为止。 0-1背包问题的贪心算法: #include #include #include #include "time.h" #include "windows.h" #include #include #define num 100 void bagloading(int x[],float p[],float w[],float c,int n) { //x[]取值为0或1，x[i]=1当且仅当背包i背装载； //p[]是物品价值； //w[]是物品重量； //c表示背包的容量； //n表示物品的件数； float t,k,pw[num]; int i,j,m,kk; for(i=0;i0) { kk=0; for(j=0;j>n; cout<<"请输入背包的最大容量："; cin>>c; cout<<"请依次输入各物品的价值与重量 \n每个物品的价值与重量之间用空格隔开，回车后输入另一个物品："<>p[i]>>w[i]; } //调用函数 bagloading(x,p,w,c,n); //统计物品的总价值、总重量以及件数并输出 //统计装入物品的价值及重量并输出 all=0; p1=0.0; w1=0.0; for(i=0;i0) { cout<<"该背包共装入的这"<wi (1)式表明：如果第i个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包；第(2)个式子表明:如果第i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi 的背包中的价值加上第i个物品的价值vi; (b)如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。 0-1背包问题的动态规划法: //计算 for(i=1;ij,第i个物品不装入背包 value[i][j]=value[i-1][j]; //w[i]<=j,且第i个物品装入背包后的价值>value[i-1][j],则记录当前最大价值 int temp=value[i-1][j-w[i]]+v[i]; if(w[i]<=j && temp>value[i][j]) value[i][j]=temp; } }