2022年2022年计算机算法总结 .pdf

《2022年2022年计算机算法总结 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年计算机算法总结 .pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法总结1.穷举法穷举法，又称暴力算法，即列举问题解空间所有可能情况，并逐个测试，从而找出符合问题条件的解。 这份通常是一种费时算法，人工手动求解困难，但计算机的出现使得穷举法有了用武之地。例如:密码破译通常用的是穷举法，即将密码进行逐个推算直到找到真正的密码为止。 理论上讲，穷举法可以破解任何一种密码，但对于一个长度为n 位的密码， 其可能的密码有2n 种。可见，当n 较大时穷举法将成为一个NP 难度问题。典型例题【百钱买百鸡问题】公元 5 世纪末， 中国古代数学家张丘建在他的算经中提到了著名的 百钱买百鸡 问题 :鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几

2、何？分析 : 设鸡翁、鸡母、鸡雏的个数各为x、y、z, 百钱买百鸡问题可以用如下方程式表示:5x+3y+z/3=100 x+y+z=1001=x20,1=y33,3=z100,z mod3=0对于百钱买白鸡问题，很容易用穷举法对x、y、z 的取值，判断方程（ 1） 、 （2）及 z mod3=0 是否成立，若成立，则是问题的一个解。百钱买白鸡问题求解算法:/百钱买白鸡问题穷举算法/设鸡翁、鸡母、鸡雏的个数分别为x、y、zfor（x=1;x20;x+ ）for（y=1;y33;y+ ）for（z=3;z100;z+ ）if（x+y+z= =100 ）and（5x+3y+z/3=100 ）and（

3、z mod 3=0）writeln （x,y,z）上述算法是一个三重循环，最内层的条件判断需要执行19*32*97 次，即 58976。在条件判断中，利用了整数的求模运算，如果将鸡雏的个数设为3z，可以避免该项判断，且可减少内重循环次数。即:for（z=1;z34;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 背包问题，是指在选择装入背包的物品时， 对

4、每种物品i 只有两种选择， 即装入背包或不装入背包。 另外， 不能将物品i 装入背包多次， 也不能只装入部分的物品i。0-1 背包问题是一种组合优化的NP 完全问题，最容易想到方法的就是穷举法。0-1 背包问题求解的穷举算法。/设数组 w0 n 1存储 n 件物品的重量， 数组 c0n-1存储/n 件物品的价值，数组b0n-1为标识数组，若物品i 未选名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - /择，则 bi-1=0 ，否

5、则 bi-1=1cmax=0for（i=1;i=2n-1;i+ ）b0.n-1= 将 i 转化为 n 位的二进制字符串tempw=求和 bj*wjtempc=求和 bj*cjIf （tempwcmax ）tempb=b0.n-1;cmax=tempc;输出最佳方案tempb0.n-1,cmax结束2.递推法递推算法是一种根据递推关系进行问题求解的方法。递推关系可以抽象为一个简单的数学模型，即给定一个数的序列a0,a1,an若存在整数n0，使当 nn0时，可以用等号（或大于号，小于号）将an与其前面的某些项ai(0i=3,n N*) 。写一算法求斐波那契数列第10 项的值。分析 :从斐波那契数列

6、的定义可知，数列的第一项为一，第二项也为一，递推关系是当前项等于前二项之和。 因此，通过顺推可以得到f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3,f(5)=f(3)+f(4)=5，以此类推，可以得到f(10)的值。求斐波那契数列的顺推算法:/求斐波那契数列第十项的值并输出f1=1f2=2n=3while（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 o

7、f Hanoi Problem ） 递 归 算 法 。分析：可以把问题用初始状态和目标状态来表达，问题求解就是要找出搬移的次序和所有的中间状态。Hanoi 塔问题递归算法:/n 为盘子数目/三根柱子 from、to 和 temp 分别表示起始柱子、目标柱子和临时柱子名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - void hanoitower(n,from,to,temp)if(n0)/把 from 柱子上的 n-1 个盘子搬

8、移到temp 柱子上，用to 柱做临时柱子hanoitower(n-1,from,temp,to);movedisk(from,to);/把 temp 柱子上的 n-1 个盘子搬移到to 柱子上，用from 柱做临时柱子hanoitower(n-1,temp,to,from);4.回溯法试探 -失败返回 -再试探的问题求解方法称为回溯法，回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯

9、法中通过构造约束函数，可以大大提升程序效率，因为在深度优先搜索的过程中，不断的将每个解 （并不一定是完整的， 事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。【八皇后问题】八皇后问题是十九世纪著名数学家高斯于1850 年提出的。问题是：在8*8的棋盘上摆放8 个皇后，使其不能互相攻击，即任意的两个皇后不能处在同意行，同一列，或同意斜线上。 可以把八皇后问题拓展为n 皇后问题， 即在 n*n 的棋盘上摆放n 个皇后， 使其任意两个皇后都不能处于同一行、同一列或同一斜线上。分析：显然，每一行可以而且必须放一个皇后，所

10、以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 行要放置

11、的皇后位置void queen(int i) for(j=0;j8;j+) /从第 0 列开始从左到右依次试探可能的位置 if(aj=0&ci+j=0 /如果无冲突 qi,j= Q ; /(i,j) 放皇后，即第i 行的皇后放在第j 列名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - aj=1; /在 j 列标记bi- j+7=1; /(i,j) 所在的主对角线做标记ci+j=1; /(i,j) 所在的从对角线做标记if(ib）

12、 ，求 a 和 b 最大公约数 (a， b）的步骤如下：用 b 除 a，得 ab=q.r1(0r1） 。若 r1=0，则（ a， b)=b；若 r10，则再用 r1除 b，得 br1=q.r2 (0r2）.若 r2=0，则（a，b)=r1，若 r20，则继续用r2除 r1，如此下去，直到能整除为止。其最后一个非零除数即为（a，b） 。法 1：求两数的最大公约数的辗转相除法减法实现: /辗转相除法求两数a 和 b 的最大公约数g int gcd(a,b) while(a!=0&b!=0) if(ab) a=a-b /* 迭代 */ else b=b-a; /*迭代 */ if(a!=0) ret

13、urn a else return b 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 法 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)是超越函数或高次多项

14、式时，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)|2 时，可以将数组分成两个元素个数较小

15、的数组，分别求解它们的最大值和最小值，最后比较两个数组的解来得到原问题的解，这样就分而治之了。求数组中最大值和最小值的分治算法: #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 (arraymid max)max = arraymid;count+;return;minmax(array, begin, mid, min ,max, count);minmax(array,

16、mid + 1, end, min ,max, count);void main()int array10 = 9,8,7,6,5,4,3,2,1,0;int min = array0, max = -1, count = 0;minmax(array, 0,9,min,max,count);printf(min = %d, max = %d, count = %dn, min,max,count);7.贪心法贪心算法 （又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说， 不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到

17、整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。基本思路：1.建立数学模型来描述问题把求解的问题分成若干个子问题。对每一子问题求解，得到子问题的局部最优解。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程：从问题的某一初始解出发；while 能朝给定总目标前进一步do 求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。【0

18、-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，则选择单位重量价值次高的物品，并尽可能多的装入背包。依此策略一直进行下去，直到背包装满为止

19、。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，xi=1 当且仅当背包i 背装载；/p是物品价值；/w 是物品重量；/c 表示背包的容量；/n 表示物品的件数；float t,k,pwnum; int i,j,m,kk; for(i=0;i0) kk=0; for(j=0;jm;j+) if (

20、pwjpwj+1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - t=pj; pj=pj+1; pj+1=t; k=wj; wj=wj+1; wj+1=k; kk=j; m=kk; /按 p/w 次序从大到小选择物品i=0; while(in&(wi=c) xi=1; c-=wi; i+; int main() int n,all; float c,p1,w1; float pnum; float wnum; int xnu

21、m; int i; coutn; coutc; cout 请依次输入各物品的价值与重量n 每个物品的价值与重量之间用空格隔开，回车后输入另一个物品： endl; /通过键盘依次输入各物品的价值与重量for(i=0;ipiwi; /调用函数bagloading(x,p,w,c,n); /统计物品的总价值、总重量以及件数并输出/统计装入物品的价值及重量并输出all=0; p1=0.0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - -

22、- w1=0.0; for(i=0;in;i+) if(xi=1) all+; p1=p1+pi; w1=w1+wi; coutendl; cout 所装物品总的价值为：p1endl; cout 所装物品总的重量为：w10) cout 该背包共装入的这all 件物品的价值与重量分别为：endl; for(i=0;in;i+) if(xi=1) coutpi wiendl; system(pause); return 0; 8.动态规划法在现实生活中， 有一类活动可将其过程分为若干个互相联系的阶段，在它的每个阶段都要做出决策， 从而使整个过程达到最好的活动效果。动态规划 (dynamic pro

23、gramming) 是运筹学 的 一 个 分 支 ， 是 求 解 决 策 过 程(decision process)最优化的数学方法。20世纪 50 年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著 名 的 最 优 化 原 理 (principle of optimality) ， 把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法 动态规划。动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。名师资料总结 - - -精品资料欢迎下载 - -

24、 - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 【0-1 背包问题3】分析：令 V(i,j) 表示在前i(1=i=n) 个物品中能够装入容量为就j(1=j=C) 的背包中的物品的最大价值，则可以得到如下的动态规划函数: (1) V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) jwi (1)式表明： 如果第 i 个物品的重量大于背包的容量，则装人前i 个物品得到的最大价值和装入前 i-1 个物品得到的最大价是相同的，即物品i 不能装入背包；第(2)个

25、式子表明 :如果第 i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第i 个物品装入背包，则背包物品的价值等于第i-1 个物品装入容量位j-wi 的背包中的价值加上第i 个物品的价值vi; (b)如果第 i 个物品没有装入背包，则背包中物品价值就等于把前i-1 个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i 个物品装入容量为j 的背包中的最优解。0-1 背包问题的动态规划法: /计算 for(i=1;irow;i+) . for(j=1;jj, 第 i 个物品不装入背包 valueij=valuei-1j; /wivaluei-1j, 则记录当前最大价值 int temp=valuei-1j-wi+vi; if(wivalueij) valueij=temp; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -