010_计算机算法设计与分析

算法设计与分析C语⾔描述（陈慧南版）课后答案第⼀章15P1-3. 最⼤公约数为1。

快1414倍。

主要考虑循环次数，程序1-2的while 循环体做了10次，程序1-3的while 循环体做了14141次（14142-2循环）若考虑其他语句，则没有这么多，可能就601倍。

第⼆章32P2-8.（1）画线语句的执⾏次数为log n 。

(log )n O 。

划线语句的执⾏次数应该理解为⼀格整体。

（2）画线语句的执⾏次数为111(1)(2)16jnii j k n n n ===++=∑∑∑。

3()n O 。

（3）画线语句的执⾏次数为。

O 。

（4）当n 为奇数时画线语句的执⾏次数为(1)(3)4n n ++，当n 为偶数时画线语句的执⾏次数为 2(2)4n +。

2()n O 。

2-10.（1）当 1n ≥ 时，225825n n n -+≤，所以，可选 5c =，01n =。

对于0n n ≥，22()5825f n n n n =-+≤，所以，22582()n n n -+=O 。

（2）当 8n ≥ 时，2222582524n n n n n -+≥-+≥，所以，可选 4c =，08n =。

对于0n n ≥，22()5824f n n n n =-+≥，所以，22582()n n n -+=Ω。

（3）由（1）、（2）可知，取14c =，25c =，08n =，当0n n ≥时，有22212582c n n n c n ≤-+≤，所以22582()n n n -+=Θ。

2-11. (1) 当3n ≥时，3log log n n n <<，所以()20log 21f n n n n =+<，3()log 2g n n n n =+>。

可选 212c =，03n =。

对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。

注意：是f (n )和g (n )的关系。

算法设计与分析——批处理作业调度（回溯法）之前讲过⼀个相似的问题流⽔作业调度问题，那⼀道题最开始⽤动态规划，推到最后得到了⼀个Johnson法则，变成了⼀个排序问题，有兴趣的可以看⼀下本篇博客主要参考⾃⼀、问题描述给定n个作业的集合{J1,J2,…,Jn}。

每个作业必须先由机器1处理，然后由机器2处理。

作业Ji需要机器j的处理时间为t ji。

对于⼀个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。

所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。

批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度⽅案，使其完成时间和达到最⼩。

例：设n=3，考虑以下实例：看到这⾥可能会对这些完成时间和是怎么计算出来的会有疑问，这⾥我拿123和312的⽅案来说明⼀下。

对于调度⽅案（1,2,3）作业1在机器1上完成的时间是2，在机器2上完成的时间是3作业2在机器1上完成的时间是5，在机器2上完成的时间是6作业3在机器1上完成的时间是7，在机器2上完成的时间是10所以，作业调度的完成时间和= 3 + 6 + 10这⾥我们可以思考⼀下作业i在机器2上完成的时间应该怎么去求？作业i在机器1上完成的时间是连续的，所以是直接累加就可以。

但对于机器2就会产⽣两种情况，这两种情况其实就是上图的两种情况，对于（1,2,3）的调度⽅案，在求作业2在机器2上完成的时间时，由于作业2在机器1上还没有完成，这就需要先等待机器1处理完；⽽对于（3,1,2）的调度⽅案，在求作业2在机器2上完成的时间时，作业2在机器1早已完成，⽆需等待，直接在作业1被机器1处理之后就能接着被处理。

综上，我们可以得到如下表达式if(F2[i-1] > F1[i])F2[i] = F2[i-1] + t[2][i]elseF2[i] = F1[i] + t[2][i]⼆、算法设计类Flowshop的数据成员记录解空间的结点信息，M输⼊作业时间，bestf记录当前最⼩完成时间和，数组bestx记录相应的当前最佳作业调度。

习题11. 图论诞生于七桥问题。

出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。

七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图是这条河以及河上的两个岛和七座桥的草图。

请将该问题的数据模型抽象出来，并判断此问题是否有解。

七桥问题属于一笔画问题。

输入：一个起点输出：相同的点1， 一次步行2， 经过七座桥，且每次只经历过一次3， 回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。

另一类是只有二个奇点的图形。

2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。

请用伪代码描述这个版本的欧几里德算法=m-n2.循环直到r=0m=nn=rr=m-n3 输出m3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。

要求分别给出伪代码和C++描述。

编写程序，求n 至少为多大时，n 个“1”组成的整数能被2013整除。

#include<iostream>using namespace std;int main(){double value=0;图 七桥问题for(int n=1;n<=10000 ;++n){value=value*10+1;if(value%2013==0){cout<<"n至少为:"<<n<<endl;break;}}计算π值的问题能精确求解吗编写程序，求解满足给定精度要求的π值#include <iostream>using namespace std;int main (){double a,b;double arctan(double x);圣经上说：神6天创造天地万有，第7日安歇。

为什么是6天呢任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。

习题2-1 求下列函数的渐进表达式：3n^2+10n; n^2/10+2n; 21+1/n; logn^3; 10 log3^n 。

解答：3n^2+10n=O(n^2),n^2/10+2^n=O(2^n),21+1/n=O(1),logn^3=O(logn),10log3^n=O(n).习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。

解答：照渐进阶从高到低的顺序为：n!、3^n、4n^2 、20n、n^2/3、logn、2习题2-4(1)假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。

在某台计算机上实现并完成该算法的时间为t秒。

现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？(2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？(3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：(1)设能解输入规模为n1的问题，则t=3*2^n=3*2^n/64,解得n1=n+6(2)n1^2=64n^2得到n1=8n(3)由于T（n)=常数，因此算法可解任意规模的问题。

习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。

对于计算复杂性分别为n，n^2，n^3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？解答：n'=100nn'^2=100n^2得到n'=10nn'^3=100n^3得到n'=4.64nn'!=100n!得到n'<n+log100=n+6.64习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并简述理由。