算法竞赛入门经典学习笔记1

发表于

算法竞赛入门经典学习笔记01

程序设计入门（顺序、分支、循环）

printf 格式控制的总结：

printf 格式控制的完整格式为： **%[-][0][m.n][l或h][格式字符]

具体的说明如下：

① %：表示格式说明的起始符号，不可缺少。

② -：有-表示左对齐输出，如省略表示右对齐输出。

③ 0：有0表示指定空位填0,如省略表示指定空位不填。

④ m.n：m指域宽，即对应的输出项在输出设备上所占的字符数。N指精度。用于说明输出的实型数的小数位数。为指定n时，隐含的精度为n=6位。

⑤ l或h:l对整型指long型，对实型指double型。h用于将整型的格式字符修正为short型。

⑥ 格式字符：用以指定输出项的数据类型和输出格式。

格式字符的总结如下：

① d格式：用来输出十进制整数。

%d：按整型数据的实际长度输出。

%md：m为指定的输出字段的宽度。如果数据的位数小于m，则左端补以空格，若大于m，则按实际位数输出。

%ld：输出长整型数据。

② o格式：以无符号八进制形式输出整数。对长整型可以用”%lo”格式输出。同样也可以指定字段宽度用“%mo”格式输出。

例：

1
2
3
4
5
int main() {
    int a = -1;
    printf("%d，%o", a, a);
    return 0;
}

上述程序的运行结果为：-1,177777

程序解析：-1在内存单元中（以补码形式存放）为二进制下的 1111111111111111，转换为八进制数为177777。

③ x格式：以无符号十六进制形式输出整数。对长整型可以用”%lx”格式输出。同样也可以指定字段宽度用”%mx”格式输出。 ④u格式：以无符号十进制形式输出整数。对长整型可以用”%lu”格式输出。同样也可以指定字段宽度用“%mu”格式输出。

⑤ c格式：输出一个字符。

⑥s格式：用来输出一个串。

有如下几种用法：

1
2
3
4
printf("%s", "CHINA");//输出"CHINA"字符串（不包括双引号）
printf("%10s", "CHINA");//%ms：输出的字符串占m列，如字符串本身长度大于m，则突破获m的限制,将字符串全部 					  //输出。若串长小于m，则左补空格
printf("%-10s", "CHINA");//%-ms：如果串长小于m，则在m列范围内，字符串向左靠，右补空格。 %m.ns：输出占						 //m列，但只取字符串中左端n个字符。这n个字符输出在m列的右侧，左补空格。
printf("%-10.3s", "CHINA"); //%-m.ns：其中m、n含义同上，n个字符输出在m列范围的左侧，右补空格。如果  							  //n>m，则自动取n值，即保证n个字符正常输出。

⑦f格式：用来输出实数（包括单、双精度），以小数形式输出。

%f：不指定宽度，整数部分全部输出并输出6位小数。

%m.nf：输出共占m列，其中有n位小数，如数值宽度小于m左端补空格。

%-m.nf：输出共占n列，其中有n位小数，如数值宽度小于m右端补空格。

⑧e格式：以指数形式输出实数。

%e：数字部分（又称尾数）输出6位小数，指数部分占5位或4位。

%m.ne和%-m.ne：m、n和”-”字符含义与前相同。此处n指数据的数字部分的小数位数，m表示整个输出数据所占的宽度。

⑨g格式：自动选f格式或e格式中较短的一种输出，且不输出无意义的零。

Tips：C语言中的逻辑运算符都是短路运算符。一旦能够确定整个表达式的值，就不再进行运算。

Tips：在C99中，double的输出必须用%f，而输入需要用%lf

第一章末的实验：

数据类型实验

实验A1：表达式11111*11111的值是多少？把5个1改成6个1，9个1呢？

1
2


实验A2：把实验A1中的所有数换成浮点数，结果如何？

1
2


实验A3：表达式sqrt(-10)的值是多少？尝试用各种方式输出。在计算过程中系统会报错吗？

1
2
3
4
5
printf("%d\n", sqrt(-10)); //0 
//warning: format '%d' expects argument of type 'int', but argument 2 has type 
//'__gnu_cxx::__enable_if<true, double>::__type {aka double}' [-Wformat=]
printf("%f\n", sqrt(-10)); //nan     no warnings at all
//nan 用于处理计算中出现的错误情况，比如 0.0 除以 0.0 或者求负数的平方根。

实验A4：表达式1.0/0.0、0.0/0.0的值是多少？尝试用各种方式输出。在计算过程中系统会报错吗？

1
2
3
4
5
6
printf("%d\n", 1.0/0.0); //0  warning: format '%d' expects argument of type 'int', but argument 2 has type 'double' [-Wformat=]
printf("%d\n", 0.0/0.0); //0 format '%d' expects argument of type 'int', but argument 2 has type 'double' [-Wformat=]
printf("%d\n", (int)(1.0/0.0)); //-2147483648
printf("%d\n", (int)(0.0/0.0)); //-2147483648
printf("%f\n", 1.0/0.0); //inf
printf("%f\n", 0.0/0.0); //nan

Tips:

inf:infinty(linux),等同于#INF:infinity(windows)

nan: not a number, 等同于#IND:indeterminate(windows)

注意：

  • inf一般是因为得到的数值，超出浮点数的表示范围（溢出，即阶码部分超过其能表示的最大值）；而nan一般是因为对浮点数进行了未定义的操作，如对-1开方。
  • nan==nan 结果是0或false，即不能和nan进行比较，和nan进行比较得到的结果总是false或0。所以可以用函数： int isNumber(double d){return (d==d);}来判断d是否为nan，若d是nan则返回0，否则返回非零值。
  • 1.0/0.0等于inf，-1.0/0.0等于-inf，0.0+inf=inf；
  • 对负数开方sqrt(-1.0)、对负数求对数(log(-1.0))、0.0/0.0、0.0*inf、inf/inf、inf-inf这些操作都会得到nan。(0/0会产生操作异常；0.0/0.0不会产生操作异常，而是会得到nan)
  • 得到inf时就查看是否有溢出或者除以0，得到nan时就查看是否有非法操作。

实验A5：表达式1/0的值是多少？在计算过程中会报错吗？

1
printf("%d\n", 1/0); //warning: division by zero [-Wdiv-by-zero]
输入格式实验
1
2
3
4
5
6
7
#include<stdio.h>
int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d %d\n", a, b);
    return 0;
}

实验B1：在同一行输入12和2，并以空格分隔，是否得到了预期的结果？Yes！

实验B2：在不同的两行中输入12和2，是否得到了预期的结果？Yes！

实验B3：在实验B1和B2中，在12和2的前面和后面加入大量的空格或水平制表符，甚至插入一些空行。Yes！

实验B4：把2换成字符s，重复前三个实验。1：12 2752512 2：12 3305472 3：12 2592768 12 4112384 [totally different!]

第一章末的习题：
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//习题1-1 平均数（average）
#include<stdio.h>
int main() {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    printf("%.3f\n", (a+b+c)/3.0);
    return 0;
}
//习题1-2 温度（temperature）
#include<stdio.h>
int main() {
    double f;
    scanf("%lf", &f);
    double c = 5 * (f-32) / 9;
    printf("%.3f\n", c);
    return 0;
}
//习题1-3 连续和（sum）
#include<stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", n*(n+1)/2);
    return 0;
}
//习题1-4 正弦和余弦（sin 和 cos）
#include<stdio.h>
#include<math.h>
int main() {
    int n;
    scanf("%d", &n);
    printf("%f %f\n", sin(n), cos(n));
    return 0;
}
//习题1-5 打折（discount）
int main() {
    int n;
    scanf("%d", &n);
    int money = n * 95;
    if(money >= 300) money = money*0.85;
    printf("%.2f", money);
    return 0;
}
//习题1-6 三角形（triangle）
#include<bits/stdc++.h>
using namespace std;
int main() {
    int a[3];
    scanf("%d%d%d", &a[0], &a[1], &a[2]);
    sort(a, a+3);
    if(a[0] + a[1] <= a[2]) printf("not a triangle\n");
    else {
        if(a[0] * a[0] + a[1] * a[1] == a[2] * a[2])
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}
//习题1-7 年份（year）
#include<stdio.h>
int main() {
    int year;
    scanf("%d", &year);
    if(year%400 == 0) printf("yes\n");
    else if(year%4 == 0) printf("yes\n");
    else printf("no\n");
    return 0;
}
第一章末的问题
问题1：int型整数的最大值和最小值是多少？
1
2
3
4
5
6
7
#include<stdio.h>
int main() {
	int i = 1;
	while(i > 0) i++;
	printf("Min = %d Max = %d\n", i, i-1);
	return 0;
} //组成原理 数据在电脑中的存储细节
问题2：double型浮点数能精确到多少位小数？或者说，这个问题本身值得商榷？
问题3：double型浮点数最大正数值和最小正数值是多少？（不必特别精确）
问题4：逻辑运算符”&&“ ”||“ ”！“ 的相对优先级是怎样的？ （test a&&b||c)
问题5：if(a) if(b) x++; else y++;的确切含义是什么？
1
2
3
if(a)
    if(b) x++;
else y++;

Tips：整数范围、浮点数范围和精度、特殊的浮点数、scanf、空格、TAB和回车符的过滤、三角函数使用弧度而非角度；

7744问题：输出形如aabb的4位完全平方数。
1
2
3
4
5
6
7
8
9
10
11
#include<stdio.h>
#include<math.h>
int main() {
    for(int a = 1; a <= 9; a++) 
        for(int b = 1; b <= 9; b++){
            int n = a * 1100 + b * 11;
            int m = floor(sqrt(n) + 0.5);//考虑到浮点数计算的误差！！！
            if(m*m == n) printf("%d\n", n);
        }
    return 0;
}

Tips:要计算只包含加法、减法和乘法的整数表达式除以正整数n的余数，可以在每步计算之后对n取余，结果不变;循环结构程序设计中最常见的两个问题：算术运算溢出和程序效率低下。

利用时间函数记录程序的运行速度：

1
2
3
4
5
#include<time.h>
int main() {
	printf("Time used = %.2f\n", (double)clock() /CLOCKS_PER_SEC);
	return 0;
}
通过使用输入输出重定向，让程序从文件中读取数据
1
2
3
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
//在main函数的入口处加入上述代码，使得scanf从文件input.txt读入，printf写入文件output.txt
常规的文件读写操作
1
2
3
4
5
6
7
8
9
FILE *fin, *fout;
fin = fopen("data.in", "rb");
fout = fopen("data.out", "wb");

fscanf(fin, "%d", &x);
fprintf(fout, "%d", x);

fclose(fin);
fclose(fout);

Tips:在多数据的题目中，要注意某些变量的初始化问题！

​ 在嵌套的两个代码块中有同名变量时，内层的变量会屏蔽外层变量，有时会引起十分隐蔽的错误！

第二章末的习题
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//习题2-1 水仙花数（daffodil）
#include<stdio.h>
int main() {
    for(int i = 100; i <= 999; i++) {
        int a = i%10;
        int b = i/10%10;
        int c = i/100;
        if(a*a*a + b*b*b +c*c*c == i)
            printf("%d\n", i);
    }
    return 0;
}
//习题2-2 韩信点兵（hanxin）
#include<stdio.h>
int main() {
    int a, b, c;
    int cnt = 0;
    while(scanf("%d%d%d", &a, &b, &c) != EOF) {
        bool flag = true;
        for(int i = 10; i <= 100; i++)
            if(i%3 == a && i%5 == b && i%7 == c) {
                flag = false;
                printf("Case %d: %d\n", ++cnt, i);
                break;
            }
        if(flag) printf("Case %d: No answer\n", ++cnt);
    }
    return 0;
}
//习题2-3 倒三角形（triangle）
#include<stdio.h>
int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
    	for(int i = 0; i < n; i++) {
        	for(int j = 0; j < i; j++) printf(" ");
        	for(int j = 0; j < 2*n-1-2*i; j++) printf("#");
        	printf("\n");
    	}
    }
    return 0;
}
//习题2-4 子序列的和（subsequence)
#include<stdio.h>
int main() {
    int n, m;
    int count = 0;
    while(scanf("%d%d", &n, &m) != EOF) {
        if(n == 0 && m == 0) return 0;
        double cnt = 0;
        for(int i = n; i <= m; i++) {
            double temp = 1.0 / i;
            temp *= temp;
            cnt += temp;
        }
        printf("Case %d: %.5f", ++count, cnt);
    }
}
//习题2-5 分数化小数（decimal）
#include<stdio.h>
int main() {
    int a, b, c, cnt = 0;
    while(scanf("%d%d%d", &a, &b, &c) != EOF) {
    	if(a == 0 && b == 0 && c == 0) return 0;
        double temp = a * 1.0 / b;
        printf("Case %d: %.*lf\n", ++cnt, c, temp);//printf("%*.*f\n", m, n, ch);
    }
    return 0;
}
//习题2-6 排列（permutation）
#include<stdio.h>
int main() {
	int a[3];
    for(a[0] = 123; a[0] <=329; a[0]++) {
        a[1] = a[0] * 2;
        a[2] = a[0] * 3;
        int c[9];
        for(int m = 0; m < 9; m += 3) {
        	c[m+2] = a[m/3]%10;
        	c[m+1] = a[m/3]/10%10;
        	c[m] = a[m/3]/100;
        }
        int add = 0, mul = 1;
        for(int i = 0; i < 9; i++) {
        	add += c[i];
        	mul *= c[i];
        }
        if(add == 45 && mul == 362880)
            printf("%d %d %d\n", a[0], a[1], a[2]);
    }
    return 0;
}
第二章末的问题

题目1：假设需要输出2，4，6，8，…,2n，每个一行，能不能通过对程序2-1进行小小的改动来实现？

1
2
3
4
5
6
7
8
9
//程序2-1
#include<stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        printf("%d\n", i);
    return 0;
}

任务1：改动第7行，不改动第6行

1
2
for(int i = 0; i < n; i++)
	printf("%d\n", (i+1)*2);

任务2：改动第6行，不改动第7行

1
2
for(int i = 2; i <= 2*n; i += 2)
	printf("%d\n", i);

题目2：下面程序的运行结果是什么？ 无法停止，因为i存在误差，无法判定与10相等。

1
2
3
4
5
6
7
#include<stdio.h>
int main() {
    double i;
    for(i = 0; i != 10; i += 0.1)
        printf("%.lf\n", i);
    return 0;
}