复试准备之二零一三上机题 | Patrick's Space

问题描述

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

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

（1）从左读与从右读都是一样的。

（2）为某一个数的平方。

例：121 是平方回文数。

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

要求编程给出解的个数。

分析

第一题

# 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;
}

第二题

# 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;
}