C语言刷题笔记3(7)

7.1 数组处理斐波那契数列

题目描述:用数组来处理Fibonacci数列并输出。

输入:一个不超过40且大于2的整数n，表示需要处理并输出的Fibonacci数个数。

输出:输出前n个Fibonacci数，每行输出5个值，按每12位向右对齐的方式输出。请注意不要在第一行前输出一个空行，并请注意行尾输出换行。

#include <stdio.h>int main() {int fib[50];fib[0] = 1;fib[1] = 1;int n = 0;scanf("%d", &n);if(n>2&&n<=40){for (int i = 2; i < n; i++) {fib[i] = fib[i - 1] + fib[i - 2];}for (int i = 0; i < n; i++) {if (i % 5 == 0 && i != 0) {printf("\n");}printf("%12d", fib[i]);}printf("\n");}return 0;
}

在C语言中定义数组时,数组元素的个数不能出现变量,只能出现常量或常量表达式.下面这种写法就会报错:

    int n;scanf("%d", &n);int arr[n];

7.2 冒泡排序法

题目描述:用起泡法（冒泡排序）对n个整数排序并输出从小到大排序后的结果。

输入:第一行包含一个大于0且不超过200的正整数n，表示以下有n个整数需要被排序。第二行有n个用空格隔开的整数。

输出:输出从小到大排序后的结果，每个整数后输出一个空格。请注意行尾输出换行。

#include <stdio.h>int main() {int arr[50];int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &arr[i]);}for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

7.3 取矩阵最大值

题目描述:读入一个3×4的矩阵，求出矩阵中的最大值，并输出最大值所在的行号和列号。

输入:共有3行，每行有4个用空格隔开的整数，表示矩阵的具体内容。

输出:在一行内输出三个用空格隔开的整数，分别表示矩阵中的最大值、最大值所在的行号和最大值所在的列号。行号和列号均从0开始排列。请注意行尾输出换行。

#include <stdio.h>int main() {int matrix[3][4];for (int i = 0; i < 3; i++) {for (int j = 0; j < 4; j++) {scanf("%d", &matrix[i][j]);}}int maxValue = matrix[0][0];int maxRow = 0;int maxCol = 0;for (int i = 0; i < 3; i++) {for (int j = 0; j < 4; j++) {if (matrix[i][j] > maxValue) {maxValue = matrix[i][j];maxRow = i;maxCol = j;}}}printf("%d %d %d\n", maxValue, maxRow, maxCol);return 0;
}

7.6 统计空格

题目描述:输入一行字符，统计并输出其中有多少个单词，单词之间用空格分隔。

输入:只有一行，保证只包含可见字符，且此行的所有字符数不超过100。

输出:一个整数，表示输入的一行字符中共有多少个单词。请注意行尾输出换行。

#include <stdio.h>int main() {char str[101];int i = 0;char c;while ((c = getchar()) != '\n' && i < 100) {str[i++] = c;}str[i] = '\0';int num = 0;int inWord = 0;for (i = 0; str[i] != '\0'; i++) {if (str[i] != ' ' && !inWord) {inWord = 1;num++;}else if (str[i] == ' ') {inWord = 0;}}printf("%d\n", num);return 0;
}

7.9 选择排序

题目描述:用选择法（选择排序）对10个整数从小到大排序，并按顺序输出。

输入:一行内有10个用空格隔开的整数。

输出:在一行中输出从小到大排序完毕的10个整数，在每个整数后输出一个空格。请注意行尾输出换行。

#include <stdio.h>int main() {int arr[10];for (int i = 0; i < 10; i++) {scanf("%d", &arr[i]);}for (int i = 0; i < 9; i++) {int minIndex = i;for (int j = i + 1; j < 10; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}for (int i = 0; i < 10; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

7.11 数组插入

题目描述：给定一个从小到大有序的整数序列，将其保存至数组。另外输入一个整数，将其插入至这个数组中并保持数组有序。

输入：第一行有一个正整数n，表示原始的整数序列长度为n，保证n不超过50。
第二行有n个整数，表示原始的整数序列，保证这个序列是从小到大给出的。
第三行有一个整数，表示需要插入的整数。

输出：在一行中输出n+1个整数，表示完成插入的整数序列。每个整数后输出一个空格。
请注意行尾输出换行。

#include <stdio.h>
int main() {int n;scanf("%d", &n);int arr[50];for (int i = 0; i < n; i++) {scanf("%d", &arr[i]);}int num;scanf("%d", &num);int i;for (i = 0; i < n; i++) {if (num < arr[i]) {break;}}for (int j = n; j > i; j--) {arr[j] = arr[j - 1];}arr[i] = num;for (int k = 0; k <= n; k++) {printf("%d ", arr[k]);}printf("\n");return 0;
}

7.14鞍点——分治思想

题目描述：找出一个二维数组中的所有鞍点，即该位置上的元素在该行中最大但是在该列中最小。需要注意有可能鞍点不存在，此时需要输出“NO”。

输入：第一行有2个正整数n和m，表示二维数组的高度和宽度，保证n和m均不超过50。
之后的n行每行有m个用空格隔开的整数，表示二维数组对应位置的值。

输出：当鞍点存在时，将每个鞍点的信息在一行内输出，输出三个用空格隔开的整数，分别为鞍点元素的值以及其所在的行号和列号，有多个鞍点时，按照元素读入的顺序进行输出。当鞍点不存在时，在一行内输出“NO”。
请注意不需要输出引号，并请注意行尾输出换行。

样例输入 

2 3
23 83 15
99 98 97

样例输出 

83 0 1

#include <stdio.h>int main() {int n, m;scanf("%d %d", &n, &m);int arr[50][50];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {scanf("%d", &arr[i][j]);}}int andian = 0;for (int i = 0; i < n; i++) {int rowMax = arr[i][0];int colIndex = 0;for (int j = 1; j < m; j++) {if (arr[i][j] > rowMax) {rowMax = arr[i][j];colIndex = j;}}int isColMin = 1;for (int k = 0; k < n; k++) {if (arr[k][colIndex] < rowMax) {isColMin = 0;break;}}if (isColMin) {printf("%d %d %d\n", rowMax, i, colIndex);andian = 1;}}if (!andian) {printf("NO\n");}return 0;
}

7.15 折半查找

1. 基本原理

• 折半查找（也叫二分查找）是一种在有序数组中查找特定元素的高效算法。它的基本思想是每次将查找区间缩小一半，直到找到目标元素或者确定目标元素不存在。
• 假设我们有一个有序数组arr，数组元素是按从大到小（或从小到大）排列的，我们要查找目标元素target。
• 我们首先定义两个指针，low和high，分别指向数组的开头和结尾。在查找过程中，计算中间元素的索引mid=(low + high)/2（为了防止整数溢出，更安全的写法是mid = low+(high - low)/2）。

2. 查找过程

• 比较中间元素arr[mid]和目标元素target：
• 如果arr[mid]==target，说明找到了目标元素，查找结束。
• 如果arr[mid]>target（对于从大到小排序的数组），因为数组是有序的，所以目标元素应该在中间元素的左侧。此时，我们更新high = mid - 1，将查找区间缩小到low到mid - 1这个范围，然后继续在新的区间进行下一轮查找。
• 如果arr[mid]<target（对于从大到小排序的数组），目标元素应该在中间元素的右侧。我们更新low = mid+1，将查找区间缩小到mid + 1到high这个范围，然后继续下一轮查找。
• 这个过程不断重复，每次都将查找区间缩小一半，直到low大于high，这意味着目标元素不在数组中，查找结束。

7.16 使用getchar逐行输入二维数组加密

题目描述：给出一篇文章，共有3行文字，每行有最多80个字符。要求分别统计出其中英文大写字母、小写字母、数字、空格以及其他字符的个数。

输入：共有3行，表示输入的文章。

输出：在一行中输出文章中的英文大写字母、小写字母、数字、空格以及其他字符的个数，用空格隔开。请注意行尾输出换行。

样例输入 

I am a program.
This is the second line!
And this is the last line........

样例输出

3 47 0 12 10

#include <stdio.h>
int main() {char lines[3][81];int da = 0, xiao = 0, num = 0, space = 0, other = 0;int i = 0, j = 0;while (i < 3) {char ch = getchar();if (ch == '\n') {lines[i][j] = '\0';i++;j = 0;}else {lines[i][j++] = ch;}}for (i = 0; i < 3; ++i) {j = 0;while (lines[i][j] != '\0') {char ch = lines[i][j];if (ch >= 'A' && ch <= 'Z') {da++;}else if (ch >= 'a' && ch <= 'z') {xiao++;}else if (ch >= '0' && ch <= '9') {num++;}else if (ch == ' ') {space++;}else {other++;}j++;}}printf("%d %d %d %d %d\n", da, xiao, num, space, other);return 0;
} 

7.17 找规律

题目描述：输出如下图案：

* * * * *

 * * * * *

  * * * * *

   * * * * *

    * * * * *

请使用字符数组的方式完成本题。

#include <stdio.h>int main() {char pattern[5][15];for (int i = 0; i < 5; i++) {int starCount = 0;for (int j = 0; j < 15; j++) {if (starCount < 5 && (i == j || ((j - i) > 0 && (j - i) % 2 == 0))) {pattern[i][j] = '*';starCount++;} else {pattern[i][j] = ' ';}}pattern[i][14] = '\0';}for (int i = 0; i < 5; i++) {printf("%s\n", pattern[i]);}return 0;
}

7.18getchar加密一维数组

题目描述：有一行电文，已经按照如下规则译成了密码：
A->Z a->z
B->Y b->y
C->X c->x
… …
… …
即第1个字母变换成第26个字母，第i个字母变换成第(26-i+1)个字母。非字母字符不变。给定一段密码，请将其译成原文并输出。

输入：一行密码，包含各种可见字符，保证长度不超过100。

输出：如题目描述中密码翻译规则译出的原文。
请注意行尾输出换行。

样例输入 

R zn z kiltizn.

样例输出 

I am a program.

#include<stdio.h>
int main() {char arr[200];int i = 0;char ch='a';while (ch != '\n') {ch = getchar();if (ch == '\n') {arr[i] = '\0';break;}else {arr[i++] = ch;}}for (int n = 0; n < i; n++) {if (arr[n] >= 'a' && arr[n] <= 'z') {arr[n] = 'a' + ('z' - arr[n]);}if (arr[n] >= 'A' && arr[n] <= 'Z') {arr[n] = 'A' + ('Z' - arr[n]);}}for (int n = 0; n < i; n++) {printf("%c", arr[n]);}return 0;
}

改进：使用gets函数进行输入（字符数组中有空格）

#include<stdio.h>
int main() {char arr[200];gets(arr);int i = 0;while (arr[i] != '\0'){i++;}for (int n = 0; n < i; n++) {if (arr[n] >= 'a' && arr[n] <= 'z') {arr[n] = 'a' + ('z' - arr[n]);}if (arr[n] >= 'A' && arr[n] <= 'Z') {arr[n] = 'A' + ('Z' - arr[n]);}}for (int n = 0; n < i; n++) {printf("%c", arr[n]);}printf("\n");return 0;
}

7.19 strcat函数功能实现

题目描述：读入两个字符串，并将其连接起来的新字符串输出。要求不要使用strcat函数。

输入：两行不包含空格的字符串。保证每个字符串的长度不超过100。

输出：将第2行的字符串连接在第1行字符串之后的新字符串。请注意行尾输出换行。

样例输入 

I am a program.
This is a program.

样例输出

I am a program.This is a program.

#include<stdio.h>
int main() {char s1[500], s2[500];int i = 0, j = 0;gets(s1);gets(s2);while (s1[i] != '\0') {i++;}while (s2[j] != '\0') {s1[i++] = s2[j++];}s1[i] = '\0';printf("%s\n", s1);return 0;
}

7.20 strcmp函数功能的实现

题目描述：读入两个字符串s1和s2，比较这两个字符串。若s1>s2，输出一个正数；若s1=s2，输出0；若s1<s2，输出一个负数。输出的非零值应该是相比较的两个字符串第一个不相同位置的字符ASCII差值，例如”And”和”Aid”比较，根据第2个字符的比较结果，应输出5。
要求不要使用strcpy和strcmp函数。

输入：两行字符串。保证每个字符串的长度不超过100。

输出：两个字符串的比较结果。请注意行尾输出换行。

样例输入

I am a program.
I am not a program.

样例输出 

-13

#include <stdio.h>
int main() {char s1[200], s2[200];gets(s1);gets(s2);int i = 0;while (s1[i] != '\0' && s2[i] != '\0') {if (s1[i] != s2[i]) {printf("%d\n", s1[i] - s2[i]);return 0;}i++;}if (s1[i] == '\0' && s2[i] == '\0') {printf("0\n");}else if (s1[i] == '\0') {printf("%d\n", s1[i] - s2[i]);}else {printf("%d\n", s1[i] - s2[i]);}return 0;
}

7.21 strcpy函数功能实现

题目描述：读入两个字符串s1和s2，将s2中的全部字符复制到字符数组s1中去。要求不使用strcpy函数，并保证字符串末尾的’\0’标识符同时被赋值。

输入：两行字符串s1和s2。保证每个字符串的长度不超过100。

输出：将s2赋值至s1后的s1对应的字符串。请注意行尾输出换行。

样例输入 

I am a program.
I am not a program.

样例输出 

I am not a program.

#include <stdio.h>
int main() {char s1[200], s2[200];gets(s1);gets(s2);int i = 0,j = 0,n = 0;while (s1[i] != '\0') {i++;}while (s2[j] != '\0') {s1[n] = s2[j];n++;j++;}s1[n] = '\0';printf("%s\n", s1);return 0;
}

8.1弦截法求方程的根

输入：两个用空格隔开的实数x1和x2，表示弦截法的区间两端。保证x1< x2，且区间内一定有解。

输出：使用弦截法计算出的方程f(x)=x3-5x2+15x-80=0的根。小数点后保留4位小数。请注意行尾输出换行。

样例输入 

2 6

样例输出 

5.0000

#include <stdio.h>
#include <math.h>
double f(double x) {return x * x * x - 5 * x * x + 16 * x - 80;
}
int main() {double x1, x2;scanf("%lf %lf", &x1, &x2);while (f(x1) * f(x2) >= 0) {if (f(x1) == 0) {printf("%.4lf\n", x1);return 0;}else if (f(x2) == 0) {printf("%.4lf\n", x2);return 0;}else {x1 -= 1;x2 += 1;}}double x;do {x = x2 - f(x2) * (x2 - x1) / (f(x2) - f(x1));double fx = f(x);if (fabs(fx) < 1e-6) {break;}if (fx * f(x1) > 0) {x1 = x;}else {x2 = x;}} while (1);printf("%.4lf\n", x);return 0;
}

8.2递归

题目描述：有n个人坐在一起。问第n个人多少岁，他说比第n-1个人大k岁。问第n-1个人多少岁，他说比第n-2个人大k岁。问第n-2个人多少岁，他说比第n-3个人大k岁。问第n-3个人多少岁，他说比第n-4个人大k岁。这样问下去，除去第1个人，所有人都说比编号小1的人大k岁，而第1个人说自己a岁。使用函数递归的方法计算并输出第n个人的年龄。

输入：3个用空格隔开的正整数n、k、a，分别为题目描述中代表的含义。输入保证n、k、a均不超过100。

输出：第n个人的年龄。请注意行尾输出换行。

#include <stdio.h>int age(int n, int k, int a) {if (n == 1) {return a;} else {return age(n - 1, k, a) + k;}
}int main(){int n, k, a;scanf("%d %d %d", &n, &k, &a);printf("%d\n", age(n, k, a));return 0;
}

8.4汉诺塔递归实现

题目描述：用递归的方法输出Hanoi（汉诺）塔问题的解决步骤。汉诺塔问题描述如下：
古代有一个梵塔，塔内有3个座A、B、C。初始时A座上有n个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这n个盘子从A座移动到C座，但是每次只允许移动一个盘子，而且在移动过程中在3个座上需要始终保持大盘在下，小盘在上，在移动过程中可以使用B座。
要求使用递归的方法模拟并输出移动的步骤。

输入：一个正整数n，保证n不超过5。

输出：解决n个盘子的汉诺塔问题的步骤。
每一步一行，在这一行中输出将盘子从一个座移动至另一个的过程。例如移动A座顶部的盘子至C座，则输出A->C。
请注意行尾输出换行。

#include <stdio.h>
void hannuo(int n, char from, char to, char aux) {if (n == 1) {printf("%c->%c\n", from, to);}else {hannuo(n - 1, from, aux, to);printf("%c->%c\n", from, to);hannuo(n - 1, aux, to, from);}
}
int main() {int n;scanf("%d", &n);hannuo(n, 'A', 'C', 'B');return 0;
}

8.8 选择排序法

题目描述：用选择法（选择排序）对数组中的n个整数从小到大排序，并输出排序后的n个整数。要求使用将数组传至函数进行排序的方法。

输入：第一行有一个整数n，表示整数的个数。保证n不超过100。第二行有n个用空格隔开的整数。

输出：在一行内输出从小到大排序完成的整数，每个整数后输出一个空格。请注意行尾输出换行。

样例输入 

10
1 3 5 7 9 10 6 4 2 8

样例输出 

1 2 3 4 5 6 7 8 9 10 

#include <stdio.h>
void f(int arr[], int n) {int i, j, minIndex, temp;for (i = 0; i < n - 1; i++) {minIndex = i;for (j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}if (minIndex != i) {temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}
}int main() {int arr[200], n,i;scanf("%d", &n);for ( i = 0; i < n; i++) {scanf("%d", &arr[i]);}f(arr, n);for (i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

8.9二维数组查找最大值

题目描述：给定一个3×4的矩阵，求出所有元素中的最大值。要求使用将数组传至函数进行操作的方法。

输入：共有3行，每行有4个用空格隔开的整数。

输出：输出矩阵中的最大值。请注意行尾输出换行。

样例输入 

12 33 15 32
92 39 1 10
23 63 22 43

样例输出 

92

#include <stdio.h>
int find(int arr[][4], int rows) {int max = arr[0][0];for (int i = 0; i < rows; i++) {for (int j = 0; j < 4; j++) {if (arr[i][j] > max) {max = arr[i][j];}}}return max;
}
int main() {int str[3][4];for (int i = 0; i < 3; i++) {for (int j = 0; j < 4; j++) {scanf("%d", &str[i][j]);}}int max = find(str, 3);printf("%d\n", max);return 0;
}

9.2 两个宏嵌套——海伦公式

题目描述：利用海伦公式，其中a、b、c为三角形的三边。要求通过定义两个带参数的宏，一个用来求s，另一个用来求area，完成三角形的面积计算。

输入三个用空格隔开的正整数，分别表示三角形的a、b、c三边。输入保证三角形不退化。

输出三角形的面积，小数点后保留3位小数。请注意行尾输出换行。

#include<stdio.h>
#include<math.h>
#define s(a,b,c)(a/2.0+b/2.0+c/2.0)
#define area(a,b,c)(sqrt(s(a,b,c)*(s(a,b,c) - a)*(s(a,b,c) - b)*(s(a,b,c) - c)))
int main() {int x, y, z;scanf("%d%d%d", &x, &y, &z);printf("%.3f\n", area(x, y, z));return 0;
}