算法（Algorithm）：计算机解题的基本思想方法和步骤。算法的描述：是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据（输入什么数据、输出什么结果）、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法
### C语言中的常见算法
#### 一、计数、求和、求阶乘等简单算法
这类算法在C语言编程中十分常见，主要用于处理简单的数学运算。这些算法的基础是循环结构，通过设置适当的循环变量来控制算法的执行过程。
**算法特点**：
- **循环变量的初始化**：确定循环变量的初始值是非常重要的，这直接影响到算法的正确性。
- **循环条件**：定义好循环的终止条件或结束条件，确保循环能够按照预期结束。
- **计算逻辑**：在循环体内进行相应的计算操作。
**示例**：使用数组统计特定范围内随机整数的个位数字出现次数。
```c
void main() {
int a[101], x[11], i, p;
for (i = 0; i <= 11; i++) {
x[i] = 0;
}
for (i = 1; i <= 100; i++) {
a[i] = rand() % 100;
printf("%4d", a[i]);
if (i % 10 == 0) printf("\n");
}
for (i = 1; i <= 100; i++) {
p = a[i] % 10;
if (p == 0) p = 10;
x[p] = x[p] + 1;
}
for (i = 1; i <= 10; i++) {
p = i;
if (i == 10) p = 0;
printf("%d, %d\n", p, x[i]);
}
printf("\n");
}
```
**解释**：
- 使用数组`a[101]`存储产生的100个随机整数。
- 数组`x[11]`用于统计个位上数字出现的次数。
- 循环生成随机数，并使用模运算提取个位数字。
- 根据个位数字更新对应位置的计数器。
#### 二、求两个整数的最大公约数和最小公倍数
求最大公约数(GCD)和最小公倍数(LCM)是算法中的经典问题。这里采用辗转相除法求最大公约数。
**算法步骤**：
1. 设两数为`m`和`n`，且`m > n`。
2. `m`除以`n`得到余数`r`。
3. 如果`r == 0`，则`n`即为最大公约数；否则继续步骤4。
4. 更新`m = n`，`n = r`，重复步骤2。
**示例**：求两个整数的最大公约数和最小公倍数。
```c
void main() {
int n, m, r, nm, t;
printf("please input two numbers:\n");
scanf("%d, %d", &m, &n);
nm = n * m;
if (m < n) {
t = n;
n = m;
m = t;
}
r = m % n;
while (r != 0) {
m = n;
n = r;
r = m % n;
}
printf("最大公约数: %d\n", n);
printf("最小公倍数: %d\n", nm / n);
}
```
**解释**：
- 输入两个整数`m`和`n`。
- 如果`m < n`，交换两个数的位置。
- 使用辗转相除法计算最大公约数。
- 计算最小公倍数`nm / n`。
#### 三、判断素数
素数是指只能被1和自身整除的大于1的正整数。判断一个数是否为素数可以采用试除法。
**算法步骤**：
1. 将待判断的数作为被除数。
2. 从2开始到该数的平方根范围内依次尝试除尽。
3. 如果不能被任何数整除，则该数为素数。
**示例**：判断一个数是否为素数。
```c
int prime(int m) {
int i, k;
k = sqrt(m);
for (i = 2; i <= k; i++) {
if (m % i == 0) return 0;
}
return 1;
}
```
**解释**：
- 使用平方根技巧减少除法次数。
- 返回1表示是素数，返回0表示不是素数。
#### 四、验证哥德巴赫猜想
哥德巴赫猜想指出，所有大于2的偶数都可以表示为两个素数之和。此猜想至今未被证明也未被证伪。
**算法步骤**：
1. 输入一个偶数`x`。
2. 从3开始到`x / 2`之间寻找两个素数`n1`和`n2`，使得`n1 + n2 = x`。
3. 如果找到满足条件的`n1`和`n2`，则验证成功。
**示例**：验证哥德巴赫猜想。
```c
int prime(int m) {
int i, k;
k = sqrt(m);
for (i = 2; i <= k; i++) {
if (m % i == 0) break;
}
if (i >= k) return 1;
else return 0;
}
void main() {
int x, i;
printf("please input an even number (>= 6):\n");
scanf("%d", &x);
if (x < 6 || x % 2 != 0) {
printf("data error!\n");
} else {
for (i = 2; i <= x / 2; i++) {
if (prime(i) && prime(x - i)) {
printf("%d + %d\n", i, x - i);
printf("验证成功!\n");
break;
}
}
}
}
```
**解释**：
- 输入一个大于等于6的偶数。
- 使用`prime()`函数检查`n1`和`n2`是否为素数。
- 如果找到符合条件的`n1`和`n2`，输出结果。
#### 五、排序
排序算法是计算机科学中最基础也是最重要的算法之一。常用的排序算法有冒泡排序、插入排序、选择排序等。
**示例**：冒泡排序算法。
```c
void bubbleSort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
```
**解释**：
- 冒泡排序通过重复遍历要排序的列表，比较每对相邻项，如果顺序错误就把它们交换过来。
- 每次遍历后最大的元素会“浮”到数组的末尾。
- 外层循环控制排序轮数，内层循环进行元素之间的比较和交换。
以上这些算法都是C语言编程中的基础算法，掌握这些算法有助于更好地理解和编写复杂的程序。
