不会飞的章鱼

熟能生巧,勤能补拙;念念不忘,必有回响。

数学归纳法:搞定循环与递归的钥匙

任务

实现一个可变循环层数的程序。

编码

我们可以一开始假设,有一个函数,是实现 5 层循环打印的程序,那么它会循环 n 次,每次调用一个实现 4 层循环打印的程序。

1
2
3
4
5
6
7
8
9
10
11
//代码框架
int print_loop(int k, int n) {
//代表 k 层循环的程序,然后循环 n 次,每次调用一个 k - 1 层循环的程序。
if (k == 0) {
// 打印一行
}
for (int i = 1; i <= n; i++) {
print_loop(k - 1, n);
}
return;
}

完善程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int arr[100];
/*
入参:
total_k,代表了一共有多少层循环,这个参数是为了方便我们最后确定循环输出的上界
*/
void print_loop(int k, int n, int total_k) {
if (k == 0) {
for (int i = total_k; i >= 1; i--) {
if (i != total_k) printf(" ");
printf("%d", arr[i]);
}
printf("\n");
return ;
}
for (int i = 1; i <= n; i++) {
arr[k] = i;
print_loop(k - 1, n, total_k);
}
return ;
}

思考题

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>

int fib(int n) {
if (n == 1 || n == 2) return 1;
return fib(n - 1) + fib(n - 2);
}

int main() {
int n;
scanf("%d", &n);
printf("%d\n", fib(n));
return 0;
}

上面这段程序中,fib 函数是求菲波那契数列第 n 项值的函数。菲波那契数列的定义如下:

根据如上内容,你需要完成两个小的思考题:

1,请将上述菲波那契数列求解的程序从递归程序,改成循环程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int fib(n) {
// 递归写法
/*
if (n == 1 || n == 2) return 1; // 终止条件 -- 数学归纳法step1
return fib(n-1) + fib(n-2); // 处理过程 -- 数学归纳法step2
*/

// 循环写法
int f1 = 1, f2 = 1, f3;
for (int i = 3; i <= n; i++) {
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;
}

2,请将上述递归程序的代码和数学归纳法中的步骤做一一对应。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>

int fib(int n) {
if (n == 1 || n == 2) return 1; //数学归纳法中所谓的 k0​ 成立,这一步保证了,fib 函数计算的第 1 项 和 第 2 项的斐波那契函数值一定是正确的。
return fib(n - 1) + fib(n - 2); //数学归纳法中的第二步,假设 ki​ 成立,证明 ki+1​ 也成立。
//最后结论,这个fib 递归函数设计是正确的。
}

int main() {
int n;
scanf("%d", &n);
printf("%d\n", fib(n));
return 0;
}

小结

  • 数学归纳法中重要的两部分,一是要边界条件成立,二是证明转移过程成立。
  • 程序设计最重要的是正确性,递归函数的正确性可以利用数学归纳法来保证。
  • 递归程序设计中的重要的两部分:边界条件和处理过程。所谓边界条件,就是当递归函数中的参数等于多少的时候,可以直接返回的条件。处理过程呢,就是设计程序过程,处理递归调用的返回结果,根据递归调用的返回结果,得到本函数的结果。
------ 本文结束------
如果本篇文章对你有帮助,可以给作者加个鸡腿~(*^__^*),感谢鼓励与支持!