0%

算法竞赛入门经典 第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结束枚举