C语言经典题目（PTA题）2

Time_Controller

已于 2024-12-07 23:03:25 修改

阅读量1.3k

点赞数 26

分类专栏： c语言文章标签： c语言数据结构开发语言排序算法算法

于 2024-11-24 12:11:14 首次发布

本文链接：https://blog.csdn.net/Time_Controller/article/details/143896988

版权

c语言专栏收录该内容

1 篇文章

订阅专栏

一.选择法排序

#include<stdio.h>

int main(){
    int n;               // 用来存储数组元素的个数
    int enterNum;        // 用来存储每次输入的整数
    int arr[10];         // 存储最多10个整数的数组

    // 读取数组元素个数
    scanf("%d", &n);

    // 输入n个整数并将它们存入数组arr
    for(int i = 0; i < n; i++){
        scanf("%d", &enterNum);  // 输入每个整数
        arr[i] = enterNum;       // 将输入的整数存入数组arr
    }

    // 选择排序：按从大到小排序数组arr
    for(int j = 0; j < n - 1; j++){  // 外层循环控制当前排序的位置
        for(int i = j + 1; i < n; i++){  // 内层循环遍历剩余部分查找最大值
            if(arr[j] < arr[i]){  // 如果当前位置的元素小于后面的元素，则交换
                int temp = arr[i];  // 临时存储arr[i]
                arr[i] = arr[j];    // arr[i]变成arr[j]
                arr[j] = temp;      // arr[j]变成临时存储的arr[i]
            }
        }
    }

    // 输出排序后的数组
    for(int i = 0; i < n; i++){
        // 输出时考虑是否是最后一个元素，避免行末多余空格
        if(i == n - 1){
            printf("%d", arr[i]);  // 如果是最后一个元素，直接输出数字
        } else {
            printf("%d ", arr[i]);  // 如果不是最后一个元素，输出数字后加空格
        }
    }
    
    return 0;
}

二.找出不是两个数组共有的元素

#include <stdio.h>
#include <stdbool.h>

// 检查元素是否存在于数组中
bool exists_in_arr(int element, int arr[], int size) {
    for (int i = 0; i < size; i++) {
        if (element == arr[i]) {
            return true;  // 找到该元素，返回 true
        }
    }
    return false;  // 未找到，返回 false
}

int main() {
    int N1, N2;          // 存储两个数组的大小
    int arr1[20], arr2[20];  // 用于存储输入的两个数组
    int result[40];      // 用于存储结果数组
    int result_size = 0; // 结果数组的大小

    // 输入第一个数组
    scanf("%d", &N1);
    for (int i = 0; i < N1; i++) {
        scanf("%d", &arr1[i]);
    }

    // 输入第二个数组
    scanf("%d", &N2);
    for (int i = 0; i < N2; i++) {
        scanf("%d", &arr2[i]);
    }

    // 判断 arr1 中不在 arr2 中的元素
    for (int i = 0; i < N1; i++) {
        if (!exists_in_arr(arr1[i], arr2, N2) && !exists_in_arr(arr1[i], result, result_size)) {
            result[result_size++] = arr1[i];
        }
    }

    // 判断 arr2 中不在 arr1 中的元素
    for (int i = 0; i < N2; i++) {
        if (!exists_in_arr(arr2[i], arr1, N1) && !exists_in_arr(arr2[i], result, result_size)) {
            result[result_size++] = arr2[i];
        }
    }

    // 输出结果数组，避免行末多余的空格
    for (int i = 0; i < result_size; i++) {
        if (i == result_size - 1) {
            printf("%d", result[i]);  // 最后一个元素不加空格
        } else {
            printf("%d ", result[i]);
        }
    }

    return 0;
}

三.打印杨辉三角

用循环实现

#include<stdio.h>
int main(){
    int N;
    int num = 1;  // 用来存储中间计算的值，初始为1
    scanf("%d", &N);  // 输入杨辉三角的行数

    // 外层循环：用于控制杨辉三角的行数
    for(int i = 0; i < N; i++){
        
        // 打印空格部分，确保数字对齐为正三角形
        for(int k = N; k > i + 1; k--){
            printf(" ");  // 每一行之前的空格数量根据行号递减
        }

        // 内层循环：计算并打印每行的数值
        for(int j = 0; j <= i; j++){
            // 处理每行的两个端点元素，端点元素为1
            if(j == 0 || j == i){
                printf("%4d", 1);  // 每行的第一个和最后一个数是1，宽度固定为4位
            } else {
                // 计算非端点位置的元素值：通过公式计算杨辉三角的中间元素
                num = num * (i - j + 1) / j;  
                printf("%4d", num);  // 打印每个元素，宽度为4
            }
        }
        
        num = 1;  // 每行结束后，重置num为1，准备计算下一行
        printf("\n");  // 换行，准备打印下一行
    }
}

用二维数组实现

#include <stdio.h>

int main() {
    int N;
    scanf("%d", &N);  // 输入需要打印的杨辉三角行数

    int triangle[10][10] = {0};  // 用于存储杨辉三角的二维数组，最大10行

    // 生成杨辉三角
    for (int i = 0; i < N; i++) {
        triangle[i][0] = 1;  // 每行第一个元素为1
        for (int j = 1; j <= i; j++) {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];  // 每个元素等于其上方两个元素之和
        }
    }

    // 打印杨辉三角
    for (int i = 0; i < N; i++) {
        // 打印行前的空格以对齐成正三角形
        for (int j = 0; j < N - i - 1; j++) {
            printf("    ");  // 每个数字占4位，所以空格按4倍计算
        }
        // 打印当前行的元素
        for (int j = 0; j <= i; j++) {
            printf("%4d", triangle[i][j]);  // 每个数字占4位宽
        }
        printf("\n");  // 换行打印下一行
    }

    return 0;
}

四.编程实现两个分数相加

#include<stdio.h>

// 寻找最大公约数
int GCD(int a, int b) {
    while (b != 0) {
        int temp = a % b;  // 计算余数
        a = b;              // 将b赋值给a
        b = temp;           // 将余数赋值给b
    }
    return a;  // 返回最大公约数
}

int main() {
    int num1, numA, num2, numB;
    
    // 输入格式应为：a/b + c/d
    scanf("%d/%d+%d/%d", &num1, &numA, &num2, &numB);
    
    // 计算分子和分母
    int numerator = num1 * numB + num2 * numA;  // 分子
    int denominator = numA * numB;              // 分母

    // 计算最大公约数
    int gcd = GCD(numerator, denominator);
    
    // 简化分数
    numerator /= gcd;
    denominator /= gcd;
    
    // 输出结果，格式化输出
    printf("%d/%d+%d/%d=%d/%d", num1, numA, num2, numB, numerator, denominator);
    
    return 0;
}

五.N个数求和

#include <stdio.h>
#include <math.h>

// 函数：计算最大公约数（GCD）
int GCD(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

int main() {
    int N;
    scanf("%d", &N);  // 读取分数的数量

    int numerator = 0;  // 分子总和
    int denominator = 1;  // 分母的初始值是1

    // 读取每个分数并求和
    for (int i = 0; i < N; i++) {
        int a, b;
        scanf("%d/%d", &a, &b);

        // 通分，分母相同则加分子
        numerator = numerator * b + a * denominator;
        denominator = denominator * b;

        // 每次通分后，简化分数
        int gcd = GCD(abs(numerator), denominator);  // 使用绝对值来避免负数的影响
        numerator /= gcd;
        denominator /= gcd;
    }

    // 输出整数部分
    int integer_part = numerator / denominator;  // 整数部分
    numerator = numerator % denominator;  // 剩余部分（分数部分）

    if (numerator == 0) {
        // 如果没有分数部分，输出整数部分
        printf("%d", integer_part);
    } else {
        // 如果有分数部分，输出整数部分和分数部分
        if (integer_part != 0) {
            printf("%d ", integer_part);  // 输出整数部分
        }
        printf("%d/%d", numerator, denominator);  // 输出分数部分
    }

    return 0;
}

六.韩信点兵

#include <stdio.h>

int main() {
    // 从 x = 1 开始寻找满足所有条件的最小士兵数
    for (int x = 1;; x++) {
        if (x % 5 == 1 && x % 6 == 5 && x % 7 == 4 && x % 11 == 10) {
            printf("%d\n", x);
            break;
        }
    }
    return 0;
}

七.寻找鞍点

#include <stdio.h>

int main() {
    int n;
    int arr[6][6]; // 定义矩阵，最大为 6×6 的方阵（根据题目要求）

    // 读取矩阵的阶数 n
    scanf("%d", &n);

    // 输入 n × n 矩阵元素
    for (int i = 0; i < n; i++) {  // 遍历每一行
        for (int j = 0; j < n; j++) {  // 遍历每一列
            scanf("%d", &arr[i][j]); // 读取矩阵元素
        }
    }

    // 遍历矩阵的每一行，寻找潜在的鞍点
    for (int i = 0; i < n; i++) {
        // 找到当前行的最大值
        int row_max = arr[i][0];    // 假设当前行的第一个元素是最大值
        int max_columns[6], max_count = 0; // 存储当前行最大值所在的列索引；初始化计数器
        max_columns[max_count++] = 0; // 记录第一个最大值的列索引

        for (int j = 1; j < n; j++) {  // 从当前行的第 2 列开始遍历
            if (arr[i][j] > row_max) { // 如果发现更大的值
                row_max = arr[i][j];  // 更新最大值
                max_count = 0; // 清空之前记录的列索引
                max_columns[max_count++] = j; // 记录新的最大值所在列
            } else if (arr[i][j] == row_max) { // 如果发现等于当前最大值的元素
                max_columns[max_count++] = j; // 记录其列索引（并列最大值）
            }
        }

        // 验证每个并列最大值是否满足列最小的条件
        for (int k = 0; k < max_count; k++) { // 遍历当前行所有并列最大值的列索引
            int col = max_columns[k]; // 获取当前列索引
            int is_saddle_point = 1; // 假设当前列索引对应的元素是鞍点

            // 检查该列是否满足“列最小”的条件
            for (int r = 0; r < n; r++) { // 遍历当前列的所有元素
                if (arr[r][col] < row_max) { // 如果发现列中有比当前元素更小的值
                    is_saddle_point = 0; // 标记该元素不是鞍点
                    break; // 退出列检查循环
                }
            }

            // 如果满足鞍点条件
            if (is_saddle_point) {
                printf("%d %d", i, col); // 输出鞍点的行、列索引
                return 0; // 程序结束（题目保证最多只有一个鞍点）
            }
        }
    }

    // 如果遍历完整个矩阵仍未找到鞍点
    printf("NONE"); // 输出 "NONE"
    return 0; // 程序正常结束
}

八.删除重复字符并排序

#include<stdio.h>

// 函数：检查字符是否在数组中，返回0表示已存在，返回1表示不存在
int is_unique(char chs[], char c, int len) {
    for (int i = 0; i < len; i++) {
        if (chs[i] == c) {
            return 0; // 字符已存在
        }
    }
    return 1; // 字符不存在
}

int main() {
    char chs[80];     // 存储原始输入字符数组
    char unique[80];  // 存储去重后的字符数组
    int len = 0;      // 原始数组长度
    int count = 0;    // 去重后的数组长度

    // 输入字符，直到遇到换行符结束
    char c = getchar();
    while (c != '\n') {
        chs[len++] = c;  // 将字符存入原始数组
        c = getchar();   // 继续读取下一个字符
    }

    // 去重操作：将不重复的字符添加到 `unique` 数组中
    for (int i = 0; i < len; i++) {
        if (is_unique(unique, chs[i], count)) {
            unique[count++] = chs[i];  // 将当前字符加入去重后的数组
        }
    }

    // 排序操作：对 `unique` 数组按 ASCII 码升序排序
    for (int i = 0; i < count - 1; i++) {
        for (int j = i + 1; j < count; j++) {
            if (unique[i] > unique[j]) {  // 交换两个字符的位置
                char temp = unique[i];
                unique[i] = unique[j];
                unique[j] = temp;
            }
        }
    }

    // 输出结果
    for (int i = 0; i < count; i++) {
        putchar(unique[i]);  // 输出去重并排序后的字符
    }

    return 0;
}

九. 字符串转换成十进制整数

#include <stdio.h>
#include <ctype.h>

int main() {
    char str[100];          // 用于存储输入的字符串
    char newstr[100];       // 用于存储去掉非十六进制字符后的字符串
    int is_fushu = 0;       // 标志变量，用来判断是否为负数
    int index = 0;          // 用于记录新字符串的索引位置

    // 输入字符串，直到遇到 '#' 为止。scanf("%[^#]", str) 表示读取除了 '#' 以外的字符。
    scanf("%[^#]", str);   // 将输入的字符串保存到 str 中，遇到 '#' 停止读取

    // 过滤非十六进制字符并转换字符
    for (int i = 0; str[i] != '\0'; i++) {  // 遍历整个输入字符串
        // 判断是否为负号，且是第一个字符
        if (str[i] == '-' && index == 0) {
            is_fushu = 1;  // 如果是负号并且在第一个字符位置，则标记为负数
        }
        // 如果是十六进制数字字符（数字0-9，字母A-F或a-f）
        else if (isxdigit(str[i])) {
            // 将字符转换为大写并保存到 newstr 中，避免大小写字母混淆
            newstr[index++] = toupper(str[i]);
        }
    }

    long long num = 0;    // 用 long long 类型存储最终的十进制结果
    newstr[index] = '\0';  // 添加字符串结束符，确保 newstr 以 '\0' 结束

    // 将十六进制字符串转换为十进制数
    for (int i = 0; newstr[i] != '\0'; i++) {  // 遍历整个十六进制字符串
        num *= 16;  // 将当前数字左移一位（相当于乘以16），为下一位的加法腾出空间
        // 判断字符是否是数字 '0' - '9'
        if (newstr[i] >= '0' && newstr[i] <= '9') {
            num += newstr[i] - '0';  // 将字符转换为对应的数字并加到 num 上
        }
        // 判断字符是否是字母 'A' - 'F'
        else if (newstr[i] >= 'A' && newstr[i] <= 'F') {
            num += newstr[i] - 'A' + 10;  // 'A' - 'F' 转换为 10 - 15
        }
    }

    // 如果是负数标志为1，则将 num 取负
    if (is_fushu) {
        num = -num;  // 将结果变为负数
    }

    // 输出最终的十进制数字
    printf("%lld", num);  // 输出转换后的十进制数

    return 0;  // 程序正常结束
}

为什么要乘以 16?

当逐位解析一个十六进制数并将其转为十进制时，乘以 16 是为了将当前数值“进位”，与十进制系统中乘以 10 是为了进位的逻辑一致。

示例：逐位处理

假设要将 2F 转为十进制：

初始化十进制结果为 0。
从左到右解析：
1. 读取 2，当前结果是 0×16+2=2
2. 读取 F，当前结果是 2×16+15=47

`isxdigit` 函数详解

功能

isxdigit 用于检查一个字符是否是有效的十六进制数字字符。

参数

c：需要检查的字符（一般是 unsigned char，或者 EOF）。

返回值

返回非零值（通常为 1），如果 c 是十六进制数字字符。
返回 0，如果 c 不是十六进制数字字符。

有效的十六进制字符

数字字符：'0' - '9'
字母字符：'a' - 'f' 和 'A' - 'F'

`toupper` 函数详解

功能

toupper 用于将小写字母转换为对应的大写字母。如果字符不是小写字母，则原样返回。

参数

c：需要转换的字符（一般是 unsigned char，或者 EOF）。

返回值

如果 c 是小写字母，返回对应的大写字母。
如果 c 不是小写字母，返回 c 本身。

转换规则

'a' - 'z' 转换为 'A' - 'Z'
其他字符保持不变。

十.黑洞数

#include <stdio.h>

int main() {
    int num;
    scanf("%d", &num);  // 输入三位数

    // 初始化序号
    int count = 1;

    // 如果输入的数是495，特殊处理
    if (num == 495) {
        int digits[3];
        // 将数字分解为三个单独的数字
        digits[0] = num / 100;        // 百位
        digits[1] = (num / 10) % 10; // 十位
        digits[2] = num % 10;        // 个位

        // 如果三位数字相同，直接输出特例结果
        if (digits[0] == digits[1] && digits[1] == digits[2]) {
            printf("%d: %d - %d = %d", count, num, num, 0); // 495的特殊情况，三位相同
            return 0;  // 结束程序
        }

        // 如果不是三位相同，将数字按升序排列
        for (int i = 0; i < 2; i++) {
            for (int j = i + 1; j < 3; j++) {
                if (digits[i] > digits[j]) { // 比较大小并交换
                    int temp = digits[i];
                    digits[i] = digits[j];
                    digits[j] = temp;
                }
            }
        }

        // 形成最小数和最大数
        int minNum = digits[0] * 100 + digits[1] * 10 + digits[2];  // 最小数
        int maxNum = digits[2] * 100 + digits[1] * 10 + digits[0];  // 最大数

        // 计算差值
        num = maxNum - minNum;

        // 输出当前步骤
        printf("%d: %d - %d = %d\n", count, maxNum, minNum, num);

        // 增加计数器
        count++;
    } else {
        // 如果输入不是495，进入常规处理循环
        while (num != 495) { // 重排求差直到得到495
            // 将数字分解为三个单独的数字
            int digits[3];
            digits[0] = num / 100;        // 百位
            digits[1] = (num / 10) % 10; // 十位
            digits[2] = num % 10;        // 个位

            // 将数字按升序排列
            for (int i = 0; i < 2; i++) {
                for (int j = i + 1; j < 3; j++) {
                    if (digits[i] > digits[j]) { // 比较大小并交换
                        int temp = digits[i];
                        digits[i] = digits[j];
                        digits[j] = temp;
                    }
                }
            }

            // 形成最小数和最大数
            int minNum = digits[0] * 100 + digits[1] * 10 + digits[2];  // 最小数
            int maxNum = digits[2] * 100 + digits[1] * 10 + digits[0];  // 最大数

            // 计算差值
            num = maxNum - minNum;

            // 输出当前步骤
            printf("%d: %d - %d = %d\n", count, maxNum, minNum, num);

            // 增加计数器
            count++;
        }
    }

    return 0;
}

十一.最长对称子串

#include <stdio.h>
#include <string.h>

// 扩展中心法：从指定的中心位置 (left, right) 向两边扩展，找到回文子串的最大长度
int expandAroundCenter(char *s, int left, int right, int len) {
    // 当左指针大于等于 0，右指针小于字符串长度，并且左右字符相等时，继续扩展
    while (left >= 0 && right < len && s[left] == s[right]) {
        left--;  // 向左扩展
        right++; // 向右扩展
    }
    // 返回回文子串的长度。由于循环结束时，left 和 right 已经超出了回文串的两端，因此用 right - left - 1
    return right - left - 1;
}

int main() {
    // 输入字符串
    char str[1000];
    
    // 计算字符串的长度
    int len = strlen(str);

    // 用于记录当前找到的最长回文子串的长度
    int maxLen = 0;

    // 遍历每个字符，作为中心点进行扩展查找回文子串
    for (int i = 0; i < len; i++) {
        // 扩展奇数长度回文：以当前字符 str[i] 为回文中心，左右扩展
        int len1 = expandAroundCenter(str, i, i, len);  // 以 str[i] 为中心，回文长度

        // 扩展偶数长度回文：以当前字符和下一个字符 str[i] 和 str[i+1] 为回文中心，左右扩展
        int len2 = expandAroundCenter(str, i, i + 1, len);  // 以 str[i] 和 str[i+1] 为中心，回文长度
        
        // 更新最大回文子串长度
        maxLen = (len1 > maxLen) ? len1 : maxLen;  // 选择 len1 和 maxLen 中的较大值
        maxLen = (len2 > maxLen) ? len2 : maxLen;  // 选择 len2 和 maxLen 中的较大值
    }

    // 输出最长回文子串的长度
    printf("%d\n", maxLen);

    return 0;
}