计算机算法总结 13页

算法总结1.穷举法穷举法，又称暴力算法，即列举问题解空间所有可能情况，并逐个测试，从而找出符合问题条件的解。这份通常是一种费时算法，人工手动求解W难，但计算机的出现使得穷举法有了用武之地。例如:密码破译通常用的足穷举法，即将密码进行逐个推算直到找到真正的密码为止。理论上讲，穷举法可以破解任何一种密码，但对于一个长度为n位的密码，其可能的密码有2An种。可见，当n较大吋穷举法将成为一个NP难度问题。典型例题【百钱买百鸡问题】公元5世纪末，中国古代数学家张丘建在他的《算经》中提到了著名的“百钱买百鸡”问题:鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各儿何？分析:设鸡翁、鸡母、鸡雏的个数各为x、y、z,百钱买百鸡问题可以用如下方程式表示：5x+3y+z/3=100x+y+z=1001<=x<20,1<=y<33,3<=z<100，zmod3=0对于百钱买白鸡问题，很容易用穷举法对x、y、z的取值，判断方程(1)、(2)及zmod3=0是否成立，若成立，则是问题的-个解。百钱买白鸡问题求解篇法：//百钱买白鸡问题穷举算法//设鸡翁、鸡母、鸡雏的个数分别为x、y、zfor(x=l;x<20;x++)for(y=l;y<33;y++)for(z=3;z<100;z++)if(x+y+z==100)and(5x+3y+z/3==100)and(zmod3=0)writeln(x，y，z)上述算法是一个三熏循环，最内层的条件判断盂要执行19*32*97次，即58976。在条件判断中，利用了整数的求模运算，如果将鸡雏的个数设为3z，可以避免该项判断，且可减少内熏循环次数。即：for(z=l;z<34;z++)if(x+y+3z==100)and(5x+3y+z=100)writeln(x，y，3z)【0-1背包fuj题1】给定n种物品和一个背包，物品i的重量是Wi,其价值为Vi，背包的容量为Wm。应如何选择装入背包的物品，使得装入背包的物品总价值最大？分析:所谓0-1背包问题，是指在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。另外，不能将物品i装入背包多次，也不能只装入部分的物品i。0-1背包问题是一种组合优化的NP完全问题，最容易想到方法的就是穷举法。0-1背包问题求解的穷举算法。//设数组w[0-n-l]存储n件物品的重量，数组c[0-n-l]存储//n件物品的价ffi，数组b[0-n-l]为秘识数组，若物品i未选//择，则b[i-l]=O，否则b[i-l]=lcmax=Ofor(i=l;i<=2An-l;i-H-)\n{b[0』-l]=将i转化为n位的二进制字符串tenipw=求和b[j]*w[j]tempc=求和b[j]*c[j]If(tempwcmax){tempb=b[O..n-l];cmax=tempc;>}输出最佳方案tempb[O..n-l],cmax结束2.递推法递推算法是一种根据递推关系进行问题求解的方法。递推关系可以抽象为一个简单的数学模型，即给定一个数的序列aeA，…，an若存在整数n。，使当吋，可以用等号(或大于号，小于号)将an与其前面的某些项a<0=3,neN*)o写一算法求斐波那契数列第10项的值。分析:从斐波那契数列的定义可知，数列的第一项为一，第二项也为一，递推关系是当前项等于前二项之和◊因此，通过顺推可以得到f(3)=f(l)+f(2)=2,f(4)=f(2)+f(3)=3,f(5)=f(3)+f(4)=5,以此类推，可以得到f(10)的值。求斐波那契数列的顺推算法：//求斐波那契数列第十项的值并输出ni]=ifT2]=2while(n<=10){f[n]=f[n-l]4f[n-2]n=n+lwrite(f[10])3.递归法在问题求解思想上，递推是从已知条件出发，一步步递推出未知项，直到问题的解。递归也是递推的一种，只不过它是对待解问题的递推，直到把-个复杂的问题递推为简单的易解W题，然后再一步步返回，从而得到原M题的解。\n【斐波那契数列算法2】利用递归思想写出求斐波那契数列的递归算法。分析：在问题求解中，求解同一个问题的方法通常不止一个。根据递归法的思想，由斐波那契数列递推公式可以很容易地写出递归算法，伪代码描述如下。求斐波那契数列递归算法：//函数fib返回第n(n>=l)个斐波那契数列的值intfib(intn){if(n==1)retum(l)if(n==2)return(2)elsereturn(fib(n-l)+fib(n-2))初始状态①移动后狀苍②移动后状苍③移动后狀态>移动后状态⑤移动后状态移动后狀态⑦移动后状态3$3阶Hanoi塔递归辺程示惠else分析：可以把问题用初始状态和目标状态来表达，问题求解就是要找出搬移的次序和所有的中间状态。\nHanoi塔问题递归算法：//n为盘子数目//三根柱子from、to和temp分别农示起始柱子、M秘柱子和胳吋柱子ttB柱C\nvoidhanoitower(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);}}2.回溯法试探-失败返回-再试探的问题求解方法称为回溯法，回溯算法的基本思想是：从-•条路往前走，能进则进，不能进则退回来，换一条路再试。对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的付能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法屮通过构造约束函数，可以人人提升程序效率，因为在深度优先搜索的过程中，不断的将每个解(并不一定是完整的，事实上这也就是构造约束函数的意义所在)与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。【八皇后问题】八皇后问题是十九世纪著名数学家高斯于1850年提出的。问题是：在8*8的棋盘上摆放8个皇后，使苒不能互相攻击，即任意的两个皇后不能处在同意行，同一列,或同意斜线上。可以把八皇后问题拓展为n皇后问题，即在^什的棋盘上摆放n个皇后，使其任意两个皇后都不能处于同一行、同一列或同一斜线上。分析：显然，每一行可以而且必须放一个皇后，所以n皇后问题的解可以用一个n元向量X=(xi，X2,..…Xn)表示，其中，1<=i<=n且1<=Xi<=n，即第n个皇后放在第i行第列上。由于两个皇后不能放在同一列上，所以，解向量X必须满足的约束条件为矣Xj;若两个皇后的摆放位置分别是(i，xD和(j，Xj),在棋盘上斜率为-1的斜线上，满足条件在棋盘上斜率为1的斜线上，满足条件i+j=Xi+Xj；综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量X必须满足的约束条件为：|i-Xi|矣lj-xj|八皇后问题求解的回溯党法：//试探第i个皇后，即第i行耍放R的皇后位界voidquccn(inti){fora=0;j<8y++)//从第0列开始从左到右依次试探可能的位置{if(a[j]=0&&c[i+j]==0//如果无冲灾{\n6bcdeb)，求a和b最大公约数(a，b)的步骤如下：用b除a，得a+b=qri((Xri)。若n=0，则(a，b)=b；若n^O,则再用ri除b，得b4-n=qr2((Xn)•若n=0，则(a，b)=n,若n关0,则继续用n除n,……如此下去，直到能整除为止。其最后一个非零除数即为(a,b)。法1:求两数的ii大公约数的辗转相除法减法实现：//辗转相除法求两数a和b的最大公约数gintgcd(a，b){while(a!=0&&b卜0){if(a>b)a=a-b/*迭代*/elseb=b-a;/*迭代3*7}if(a»=O)returnaelsereturnb\n法2:求两数的最人公约数的辗转相除法模拟实现：//辦转相除法求两数a和b的最大公约数gintgcd(a，b){t=a%b;\vhilc(t!=O){a=b;/*迭代b=t;/*迭代*/t=a%b;}returnb}【解一元非线性方程】用迭代法求一元非线性方程f(x)=O的解分析：当f⑻是超越函数或高次多项式时，f⑻=0称为非线性方程，此类方程除少数情形外，只能求近似解。求解非线性方程的最简单的方法是二分法(Bisectionmethod),又称二分区间法。其基本思想是设f(x)在区间［a，b］上为连续函数，如果f(a)*f(b)<0,则f(x)在区间［a，b］上至少有一个根。如果f(x)在区间［a，b］上是单调的，则f(x)在区间［a，b］上只存在一个实根，如右图所示。求方程f(x)=0在区M［a，b］内的根的迭代算法：Stepl:求a，b的屮点也标x=a+b/2。Step2:计算f(x)。Step3:若|f(x)|2时，可以将数组分成两个元素个数较小的数组，分别求解它们的最大值和最小值，最后比较两个数组的解来得到原问题的解，这样就分而治之了。求数组中最大值和最小值的分治算法：//includevoidminmax(intarray[],intbegin,intend,int&min，int&max,int&count){intmid=(begin+end)/2;if(begin=end){count++；if(array[mid]else{if(array[mid]>max)max=arrayfmid];count♦•+;}return;}minmax(array,begin，mid，min，max，count);minmax(array，mid+1，end，min,max，count);}voidmain()!intarray[10]={9,8,7,6,5,4,3,2,1,0};intmin=array[0]，max=-1，count=0;minmax(array,0,9，min，niax，count);printf(Hmin=%d，max=%d，count=%d\n"，min,max,count);}2.贪心法贪心算法(乂称贪婪算法)是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有M题都能得到整体最优解，但对范围相当广泛的许多W题他能产生整体最优解\n或者是整体最优解的近似解。基本思路：1.建立数学模型来描述问题2.把求解的问题分成若干个子问题。3.对每一子I'M)题求解，得到子I'M)题的局部最优解。4.把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程：从M题的某一初始解出发；while能朝给定总目林前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。【0-1背包问题2】有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品ABCDEFG重W:35kg30kg6kg50kg40kg10kg25kg价值10$40$30$50$35$分析：用贪心算法解背包问题的基本步骤是，首先计算每种物品单位重量的价值Vi/Wb然后依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超出C,则选择单位重量价值次高的物品，并尽可能多的装入背包。依此策略一直进行下去，直到背包装满为止。0-1背包问题的贪心算法：includeincludeincludeinclude"time.h"#includenwindows.h"includeinclude#definenum100voidbagloading(intx[],floatp[],floatw[],floatcjntn){//x[]取值为0或1,x[i]=1当且仅当背包i背装载;//p□是物品价值；//wU是物品熏量；//C表示背包的容景；//n表示物品的件数；floatt，k，pw[num];inti，j，m，kk;for(i=0;i0){kk=0;for(j=0;j0){cout«"该背包共装入的这"《all«"件物品的价值与熏呈分别为："《endl;for(i=0;iwi(1)式表明：如果第i个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包；第(2)个式子表明:如果第i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第i个物品装入背包，则背包物品的价值等于第个物品装入容量位.卜wi的背包中的价值加上第i个物品的价值vi;(b>如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。0-1背包问题的动态规划法://计算for(i=l;ivalUe[i-l]Lj]，则记录当前最大价值inttemp=value[i-l][j-w[i]]+v[i];if(w[i]<=j&&temp>value[i][j])value[i][j]=temp;