汉诺塔问题
约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。
- 分析
移动n个盘子到终点，总的来说分三步：
1、把n-1个盘子移动到暂放区
2、把最大的移到终点
3、把暂放区的n-1个盘子移到终点
很明显是一个递归问题
用f(n, a, b, c)表示要求解的问题，其含义是有a、b、c三根棒和n只盘，且这n个盘叠放在a棒上，依次叠放为大盘在下，小盘在上。借助b棒将n只盘从a棒移到c棒上。每次只移一个盘，在移动时保持大盘在下，小盘在上。
将f(n, a, b, c)转化分解为如下三个子问题：
①f(n - 1, a, c, b)，即将a棒上面的n-1个盘移到b棒，借助c棒。
②move(a, c)，即将在a棒上的一个盘移到c棒。
③f(n - 1, b, a, c)，即将b棒上面的n-1个盘移到c棒，借助a棒。
编程实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<stdio.h>
#include<stdlib.h>
void move(char from, char to) {
printf("%c-->%c\n", from, to);
}
void hanoit(int n, char a, char b, char c) {
if(n == 1){
move(a, c);
} else {
hanoit(n - 1, a, c, b);
move(a, c);
hanoit(n - 1, b, a, c);
}
}
int main() {
int m;
scanf("%d", &m);
hanoit(m, 'A', 'B', 'C');
return 0;
}
求最小公倍数和最大公约数
1、求最小公倍数：
最小公倍数=两整数的乘积 / 最大公约数
2、最大公约数：
辗转相除法:
① a%b得余数c
② 若c=0，则b即为两数的最大公约数
③ 若c≠0，则a=b，b=c，再回去执行①
例如求27和15的最大公约数过程为：
27÷15 余1215÷12余312÷3余0因此，3即为最大公约数
编码：
1 | #include<stdio.h> |
合并数组
给定两个元素个数不超过20的整数数组a和b，要求将a和b合并成一个新数组。合并规则：如果一个元素在两个数组中同时出现，则需在合并后的数组中去掉该元素；对于只在一个数组中重复出现的元素，合并后只保留一个。合并后按照从小到大的顺序将新数组输出（测试数据保证不会出现合并后无数据的情况）
输入：
5 1 4 1 2 9
7 2 3 1 5 7 6 5
输出：
3 4 5 6 7 9
分析：
首先是合并数组，除去相同的数字，然后是对此数组进行排序。对于相同的数字，在输出时只输出一个（可能比事先对输入数组去重简单一些）
编程：
1 | #include<stdio.h> |