算法竞赛入门经典章节练习

算法竞赛入门经典的习题，变种题是自己想的和自己添加的，其他的题目则为书本上选取

第二章

水仙花数

输出100-999 中所有的水仙花数, ABC 满足 ABC = A^3 + B^3 + C^3 则称之为水仙花数

适合穷举法

void f_1(void) {
    for (int i = 100; i <= 999; i++) {
        int a, b, c;
        a = i / 100;
        b = i / 10 % 10;
        c = i % 100 % 10;
        if (i == a * a * a + b * b * b + c * c * c)
            printf("%d\n", i);
    }
}

韩信点兵

利用队尾剩余人数求出队伍总人数(人数大于10, 小于100)

input: 2 1 6 input: 2 1 3 output: 41 output: No answer

适合穷举法

void f_1(int a, int b, int c) {
   for (int i = 10; i <= 100; i++) {
       if ((i % 3 == a) && (i % 5 == b) && (i % 7) == c) {
           printf("%d\n", i);
           return;
       }
   }
   printf("No answer.\n");
}

倒三角形

输出n层的倒三角形

void f_1(int n) {
    for (int i = n; i 0; i--) {
        for (int j = n - i; j 0; j--)
            printf(" ");
        for (int j = i * 2; j 1; j--)
            printf("#");
        printf("\n");
    }
}

计算子序列

计算 1/n^2 + 1/(n + 1)^2 + … 1/m^2

double f_1(long long n, long long m) {
    double ans = 0;
    while (n <= m) {
        ans = 1.0 / (n * n) + ans;
        n++;
    }
    return ans;
}

分数化小数

输入a,b,c 计算a/b, 精确到c位

自己实现除法

int division(int a, int b)
{
    int quotient;
    quotient = 0;
    while (a b) {
        quotient++;
        a -= b;
    }
    return quotient;
}

void f_1_1(int a, int b, int c) {
    int quotient, remainder;
    quotient = division(a, b);
    remainder = a - quotient * b;
    remainder *= pow(10, c);
    int decimal;
    decimal = division(remainder, b);
    if ((remainder - decimal * b) % 100000 5)
        decimal++;
    char buffer[200] = { '0' };
    sprintf(buffer, "%d.%d", quotient, decimal);
        printf("%s", buffer);
}

利用系统除法, 转换为string, 取出c位

void f_1_2(int a, int b, int c) {
    char buffer[200] = { '0' };
    sprintf(buffer, "%.100f", (float)a / (float)b);
    int temp;
    int flag = 0;
    for (int i = 0;; i++) {       
        if (buffer[i] == '.') {
            flag = 1;
            temp = i;
        }
        if (flag == 1 && (i - temp) == c) {
            if(buffer[i + 1] - '0' 5)
                printf("%c", buffer[i] + 1);
            else
                printf("%c", buffer[i]);
            break;
        }          
        printf("%c", buffer[i]);
    }
}

分数化小数

用1-9组成 3位数abc, def, ghi,每个数字恰好一次, 使得abc : def : ghi = 1 : 2: 3

穷举法

int check(int i) {
    char buffer[10];
    sprintf(buffer, "%d%d%d", i, i * 2, i * 3);
    int flag = 0;
    char a[10] = {0};
    for (int i = 1; i <= 9; i++) {
        if (a[buffer[i] - '0'] != 'Q')
            a[buffer[i] - '0'] = 'Q';
        else
            return 0;
    }
    return 1;
}
void f_1(void) {
    for (int i = 101; i < 333; i++) {
        if (check(i))
            printf("%d, %d, %d\n", i, i * 2, i * 3);
    }
}

第三章