XieNaoban's Blog
0%

算法竞赛入门经典 第2章习题

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 2.5k 阅读时长 ≈ 2 分钟

题目：算法竞赛入门经典 2-1 水仙花数 代码： 

1
2
3
4
5
6
#include<iostream>
void main()
{
	for (int i = 100;i < 999;++i)
		if ((i % 10)*(i % 10)*(i % 10) + (i % 100 / 10)*(i % 100 / 10)*(i % 100 / 10) + (i / 100)*(i / 100)*(i / 100) == i) std::cout << i << '\n';
}

题目：算法竞赛入门经典 2-2 韩信点兵 代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
void main()
{
	int a,b,c,times=0;
	while (cin >> a >> b >> c) {
		cout << "Case " << ++times << ": ";
		c < 3?c += 14 : c+=7;;
		for (;c <= 100;c += 7)
			if (c % 5 == b&&c % 3 == a) {
				cout << c << '\n';
				break;
			}
		if (c > 100) cout << "No answer\n";
	}
}

题目：算法竞赛入门经典 2-3 倒三角形 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int main()
{
	int n;cin >> n;
	for (int i = 0;i < n;++i)
	{
		for (int j = 0;j < i;++j) cout << ' ';
		for (int j = 0;j < 2 * (n - i) - 1;++j) cout << '*';
		cout << '\n';
	}
	return 0;
}

题目：算法竞赛入门经典 2-4 子序列的和 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<iomanip>
using namespace std;

double f(int a, int b)
{
	double sum = 0;
	for (;a <= b;++a) sum += 1.0 / a / a;
	return sum;
}

int main()
{
	int n, m,times=0;
	cout << setprecision(5)<<fixed;
	do {
		do {
			cin >> n >> m;
			if (n == 0 && m == 0) return 0;
		} while (n >= m || n <= 0);
		cout << "Case " << ++times << ": " << f(n, m) << endl;
	} while (1);
	return 0;
}

题目：算法竞赛入门经典 2-5 分数化小数 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
	int a, b, c,CASE=0;
	while (1)
	{
		do {
			cin >> a >> b >> c;
			if (a == 0 && b == 0 && c == 0) return 0;
		} while (a > 1e6 || b > 1e6 || c > 100);
		cout << "Case " << ++CASE << ": "
			<< fixed << setprecision(c)
			<< (double)a / (double)b << endl;;
	}
	return 0;
}

题目：算法竞赛入门经典 2-6 排列 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;

int ge(int n) { return n % 10; }
int shi(int n) { return (n % 100) / 10; }
int bai(int n) { return n / 100; }

int main()
{
	int n[9],i,j;
	for (int num = 123;num <= 321;++num)
	{
		n[0] = bai(num), n[1] = shi(num), n[2] = ge(num);
		n[3] = bai(2 * num), n[4] = shi(2 * num), n[5] = ge(2 * num);
		n[6] = bai(3 * num), n[7] = shi(3 * num), n[8] = ge(3 * num);
		for (i = 0;i < 8;++i) {
			for (j = i + 1;j < 9;++j)
				if (n[i] == n[j]) break;
			if (j < 9) break;
		}
		if (i == 8 && j == 9) cout << num << endl;
	}
	return 0;
}

分析： 2-2无需一个一个地枚举，七个七个地枚举就行，因为每七个里有6个事绝壁不可能的数据。当然应该有更直接的数学方法，我不知道（小学奥数书上是不是有来着）。 2-4所说的陷阱是，6553665536刚好溢出，所以算1/n^2时，写1/n/n，而不要写1 / (n n)。 2-6因为每个数字只能使用一次，所以从123开始枚举，而又要存在3倍关系，所以以321结束枚举