I am an amazing person.

5 minute read

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

第一章

圆柱体表面积

输入底面半径r和高h，输出圆柱体的表面积，保留3位小数

3.5 9

Area = 274.889

double fun(double r, double h) {
    return (r * r * PI) * 2 + ((PI * 2 * r) * h);
}
void f_2(void) {
    double r, h;
    scanf("%lf%lf", &r, &h);
    printf("Area = %.3lf", O_1_1(r, h));
}

// -----------------

void f_simple(void) {
    // one way to get the value of pi
    const double pi = acos(-1.0);
    double r, h;
    scanf("%lf%lf", &r, &h);
    printf("Area = %.3f", (r * r * pi) * 2 + ((pi * 2 * r) * h));
}

三位数反转

输入一个三位数，分离出他的百位，十位，个位 并输出

127

721

void fun(void) {
    int n;
    scanf("%d", &n);
    printf("%d%d%d", n % 10, n / 10 % 10, n / 100 );
}

变种一 3位反转后首位为0

首位为0保留

  1. 上例代码。
  2. 转换为字符串。

// In Programming language C, it has several methods to convert some types into string. // 1. using sprintf // 2. using the standard library (itoa)

// in this question, we can know it only has 3 digits, using the sprintf will be the simplest.

void swap(char *a, char *b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}
void fun_2(int num) {
    char answer[4];
    // convert to string
    sprintf(answer,"%d", num);
    swap(&answer[0], &answer[2]);
    printf("%s", answer);
}

首位为0去除

  1. 转换为字符串， 然后输出时判断为0 不输出。
  2. 将值加和，成为数字。
void swap(char *a, char *b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}
void f_2_1(int num) {
    char answer[4];
    // convert to string
    sprintf(answer,"%d", num);
    swap(&answer[0], &answer[2]);
    for(int i = 0; i != 4; i++)
        if(answer[i] != '0')
            printf("%c", answer[i]);
}

void f_2_2(int num) {
    int answer = (num % 10) * 100 + (n / 10 % 10) * 10 + (n / 100);
    printf("%d",answer);
}

变种二 任意位数的值都反转

首位为0保留

  1. 转换为字符串 Because we don’t know how many digits we need to use, we can’t use sprintf

首位为0去除

交换变量

输入两个整数a和b，交换2者的值

824 16

16 824

最简单的, 3个变量交换方式.

变种一 任意基本变量都交换

传递另外的参数, 使用switch 确定 基本变量的类型.

enum types {
    Int, Double, Float
};

void swap_int(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void swap_double(double* a, double* b) {
    double temp = *a;
    *a = *b;
    *b = temp;
}

void swap(void* a, void* b, enum types type) {
   
    switch (type) {
    case Int:
        swap_int((int*)a, (int*)b);
        break;
    case Double:
        swap_double((double*)a, (double*)b);
        break;
    }
}

鸡兔同笼

已经鸡和兔的总数量为n，总腿数为m， 输入n和m，以此输出鸡和兔的数目，如果无解，则输出no answer.

14 32

12 2

// 略

三整数排序

输入3个整数，从小到大排序后输出

20 7 33

7 20 33

特别的，本题意在给出数据量固定，且比较少的特殊情况下 可以直接暴力输出.

第二章

形如aabb的4位完全平方数(即前两位数字相等, 后两位数学也相等)

1122

枚举,然后判断

枚举方式

  • 枚举每个数符合aabb,然后判断是否是完全平方数
  • 枚举每个数平方后判断是否为aabb

3n +１

任意大于1的自然数,若n为奇数, 则将n变为3n + 1, 否则将变为n的一半,经过这样的若干次变换,一定会使n变为1. 例如3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

输入n,输出变换的次数.

3 7

int fun(int n) {
    int index = 0;
    while (n != 1) {
        if (n % 2 == 1) {
            n = 3 * n + 1;
        }
        else {
            n /= 2;
        }
        index++;
    }
    return index;
}

近似计算

计算pi/4 = 1 - 1/3 + 1/5 - 1/7 + … 直到最后一项小于10e-6

double fun(void) {
    double sum = 0;
    double item;
    for (int i = 0; ; i++) {
        item = 1.0 / (i * 2 + 1);
        if (i % 2) {
            sum -= item;
        }
        else {
            sum += item;
        }
        if (item < 1e-6)
            break;
    }
    return sum; 
}

阶乘之和

输入n, 计算S = 1! + 2! + 3! + …. + n! 的末6位(不含前导0). n <= 1e6

10 37913

  • 只计算末尾6位 (因为只需要末尾的6位,可以只用考虑末尾6位的情况, 防止溢出的可能)
  • 全部计算,最后取出6位数据,因为该式为阶乘,所以很大概率会溢出

特别的 25! 末尾有6个0, 所以后面的加和不会影响数据的结果. if(n > 25) n = 25;

int fun(int n) {
    if (n > 25)
        n = 25;
    int sum = 0;
    int temp;
    for (int i = 1; i <= n; i++) {
        temp = 1;
        for (int j = 1; j <= i; j++) {
            temp = j * temp % 1000000;
        }
        sum = (sum + temp) % 1000000;  
    }
    return sum;
}

数据统计

输入一些整数, 求出它们的最小值,最大值和平均值(保留3位小数) 保证不超过1000的整数

变种 不作任何限制,产生溢出的情况下

自己实现相关的数据结构和运算(考虑到溢出的情况)

  • 简单: 利用字符串完成所有的操作
  • 比较难: 位运算

第三章

开灯问题

有n盏灯,编号1-n, 第1个人把所有的灯打开, 第二个人按下所有编号为2的倍数的开关, 第三个人按下所有编号为3的倍数的开关. 以此类推, 一共有k个人,最后哪些灯开着?

7 3 1 5 6 7

void fun(int n, int k) {
    // 灯的个数以1开头,为了不进行加减运算, 直接创建的时候,浪费了0下标的元素
    int* p = (int*)malloc(sizeof(int) * n + 1);
   
    for (int i = 0; i <= n; i++) {
        p[i] = 1;
    }
    p[0] = 0; 
    for (int i = 1; i <= k; i++) {
        if (i != 1) {
            int temp = 1;
            for (int j = i; j <= n;) {
                j = temp * i;
                p[j] = !p[j];
                temp++;
            }
        }
    }
    for (int i = 0; i <= n; i++)
        if (p[i] == 1)
            printf("%d ", i);
}

蛇形填数

在n * n 的方阵中填成蛇形, 1, 2, 3….

10 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4

可以判断相应位置, 和周围是否已经被填入数字(先用0 填满整个数组)

x = 0;
y = n - 1;
tot = a[x][y] = 1;
while(tot < n * n) {
    while(x + 1 < n && !a[x + 1][y])
        a[++x][y] = ++tot;
    while(y - 1 >= 0 && !a[x][y-1])
        a[x][--y] = ++tot;
    while(x - 1 >= 0 && !a[x - 1][y])
        a[--x][y] = ++tot;
    while(y + 1 < n && !a[x][y + 1])
        a[x][++y] = ++tot;
}

自己实现的:

void fun(int n)
{
    int** matrix = (int**)malloc(sizeof(int*) * n);
    for (int i = 0; i != n; i++)
        matrix[i] = (int*)malloc(sizeof(int) * n);
    int x;
    int y;
    int index = 1;
    int round = 1;
    while (index < n * n) {
        x = round - 1; 
        y = n - round; 
        while (x < n - round && index <= n * n)
            matrix[x++][y] = index++;
        while (y >  round - 1 && index <= n * n)
            matrix[x][y--] = index++;    
        while (x > round - 1 && index <= n * n)
            matrix[x--][y] = index++;
        while (y < n - round && index <= n * n)
            matrix[x][y++] = index++;
        round++; 
    }
    if (n % 2)
        matrix[++x][--y] = index;
    for (int i = 0; i != n; i++) {
        for (int j = 0; j != n; j++)
            printf("%3d ", matrix[i][j]);
        putchar('\n');
    }
}

猴子排位

题目内容：n只猴子（n<100）要选大王，选举方法如下：所有猴子按1,2,3,……, n编号围坐一圈，从第1号开始按照1,2,……, m报数，凡报到m号的退出圈外，如此循环报数，直到圈内剩下一只猴子时，这只猴子就是大王。编程一个程序实现上述过程，n和m由键盘输入。

5 3 3 1 5 2 4

void fun(int n, int k) {
    int* p = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i != n; i++)
        p[i] = i + 1;
    int temp = 1;
    
    int out_number = 0;
    for (int i = 0;; ) {
        if (p[i] != -1) {
            if (temp == k) {
                printf("%d ", p[i]);
                temp = 0;
                p[i] = -1;
                out_number++;             
            }
            temp++;
        }
   
        if (out_number == n - 1)
            break;
        i++;
        i %= n;
    }
    for (int i = 0; i != n; i++)
        if (p[i] != -1)
            printf("%d", p[i]);
}

竖式问题

输入一些数字, 利用这些数字生成 abc * bc 的竖式. 要求中间的每个步骤生成的数,都必须在输入的数字范围内. 并根据有多少解,输出相应的竖式. 若不存在,输出不存在.

int x = abc * (de % 10), y = abc * (de / 10), z = abc * de;
sprintf(buf, "%d%d%d%d%d", abc, de, x, y, z);

以此判读buf中的数是否在输入的范围之中. 使用strchr 函数

TeX中的引号

将双引号转换为其他字符

用一个变量保存状态就可以

int status = 1;
if(c == '"') {
    printf("%s", status ? "-", "+");
    status = !status;
}
else
    printf("%c", c);

错位键盘

输入一个顺序错误的字符串, 每一个字符都依照键盘位置向右边一位. 输出一个顺序正确的字符串

建立表,查找

回文词和镜像

判断一个字符串是回文词和镜像串

建立表,查找

猜数字

生成元

环状序列

You may also enjoy

Word Break

less than 1 minute read

<-H 139> Word Break