算法竞赛入门经典第一章【小结与习题】

曾经终败给现在 2022-09-18 03:50 178阅读 0赞

**数据类型：**

6个1的平方用int数据类型存已经溢出了，并且用\-Wall还给出警告：test.c:7: warning: integer overflow in expression。

6个1的平方用double没问题，修改程序时，只需要改111111\*111111为111111.0\*111111就能正确运行了。

sqrt(-10) 没有报错，输出是nan；而用"%d"来输出，警告类型不匹配，但能输出10位数，并且每次输出不同。猜想是溢出，换成“%lld”输出，结果前面高6位不变，后面似乎在一个范围内来回变化，但未发现不循环。这个有点意思。。。循环输出1000次，发现第一次与之后的不同，第二次到1000次都相同。再执行也是这个效果，每次执行的结果不一样。

浮点数 1.0/0.0 结果是inf，0.0/0.0结果是nan，1/0报错

**scanf()：**

可以滤空（空格 tab 回车符）

**printf()：**

输出%d用"%%d"，输出“\\n”用"\\\\n"，以此类推

**实践能力：**

问题1：int型浮点数的最小值和最大值是多少？

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

2.  **int**

3.  main(**void**)

4.  \{

5.      **int** i;

7.      **for** (i = 1; i > 0; i++) NULL;

8.      printf("%d %d\\n", i, i-1);

9.      **return** 0;

10. \}

这个方法最容易想到，但比较慢。原理就是一旦溢出变成负数，那么停止循环，i++也不会执行了，然后输出这个负数和比这个最小值“还小”的值，其实就是刚才溢出前的最大值

问题2：double型浮点数能精确到多少位小数？或者，这个问题本身值得商权？

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

3.  **int**

4.  main(**void**)

5.  \{

6.      printf("%f", 10.0/3.0);

7.      **return** 0;

8.  \}

输出默认是小数点后面有6位，改成"%.2lf"重新编译运行后保留2位，改成100呢？

输出：3.3333333333333334813630699500208720564842224121093750000000000000000000000000000000000000000000000000

那么是精确到15位？把10.0/3.0改成1.0/0.3呢？结果确实一样，改成20.0/3.0呢？

输出：6.6666666666666669627261399000417441129684448242187500000000000000000000000000000000000000000000000000

也是精确到15位。。。

问题3：double型浮点数最大正数值和最小正数值分别是多少？（不必特别精确）

这里有一个精度的概念和溢出的概念，注意区分？

此题留白。

问题4：

a&&b||c 等效于 (a&&b)||c

单独测试更快：先测试a&&b||c；a b c分别赋值0 1 1如果是(a&&b)||c结果会是1，如果是a&&(b||c)结果会是0

结论就是&&优先级高于||0

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

3.  **int**

4.  main(**void**)

5.  \{

6.      **int** a, b, c;

7.      a = 0, b = 1, c = 1;

8.      printf("%d\\n", a&&b||c);

9.      **return** 0;

10. \}

\-Wall真强大，还会给出警告：warning: suggest parentheses around && within ||

再测试!a&&b，设置a b均为0，那么如果是!(a&&b)结果是1，如果是(!a)&&b结果是0；

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

3.  **int**

4.  main(**void**)

5.  \{

6.      **int** a, b;

8.      a = b = 0;

9.      printf("%d\\n", !a&&b);

10.     **return** 0;

11. \}

结果证明!优先级大于&&优先级。即!a&&b||c等效于((!a)&&b) || c

值得一提的是\-Wall编译上面的程序时并没有给出警告，也就是说一般认为!比&&和||优先级高是非常明显的。

问题5：

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

3.  **int**

4.  main(**void**)

5.  \{

6.      **int** a, b, x, y;

8.      **if** (a)

9.          **if** (b)

10.             x++;

11.         **else**

12.             y++;

13.     **return** 0;

14. \}

虽然缩进使得逻辑关系比较明朗，但是还是容易给初学者带来困惑，用-Wall编译还给出了警告：warning: suggest explicit braces toavoid ambiguous 'else'

改成：

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

3.  **int**

4.  main(**void**)

5.  \{

6.      **int** a, b, x, y;

8.      **if** (a) \{

9.          **if** (b)

10.             x++;

11.         **else**

12.             y++;

13.     \}

14.     **return** 0;

15. \}

警告便消失了。

【上机练习】

习题1-1 平均数(average)

输出3个整数，输出它们的平均值，保留3位小数。

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

3.  **int**

4.  main(**void**)

5.  \{

6.      **int** a, b, c;

8.      scanf("%d%d%d", &a, &b, &c);

9.      printf("%.3f\\n", (a+b+c) / 3.0);

10.     **return** 0;

11. \}

注意：保留三位小数，用浮点数格式输出，(a+b+c)/3会是整型的，讲分子分母其中一个变成浮点数类型就可以了。或者使用强制类型转换，在进行运算前会转换了该类型。如：(double)(a+b+c)/ 3;

习题1-2 温度(temperature)

输入华氏温度f，输出对应的摄氏温度c，保留3位小数。提示：c =  5(f-32)/9。

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

3.  **int**

4.  main(**void**)

5.  \{

6.      **int** f;

8.      scanf("%d", &f);

9.      printf("%.3f\\n", 5.0\*(f-32.0)/9.0);

10.     **return** 0;

11. \}

这里当然也可以用强制类型转换：printf("%.3f\\n",(double)5\*(f-32)/9);我想这里应当是把5转为浮点数，因为有了一个浮点数，其他的也就跟着变成了浮点数，最后进行浮点数的四则运算。而不是做完整型的四则运算后再转换为浮点数，这样已经丢失了“精度”。

习题1-3 连续和(sum)

输入正整数n，输出1+2+...+n的值。提示：目标是解决问题，而不是练习编程。

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

3.  **int**

4.  main(**void**)

5.  \{

6.      **int** n;

8.      scanf("%d", &n);

9.      printf("%d\\n", (n\*(n+1)) / 2);

10.     **return** 0;

11. \}

根据正写和反写序列可以得到上述公式，因为此处还没学for循环，直接用公式即可。

习题1-4 正弦和余弦(sincos)

输入正整数n(n < 360)，输出n度的正弦、余弦函数值。提示：使用数学函数。

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

2.  \#include <math.h>

4.  **int**

5.  main(**void**)

6.  \{

7.      **int** n;

8.      **double** x;

9.      **const double** PI = 4.0 \* atan(1.0);

10.

11.     scanf("%d", &n);

12.     x = (n/180.0)\*PI;

13.     printf("%.3f\\n%.3f\\n", sin(x), cos(x));

14.     **return** 0;

15. \}

我们知道，sincos函数接受的参数单元是弧度，输入度就需要现转为弧度，我们知道或记住180度==PI即，这样根据作比就可以转换了。这里我保留3位小数。

习题1-5 距离(distance)

输入4个浮点数x1, y1, x2, y2, 输出平面坐标系中(x1, y1)到(x2, y2)的距离。

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

2.  \#include <math.h>

4.  **int**

5.  main(**void**)

6.  \{

7.      **double** x1, y1, x2, y2;

8.      **double** dist;

10.     scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);

11.     dist = sqrt((x2-x1)\*(x2-x1) + (y2-y1)\*(y2-y1));

12.     printf("%.3f\\n", dist);

13.     **return** 0;

14. \}

习题1-6 偶数(odd)

输入一个整数，判断它是否为偶数，如果是，则输出"yes"，否则输出"no"。提示：可以用多种方法判断。

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

3.  **int**

4.  main(**void**)

5.  \{

6.      **int** x;

8.      scanf("%d", &x);

9.      printf(0 == x%2 ? "yes\\n" : "no\\n");

10.     **return** 0;

11. \}

注意：这里用了一个三目运算符，它是C语言中最常用的运算符了。作用不难从程序中看出。

习题1-7 打折(discount)

一件衣服95元，若消费满300元，可打八五折。输入购买衣服件数，输出需要支付的金额（单位：元），保留两位小数。

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

3.  **int**

4.  main(**void**)

5.  \{

6.      **int** num;

8.      scanf("%d", &num);

9.      printf("%.2f\\n", num > 4 ? 95\*num\*0.85 : 95.0\*num);

10.     **return** 0;

11. \}

习题1-8 绝对值(abs)

输入一个浮点数，输出它的绝对值，保留两位小数。

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

2.  \#include <stdlib.h>//can call abs();

3.  \#include <math.h>//can call fabs();

4.  \#define Abs(x) ( (x) > 0 ? (x) : (-(x))  )//define Abs();

6.  //a function for abs

7.  **double**

8.  Fabs(**double** x)

9.  \{

10.     **return** x > 0 ? x : -x;

11. \}

12.

13. **int**

14. main(**void**)

15. \{

16.     **double** x;

17.

18.     scanf("%lf", &x);

19.     printf("%.2f\\n", (**double**)abs(x));//wrong answer

20.     printf("%.2f\\n", fabs(x));

21.     printf("%.2f\\n", Abs(x));

22.     printf("%.2f\\n", Fabs(x));

23.     **return** 0;

24. \}

注意：这里用了四个abs函数，abs()在stdlib.h中定义，只能用于整型求绝对值。fabs函数本身适用于浮点数。宏定义的根据类型自适应，Fabs函数也要事先确定类型。如此看来还是宏定义的比较好用。

习题1-9 三角形(triangle)

输入三角形三边长度值(均为正整数)，判断它是否能为直角三角形的三个边长。如果可以，则输出"yes"，如果不能，则输出“no”。如果根本无法构成三角形，则输出"not atriangle"。

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

3.  **int**

4.  main(**void**)

5.  \{

6.      **int** a, b, c;

7.      **int** tmp;

9.      scanf("%d%d%d", &a, &b, &c);

10.

11.     **if** (a < b) \{

12.         tmp = a;

13.         a = b;

14.         b = tmp;

15.     \}

16.     **if** (a < c) \{

17.         tmp = a;

18.         a = c;

19.         c = tmp;

20.     \}

21.     **if** (b < c) \{

22.         tmp = b;

23.         b = c;

24.         c = tmp;

25.     \}

26.

27.     **if** (b\*b+c\*c == a\*a)

28.         printf("yes\\n");

29.     **else**

30.         printf(a >= b+c ? "not a triangle\\n" : "no\\n");

31.

32.     **return** 0;

33. \}

用前面介绍的方法将三个正整数排个序（这里是非升序），然后方便进行判断，逻辑层次是，是直角三角形，不是直接三角形又包括：构不成三角形和其他情况。

习题1-10 年份(year)

输入年份，判断是否为闰年。如果是，则输出"yes"，否则输出"no"。提示：简单地判断除以4的余数是不够的。

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include <stdio.h>

3.  **int**

4.  main(**void**)

5.  \{

6.      **int** year;

8.      scanf("%d", &year);

9.      **if** ( year%400 == 0 || (year%4 == 0 && year%100 != 0) )

10.         printf("yes\\n");

11.     **else**

12.         printf("no\\n");

13.     **return** 0;

14. \}

[view plain]: http://blog.csdn.net/architect19/article/details/8551145

算法竞赛入门经典第一章【小结与习题】

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关算法竞赛入门经典+挑战编程+USACO

相关算法竞赛入门经典第二章【小结与习题】

相关算法竞赛入门经典第一章【小结与习题】

相关《算法竞赛入门经典》——刘汝佳

相关《算法竞赛入门经典》之开发环境与方法小收获

相关算法竞赛入门经典笔记02

相关算法算法竞赛入门经典第二版 2-6 排列

相关算法竞赛入门经典WERTYU

相关《竞赛入门经典》1-5章语言篇总结（一轮）

相关【算法竞赛入门经典—训练指南】学习笔记（含例题代码与思路）第一章：算法设计基础...