2013北航机试

代码均为自做

题目一

给一个真分数的分子分母，输出约分后的分子分母。

#include <iostream>

using namespace std;
int getComApprox(int a, int b) {
    int tmp = a;
    while (b % a != 0) {
        tmp = b % a;
        b = a;
        a = tmp;
    }
    return a;
}
int main()
{
    int a, b;
    cin >> a >> b;
    int comApprox = getComApprox(a, b);
    cout << a / comApprox << " " << b / comApprox << endl;
    return 0;
}
           

题目二

八皇后

在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

输出：92

#include <iostream>
#include <cmath>
using namespace std;
bool check(int *place, int cnt) { // 检查cnt号皇后的位置是否可行
    for (int i = 0; i < cnt; i++) {
        if (place[i] == place[cnt] || abs(cnt-i) == abs(place[cnt]-place[i])) {
            return false;
        }
    }
    return true;
}
int main()
{
    int n = 8; // 八皇后
    int *place = new int[n]; // 村皇后位置
    for (int i = 0; i < n; i++) { place[i] = 0; }
    int cnt = 0; // cnt号皇后
    int sum = 0; // 满足情况的方法sum种
    place[0] = -1; // 因为进循环就要++，故这里设为-1，每个皇后都是从0号位置开始放
    while(cnt >= 0) {
        place[cnt]++;
        if (place[cnt] == n) { // 如果皇后放到了 n 号位置，则越界了
            cnt--; // 退一行 看上一个皇后
            continue;
        }
        if (check(place, cnt)) { // cnt号皇后可以放在这里
            // cout << place[cnt] << "\t" << cnt << endl;
            cnt++; // 看下一个皇后
            if (cnt < n) { // 皇后的个数还没到达 n
                place[cnt] = -1; // 因下一次循环要++ 皇后的位置要从 0 开始，故设置为-1
            }
            else { // 皇后个数到达 n
                sum++; // 满足情况的个数加一
                cnt--; // 回到上一层
            }
        }
    }
    cout << sum << endl;
    return 0;
}
           

题目三

给出一个标准输入的正数（开头末尾没有多余的零），输出其科学计数法表示结果。

输入：

0.000002

输出：

2e-6

输入：

123.456

输出：

1.23456e2.

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

int main()
{
    string n;
    cin >> n; // 读入数据
    int len = n.size(); // 计算长度
    while (n[len-1] == '0') { // 把数字最后的 0 去掉
        len--;
    }
    int pointIndex = len; // 初始化小数点在 n 最后的下一位
    int firstNotZeroIndex = 0; // 初始化第 0 位为非零
    bool notZero = false; // 非零标记，标记是否已经读了一个非零的数字
    for (int i = 0; i < len; i++) { // 以为以为的看
        if (notZero == false && n[i] == '0') { // 读入的是零，且还没有读到一个非零的数字，说明这是开头的 0
            if (len == 1) { // n 就是 0
                cout << n[i];
            }
            continue;
        }
        if (n[i] == '.') { // 读到了点，记下位置
            pointIndex = i;
        }
        else {
            cout << n[i];
            if (notZero == false) { // 第一个非零的数字，记下位置
                if (i != len-1) // 这不是最后一位就要输出一个点
                    cout << '.';
                firstNotZeroIndex = i; // 记下第一个非零的数字的位置
                notZero = true; //
            }
        }
    }
    int sub = pointIndex - firstNotZeroIndex; // 点的位置与最开始的非零数字的位置之间的差值
    if (sub > 0) { // 点在第一个非零数的后面，小数点要移动 sub-1 位
        sub--; // 例如 123.456 ==> 1.23456e2
    }
    // sub < 0 移动sub位，例如0.002 ==> 2e-3
    if (sub) // 只要移动非零位，就会有e...这种形式
        printf("e%d\n", sub);
    return 0;
}