算法设计与分析(第2版)吕国英主编(第三章课后习题)(4)

3——15

#include

void main()

{

int c,a,b;

for(c=88;c<=90;c++)

if((c!=88)&&(c!=90))

for(a=88;a<=90;a++)

if((a!=88)&&(a!=c))

for(b=88;b<=90;b++)

if((b!=a)&&(b!=c))

printf("A<==>%c\nB<==>%c\nC<==>%c",a,b,c);

}

3——16

#include

void main()

{

int num[3]={4,7,9},flag[3]={0};

int n,i,sum;

printf("此程序用于判断该数能否被4，7，9整除，并输出相关信息。\n");

printf("请输入n：");

scanf("%d",&n);

if(n%4!=0&&n%7!=0&&n%9!=0)

printf("%d不能被4，7，9任一个整除。\n",n);

else

{

if(n%4==0)

flag[0]=1;

if(n%7==0)

flag[1]=1;

if(n%9==0)

flag[2]=1;

sum=flag[0]+flag[1]+flag[2];

if(sum==1)

printf("%d能被一个数整除，它是%d\n",n,flag[0]?num[0]:flag[1]?num[1]:num[2]);

else

{

if(sum==3)

printf("%d能同时被4，7，9整除。\n");

else

printf("%d能被两个数整除，它

是%d，%d\n",n,flag[0]?num[0]:num[1],flag[2]?num[2]:num[1]);

}

}

}

3——18

#include

int dif(int i,int j,int k,int l)

{

if(i==j||i==k||i==l||j==k||j==l||k==l)

return 0;

else

return 1;

}

int dis(int m,int i,int j,int k,int l)

{

if(m==i||m==j||m==k||m==l)

return 0;

else

return 1;

}

void main()

{

int i1,i2,i3,i4,j2,j3,j4,j5,num=0;

int a,b;//a为四位数，首位应该最小为5；b为五位数，首位应为1，末尾为偶数

for(i1=5;i1<10;i1++)

for(i2=0;i2<10;i2++)

for(i3=0;i3<10;i3++)

for(i4=0;i4<10;i4++)

if(dif(i1,i2,i3,i4))

for(j2=0;j2<10;j2++)//首位j1为1

for(j3=0;j3<10;j3++)

for(j4=0;j4<10;j4++)

for(j5=0;j5<10;j5+=2)//末尾j5为偶数

if(dis(1,i1,i2,i3,i4)&&dis(j2,i1,i2,i3,i4)&&dis(j3,i1,i2,i3,i4)&&dis(j4,i1,i2,i3,i4)&&dis(j5,i1, i2,i3,i4)&&dis(1,j2,j3,j4,j5))

if(dif(j2,j3,j4,j5))

{

a=i1*1000+i2*100+i3*10+i4;

b=10000+j2*1000+j3*100+j4*10+j5;

if(b%a==0)

{

num+=1;

printf("第%2d个：%d = %d * 2\n",num,b,a);

}

}

}

算法设计与分析 吕国英 习题答案第四章

算法设计与分析（第二版）主编：吕国英 习题答案 第四章 1. #include int main(void) { int buf[100]; int n; int i,j,k; scanf("%d",&n); for(i=0;i=10) { buf[j+1]+=buf[j]/10; buf[j]=buf[j]%10; } } for(i=n-1;i>=0;i--) printf("%d",buf[i]); printf("\n"); return 0; } 2. #include int main(void) { int n=2; int i;

for(i=1;i<=9;i++) { n=(n+2)*2; } printf("%d\n",n); return 0; } 3. #include int main(void) { int a=54; int n; int m; printf("计算机先拿3张牌\n"); a=a-3; while(a>=0) { printf("还剩%d张牌\n",a); printf("你拿几张？请输入："); scanf("%d",&n); if(n>4||n<1||n>a) { printf("错误！重新拿牌\n"); continue; } a=a-n; printf("还剩%d张牌\n",a); if(a==0) break; m=5-n; printf("计算机拿%d\n",m); a=a-m; } return 0; } 4. #include int d; int a1,a2; int fun(int n); int main(void) { int n;

算法设计与分析习题解答

第一章作业 1.证明下列Ο、Ω和Θ的性质 1）f=Ο(g)当且仅当g=Ω(f) 证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。 必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。 2）若f=Θ(g)则g=Θ(f) 证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。 3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。 证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4）log(n!)= Θ(nlogn)

证明： ?由于log(n!)=∑=n i i 1 log ≤∑=n i n 1 log =nlogn ，所以可得log(n!)= Ο(nlogn)。 ?由于对所有的偶数n 有， log(n!)= ∑=n i i 1 log ≥∑=n n i i 2 /log ≥∑=n n i n 2 /2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。 当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得?n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。 综合以上两点可得log(n!)= Θ(nlogn) 2. 设计一个算法，求给定n 个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法： V oid findsecond(ElemType A[]) { for (i=2; i<=n;i++) if (A[1]

算法设计与分析复习资料1

一 1.循环赛日程表问题的相关叙述。 2.算法运行时所需要占用的存储空间有？ 3.动态规划法的求解步骤 4.解空间树是排列树的问题有。 5.分治法的步骤 6.就会场安排问题，贪心法的最佳贪心策略 7.快速排序法基准元素的选取方法 8.满足满m叉树的问题有？ 9.分支限界法的解题步骤 10.事前分析法相关的影响因素有 11.用分治法求解的问题一般需要具备一些特征，主要有？ 二 1．给定一个有向带权图G=(V，E)，其中每条边的权是一个非负实数，另外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和，这个问题通常称为单源最短路径问题。 2．采用回溯法可以求解0-1背包问题，其解空间的形式为：（x1,x2,…,xn）或n 元组。 3．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。 4．一个正在生成孩子的结点称为扩展结点。 5．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。 6．当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合，这类问题的解空间树称为满m叉树。 7．一个自身已生成但其孩子还没有全部生成的结点称为活结点 8．回溯法中，对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间 9．分支限界法有两种：队列式分支限界法和优先队列式分支限界法。 10．分支限界法采用的是宽度优先搜索。 11．时间复杂性的度量方法通常有两种：事后统计法和事前分析估算法 12．一个所有孩子已经生成的结点称做死结点 13．在最小生成树的生成方法中，Kruskal算法从边的角度出发，每一次将图中的权值最小的边取出来，在不构成环的情况下，将该边加入最小生成树。 三 1．分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子问题，子问题相互独立，如果子问题还是不容易解决，再把子问题分成更小的子问题…，直到最后各个子问题可以简单地直接求解，对各个子问题递归求解，将子问题的解进行合并即得原问题的解。 2．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采

算法设计与分析考试重点归纳

算法设计考试重点整理 题型： 一选择题（10*2=20 分） 二简答题（4*5=20 分） 三应用题（3*10=30 分） 四算法题（3*10=30 分） 第一、二章 算法的定义：解某一特定问题的一组有穷规则的集合（对特定问题求解步骤的一种描述，是指令的有限序列） 算法的特征：1）有限性 2）确定性 3）输入 4）输出 5）能行性 算法分析的目的： 基本数据结构： 线性结构(元素之间是一对一的关系) 用顺序存储结构存储的线性表称为顺序表 用链式存储结构存储的线性表称为链表。 树形结构(元素之间是一对多的关系) 图(网)状结构(元素之间是多对多的关系) 栈：是一种只允许在表的一端进行插入或删除操作的线性表。允许进行插入、删除操作的一端称为栈顶，另一端称为栈底。当栈中没有数据元素时，称之为空栈。栈的插入操作称为进压栈，删除操作称为出栈。 队列：只允许在一端进行插入操作，在另一端进行删除操作的线性表。允许进行插入操作的一端称为队尾。允许进行删除操作的一端称为队头。当队列中没有数据元素时，称之为空队列。队列的插入操作称为进队或入队。队列的删除操作称为退队或出队。 树：树型结构是一种非线性结构，它用于描述数据元素之间的层次关系图 图：G＝(V，E)是一个二元组

其中：V是图G中数据元素（顶点）的非空有限集集合 E是图G中关系的有限集合 由表达式求渐进表达式：例：(n2+n)/4 n2/4（增长速率最快的那一项） 时间复杂度的计算：（P23） 性能的比较：O(1) < O(log2n) < O(n) < O(nlog2n) =O(nlogn)< O(n2) < O(n3) < O(n k) < O(2n) 第三章 算法思想、稳定性、时间复杂度、应用、排序的移动次数： 希尔排序（数据结构P265）：先将待排序列分割为若干个子序列分别进行直接插入排序；待整个序列基本有序时，再对全体记录进行一次直接插入排序。也称缩小增量的直接插入排序。 希尔排序的时间复杂度在O(nlog2n)和 O(n2)之间，大致为O 合并排序（P59）：设初始序列含有n个记录，则可看成n个表长为1的有序表将这n个有序表两两合并，则可得n/2个表长为2的有序表再将这n/2个有序表两两合并，则可得n/4个长为4的有序表依次重复，直到对2个表长为n/2的有序表两两合并得1个表长为n的有序表为止。 堆排序、堆调整（P62）： 初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。 基数排序（P71）：不进行记录关键字的比较，借助多关键字排序的思想对单逻辑关键字进行排序。 算法时间复杂度稳定性 希尔排序 O不稳定 快速排序 O(nlogn)不稳定

算法设计与分析习题答案

算法设计与分析习题答案（第二版） 主编：吕国英 习题答案 习题答案 第三章： 1. #include #include int main(int argc,char **argv) { int n; int i,j,k; int *buf; printf("请输入n的数值:"); scanf("%d",&n); buf=(int *)malloc(n*sizeof(int)); for(i=0;i=0;i--)

for(j=i;j>=0;j--) { buf[j]+=2; } } for(k=0;k<=n-2;k++) { if(buf[k]>=10) { buf[k+1]+=buf[k]/10; buf[k]%=10; } } for(i=n-1;i>=0;i--) printf("%d",buf[i]); printf("\n"); return 0; } 2. #include int main(int argc,char **argv)

int buf[6][6]; int i,j; printf("任意输入6个数字:"); for(i=0;i<6;i++) scanf("%d",&buf[0][i]); for(i=0;i<5;i++) { for(j=0;j<5;j++) { buf[i+1][j+1]=buf[i][j]; } buf[i+1][0]=buf[i][j]; } for(i=0;i<6;i++) { for(j=0;j<6;j++) printf("%d ",buf[i][j]); printf("\n"); } return 0; }

算法设计与分析第三章课后答案吕国英主编.

2、#include void main() { int a[6][6],b[6],i,j; printf("请输入6个整数："); for(i=0;i<6;i++) { scanf("%d",&b[i]); } for(i=0;i<6;i++) { a[0][i]=b[i]; } for(i=1;i<=5;i++) a[i][0]=b[6-i]; for(i=1;i<=5;i++) for(j=1;j<=5;j++) { a[i][j]=a[i-1][j-1]; } for(i=0;i<=5;i++) { for(j=0;j<=5;j++) printf("%d ",a[i][j]); printf("\n"); } } 3、#include void main() { int i,j,count,n; int a[100][100]; printf("请输入矩阵的阶n="); scanf("%d",&n); count=1; for(i=1;i<=n/2;i++) { for(j=i;j<=n-i+1;j++)//上侧 { a[i][j]=count; count++; } for(j=i+1;j<=n-i;j++)//右侧 {

a[j][n-i+1]=count; count++; } for(j=n-i+1;j>=i+1;j--)//下侧 { a[n-i+1][j]=count; count++; } for(j=n-i+1;j>=i+1;j--)//左侧 { a[j][i]=count; count++; } } if(n%2==1) { i=(n+1)/2; a[i][i]=n*n; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%2d ",a[i][j]); printf("\n"); } } 4、#include void main() { int i,j,n,a[100][100],count=1; printf("请输入方阵的阶n:"); scanf("%d",&n); for(i=1;i<=n;i++) for(j=1;j<=i;j++) { a[i-j+1][j]=count; count++; } for(i=1;i<=n;i++) { for(j=1;j<=n-i+1;j++) printf("%4d",a[i][j]); printf("\n");

算法设计与分析C++语言描述(陈慧南版)课后答案

第一章 15P 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数，程序1-2的while 循环体做了10次，程序1-3的while 循环体做了14141次（14142-2循环） 若考虑其他语句，则没有这么多，可能就601倍。 第二章 32P 2-8.（1）画线语句的执行次数为 log n ????。(log )n O 。划线语句的执行次数应该理解为一格整体。 （2）画线语句的执行次数为 111 (1)(2) 16 j n i i j k n n n ===++= ∑∑∑。3()n O 。 （3 ）画线语句的执行次数为 。O 。 （4）当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++， 当n 为偶数时画线语句的执行次数为2 (2)4 n +。2()n O 。 2-10.（1）当1n ≥时，225825n n n -+≤，所以，可选5c =，01n =。 对于0n n ≥，22 ()5825f n n n n =-+≤，所以，22 582()n n n -+=O 。 （2）当8n ≥时，2222 582524n 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 ≥时，3 log log n n n <<，所以()20log 21f n n n n =+<，3 ()log 2g n n n n =+>。可选21 2 c = ，03n =。对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。注意：是f (n )和g (n )的关系。 （2）当4n ≥时，2 log log n n n <<，所以2 2 ()/log f n n n n =<，2 2 ()log g n n n n =≥。可选1c =，04n =。对于0n n ≥，2 ()()f n n cg n <≤，即()(())f n g n =O 。 （3）因为log log(log )()(log ) n n f n n n ==，()/log log 2n g n n n n ==。当4n ≥时，log(log )()n f n n n =≥，

算法设计与分析课后习题

第一章 1. 算法分析题 算法分析题1－1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是，n^2 < 2 ^n 所以，当n >= 1时，n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为：f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以：f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为：log(n) < √n; f(n) = 2log(n); g(n)= √n 所以：f(n) = O(g(n)) (3)因为：log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以；f(n) = Ω(g(n)) (4)因为：f(n) = nlogn +n; g(n) = logn 所以：f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10)

所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为：f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1－9 证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答： 因此，Tmax(N) = Ω(Tavg(N)) = Ω(Θ(f(n)))=Ω(f(n)). 第二章 算法分析题

算法设计与分析 王红梅 胡明 习题答案

习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现 在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次， 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 ??m=n ???n=r ??r=m-n 3?输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C ++描述。 编写程序，求n 至少为多大时，n 个“1”组成的整数能被2013整除。 #include 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至少为:"< using namespace std; int main () { double a,b; double arctan(double x);圣经上说：神6天创造天地万有，第7日安歇。为什么是6天呢？任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。例如，6=1+2+3，因此6是完美数。神6天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数 #include using namespace std; int main() { int value, k=1; cin>>value; for (int i = 2;i!=value;++i) { while (value % i == 0 ) { k+=i;有4个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用1分钟，乙过桥要用2分钟，丙过桥要用5分钟，丁过桥要用10分钟，显然，两个人走路的速度等于其中较慢那个人的速度，问题是他们全部过桥最少要用多长时间？ 由于甲过桥时间最短，那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如： 第一趟：甲，乙过桥且甲回来

习题答案第四章 算法设计与分析 吕国英

习题答案第四章算法设计与分析吕国英 main(void) { int buf[100]; int n; int i,j,k; scanf("%d",&n); for(i=0;i=10) { buf[j+1]+=buf[j]/10; buf[j]=buf[j]%10; } } for(i=n-1;i>=0;i--) printf("%d",buf[i]); printf("\n"); return 0; }2、 #includeint main(void){int n=2;int i;for(i=1;i<=9;i++){n=(n+2)*2;}printf("%d\n",n);return 0;}3、#includeint main(void){int a=54;int n;int m;printf("计算机先拿3张牌\n");a=a-3;while(a>=0){printf("还剩%d张牌\n",a);printf("你拿几张？请输入： ");scanf("%d",&n);if(n>4||n<1||n>a){printf("错误！重新拿牌\n");continue;}a=a-n;printf("还剩%d张牌 \n",a);if(a==0)break;m=5-n;printf("计算机拿%d\n",m);a=a-m;}return 0;}4、#includeint d;int a1,a2;int fun(int n);int main(void){int

最新算法设计与分析复习要点(1)

算法设计与分析的复习要点 第一章：算法问题求解基础 算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 一．算法的五个特征： 1．输入：算法有零个或多个输入量； 2．输出：算法至少产生一个输出量； 3．确定性：算法的每一条指令都有确切的定义，没有二义性； 4．可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现； 5．有穷性：算法必须总能在执行有限步之后终止。 二．什么是算法？程序与算法的区别 1．笼统地说，算法是求解一类问题的任意一种特殊的方法；较严格地说，算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 2．程序是算法用某种程序设计语言的具体实现；算法必须可终止，程序却没有这一限制；即：程序可以不满足算法的第5个性质“有穷性”。 三．一个问题求解过程包括：理解问题、设计方案、实现方案、回顾复查。 四．系统生命周期或软件生命周期分为： 开发期：分析、设计、编码、测试；运行期：维护。 五．算法描述方法：自然语言、流程图、伪代码、程序设计语言等。 六．算法分析：是指对算法的执行时间和所需空间的估算。算法的效率通过算法分析来确定。 七．递归定义：是一种直接或间接引用自身的定义方法。一个合法的递归定义包括两部分：基础情况和递归部分； 基础情况：以直接形式明确列举新事物的若干简单对象； 递归部分：有简单或较简单对象定义新对象的条件和方法 八．常见的程序正确性证明方法： 1.归纳法：由基础情况和归纳步骤组成。归纳法是证明递归算法正确性和进行算法分析的强有力工具； 2.反证法。 第二章：算法分析基础 一．会计算程序步的执行次数（如书中例题程序2-1,2-2,2-3的总程序步数的计算）。二．会证明5个渐近记法。（如书中P22-25例2-1至例2-9） 三．会计算递推式的显式。（迭代法、代换法，主方法） 四．会用主定理求T(n)=aT(n/b)+f(n)。（主定理见P29，如例2-15至例2-18）五．一个好的算法应具备的4个重要特征： 1.正确性：算法的执行结果应当满足预先规定的功能和性能要求； 2.简明性：算法应思路清晰、层次分明、容易理解、利于编码和调试； 3.效率：算法应有效使用存储空间，并具有高的时间效率； 4.最优性：算法的执行时间已达到求解该类问题所需时间的下界。 六．影响程序运行时间的主要因素： 1.程序所依赖的算法； 2.问题规模和输入数据规模； 3.计算机系统性能。 七．1.算法的时间复杂度：是指算法运行所需的时间；

算法设计与分析第一章习题解1.1,1.10,1.15

1.15练习 1.1（a） 1)A[1…60] = A[(1+60)/2]=A[30]=40 由于33<40，舍弃A[30…60]; 2)A[1…29] = A[(1+29)/2]=A[15]=25 由于33>25，舍弃A[1…15]; 3) A[16…29]= A[(16+29)/2]=A[22]=32 由于33>32，舍弃A[16…22]; 4) A[23…29] = A[(23+29)/2]=A[26]=36 由于33<36，舍弃A[26…29]; 5) A[23…25] = A[(23+25)/2]=A[24]=34; 由于33<34，舍弃A[24, 25]; 6) A[23] = 11 12 13 … 68 69 70 11 12 13 … 37 38 39 26 27 28 … 37 38 39 33 34 35 36 37 38 39 33 34 35 33

由于33=33，搜索完毕。 综上，搜索33共执行了6次比较。 同理可得（b ）搜索7共执行了5次比较。 （c ）搜索70共执行了6次比较。 （d ）搜索77共执行了6次比较。 1.10 对11 12 1 5 15 3 4 10 7 2 16 9 8 14 13 6用bottomupsort 算法，按非降序排列。 解：用图示，如下进行。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 3 4 5 10 11 12 15 1 5 11 1 2 1.15用Θ表示函数。 (b) 2 6 7 8 9 1 3 1 4 16 3 4 10 1 5 2 7 9 1 6 6 8 13 14 11 12 1 5 15 3 4 10 2 7 9 16 8 14 6 13

算法设计与分析-第2版-吕国英-第三章课后习题答案 (1)

3.1//计算2+22+222+...+222 (2) void main() { int i,n,sum=0; print("请输入最后一个因子的位数\n"); scanf("%d",&n); for(i=1;i<=n;i++) sum=sum+((int)pow(10,i)-1)/9*2; print("2+22+222+...+222……2=%d\n",sum); } 3.2显示{5，7，4，8，9，1}的方阵方式 main() { int i,j,t,ori[6]={5,7,4,8,9,1}; for(i=0;i<6;i++) { for(j=0;j<6;j++) { t=(j-i)<0?j-i+6:j-i; printf("%d ",ori[t]);} printf("\n"); } } 3.3 main() { int n; int **up(int **array); scanf("%d",&n); int arr[1][1]={{n*n}}; for(j=1;j

for(i=1;i<=n;i++) tem[n][i]=tem[n][i-1]+1; for(i=1;i<=n;i++) tem[n][n-i]=tem[n][n+1-i]+1; for(i=1;i

算法设计与分析基础第七章作业

第七章 习题7.1 1.分步计数算法是稳定的吗？ 解： 分步计数算法是稳定的。 习题7.2 3.用Horspool算法在一个1000个0构成的二进制文本中查找下列模式时，分别需要进行多少次字符比较？ a.00001; b.10000; c.01010; 5 解： a. 比较次数：(1000/5)*1=200 b.

比较次数：[(1000-5+1]*5=4980 c. 比较次数：[(1000-3)/2]*2=996 (1000-3)/2取整数部分 4.用Horspool算法在一个长度为n的文本中查找一个长度为m(n>=m)的模式。请分别给出下面两种例子。 a.最差输入； b.最优输入。 解： a.模式的每次一移动的举例均为1，且没有匹配成功，或者到最后一次匹配才成功。 b.模式不需要移动，且比较了m次即成功。 7.用Boyer-Moore算法在一个1000个0构成的二进制文本中查找 列模式时，分别需要进行多少次字符比较？ a.00001; b.10000; c.01010; 解： a.

坏符号移动表： 后缀移动表： d1=max{t1(0),1}=1,d2=5 模式移动max(d1,d2)=5，所以每次移动5位，且每次只比较一次。比较次数为:1000/5=200 b. 坏符号移动表： 后缀移动表：

d1=max{t1(0)-4,1}=1,d2=1 模式移动max(d1,d2)=1,所以每次都移动一位，比较5次。比较次数：[(1000-5+1]*5=4980 c. 坏符号移动表： 后缀移动表： d1=max{t1(0)-1,1}=1,d2=2 模式移动max(d1,d2)=2,所以每次都能移动2位，比较2次。比较次数：[(1000-3)/2]*2=996 习题7.3 2.对于输入30,20,56,75,31,19和散列函数h(K)=K mod11 a.构造它们的闭散列表； b.求在本表中成功查找的最大键值比较次数； c.求在本表中成功查找的平均键值比较次数；

算法设计与分析_第二版_吕国英_第四章课后习题答案

4.1#include #include void main() { int i,n,sum=0,power,proce,remainder,interger,decimal; printf("请输入2+22+…+2222(n个2)(不考虑精度)的n\nn="); scanf("%d",&n); for(i=1;i<=n&&i<=9;i++) { proce=(int)(pow(10,i)-1)/9*2; sum=sum+proce; } if(n>9) { for(i=1,power=n-9;i<=power;i++) { proce=(int)(pow(10,9)-1)/9*2; sum=sum/10+proce; remainder=sum%10; if(remainder>=5) sum++; } interger=sum/100000000; decimal=sum%100000000; printf("2+22+…+2222(n个2)(不考虑精度)=%d.%d*e+%d\n",interger,decimal,n-1); } else printf("2+22+…+2222(n个2)(不考虑精度)=%d\n",sum); } 4.2 #include void main() { int i,total=2,day=10; for(i=day-1;i>=1;i--) total=(total+2)*2; printf("第一天共有%d个桃。\n",total);

} 4.3 #include void main() { int flag=0,last=54,card; printf("共有牌：%d \n",last); printf("计算机出：3 "); last=last-3; while(last>1) { printf("还有牌：%d ",last); printf("您出："); scanf("%d",&card); printf("计算机出：%d ",5-card); last=last-5; } printf("\n还有牌：%d 。您只能输入1。\n",last); printf("您出："); scanf("%d",&card); printf("Sorry!您输了……\n"); } 4.5 #include void main() { int array[8][8],i,j,i1=0,i2=1,i3=2,i4=3,i5=4,i6=5,i7=6,i8=7,j1=0,j2=0,j3=0,j4=0,j5= 0,j6=0,j7=0,j8=0; //先判断不在同一行和同一列，然后再做不在对角线 printf("此处预先规定，第一行第一列处是皇后。\n"); for(j2=1;j2<8;j2++) for(j3=1;j3<8;j3++) for(j4=1;j4<8;j4++) for(j5=1;j5<8;j5++)

湘潭大学算法设计与分析知识点

第一章算法概述 1、算法的五个性质：有穷性、确定性、能行性、输入、输出。 2、算法的复杂性取决于：（1）求解问题的规模（N）,（2）具体的输入数据（I），（3）算法本身的设计（A），C=F(N,I,A)。 3、算法的时间复杂度的上界记号O， 下界记号Ω(记为f(N) = Ω(g(N))。即算法的实际运行时间至少需要g(n)的某个常数倍时间)， 同阶记号Θ：f(N)= Θ(g(N))表示f(N)和g(N)同阶。 即算法的实际运行时间大约为g(n)的某个常数倍时间。 低阶记号o：f(N)=o(g(N))表示f(N)比g(N)低阶。 多项式算法时间： O(1)

算法设计与分析习题与实验题(12.18)

《算法设计与分析》习题 第一章引论 习题1-1 写一个通用方法用于判定给定数组是否已排好序。 解答： Algorithm compare(a,n) Begin J=1; While (j=a[j+1]) do j=j+1; If j=n then return true else return false end if End if end 习题1-2 写一个算法交换两个变量的值不使用第三个变量。 解答：x=x+y; y=x-y; x=x-y; 习题1-3 已知m,n为自然数，其上限为k（由键盘输入，1<=k<=109）,找出满足条件(n2-mn-m2)2=1 且使n2+m2达到最大的m、n。 解答： m:=k; flag:=0; repeat n:=m; repeat l:=n*n-m*n-m*n; if (l*l=1) then flag:=1 else n:=n-1; until (flag=1) or (n=0) if n=0 then m:=m-1 until (flag=1) or (m=0); 第二章基础知识

习题2-1 求下列函数的渐进表达式： 3n 2+10n ; n 2/10+2n ; 21+1/n ; log n 3; 10 log3n 。 解答： 3n 2+10n=O （n 2）， n 2/10+2n =O （2n ）， 21+1/n=O （1）， log n 3=O （log n ），10 log3n =O （n ）。 习题2-2 说明O (1)和 O (2)的区别。 习题2-3 照渐进阶从低到高的顺序排列以下表达式：!n ， 3/22,2,20,3,log ,4n n n n n 。 解答：照渐进阶从低到高的顺序为：!n 、 3n 、 2 4n 、23 n 、20n 、log n 、2 习题2-4 （1） 假设某算法在输入规模为n 时的计算时间为n n T 23)(?=。在某台计算机 上实现并完成该算法的时间为t 秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t 秒内能解输入规模为多大的问题？ （2） 若上述算法的计算时间改进为2)(n n T =，其余条件不变，则在新机器上用 t 秒时间能解输入规模多大的问题？ （3） 若上述算法的计算时间进一步改进为8)(=n T ,其余条件不变，那么在新机 器上用t 秒时间能解输入规模多大的问题？ 解答： （1） 设新机器用同一算法在t 秒内能解输入规模为1n 的问题。因此有 64/23231n n t ?=?=，解得61+=n n 。 （2） n n n n 8641221==>=。 （3） 由于=)(n T 常数，因此算法可解任意规模的问题。 习题2-5 XYZ 公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC 公司同类产品的100倍。对于计算复杂性分别为n ，2n ，3n 和!n 的各算法，若用ABC 公司的计算机能在1小时内能解输入规模为n 的问题，那么用XYZ 公司的计算机在1小时内分别能解输入规模为多大的问题？

算法设计与分析 第7章作业

「算法设计与分析」第7章作业2015.10 学号: 15S103172 姓名: 谢浩哲 1.在下图中考虑哈密顿环问题. 将问题的解空间表示成树, 并分别利用深度优先搜索和广度优先搜索判 定该图中是否存在哈密顿环. 问题解空间的树状结构: 算法概述: 从起始点出发, 搜索从这个点出发所有可到达的点(深度优先或广度优先策略均可). 对于每到达一个点, 判断: 是否已经回到起始点, 是否经过重复的点. 若经过了重复了点, 则不再搜索. 若到达了起始点, 并且恰好经过了所有的点, 则找到了最优解.

算法实现: 深度优先搜索: 35

广度优先搜索:

!isVisited(startPoint, i, 37 2.考虑8-魔方问题. 分别用深度优先算法, 广度优先算法, 爬山法, 最佳优先方法判定上图所示的初始 格局能够通过一系列操作转换成目标格局, 将搜索过程的主要步骤书写清楚.

问题的部分解空间树状结构:

深度优先搜索: 搜索顺序为1 -> 2 -> 4 -> 10 -> … 广度优先搜索: 搜索顺序为1 -> 2 -> 3-> 4 -> 5 -> 6 -> … 爬山法: 基于深度优先搜索, 选取当前分支上最优解; 搜索顺序为1 -> 2 -> 4 -> 11 -> … 最佳优先方法: 基于深度优先搜索, 选取所有分支上最优解; 搜索顺序为1 -> 2 -> 4 -> 11 -> … 3.分别使用深度优先法和分支限界法求解子集和问题的如下实例. 输入: 集合S=7, 4, 6, 13, 20, 8和整数K=18. 输出: S’使得S’中元素之和等于K. 深度优先搜索: 问题的部分解空间如下如所示: 算法实现: