下载文档原格式
语言篇第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，但读者很快就会发现：无法在键盘上找到乘号和除号。
算法设计与分析基础课后练习答案习题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. 这个断言是正确的。
第一章习题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);return 0;}习题1-2#include <stdio.h>int main(){int f;double c;scanf("%d",&f);c=5*(f-32)/9;printf("%.3lf\n",c);return 0;习题1-3#include <stdio.h>int main(){int n;scanf("%d",&n);printf("%d\n",(n*(1+n))/2);return 0;}习题1-4#include <stdio.h>#include <math.h>#define pi 4.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));return 0;习题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);return 0;}习题1-6#include <stdio.h>int main(){int n;scanf("%d",&n);if(n%2==0){printf("YES\n");}else{printf("NO\n");}return 0;}习题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);}return 0;}习题1-8#include <stdio.h>#include <math.h>int main(){double n;scanf("%lf",&n);printf("%.2lf",fabs(n));return 0;}习题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");}return 0;}习题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");}return 0;}第二章习题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);return 0;}习题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);}}return 0;}习题2-3#include<stdio.h>int main(){int a,b,c,i,kase=1;while(~scanf("%d%d%d",&a,&b,&c)){for(i=10;i<=100;i++){if(i%3==a&&i%5==b&&i%7==c)printf("Case %d:%d\n",kase++,i);else if(i=100)printf("Case %d:No answer\n",kase++);} }return 0;}习题2-4#include<stdio.h>int main(){int n;while(~scanf("%d",&n)){for(int i=n;i>=0;i--){for(int j=n-i;j>0;j--)printf(" ");for(int j=2*i-1;j>0;j--)printf("#");printf("\n");}}}习题2-5文件题，南邮竞赛基本不涉及。
算法语言书后习题参考答案(第二版)第一章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.14.设计一个计算的算法,n是任意正整数。
除了赋值和比较运算,该算法只能用到基本的四则运算操作。
算法求 //输入:一个正整数n2//输出:。
step1:a1; step2:若a*an 转step 3,否则输出a; step3:aa+1转step 2;5. a.用欧几里德算法求gcd(31415,14142)。
b. 用欧几里德算法求gcd(31415,14142),比检查min{m,n}和gcd(m,n)间连续整数的算法快多少倍?请估算一下。
a. gcd31415, 14142 gcd14142, 3131 gcd3131, 1618 gcd1618, 1513 gcd1513, 105 gcd1513, 105 gcd105, 43 gcd43, 19 gcd19, 5 gcd5, 4 gcd4, 1 gcd1, 0 1.b.有a可知计算gcd(31415,14142)欧几里德算法做了11次除法。
连续整数检测算法在14142每次迭代过程中或者做了一次除法,或者两次除法,因此这个算法做除法的次数鉴于1?14142 和 2?14142之间,所以欧几里德算法比此算法快1?14142/11 ≈1300 与2?14142/11 ≈ 2600 倍之间。
6.证明等式gcdm,ngcdn,m mod n对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和rm mod nm-qn;显然,若d能整除n和r,也一定能整除mr+qn和n。
数对m,n和n,r具有相同的公约数的有限非空集,其中也包括了最大公约数。
故gcdm,ngcdn,r7.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0mn的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcdm,ngcdn,m并且这种交换处理只发生一次.8.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?1次b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?5次gcd5,8习题1.21.农夫过河P?农夫W?狼 G?山羊 C?白菜2.过桥问题1,2,5,10---分别代表4个人, f?手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c0的实根,写出上述算法的伪代码可以假设sqrtx是求平方根的函数算法Quadratica,b,c//求方程ax^2+bx+c0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D0temp←2*ax1←-b+sqrtD/tempx2←-b-sqrtD/tempreturn x1,x2else if D0 return ?b/2*ael se return “no real roots”else //a0if b≠0 return ?c/belse //ab0if c0 return “no real numbers”else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答:a.将十进制整数转换为二进制整数的算法输入:一个正整数n输出:正整数n相应的二进制数第一步:用n除以2,余数赋给Kii0,1,2,商赋给n第二步:如果n0,则到第三步,否则重复第一步第三步:将Ki按照i从高到低的顺序输出b.伪代码算法 DectoBinn//将十进制整数n转换为二进制整数的算法//输入:正整数n//输出:该正整数相应的二进制数,该数存放于数组Bin[1n]中i1while n!0 doBin[i]n%2;nintn/2;i++;while i!0 doprint Bin[i];i--;9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.算法略对这个算法做尽可能多的改进.算法 MinDistanceA[0..n-1]//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements 习题1.3考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.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. 如果tn∈Ogn,则gn∈Ωtnb.α0时,Θαgn Θgn解:a这个断言是正确的。
第一章习题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文件题，南邮竞赛基本不涉及。
2.5.1 最公平路从小到大枚举最小边，则最大边不减。
每次用O(m)的时间判连通即可。
的时间判连通即可。
2.5.3 最小圈初始时设置d[i,i]=无穷大，再套用floyd-warshall 算法即可。
算法即可。
2.5.6 路的最小公倍数单独考虑每个素数a ，那么一条路p 的s(p)值中a 的指数就是p 上的权中a 的最小指数，即路的“瓶颈”。
所有s(p)的最小公倍数就是所有路的瓶颈最大值。
的最小公倍数就是所有路的瓶颈最大值。
把把“求和”“求和”操作改成操作改成操作改成“取“取最小值”操作，然后套用dijkstra 即可。
即可。
2.5.7 货币兑换这道题目的本质是判断加权有向图是否有正圈，套用bellman-ford 算法即可。
如果迭代n-1次以后标号仍然会改变，则有正圈。
为了找到正圈，需要记录每个标号变化最后一次是由那个结点引起的。
由那个结点引起的。
2.5.8 速度限制如果每条道路都有限速标志，如果每条道路都有限速标志，那么此问题只是最普通的最短路径。
那么此问题只是最普通的最短路径。
那么此问题只是最普通的最短路径。
基于此，基于此，我们尝试给每条道路标上限速标志。
每条道路标上限速标志。
无标志路径的速度由上一条道路的速度决定；如果上一条道路亦无标志，那么它们的速度又由上两条道路的速度决定；如果上两条道路亦无标志，那么它们的速度又由上三条道路的速度决定……如此向前追溯，直至遇到有标志路径或者起点。
直至遇到有标志路径或者起点。
所以逆向思维，所以逆向思维，我们从每一条有标志路径或者起点出发，在它们的后面接上所有单独的或者一串连续的无标志路径，使之成为一条有限速标志的新路。
之成为一条有限速标志的新路。
这样，此问题就转化为普通最短路径。
这样，此问题就转化为普通最短路径。
这样，此问题就转化为普通最短路径。
当然，如何求出所有当然，如何求出所有单独的或者一串连续的无标志路径可以用O(n 3)的Floyd 算法。
算法。
//ACM/ICPC Seoul 2005,UVa15851 #include <iostream>2 #include <cstring>3 using namespace std;4 int main (void )5 {6 int a;7 cin >>a;8 while (a) 9 {1011 string s; 12 cin >>s;13 int n =s.size (); 14 int num =0,ans =0;15 for (int i =0;i <n;i++)16 { 17 if (s[i] =='O')18 num++; 19 else20 {21 for (int j =1;j <=num;j++) 22 ans +=j;23 num =0; 24 }25 }26 for (int j =1;j <=num;j++) 27 ans +=j;28 cout <<ans <<endl; 29 a--;30 }31 return 0; 32 }3-1 Score2017年10月1日15:00// ACM/ICPC Seoul 2007,UVa15861 #include <iostream>2 #include <cstring>3 #include <cctype>4 #include <iomanip>5 using namespace std;6 const double Mass[] = {0,0,12.01,0,0,0,0,1.008,0,0,0,0,0,14.01,16.00};7 int main (void )8 {9 int n; 10 cin >>n;11 while (n) 12 { 13 string s; 14 double ans =0; 15 cin >>s; 16 for (int i =0;i <s.size ();i++)17 { 18 int num; 19 if (isupper (s[i])) 20 { 21 if (isdigit (s[i+1])) 22 {23 num =s[i+1] -'0'; 24 for (int j =i+2;j <s.size () &&isdigit (s[j]);j++) 25 num =num*10+s[j] -'0'; 26 ans +=num*Mass[s[i] -'A']; 27 } 28 else29 ans +=Mass[s[i] -'A']; 30 } 31 } 32 cout <<setiosflags (ios::fixed) <<setprecision (3) <<ans <<endl; 33 n--; 34 }35 return 0; 36 }3-2 Molar Mass2017年10月1日15:04// ACM/ICPC Danang 2007,UVa12251 #include <iostream>2 #include <cstring>3 using namespace std;4 int main (void )5 {6 int num;7 cin >>num;8 while (num) 9 {10 int s[10];11 memset (s,0,sizeof (s)); 12 int n,LS;13 cin >>n; 14 for (int i =1;i <=n;i++)15 {16 int LS2 =i; 17 while (LS2)18 { 19 LS =LS2%10;20 s[LS]++;21 LS2 /=10; 22 }23 } 24 for (int i =0;i <9;i++)25 cout <<s[i] <<" ";26 cout <<s[9] <<endl; 27 num--;28 } 29 return 0;30 }3-3 Digit Counting2017年10月1日15:06// UVa4551 #include <iostream>2 #include <cstring>3 using namespace std;4 int next1[80];5 void GetNext (int n,const char s[]){ //获取Next 数组，预处理6 int i =0,k = -1; //表示字符长度（位置）7 memset (next1,0,sizeof (next1));8 next1[0] = -1; //字符串的前缀和后缀最大公共长度 9 while (i <n) //n 为主串长度10 {11 if (k == -1||s[i] ==s[k])12 {13 next1[i+1] =k+1; 14 i++;15 k++;16 }17 else18 k =next1[k]; 19 }20 }21 int main (void )22 {23 int num; 24 cin >>num;25 while (num)26 {27 bool out =true ; 28 char s[80];29 cin >>s;30 int n =strlen (s);31 GetNext (n,s);3233 //GetNext 成功获取34 /*35 for(int i = 0;i <= n;i++)36 cout << next1[i] << " ";37 cout << endl;38 */ 39 if (n % (n -next1[n]) ==0&&next1[n] !=0)40 cout <<n -next1[n] <<endl;41 else42 cout <<n <<endl;43 if (num >1) 44 cout <<endl;45 num--;46 }47 return 0;3-4 Periodic Strings2017年10月1日15:0747 return0;48 }// ACM/ICPC World Finals 1993,UVa2271 #include <iostream>2 #include <cstring>3 #include <cstdio>4 #define maxn5 5 using namespace std;6 bool check (int x,int y,int n){7 switch (n)8 { 9 case 1: 10 if (x ==0) 11 return false ; 12 else 13 return true ; 14 break ;15 case 2: 16 if (x ==4) 17 return false ; 18 else 19 return true ; 20 break ; 21 case 3: 22 if (y ==4)23 return false ; 24 else 25 return true ; 26 break ; 27 case 4: 28 if (y ==0) 29 return false ; 30 else31 return true ; 32 break ; 33 } 34 } 35 int main (void ) 36 { 37 int kase =0; 38 while (1)39 { 40 char s[maxn][maxn]; 41 42 for (int i =0;i <5;i++) 43 for (int j =0;j <5;j++) 44 { 45 s[i][j] =getchar ();46 if (s[0][0] =='Z') 47 return 0; 48 if (s[i][j] =='\n') 49 j--; 50 } 51 523-5 Puzzle2017年10月1日15:085253 //成功读入数组54 /*55 cout << endl;56 for(int i = 0;i < 5;i++)57 {58 for(int j = 0;j < 5;j++)59 cout << s[i][j];60 cout << endl;61 }62 */63 int x,y;64 for(int i =0;i <5;i++)65 for(int j =0;j <5;j++)66 if(s[i][j] ==' ')67 {68 x =i;69 y =j;70 }71 // cout << "x: " << x << "y: " << y << endl;72 bool flag =true;73 getchar(); //吃换行符74 while(1)75 {76 char ch;77 if((ch =getchar()) !='\n')78 {79 // cout << "ch: " << ch << endl;80 if(ch =='0')81 break;82 else if(ch =='A'&&check(x,y,1))83 {84 s[x][y] =s[x-1][y];85 s[x-1][y] =' ';86 x--;87 }88 else if(ch =='B'&&check(x,y,2))89 {90 s[x][y] =s[x+1][y];91 s[x+1][y] =' ';92 x++;93 }94 else if(ch =='R'&&check(x,y,3))95 {96 s[x][y] =s[x][y+1];97 s[x][y+1] =' ';98 y++;99 }100 else if(ch =='L'&&check(x,y,4))101 {102 s[x][y] =s[x][y-1];103 s[x][y-1] =' ';104 y--;105 }106 else107 flag =false;107 flag =false;108 }109 }110 //cout << endl;111 if(kase) //输出格式注意！ 112 cout <<endl;113 cout <<"Puzzle #"<< ++kase <<":"<<endl;114115 if(flag)116 {117118 bool first =true;119 for(int i =0;i <5;i++)120 {121 for(int j =0;j <5;j++)122 {123 if(first)124 {125 cout <<s[i][j];126 first =0;127 }128 else129 cout <<" "<<s[i][j];130 }131 first =true;132 cout <<endl;133 }134 }135 else136 cout <<"This puzzle has no final configuration."<<endl;137138 }139 return0;140 }// ACM/ICPC World Finals 1994,UVa2321 #include <iostream>2 #include <cstring>3 #include <cstdio>4 #define maxn 15 5 char s[maxn][maxn];6 int start_num[maxn][maxn];7 using namespace std;8 int Across (int i,int j,int c){9 if (start_num[i][j] !=0) 10 { 11 if (start_num[i][j] <10) //'%3d' 12 cout <<" "<<start_num[i][j] <<"."; 13 else 14 cout <<" "<<start_num[i][j] <<".";15 for (j;j <c;j++) 16 { 17 if (s[i][j] =='*')18 { 19 cout <<endl; 20 return j;21 } 22 else 23 cout <<s[i][j];24 } 25 cout <<endl; 26 return j;27 } 28 return j; 29 }30 31 int Down (int i,int j,int r){32 if (start_num[i][j] !=0) 33 { 34 if (start_num[i][j] <10)35 cout <<" "<<start_num[i][j] <<"."; 36 else 37 cout <<" "<<start_num[i][j] <<".";38 for (i;i <r;i++) 39 { 40 if (s[i][j] =='*')41 { 42 cout <<endl; 43 return 0;44 } 45 else 46 {47 cout <<s[i][j];3-6 Crossword Answers2017年10月1日15:0947 cout <<s[i][j];48 start_num[i][j] =0;49 }50 }51 cout <<endl;52 }53 }5455 int main(void)56 {57 int kase =0;58 while(1)59 {60 int r,c;61 cin >>r;62 if(r ==0)63 return0;64 cin >>c;65 for(int i =0;i <r;i++)66 scanf("%s", &s[i]);6768 //Read in69 /*70 for(int i = 0;i < r;i++)71 {72 for(int j = 0;j < c;j++)73 cout << s[i][j];74 cout << endl;75 }76 */7778 int num =0;79 memset(start_num,0,sizeof(start_num));8081 //the first number82 for(int i =0;i <r;i++)83 for(int j =0;j <c;j++)84 {85 if(s[i][j] !='*')86 {87 if(i ==0||j ==0)88 start_num[i][j] = ++num;89 else if(s[i][j-1] =='*'||s[i-1][j] =='*')90 start_num[i][j] = ++num;91 }92 }9394 //check the first number95 /*96 for(int i = 0;i < r;i++)97 {98 for(int j = 0;j < c;j++)99 cout << start_num[i][j];99 cout << start_num[i][j];100 cout << endl;101 }102 */103 if(kase)104 cout <<endl;105 cout <<"puzzle #"<< ++kase <<":"<<endl; 106107 cout <<"Across"<<endl;108 for(int i =0;i <r;i++)109 for(int j =0;j <c;j++)110 j =Across(i,j,c);111112 cout <<"Down"<<endl;113 for(int i =0;i <r;i++)114 for(int j =0;j <c;j++)115 Down(i,j,r);116117 }118 return0;119 }// ACM/ICPC Seoul 2006,UVa13681 #include <iostream>2 #include <cstdio>3 #include <cstring>4 using namespace std;5 int main (void )6 {7 int num;8 int Hamans =0;9 cin >>num;10 while (num) 11 { 12 int m,n; 13 cin >>m >>n;14 char s[m][n]; 15 for (int i =0;i <m;i++) 16 cin >>s[i];1718 //数组正确读入19 /* 20 for(int i = 0;i < m;i++) 21 { 22 for(int j = 0;j < n;j++)23 cout << s[i][j]; 24 cout << endl; 25 } 26 */27 28 int LS =0; 29 int Repeat[4]; 30 char ans[n];31 for (int j =0;j <n;j++) 32 { 33 memset (Repeat,0,sizeof (Repeat));34 for (int i =0;i <m;i++) 35 { 36 if (s[i][j]=='A')Repeat[0]++; 37 else if (s[i][j]=='C')Repeat[1]++;38 else if (s[i][j]=='G')Repeat[2]++; 39 else Repeat[3]++;40 //思路：检查Hamming 距离最小的字符，若有相同的情况则再判断字典序 41 } 4243 //测试Repeat 的数据是否正确44 /*45 for(int LS = 0;LS < 4;LS++) 46 cout << Repeat[LS] << " "; 47 cout << endl; 48 */49 int PD =0; 50 int LSans =0;3-7 DNA Consensus String2017年10月1日15:1050 int LSans =0;51 for(int LS =0;LS <4;LS++)52 if(PD <Repeat[LS])53 {54 PD =Repeat[LS];55 LSans =LS;56 }5758 Hamans += (m -Repeat[LSans]); //求Hamming距离的总和5960 //测试当前最大的数组下标是否正确61 /*62 cout << "LSans: " << LSans << endl;63 */64 switch(LSans)65 {66 case0:67 ans[j] ='A';68 break;69 case1:70 ans[j] ='C';71 break;72 case2:73 ans[j] ='G';74 break;75 case3:76 ans[j] ='T';77 break;78 }79 }8081 for(int j =0;j <n;j++)82 cout <<ans[j];83 cout <<endl;84 cout <<Hamans <<endl;85 Hamans =0; //清零Hamming距离以便下一次计算86 num--;87 }88 return0;89 }// ACM/ICPC World Finals 1990,UVa2021 #include <iostream>2 #include <cstring>3 #include <cstdio>4 #define maxn 50000005 using namespace std;6 int s[maxn],next1[maxn],YS[maxn],repeat[maxn]; 78 void GetNext (const int n){ 9 memset (next1,0,sizeof (next1)); 10 next1[0] = -1; 11 int i =0,k = -1;12 while (i <n) 13 { 14 if (k == -1||repeat[i] ==repeat[k]) 15 { 16 next1[i+1] =k+1;17 i++; 18 k++; 19 } 20 else21 k =next1[k]; 22 } 23 } 2425 void Next_Loop (int n,int &loop){ 26 int j; 27 bool flag1 =true ; 28 for (int i =0;i <n;i++) 29 {30 if (next1[i] == -1||next1[i] ==0) 31 continue ; 32 j =i -next1[i]; 33 if (i %j ==0)34 { 35 loop =i/2; 36 if (YS[n] ==YS[n+loop]) 37 break ;38 } 39 } 40 } 41 int main (void ) 42 {43 int a,b; 44 int YS_1 =0; 45 int loop =0; 46 while (scanf ("%d", &a) !=EOF)47 { 48 scanf ("%d", &b); 49 int a1 =a; 50 bool flag =true ;51 52 memset (s,0,sizeof (s)); 53 memset (YS,0,sizeof (YS)); 5455 //模拟四则运算,计算50000位，maxn 较大56 for (int i =0;i <50000;i++) 57 { 58 if (a >=b)59 s[i] =a/b; 60 if (a <b) 61 s[i] =0;3-8 Repeating Decimals2017年10月1日15:1261 s[i] =0;62 a = (a -s[i]*b)*10;63 YS[i] =a;64 if(a ==0)65 {66 flag =false;67 break;68 }69 }70 if(flag)71 {7273 //模拟四则运算测试输出74 /*75 cout << s[0] << ".";76 for(int i = 1;i < b*3;i++)77 cout << s[i];78 cout << endl;79 */8081 //从后面开始复制以避开干扰数8283 memset(repeat,0,sizeof(repeat));84 for(int i =0;i <3*b+1;i++)85 repeat[i] =s[i+b+1];8687 GetNext(3*b+1);88 Next_Loop(3*b+1,loop);8990 //检查next数组91 /*92 cout << "Next: " << endl;93 for(int i = 0; i < 50; i++)94 cout << next1[i];95 cout << endl;96 */9798 //检查周期99 // cout << "loop: " << loop << endl;100101 //用于排除前方干扰数的影响（使用余数）102 bool flag2 =true;103104 for(int i =0;i <maxn;i++)105 {106 for(int j =0;j <loop;j++)107 if(YS[i] !=YS[i+loop])108 flag2 =false;109 if(flag2)110 {111 i++;112 int num =0;113 cout <<a1 <<"/"<<b <<" = ";114 cout <<s[0] <<".";115 for(int j =1;j <i;j++)116 {117 cout <<s[j];118 num++;119 }120 cout <<"(";121 if(i ==0)i++;122 if(loop >50)123 {124 for(int j =i;j <50-num+i;j++)124 for(int j =i;j <50-num+i;j++)125 cout <<s[j];126 cout <<"...";127 }128 else129 for(int j =i;j <loop+i;j++)130 cout <<s[j];131 cout <<")"<<endl;132 cout <<" "<<loop <<" = number of digits in repeating cycle"<<endl; 133 break;134 }135 flag2 =true;136 }137 }138 //整除的情况139 else140 {141 cout <<a1 <<"/"<<b <<" = ";142 cout <<s[0] <<".";143 for(int i =1;i <maxn;i++)144 {145 if(YS[i-1] ==0)146 break;147 cout <<s[i];148 }149 cout <<"(0)"<<endl;150 cout <<" "<<"1 = number of digits in repeating cycle"<<endl;151 }152 cout <<endl;153 }154 return0;155 }// UVa 103401 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #define maxn 100000000 5 char k[maxn]; 6 char s[maxn]; 7 using namespace std; 8 int main (void ) 9 { 10 while (scanf ("%s", &k) !=EOF) 11 { 12 13 scanf ("%s", &s); 14 int n1 =strlen (k); 15 int n2 =strlen (s); 16 int num =0; 17 int wz =0; 18 for (int j =0;j <n1;j++) 19 for (int i =wz;i <n2;i++) 20 if (k[j] ==s[i]) 21 { 22 num++; 23 wz =i+1; 24 break ; 25 } 26 if (num ==n1)27 cout <<"Yes"<<endl; 28 else 29 cout <<"No"<<endl; 30 } 31 return 0; 32 }1 #include <iostream>2 #include <cstdio>3 #include <cstring>4 #include <algorithm>5 #define maxn 1000006 using namespace std;7 char s1[maxn],s2[maxn];8 int value2[2][maxn];9 int main (void )10 { 11 while (~scanf ("%s%s", &s1, &s2)) 12 { 13 memset (value2,0,sizeof (value2)); 14 int i,j; 15 int tem =1; 16 for (i =0;s1[i];i++) 17 { 18 for (j =0;s2[j];j++) 19 { 20 if (s1[i] ==s2[j]) 21 value2[tem][j] =value2[1-tem][j-1]+1; 22 else23 value2[tem][j] =max (value2[1-tem][j],value2[tem][j-1]); //状态转移方程 24 }25 tem =1-tem; //空间优化 26 } 27 if (value2[1-tem][j-1] ==strlen (s1)) 28 cout <<"Yes"<<endl; 29 else3-9 All in All2017年10月1日15:1429 else30 cout <<"No"<<endl;31 }32 return0;33 }// ACM/ICPC NEERC 2004,UVa15871 #include <iostream>2 #include <cstring>3 #include <algorithm>4 #include <cstdio>5 using namespace std;6 struct box7 {8 int x;9 int y;10 }s[6]; 11 bool cmp (const box &x,const box &y) 12 {13 return x.x*x.y >y.x*y.y; 14 } 1516 int main (void ) 17 { 18 memset (s,0,sizeof (s)); 1920 //读入长宽数据21 while (scanf ("%d %d", &s[0].x, &s[0].y) !=EOF) 22 {23 for (int i =1;i <6;i++) 24 cin >>s[i].x >>s[i].y; 2526 //长宽定义统一27 for (int i =0;i <6;i++) 28 if (s[i].x <s[i].y)29 swap (s[i].x,s[i].y); 30 31 bool flag =true ; 3233 //面积排序34 sort (s,s+6,cmp); 3536 //排序函数正常37 /* 38 cout << endl;39 for(int i = 0;i < 6;i++) 40 cout << s[i].x << " " << s[i].y << endl; 41 */4243 //判断矩形各面是否合法，思路来源CSDN: codekun44 //巧妙之处：排序后memcmp 只存在0或大于0的返回值！45 if (memcmp (s,s+1,sizeof (box)) ||memcmp (s+2,s+3,sizeof (box)) ||memcmp (s+4,s+5,sizeof (box))) 46 flag =false ; 4748 //判断矩形各长宽高是否合法49 if (s[0].x !=s[2].x ||s[0].y !=s[4].x ||s[2].y !=s[4].y) 50 flag =false ; 5152 //输出53 if (flag) 54 cout <<"POSSIBLE"<<endl;55 else 56 cout <<"IMPOSSIBLE"<<endl; 57 }58 return 0; 59 }3-10 Box2017年10月1日15:14// ACM/ICPC NEERC 2006,UVa15881 #include <iostream>2 #include <cstring>3 #include <cstdio>4 #include <cmath>5 using namespace std;6 int main (void )7 {8 string s1,s2;9 while (cin >>s1 >>s2) 10 {11 int ans =s1.size () +s2.size (); 12 bool flag;13 for (int i =0;i <s1.size ();i++)14 { 15 flag =true ;16 int k =i; //起点 17 for (int j =0;j <s2.size ();j++)18 {19 if (k <s1.size () &&s1[k++] +s2[j] -'0'-'0'>3) 20 {21 flag =false ;22 break ; 23 }24 } 25 if (flag) 26 {27 ans =max (s1.size (),s2.size ()+i);28 break ;29 }30 } 31 for (int i =0;i <s2.size ();i++)32 {33 flag =true ;34 int k =i; //起点 35 for (int j =0;j <s1.size ();j++)36 {37 if (k <s2.size () &&s2[k++] +s1[j] -'0'-'0'>3) 38 { 39 flag =false ;40 break ;41 } 42 }43 if (flag) 44 { 45 int temp =max (s2.size (),s1.size ()+i);3-11 Kickdown2017年10月1日15:1545 int temp =max(s2.size(),s1.size()+i);46 ans =min(ans,temp);47 break;48 }49 }50 cout <<ans <<endl;51 }52 return0;53 }// UVa118091 #include <iostream>2 #include <cstring>3 #include <cstdio>4 #include <sstream>5 #include <cmath>6 using namespace std;7 long long table[15][35];8 double table2[15][35];9 template <class Type>10 Type stringToNum (const string&str){ 11 istringstream iss (str);12 Type num;13 iss >>num;14 return num;15 }16 void make_tab (){ 17 for (int i =0;i <10;i++)18 for (int j =1;j <=30;j++)19 {20 double expow =pow (2,j) -1; //mantissa and exponent21 double mansa =1-pow (2, -1-i); 22 double t =log10(mansa) +expow*log10(2);23 table[i][j] =t;table2[i][j] =pow (10,t-table[i][j]); //使用对数来缩小规模24 } //若试图使用结果直接计算，会在约2^991处（不一定相同）卡死 25 } 26 int main (void )27 {28 string s,num;29 make_tab ();30 while (cin >>s &&s !="0e0") 31 {3233 num =s.substr (0,s.find ('e'));34 s =s.substr (s.find ('e')+1,s.size ());35 double A =stringToNum<double >(num);36 int B =stringToNum<int >(s); 37 while (A <1){A *=10;B -=1;}38 for (int i =0;i <10;i++)39 for (int j =1;j <=30;j++)40 {41 if (B ==table[i][j] && (fabs (A -table2[i][j]) <1e-4||fabs (A /10-table2[i][j]) <1e-4)) 42 {43 cout <<i <<" "<<j <<endl;44 break ;45 }46 } 47 }48 return 0;49 }50 //CSDN:crazysillynerd 的思路3-12 Floating-Point Numbers2017年10月1日15:16。
