算法竞赛入门经典第一章小结与练习

之前没怎么系统地学习过算法，在网上看到《算法竞赛入门经典》这本书还不错，下决心跟着做一做练一练。

第一章

【学习目标】

1.熟练C语言程序的编译和运行

  流程：C源程序头文件 —> 预编译处理(cpp) —> 编译程序本身 —> 优化程序 —> 汇编程序 —> 链接程序 —> 可执行文件

  具体原理以后再做研究吧。。。

2.学会编程计算并输出常见的算法表达式的结果

  • 输出时%d,%ld,%f,%lf,%5.2f,包括数据强制转换。
  • include <math.h>中常用数学函数包括：
    • 绝对值double fabs(double);
    • 三角函数double sin(double);
    • 反三角double asin(double);
    • 开方double sqrt(double);
    • 求幂double pow(double a, double x)means a^x;
    • 求对数 （e为底）double log(double);（10为底）double log10(double)
    • 取上整double ceil(double);取下整double floor(double); 这里上和下可以理解为取大和取小，比如-1.44，floor后是-2.0，ceil后是-1.0
    • 注意abs()定义在<stdlib.h>中，也可宏定义：“abs(x) : ((x > 0) ? (x) : (-(x)))”。

3.掌握整数和浮点数的含义和输出方法

  int、float和double，基本上可以一直使用double吧。scanf()会区分%lf和%f。

4.掌握数学函数的使用方法

const double pi = 4.0 * atan(1.0);

5.初步了解变量的含义

6.掌握整数和浮点数变量的声明方法

int i; float a; double s;

7.掌握整数和浮点数变量的读入方法

scanf("%d %f", &i, &a);

8.掌握变量交换的三变量法

1
2
3
4
5

int i, j, tmp;

tmp = i;
i = j;
j = tmp;

例题

三整数排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include<stdio.h>

int main()
{
	int a, b, c, t;
	
	scanf("%d %d %d", &a, &b, &c);
	if(a>b)	{
		t = a, a = b, b = t;
	}
	if(a>c)	{
		t = a, a = c, c = t;
	}
	if(b>c)	{
		t = b, b = c, c = t;
	}
	printf("%d %d %d\n", x, y, z);
	return 0;
}

实验

使用整型数据时，6个1平方会溢出。sqrt(-10)，使用整型输出时为0，浮点型时为-1.#IND00。浮点数 1.0/0.0 结果是inf，0.0/0.0结果是nan，1/0报错。

scanf()自动滤掉空格；输出%d用”%%d”，输出“\n”用”\n”。

实践

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

1
2
3
4
5
6
7
8
9

#include <stdio.h>    
int main()    
{    
    int i;    
    
    for (i = 1; i > 0; i++) NULL;    
    printf("%d %d\n", i, i-1);    
    return 0;    
}

输出较慢。

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

练习

1-1 average

1
2
3
4
5
6
7
8
9
10
11
12

#include <stdio.h>

int main()
{
    int a, b, c;
    float ave;

    scanf("%d%d%d", &a, &b, &c);
    ave = (a + b + c) / 3.0;
    printf("%.3f\n", ave);
    return 0;
}

1-2 temperature

1
2
3
4
5
6
7
8
9
10

#include <stdio.h>

int main()
{
    int f;

    scanf("%d", &f);
    printf("%.3f\n", 5.0 * (f - 32.0) / 9.0);
    return 0;
}

1-3 sum

1
2
3
4
5
6
7
8
9
10

#include <stdio.h>

int main()
{
    int n;

    scanf("%d", &n);
    printf("%d\n", n * (n + 1) / 2);
    return 0;
}

1-4 sincos

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <stdio.h>
#include <math.h>

int main()
{
    int n;
    double d;
    const double PI = 4.0 * atan(1.0);

    scanf("%d", &n);
    d = (n / 180.0) * PI;
    printf("%.3f %.3f\n", sin(d), cos(d));
    return 0;
}

1-5 distance

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <stdio.h>
#include <math.h>

int main()
{
    double x1, y1, x2, y2;
    double d;

    scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
    d = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    printf("%.3f\n", d);
    return 0;
}

这个开始时输入使用%f，输出为错误，改为%lf结果正确。

1-6 odd

1
2
3
4
5
6
7
8
9
10

#include <stdio.h>

int main()
{
    int n;

    scanf("%d",&n);
    printf(n / 2 == 1 ? "No\n" : "Yes\n");
    return 0;
}

1-7 discount

1
2
3
4
5
6
7
8
9
10

#include <stdio.h>

int main()
{
    int n;

    scanf("%d", &n);
    printf("%.3f\n", (95 * n < 300) ? 95.0 * n : 95.0 * n * 0.85);
    return 0;
}

1-8 abs

1
2
3
4
5
6
7
8
9
10
11

#include <stdio.h>
#define ABS(x) ( (x) > 0 ? (x) : (-(x))  )

int main()
{
    double s;

    scanf("%lf", &s);
    printf("%.3lf\n", ABS(s));
    return 0;
}

1-9 triangle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <stdio.h>

int  main()
{
    int a, b, c;
    int tmp;

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

    if (a < b) {
        tmp = a;
        a = b;
        b = tmp;
    }
    if (a < c) {
        tmp = a;
        a = c;
        c = tmp;
    }
    if (b < c) {
        tmp = b;
        b = c;
        c = tmp;
    }

    if (b*b+c*c == a*a)
        printf("yes\n");
    else
        printf(a >= b+c ? "not a triangle\n" : "no\n");

    return 0;
}

1-10 year

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <stdio.h>

int main()
{
    int n;

    scanf("%d", &n);
    if( n % 400 == 0 || (n % 4 == 0 && n % 100 != 0))
        printf("yes\n");
    else
        printf("no\n");
    return 0;
}
算法基础
算法