复试准备之二零一三上机题

Author Avatar
Patrick 3月 07, 2019

问题描述

  1. 输出 100-1000 的所有平方回文数。

平分回文数字是满足下列条件的整数:

(1)从左读与从右读都是一样的。

(2)为某一个数的平方。

例:121 是平方回文数。

  1. 编程解决“八皇后问题”:即在一个 8*8 的矩形格子中排放 8 个皇后,要满足的条件包 括:任意两个皇后不能在同一行,同一列,也不能在同一条对角线上。

要求编程给出解的个数。

分析

第一题

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
# include <iostream>
# include <cmath> // 用来求平方根

using namespace std;

bool is_square(int num) {
double x = sqrt(num);
int y = (int)x;

return x == y;
}

bool is_huiwen(int num) {
int x = num % 10;
int y = num / 100;

return x == y;
}

int main() {

for (int i = 100; i < 1000; ++i) {
if (is_square(i) && is_huiwen(i)) {
cout << i << ' ';
}
}
cout << endl;

return 0;
}

第二题

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
# include <iostream>
# include <string>

using namespace std;

int arr[8][8] = {0};
int col_flags[8] = {0};
int cnt = 0;

void queen(int row) {
if (row == 8) {
cnt++;
for (int i = 0; i < 8; ++i) {
for (int j = 0; j < 8; ++j) {
cout << arr[i][j] << ' ';
}
cout << endl;
}
cout << endl;
}

for (int i = 0; i < 8; ++i) {
// 纵列上没有皇后
if (col_flags[i] == 1) continue;
// 左斜对角线上没有皇后
int flag = 0;
for (int j = 1; j + i < 8; ++j) {
if (row - j >= 0) {
if (arr[row - j][i + j] != 0) {
flag = 1;
continue;
}
}
}
if (flag == 1) {
continue;
}
flag = 0;
// 右斜对角线没有皇后
for (int j = 1; j <= i; ++j) {
if (row - j >= 0) {
if (arr[row - j][i - j] != 0) {
flag = 1;
continue;
}
}
}
if (flag == 1) {
continue;
}

arr[row][i] = 1;
col_flags[i] = 1;
queen(row + 1);
arr[row][i] = 0;
col_flags[i] = 0;
}
}

int main() {
queen(0);
cout << cnt << endl;

return 0;
}