《算法竞赛入门经典（第二版）》第二章

发表于 更新于 阅读次数： Valine：
本文字数： 6.2k 阅读时长 ≈ 6 分钟

为了更深入地了解数据结构与算法，想通过一系列的书籍加深对算法的理解，首先从《算法竞赛入门经典》（第二版）这本书谈起。

水仙花数shuǐ xiān huā shù

题目：输出100～999中的所有水仙花数。若3位数ABC满足$ABC＝A^3＋B^3＋C^3$，则称其为水仙花 数。例如$153＝1^3＋5^3＋3^3$，所以153是水仙花数。

题解：遍历100～999的数字，判断其百位、十位和个位的数字是否满足条件即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
void daffodil()
{
	int hun = 0, ten = 0, bit = 0, res = 0;
	for (int i = 100; i < 1000; i++)
	{
		hun = i / 100;					// 百位
		ten = (i - hun * 100) / 10;			// 十位
		bit = i % 10;					// 个位
		res = hun * hun * hun + ten * ten * ten + bit * bit * bit;
		if (res == i)
			printf("%d\n", i);
	}
}

韩信点兵hán xìn diǎn bīng

题目：相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人 一排、七人一排地变换队形，而他每次只掠一眼队伍的排尾就知道总人数了。输入包含多组 数据，每组数据包含3个非负整数a，b，c，表示每种队形排尾的人数（a＜3，b＜5，c＜ 7），输出总人数的最小值（或报告无解）。已知总人数不小于10，不超过100。输入到文件 结束为止。

样例输入：

2 1 6

2 1 3

样例输出：

Case 1: 41

Case 2: No answer

题解：

一、遍历法

在本例中，数字范围为10～100，范围较小，可以采用遍历的方式，遍历10～100的数字，判断其对3、5、7取余的数组是否等于所给出的数字，当判断到100仍未满足条件，即判断没有答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void hanxin_traverse()
{
	int r1 = 0, r2 = 0, r3 = 0;				// 三个余数
	int n = 1, i = 0;					// 对应情况的数目
	while (scanf_s("%d%d%d", &r1, &r2, &r3))
	{
		for (i = 10; i <= 100; i++)
		{
			if (i % 3 == r1 && i % 5 == r2 && i % 7 == r3)
			{
				printf("Case %d:%d\n", n++, i);
				break;
			}
			else if (i == 100)
				printf("Case %d:No answer\n", n++);
		}
	}
}

二、孙子定理

孙子定理具体介绍在下文中，在本文中主要介绍代码是如何实现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void hanxin_sunzi()
{
	int r1 = 0, r2 = 0, r3 = 0;				// 三个余数
	int n = 1;						// 对应情况的数目
	int res = 0;						// 每轮的结果
	while (scanf_s("%d%d%d", &r1, &r2, &r3))
	{
		res = r1 * 70 + r2 * 21 + r3 * 15;		// 由于三个除数已知，可以直接得到Mi*ti
		res %= 105;					// 结果对M=105取余
		if (res >= 10 && res <= 100)			// 在范围内则正确
			printf("Case %d:%d\n", n++, res);
		else
			printf("Case %d:No answer\n", n++);	// 否则为错
	}
}

孙子定理sūn zǐ dìng lǐ

孙子定理是中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。

用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组：

孙子定理说明：假设整数$m_1,m_2,\dots,m_n$两两互质，则对任意的整数：$a_1,a_2,\dots,a_n$，方程组（S）有解，且通解可以用以下方式构造得到：

设$M = m1 × m_2 × \cdots × m_n = \prod{i=1}^{n}m_i$是整数$m_1,m_2,…,m_n$的乘积，并设$M_i=M/m_i,\forall i \in \left{1,2,…,n \right}$是除$m_i$以外的$n-1$个整数的乘积。

设$ti=M^{-1}{i}$为$M_i$模$m_i$的数论倒数（$t_i$为$M_i$模$m_i$意义下的逆元）$M_i t_i \equiv 1 \quad (mod\ m_i), \forall i \in \left{1,2,…,n \right}$

方程组（S）的通解形式为$x=a1 t_1 M_1 + a_2 t_2 M_2 + \cdots + a_n t_n M_n + kM = kM + \sum{i=1}^{n}a_i t_i M_i, k \in \mathbb{Z}$

在模$M$的意义下，方程组（S）只有一个解：$x=\big ( \sum_{i=1}^{n}a_i t_i M_i \big ) mod\ M$。

坐而论道，不如起而行之。下面就结合上文中孙子算经的实例讲解一下。

首先，将文字转换为数学的形式。

其次，求M的值。$M=3×5×7=105$

然后，求出对应的$M_i$的值。

接着，求出$t_i=M_i^{-1}的值$。

同理可得$t_2=1,t_3=1$。

最后可得解：

所以答案为23。

倒三角形dào sān jiǎo xíng

题目：输入正整数n≤20，输出一个n层的倒三角形。例如，n＝5时输出如下：

1
2
3
4
5
#########
 #######
  #####
   ###
    #

题解：此题较为简单，先输入一个数字，先判断其是否在范围内，若在范围内，循环n次，然后循环体内又是两个循环，用于生成空格和#号，第一个循环，循环i次（i为循环量，初始值为0），循环体内用于输出空格；第二个循环，循环2*(n-i)-1次，循环体内输出#。在每个外循环结束后，需要输出换行符用于换行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void triangle()
{
	int n = 0;
	scanf_s("%d", &n);
	if (n > 20 || n < 0)					// 判断是否在范围内
	{
		printf("Wrong input.");
		return;
	}
	for (int i = 0; i < n; i++)				// 循环n次
	{
		for (int j = 0; j < i; j++)			// 循环输出空格
			printf(" ");
		for (int k = 0; k < 2 * (n - i) - 1; k++)	// 循环输出#
			printf("#");
		printf("\n");					// 换行
	}
}

子序列的和zǐ xù liè de hé

题目：输入两个正整数$n＜m＜10^6$，输出 $\frac{1}{n^2}+\frac{1}{(n+1)^2}+\cdots+\frac{1}{m^2}$，保留5位小数。输入包含多组数据， 结束标记为$n＝m＝0$。

提示：本题有陷阱。

样例输入：

2 4

65536 655360

0 0

样例输出：

Case 1: 0.42361

Case 2: 0.00001

题解：本题目先输入对应的n和m的值，然后判断是否均为0，如果均为0，则跳出；反之，循环m-n+1次，将对应的平方倒数加到结果中，最后输出即可。本题干中提到的陷阱主要是由于对应的整数范围的问题，需要使用long long类型解决即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void subsequence()
{
	long long n = 0, m = 0;
	int time = 1;
	float res = 0;
	while (scanf_s("%lld %lld", &n, &m))
	{
		if (n == 0 && m == 0)
			break;
		res = 0;
		for (int i = n; i <= m; i++)			// 遍历m-n+1次
			res += 1.0 / pow(i, 2);
		printf("Case %d: %.5f\n", time++, res);
	}
}

分数化小数fēn shù huà xiǎo shù

题目：输入正整数$a,b,c$，输出$\frac{a}{b}$的小数形式，精确到小数点后c位。$a，b≤10^6，c≤100$。输 入包含多组数据，结束标记为$a＝b＝c＝0$。

样例输入：

1 6 4

0 0 0

样例输出：

Case 1: 0.1667

题解：同上题相同，需要输入三个数字，由于在C语言中，笔者暂未找到对应设置特定精度的方法，退而求其次，笔者使用了C++中iomanip库中的std::setprecision函数用于设置精度。

1
2
3
4
5
6
7
8
9
10
11
12
13
void decimal()
{
	int a = 0, b = 0, c = 0;
	int time = 1;
	double res = 0;
	while (scanf_s("%d%d%d", &a, &b, &c))
	{
		if (a == 0 && b == 0 && c == 0)
			break;
		res = 0;
		std::cout << "Case " << time++ << ":" << std::setprecision(c) << (double)a / (double)b << std::endl;
	}
}

排列pái liè

题目：用$1,2,3,…,9$组成3个三位数$abc，def和ghi$，每个数字恰好使用一次，要求$abc：def：ghi＝1：2：3$。按照$“abc\ def\ ghi”$的格式输出所有解，每行一个解。提示：不必 太动脑筋。

题解：题目中给出每个三位数的范围为$[100,999]$，但是由题意，1~9中每个数字只能使用一次，我们还可以进一步得知每个三位数最小值为123，最大值为987，因为最大值不超过987，那么由对应的比值关系可知，$abc$的值不超过$987/3=329$，因而可以采用暴力搜索法。

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
bool a[10] = { 1,1,1,1,1,1,1,1,1 };					// 用于判断某一数字是否使用的数组

bool isOK(int num)							// 用于判断某一个数字是否已经被使用
{
	if (a[num - 1])							// 如果被使用则修改为0
	{
		a[num - 1] = 0;
		return true;
	}
	return false;							// 反之返回false
}

void permutation()
{
	int i = 0, j = 0, k = 0;
	for (int i = 123; i <= 329; i++)				// 最小值在此范围内
	{
		j = 2 * i;						// 根据比值得到剩余两个数组
		k = 3 * i;
		if (isOK(i / 100) && isOK(i / 10 % 10) && (i % 10) 	// 判断每一位上数字
			&& isOK(j / 100) && isOK(j / 10 % 10) && isOK(j % 10) 
			&& isOK(k / 100) && isOK(k / 10 % 10) && isOK(k % 10))
			printf("%d %d %d\n", i, j, k);
		for (int t = 0; t < 10; t++)				// 重新初始化数组
			a[t] = 1;
	}
}