最新算法竞赛入门经典各章(第二版)前4章课后习题答案电子教案

算法设计与分析第二版课后习题解答算法设计与分析基础课后练习答案习题 4.设计一个计算的算法，n是任意正整数。

除了赋值和比较运算，该算法只能用到基本的四则运算操作。

算法求//输入：一个正整数n2//输出：。

step1:a=1；step2:若a*a 5. a．用欧几里德算法求gcd。

b. 用欧几里德算法求gcd,比检查min｛m，n｝和gcd间连续整数的算法快多少倍？请估算一下。

a. gcd(31415, 14142) = gcd(14142, 3131) = gcd(3131, 1618) =gcd(1618, 1513) = gcd(1513,105) = gcd(1513, 105) = gcd(105, 43) =gcd(43, 19) = gcd(19, 5) = gcd(5, 4) = gcd(4, 1) = gcd(1, 0) = 1.b.有a可知计算gcd欧几里德算法做了11次除法。

连续整数检测算法在14142每次迭代过程中或者做了一次除法，或者两次除法，因此这个算法做除法的次数鉴于1·14142 和 2·14142之间，所以欧几里德算法比此算法快1·14142/11 ≈ 1300 与 2·14142/11 ≈ 2600 倍之间。

6.证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

故gcd(m,n)=gcd(n,r)7.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint:对于任何形如0 gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次) b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次) gcd(5,8) 习题 1.(农夫过河)P—农夫 W—狼G—山羊C—白菜 2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法 //输入:实系数a,b,c//输出:实根或者无解信息 If a≠0D←b*b-4*a*c If D>0temp←2*ax1←(-b+sqrt(D))/temp x2←(-b-sqrt(D))/temp return x1,x2else if D=0 return –b/(2*a) else return “no real roots” else //a=0if b≠0 return –c/b else //a=b=0if c=0 return “no real numbers”else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出 b.伪代码算法 DectoBin(n)//将十进制整数n转换为二进制整数的算法 //输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中 i=1while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; }9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1]) //输入:数组A[0..n-1] //输出:the smallest distance d between two of its elements习题1. 考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗? 解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count 4.(古老的七桥问题) 第2章习题7.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n)∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。

算法语言书后习题参考答案(第二版)第一章1(1)A (2)D (3)D (4)AC第二章1、(1)AC (2)BD (3)CD (4)C (5)B (6)D2、(2)Hi FrankWelcome(3)3 Apr Wed第三章1(1) A (2) AB (3) AD2(5)方法MyMethod1的重载形式不合法，因为访问限制修饰符和返回类型都不是方法的标识。

方法MyMethod2的重载形式合法。

(6) 运行结果为x=0, y=5, z=0x=0, y=5, z=5(8)应将public static readonly InnerClasses inner;改成public static readonly InnerClasses inner=new InnerClasses();运行结果为7913第四章1（1）C（2）A（3）BC（4）A（5）A第(5)涉及到对负数的移位，不要求掌握对负数的移位，但要求掌握对正数的移位。

2（10）true true false true false第五章1（1）没有一个是正确的（2）C（3）D（4）A（5）B（6）D（7）BC第(6)题应改为：下面语句所计算的x数学表达式为_______。

for (int x = 0, y = 1, z = 1; z <= 10; x += y, y *= ++z)第(7)的选项A应改为：A. int x = 1, y = 0; while (true) if ((x += (y++)) > 100) break;第六章1（1）D（2）A（3）D（4）不作要求（5）AC2（7）没有错误。

但它在属性的get访问函数中修改了所封装的字段值，这违反了访问函数的设计原则，容易引起误解。

应避免使用这类代码。

第七章1（1）C（2）没有一个正确（3）B（4）AC (5) ABD(不作要求)2 (9) 代码中存在一处错误，派生类B的属性Y在重载基类A的属性Y时，必须同时重载其get和set访问函数。

算法与数据结构课后习题答案第一章一、选择题CCADB二、判断题FFFFT三、简答题5.(1) n-1 (2)1 (3)n(n+1)/2 (4)if(a<b) n , a++ n/2(5)if(x>100) 11*100-1, x-=10;y-- 1006.(1)O(log3n) (2) O(n2) (3) O(n2)第二章一、选择题1~5: AADCD 6~10:BCBAD 11~12:BD二、判断题1~5:FTFTF 6~10:TFTTF 11~12:FF三、算法设计题1.#define arrsize 100int Inserseqx(datatype A[ ], int *elenum, datatype x ) { int i=*elenum-1;if(*elenum==arrsize) return 0;while(i>=0&&A[i]>=x ){ A[i+1]=A[i]; i--; }A[i+1]=x; *elenum ++;return 1;}6.typedef struct node{ dataype data;struct node *next;}LNode, *LinkList;int Inserlinkx(LinkList L,datatype x ){ LNode *p=L,*s;s=(LNode *)malloc(sizeof(LNode));if(!s) return 0;s->data=x;while(p->next&&p->next->data<=x) p=p->next;s->next=p->next; p->next=s;return 1;}第三章一、选择题1~5:CBDBB 6~10: CBDCC二、判断题1~5:TTTFF三、简答题4. 共14种顺序：4321 3214 3241 3421 2134 2143 23142341 2431 1234 1243 1324 1342 1432四、简答题1.#define MAXSIZE 1000typedef struct{datatype data[MAXSIZE];int top;}SeqStack;SeqStack *Init_SeqStack(); /*栈初始化*/int Empty_SeqStack(SeqStack *s)；/*判栈空*/int Push_SeqStack(SeqStack *s,datatype x); /*x入栈*/ int Pop_SeqStack(SeqStack *s,datatype *x); /*出栈*/int judgehuiwen(char *str)/*返回1表示是回文，否则不是*/{ SeqStack *s=Init SeqStack( );char *ch=str,ch1;while(*ch!=’@’){Push_SeqStack(s, *ch);ch++;}ch=str;while(!Empty_SeqStack(s)){ Pop_SeqStack(s,&ch1);if(*ch!=ch1) return 0;ch++;}return 1;}5.#define MAXSIZE 1000typedef struct{datatype data[MAXSIZE];int top;}SeqStack;SeqStack *Init_SeqStack(); /*栈初始化*/int Empty_SeqStack(SeqStack *s)；/*判栈空*/int Push_SeqStack(SeqStack *s,datatype x); /*x入栈*/ int Pop_SeqStack(SeqStack *s,datatype *x); /*出栈*/ int judge(char *str)/*返回1表示是匹配，否则不是*/{ SeqStack *s=Init SeqStack( );char *ch=str,ch1;while(*c h!=’\0’){ if（*ch==’(‘) Push_SeqStack(s, *ch);else if(*ch==’)‘)if(!Pop_SeqStack(s,&ch1)) return 0;ch++;}if(Empty_SeqStack(s)) return 1;else return 0;}4.typedef struct node{ dataype data;struct node *next;}Lqnode, *LqList;置空：LqList Init_lq(){ LqList rear=(LqList *)malloc(sizeof(LqList)); rear->next=rear;return rear;}入队：int in_lq(LqList *rear, datatype x){ Lqnode *p=(LqList *)malloc(sizeof(LqList)); if(!p) return 0;p->data=x;p->next=*rear->next; *rear->next=p; *rear=p; return 1;}出队：int out_lq(LqList *rear, datatype x){ Lqnode *p;if(*rear->next==*rear) return 0;p=*rear->next->next;if(p==*rear){*rear=*rear->next;*rear->next=*rear;} else *rear->next->next=p->next;free(p);return 1;}第四章一、选择题1-3：CBA 4：DAB 5:CCC 6:C二、判断题FTFFFFF三、简答题2.4. k=i+j-2+(i+1)%2 或k=i+j-1+i%26.第五章一、选择题：1~5：CCBBB 6~10:CBDAD 11~15:DCBDB3 5 6 7 98 13 17二、判断题：1~5：FTFFT 6~10:FFFTF 11~15:TFTFF 16~20:FTFFT 三、简答题：（(2)4、条件：森林中既没有孩子也没有右边的兄弟的结点11. 最大值：2h-1 最小值：2h-116.0.31 0.16 0.10 0.08 0.11 0.20 0.04 0.12 0.21 0.28 0.410.59a b c d e f ga:01 b:001 c:110 d:0000 e:111 f:10 g:0001四、算法设计题：typedef struct bitnode{ datatype data;struct bitnode *lchild, *rchild;}BiTNode, *BiTree;1.计算结点数目int counttotal(BiTree bt){ if(bt==NULL) return 0;return counttotal(bt->lchild)+counttotal(bt->rchild)+1;}计算度为1的结点数目：int countdegree1(BiTree bt){ if(bt==NULL) return 0;if( bt->lchild==NULL&& bt->rchild==NULL) return 0;if( bt->lchild==NULL|| bt->rchild==NULL)return countdegree1(bt->lchild)+ countdegree1(bt->rchild)+1; return countdegree1(bt->lchild)+ countdegree1(bt->rchild);}3.求深度;int depth(BiTree bt){ int ld,rd;if(bt==NULL) return 0;ld= depth(bt->lchild); rd=depth(bt->rchild);if( ld>=rd) return ld+1;return rd+1;}第6章作业讲评一、选择题1-4：BABC 5:BD 6-10:DBACB二、判断题1-5：FTTFF 6-10:TTFFT 11-15:FTFFF三、简答题1.（1）ID(1)=2 OD(1)=1ID(2)=2 OD(2)=2ID(3)=1 OD(3)=3ID(4)=3 OD(4)=0ID(5)=2 OD(5)=3ID(6)=1 OD(6)=2(2)0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0(3) （4）54 3 2 1 0 54 3 2 1 0（5） 2. （1）0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0（2）（4）（5）v1 v2 v3 v4 v5 v6 v73. 邻接矩阵表示图时，与顶点个数有关，与边的条数无关。

第一章习题1-1#include<stdio.h>int main(){int a,b,c;double d;scanf("%d%d%d",&a,&b,&c);d=(double)(a+b+c);printf("%.3lf\n",d/3.0);return0;}习题1-2#include<stdio.h>int main(){int f;double c;scanf("%d",&f);c=5*(f-32)/9;printf("%.3lf\n",c);return0;}习题1-3#include<stdio.h>int main(){int n;scanf("%d",&n);printf("%d\n",(n*(1+n))/2);return0;}习题1-4#include<stdio.h>#include<math.h>#define pi4.0*atan(1.0)int main(){int n;scanf("%d",&n);printf("%lf\n",sin((pi*n)/180));printf("%lf\n",cos((pi*n)/180));return0;}习题1-5#include<stdio.h>int main(){double x1,y1,x2,y2,a;scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));printf("%lf\n",a);return0;}习题1-6#include<stdio.h>int main(){int n;scanf("%d",&n);if(n%2==0){printf("YES\n");}else{printf("NO\n");}return0;}习题1-7#include<stdio.h>int main(){int n;double a;scanf("%d",&n);a=n*95.0;if(a<300){printf("%.2lf\n",a);}else{printf("%.2lf\n",a*0.85);}return0;}习题1-8#include<stdio.h>#include<math.h>int main(){double n;scanf("%lf",&n);printf("%.2lf",fabs(n));return0;}习题1-9#include<stdio.h>int main(){int a,b,c;scanf("%d%d%d",&a,&b,&c);if(a==b&&b==c){printf("no\n");}if((a*a+b*b==c*c)||(a*a+c*c==b*b)||(b*b+c*c==a*a)) {printf("yes\n");}else{printf("no\n");}return0;}习题1-10#include<stdio.h>int main(){int n;scanf("%d",&n);if(n%4==0){if(n%100!=0){printf("no\n");}else{if(n%400==0){printf("yes\n");}else{printf("no\n");}}}else{printf("no\n");}return0;}第二章习题2-1#include<stdio.h>int main(){int n,count=0;scanf("%d",&n);while(n>0){count++;n=n/10;}printf("%d\n",count);return0;}习题2-2#include<stdio.h>int main(){int a,b,c;for(int i=100;i<=999;i++){a=i%10;b=i/10%10;c=i/100;if(i==a*a*a+b*b*b+c*c*c){printf("%d\n",i);}}return0;}习题2-3#include<stdio.h>int main(){int i,a,b,c;scanf("%d%d%d",&a,&b,&c);for(i=10;i<=100;i++){if(i%3==a&&i%5==b&&i%7==c){printf("%d\n",i);}}if(i==101){printf("no answer\n");}return0;}习题2-4#include<stdio.h>int main(){int i,j,k,n;scanf("%d",&n);for(i=n;i>0;i--){for(k=0;k<n-i;k++){printf("");}for(j=0;j<2*i-1;j++){printf("#");}printf("\n");}return0;}习题2-5文件题，南邮竞赛基本不涉及。

算法设计与分析基础课后练习答案习题1.14.设计一个计算的算法，n是任意正整数。

除了赋值和比较运算，该算法只能用到基本的四则运算操作。

算法求//输入：一个正整数n 2//输出：。

step1:a=1；step2:若a*a<n 转step 3，否则输出a；step3:a=a+1转step 2；5. a．用欧几里德算法求gcd（31415，14142）。

b. 用欧几里德算法求gcd（31415，14142）,比检查min｛m，n｝和gcd（m，n）间连续整数的算法快多少倍？请估算一下。

a. gcd(31415, 14142) = gcd(14142, 3131) = gcd(3131, 1618) =gcd(1618, 1513) = gcd(1513, 105) = gcd(1513, 105) = gcd(105, 43) =gcd(43, 19) = gcd(19, 5) = gcd(5, 4) = gcd(4, 1) = gcd(1,0) = 1.b.有a可知计算gcd（31415，14142）欧几里德算法做了11次除法。

连续整数检测算法在14142每次迭代过程中或者做了一次除法，或者两次除法，因此这个算法做除法的次数鉴于1·14142 和2·14142之间，所以欧几里德算法比此算法快1·14142/11 ≈1300 与2·14142/11 ≈2600 倍之间。

6.证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:●如果d整除u和v, 那么d一定能整除u±v;●如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

算法设计与分析基础课后练习答案习题1.14.设计一个计算的算法，n是任意正整数。

除了赋值和比较运算，该算法只能用到基本的四则运算操作。

算法求//输入：一个正整数n 2//输出：。

step1:a=1；step2:若a*a<n 转step 3，否则输出a；step3:a=a+1转step 2；5. a．用欧几里德算法求gcd（31415，14142）。

b. 用欧几里德算法求gcd（31415，14142）,比检查min｛m，n｝和gcd（m，n）间连续整数的算法快多少倍？请估算一下。

a. gcd(31415, 14142) = gcd(14142, 3131) = gcd(3131, 1618) =gcd(1618, 1513) = gcd(1513, 105) = gcd(1513, 105) = gcd(105, 43) =gcd(43, 19) = gcd(19, 5) = gcd(5, 4) = gcd(4, 1) = gcd(1,0) = 1.b.有a可知计算gcd（31415，14142）欧几里德算法做了11次除法。

连续整数检测算法在14142每次迭代过程中或者做了一次除法，或者两次除法，因此这个算法做除法的次数鉴于1·14142 和2·14142之间，所以欧几里德算法比此算法快1·14142/11 ≈1300 与2·14142/11 ≈2600 倍之间。

6.证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:●如果d整除u和v, 那么d一定能整除u±v;●如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

算法设计与分析基础课后练习答案算法设计与分析基础课后练习答案习题1.1 4.设计一个计算的算法，n 是任意正整数。

除了赋值和比较运算，该算法只能用到基本的四则运算操作。

能用到基本的四则运算操作。

算法求//输入：一个正整数n 2 //输出：。

step1:a=1；step2:若a*a<n 转step 3，否则输出a ； step3:a=a+1转step 2； 5. a ．用欧几里德算法求gcd （31415，14142）。

b. 用欧几里德算法求gcd （31415，14142）,比检查min ｛m ，n ｝和gcd （m ，n ）间连续整数的算法快多少倍？请估算一下。

a. gcd(31415, 14142) = gcd(14142, 3131) = gcd(3131, 1618) =gcd(1618, 1513) = gcd(1513, 105) = gcd(1513, 105) = gcd(105, 43) =gcd(43, 19) = gcd(19, 5) = gcd(5, 4) = gcd(4, 1) = gcd(1, 0) = 1. b.有a 可知计算gcd （31415，14142）欧几里德算法做了11次除法。

次除法。

连续整数检测算法在14142每次迭代过程中或者做了一次除法，或者两次除法，因此这个算法做除法的次数鉴于1·14142 和 2·14142之间，之间，所以欧几里德算法所以欧几里德算法比此算法快1·14142/11 ≈ 1300 与 2·14142/11 ≈ 2600 倍之间。

倍之间。

6.证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数对每一对正整数m,n 都成立. Hint: 根据除法的定义不难证明: l 如果d 整除u 和v, 那么d 一定能整除u ±v;l 如果d 整除u,那么d 也能够整除u 的任何整数倍ku. 对于任意一对正整数m,n,m,n,若若d 能整除m 和n,n,那么那么d 一定能整除n 和r=m mod n=m-qn n=m-qn；显然，若；显然，若d 能整除n 和r ，也一定能整除m=r+qn 和n 。

2-1 Daffodil2017年10月1日12:561 #include<stdio.h>2 int main(void)3 {4 int shui,xian,hua;5 int n =100;6 int g,s,b;7 int sum =0;8 while(n <1000)9 {10 g =n%10;11 s =n/10%10;12 b =n/100;13 shui =g*g*g;14 xian =s*s*s;15 hua =b*b*b;16 sum =shui +xian +hua;17 if(sum ==n)printf("%d\n",n);18 n++;19 }20 return0;21 }2-2 Hanxin2017年10月1日12:591 #include<stdio.h>2 int main(void)3 {4 int s,w,q;5 int kase =0;6 while(scanf("%d%d%d", &s, &w, &q) !=EOF)7 {8 int i =0;9 int n =10;10 while(n <=101)11 {12 if(n%3==s &&n%5==w &&n%7==q &&n <=100)13 {14 printf("Case %d: %d\n", ++kase,n);15 i =1;16 }17 else if(n >100&&i ==0)printf("Case %d: No answer\n", ++kase);18 n++;19 }20 }21 return0;22 }2-3 Triangle2017年10月1日12:591 #include <stdio.h>2 int main()3 {4 int i, j, n;5 scanf("%d", &n);6 for(i = 0; i < n; i++)7 {8 for(j= 0; j< I; j++)9 printf(" ");10 for(j= 0; j< 2*(n-i)-1; j++)11 printf("#\n");12 }13return0;14}2-4 Subsequence2017年10月1日13:001 #include<stdio.h>2 int main(void)3 {4 long long n,m;5 int kase =0;6 for( ; ; )7 {8 scanf("%lld%lld", &n, &m);9 if(n ==0&&m ==0)break;10 double sum =0.0;11 while(n <=m)12 {13 long long a =n*n;14 double b = (double)1.0/a;15 sum +=b;16 n++;17 }18 printf("Case %d: %.5lf\n", ++kase,sum);19 }20 return0;21 }22 /*23 将所有int改为long long方才解决问题，为什么？24 long long n, m; 为什么不能为int n, m; ?25 */2-5 Decimal2017年10月1日13:001 #include<stdio.h>2 int main(void)3 {4 int a,b,c;5 int kase =0;6 int i;7 for(;;)8 {9 scanf("%d%d%d", &a, &b, &c);10 if(a ==0&&b ==0&&c ==0)break;11 a %=b;12 printf("Case %d: %d.", ++kase,a/b);13 for(i =1;i <c;i++)14 {15 printf("%d",a*10/b);16 a =a*10%b;17 }18 if(a%b*10*10/b >=5)19 printf("%d\n",a%b*10/b+1);20 else21 printf("%d\n",a%b*10/b);22 }23 return0;24 }25 /*26 循环+判断 可以避开数组...27 求余的式子很巧妙...28 */2-6 Permutation2017年10月1日13:001 #include<stdio.h>2 int main(void)3 {4 int a,b,c,d,e,f,g,h,i;5 int n =100;6 while(n <=333)7 {8 a =n/100;9 b =n/10%10;10 c =n%10;11 if(a ==b ||a ==c ||b ==c )12 n++;13 else if(b ==0||c ==0)14 n++;15 else16 {17 int n2 =n*2;18 d =n2/100;19 e =n2/10%10;20 f =n2%10;21 if(e ==0||f ==0)22 n++;23 else if(d ==e ||d ==f ||e ==f)24 n++;25 else if(d ==b ||d ==c)// d == a省略,百位不会相等26 n++;27 else if(e ==a ||e ==b ||e ==c)28 n++;29 else if(f ==a ||f ==b ||f ==c)30 n++;31 else32 {33 int n3 =n*3;34 g =n3/100;35 h =n3/10%10;36 i =n3%10;37 if(h ==0||i ==0)38 n++;39 else if(g ==h ||g ==i ||h ==i)40 n++;41 else if(g ==b ||g ==c ||g ==e ||g ==f)42 n++;43 else if(h ==a ||h ==b ||h ==c ||h ==d ||h ==e ||h ==f)43 else if(h ==a ||h ==b ||h ==c ||h ==d ||h ==e ||h ==f)44 n++;45 else if(i ==a ||i ==b ||i ==c ||i ==d ||i ==e ||i ==f)46 n++;47 else48 {49 printf("%d %d %d\n",n,n2,n3);50 n++;51 }52 }53 }54 }55 return0;56 }Chapter 2 Q&A2017年10月1日13:001 #include<stdio.h>2 int main(void)3 {4 int n,i;5 scanf("%d", &n);6 for(i =1;i <=n;i++)7 printf("%d\n",i);89 /*10 for(i = 1; i <= n; i++)11 printf("%d\n", 2*i); //任务一1213 for(i = 2; i <= 2*n; i+=2) //任务二14 printf("%d\n", i);15 */1617 return0;18 }1 #include<stdio.h>2 int main(void)3 {4 double i;5 for(i =0;i !=10;i +=0.1)6 printf("%.1f\n",i);7 return0;8 }。

算法竞赛-入门经典-作者刘汝佳.doc第1部分语言篇第1章程序设计入门学习目标☑熟悉C语言程序的编译和运行☑学会编程计算并输出常见的算术表达式的结果☑掌握整数和浮点数的含义和输出方法☑掌握数学函数的使用方法☑初步了解变量的含义☑掌握整数和浮点数变量的声明方法☑掌握整数和浮点数变量的读入方法☑掌握变量交换的三变量法☑理解算法竞赛中的程序三步曲：输入、计算、输出☑记住算法竞赛的目标及其对程序的要求计算机速度快，很适合做计算和逻辑判断工作。

本章首先介绍顺序结构程序设计，其基本思路是：把需要计算机完成的工作分成若干个步骤，然后依次让计算机执行。

注意这里的“依次”二字——步骤之间是有先后顺序的。

这部分的重点在于计算。

接下来介绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。

本章内容不复杂，但是不容忽视。

注意：编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读本书，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。

千万不要图快——如果没有足够的时间用来实践，那么学得快，忘得也快。

（为帮助没有分值的朋友能下载，特此修改文档，以免上传不了）1.1 算术表达式计算机的“本职”工作是计算，因此下面先从算术运算入手，看看如何用计算机进行复杂的计算。

程序1-1 计算并输出1+2的值#include<stdio.h>int main(){printf("%d\n", 1+2);return 0;}算法竞赛入门经典这是一段简单的程序，用于计算1+2的值，并把结果输出到屏幕。

如果你不知道如何编译并运行这段程序，可阅读附录或向指导教师求助。

即使你不明白上述程序除了“1+2”之外的其他内容，仍然可以进行以下探索：试着把“1+2”改成其他东西，而不要去修改那些并不明白的代码——它们看上去工作情况良好。

下面让我们做4个实验：实验1：修改程序1-1，输出3-4的结果实验2：修改程序1-1，输出5×6的结果实验3：修改程序1-1，输出8÷4的结果实验4：修改程序1-1，输出8÷5的结果直接把“1+2”替换成“3+4”即可顺利解决实验1，但读者很快就会发现：无法在键盘上找到乘号和除号。

第2章循环结构程序设计【教学内容相关章节】2.1 for循环 2.2 循环结构程序设计2.3文件操作 2.4 小结与习题【教学目标】（1）掌握for循环的使用方法；（2）掌握while循环的使用方法；（3）学会使用计算器和累加器；（4）学会用输出中间结果的方法调试；（5）学会用计时函数测试程序效率；（6）学会用重定向的方式读写文件；（7）学会fopen的方式读写文件；（8）了解算法竞赛对文件读写方式和命名的严格性；（9）记住变量在赋值之前的值是不确定的；（10）学会使用条件编译指示构建本地运行环境。

【教学要求】掌握for循环的使用方法；掌握while循环的使用方法；掌握几个常用的文件操作库函数fopen、fclose、fprintf、fscanf等。

【教学内容提要】在有些程序中，需要反复执行某些语句。

将n条相同的语句简单地复制会使程序变得不合理的冗长，因此高级语言中提供了支持程序重复执行某一段程序的循环控制语句。

相关的语句有：for、while、do while、break、continue等。

既可以从文件中读取数据, 也可以向文件中写入数据。

读写文件之前，首先要打开文件。

读写文件结束后，要关闭文件。

C/C++提供了一系列库函数，声明于stdio.h中，用于进行文件操作。

这里介绍其中几个常用的文件操作库函数fopen、fclose、fprintf、fscanf等。

【教学重点、难点】教学重点：（1）掌握for循环的使用方法；（2）掌握while循环的使用方法；（3）掌握文件有关操作；（4）条件编译。

教学难点：（1）掌握for循环的使用方法；（2）掌握while循环的使用方法；【课时安排（共2学时）】2.1 for循环 2.2 循环结构程序设计2.3 文件操作 2.4 小结与习题2.1 for循环请用for循环实现输入正整数n，打印1,2,3,…,10，每个占用一行。

程序如下：程序2-1 输出1,2,3,…,n的值#include <stdio.h>int main(){int i, n;scanf("%d", &n);for(i = 1; i <= n; i++)printf("%d\n", i);return 0;}提示2-1：for循环的格式：for(初始化；条件；调整) 循环体；提示2-2：尽管for循环反复执行相同的语句，但这些语句每次的执行效果往往不同。

算法设计与分析基础课后练习答案习题1.14.设计一个计算的算法，n是任意正整数。

除了赋值和比较运算，该算法只能用到基本的四则运算操作。

算法求//输入：一个正整数n 2//输出：。

tep1:a=1；step2:若a*a<n 转step 3，否则输出a；step3:a=a+1转step 2；5. a．用欧几里德算法求gcd（31415，14142）。

. gcd(31415, 14142) = gcd(14142, 3131) = gcd(3131, 1618) =gcd(1618, 1513) = gcd(1513, 105) = gcd(1513, 105) = gcd(105, 43) =gcd(43, 19) = gcd(19, 5) = gcd(5, 4) = gcd(4, 1) = gcd(1, 0) = 1..有a可知计算gcd（31415，14142）欧几里德算法做了11次除法。

连续整数检测算法在14142每次迭代过程中或者做了一次除法，或者两次除法，因此这个算法做除法的次数鉴于1·14142 和2·14142之间，所以欧几里德算法比此算法快1·14142/11 ≈1300 与2·14142/11 ≈2600 倍之间。

6.证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:●如果d整除u和v, 那么d一定能整除u±v;●如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

故gcd(m,n)=gcd(n,r)7.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.8.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息f a≠0D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”lse //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5.描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法DectoBin(n)//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {in[i]=n%2;=(int)n/2;++;}while i!=0 do{rint Bin[i];--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗? 解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[] 4.(古老的七桥问题)第2章 习题2.17.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n )∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。

算法设计与分析基础第二版课后答案【篇一：算法设计与分析基础课后习题答案(中文版)】class=txt>习题1.15..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. hint:根据除法的定义不难证明:?如果 d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n 和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? hint:对于任何形如0=mgcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.2 1.(农夫过河)p—农夫w—狼 g—山羊 c—白菜 2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数) 算法quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法 //输入:实系数a,b,c//输出:实根或者无解信息if a≠0d←b*b-4*a*c if d0temp←2*ax1←(-b+sqrt(d))/temp x2←(-b-sqrt(d))/temp return x1,x2else if d=0 return –b/(2*a) else return “no real roots” else //a=0 if b≠0 return –c/b else //a=b=0if c=0 return “no real numbers”else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述解答： a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步第三步：将ki按照i从高到低的顺序输出b.伪代码算法 dectobin(n)//将十进制整数n转换为二进制整数的算法 //输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组bin[1...n]中 i=1 while n!=0 do { bin[i]=n%2; n=(int)n/2; i++; }while i!=0 do{ print bin[i]; i--; }9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进. 算法 mindistance(a[0..n-1]) //输入:数组a[0..n-1]//输出:the smallest distance d between two of its elements习题1.31. 考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表‖60,35,81,98,14,47‖排序b.该算法稳定吗?c.该算法在位吗? 解:a. 该算法对列表‖60,35,81,98,14,47‖排序的过程如下所示:b.该算法不稳定.比如对列表‖2,2*‖排序c.该算法不在位.额外空间for s and count[] 4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i个元素(1=i=n)b.删除有序数组的第i个元素(依然有序) hints:a. replace the ith element with the last element and decreasethe array size of 1b. replace the ith element with a special symbol that cannot be a value of the arr ay’s element(e.g., 0 for an array of positive numbers ) to mark the ith position is empty. (―lazy deletion‖)第2章习题2.1a. 这个断言是正确的。

第1部分语言篇第1章程序设计入门学习目标☑熟悉C语言程序的编译和运行☑学会编程计算并输出常见的算术表达式的结果☑掌握整数和浮点数的含义和输出方法☑掌握数学函数的使用方法☑初步了解变量的含义☑掌握整数和浮点数变量的声明方法☑掌握整数和浮点数变量的读入方法☑掌握变量交换的三变量法☑理解算法竞赛中的程序三步曲：输入、计算、输出☑记住算法竞赛的目标及其对程序的要求计算机速度快，很适合做计算和逻辑判断工作。

本章首先介绍顺序结构程序设计，其基本思路是：把需要计算机完成的工作分成若干个步骤，然后依次让计算机执行。

注意这里的“依次”二字——步骤之间是有先后顺序的。

这部分的重点在于计算。

接下来介绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。

本章内容不复杂，但是不容忽视。

注意：编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读本书，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。

千万不要图快——如果没有足够的时间用来实践，那么学得快，忘得也快。

1.1 算术表达式计算机的“本职”工作是计算，因此下面先从算术运算入手，看看如何用计算机进行复杂的计算。

程序1-1 计算并输出1+2的值#include<stdio.h>int main()算法竞赛入门经典·2·{printf("%d\n", 1+2);return 0;}这是一段简单的程序，用于计算1+2的值，并把结果输出到屏幕。

如果你不知道如何编译并运行这段程序，可阅读附录或向指导教师求助。

即使你不明白上述程序除了“1+2”之外的其他内容，仍然可以进行以下探索：试着把“1+2”改成其他东西，而不要去修改那些并不明白的代码——它们看上去工作情况良好。

下面让我们做4个实验：实验1：修改程序1-1，输出3-4的结果实验2：修改程序1-1，输出5×6的结果实验3：修改程序1-1，输出8÷4的结果实验4：修改程序1-1，输出8÷5的结果直接把“1+2”替换成“3+4”即可顺利解决实验1，但读者很快就会发现：无法在键盘上找到乘号和除号。