迭代法、数学归纳法、递归

故事

古印度国王舍罕酷爱下棋,他打算重赏国际象棋的发明人宰相西萨·班·达依尔。这位聪明的大臣指着象棋盘对国王说:“陛下,我不要别的赏赐,请您在这张棋盘的第一个小格内放入一粒麦子,在第二个小格内放入两粒,第三小格内放入给四粒,以此类推,每一小格内都比前一小格加一倍的麦子,直至放满 64 个格子,然后将棋盘上所有的麦粒都赏给您的仆人我吧!”

迭代法

简单来说,其实就是不断地用旧的变量值,递推计算新的变量值

计算机语言中的循环即是迭代的最好应用

#include <stdio.h>

typedef unsigned long ulong;
long get_wheat_num(int grid_num)
{
	int 	i;
	ulong 	sum = 0;	// 麦粒总数

	// 第一个格子的麦粒数
	ulong 	num_in_grid = 1;
	
	// 1格时麦粒总数
	sum += num_in_grid;

	// 因为已经计算出了第一格,所以只需要迭代 grid_num - 1 次
	for (i = 1; i < grid_num; i++)
	{
		num_in_grid *= 2;
		sum += num_in_grid;
	}

	return sum;
}

int main(int argc, char **argv)
{
	int 	grid_num;
	ulong 	sum;

	grid_num = atoi(argv[1]);
	sum = get_wheat_num(grid_num);

	printf("girds:%d grains:%lu\n", grid_num, sum);

	return 0;
}
[root@izbp1irxwqt7ei21awv6wvz ccc]# ./a.out 1
girds:1 grains:1
[root@izbp1irxwqt7ei21awv6wvz ccc]# ./a.out 2
girds:2 grains:3
[root@izbp1irxwqt7ei21awv6wvz ccc]# ./a.out 64
girds:64 grains:18446744073709551615

迭代法具体应用

1.求数值的精确或者近似解。典型的方法包括二分法(Bisection method)和牛顿迭代法(Newton’s method)

2.在一定范围内查找目标值。典型的方法包括二分查找


数学归纳法

数学归纳法(Mathematical Induction, MI)是一种数学证明方法,通常被用于证明某个给定命题在整个(或者局部)自然数范围内成立

上节我们提到,在棋盘上放麦粒的规则是,第一格放一粒,第二格放两粒,以此类推,每一小格内都比前一小格多一倍的麦子,直至放满 64 个格子。我们假想一下自己穿越到了古印度,正站在国王的身边,看着这个棋盘,你发现第 1 格到第 8 格的麦子数分别是:1、2、4、8、16、32、64、128。

根据这个观察,我们是不是可以大胆假设,前 n 个格子的麦粒总数就是 2^n−1

一般步骤可以是这样:

1.证明基本情况(通常是 n=1 的时候)是否成立

2.假设 n = k−1 成立,再证明 n=k 也是成立的(k 为任意大于 1 的自然数)

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

typedef unsigned long ulong;
typedef unsigned int uint;


int main(int argc, char **argv)
{
	int 	grid_num;
	ulong 	sum;

	grid_num = atoi(argv[1]);
	sum = (ulong)(pow(2, grid_num) - 1);

	printf("girds:%d grains:%lu\n", grid_num, sum);

	return 0;
}
[root@izbp1irxwqt7ei21awv6wvz ccc]# ./a.out 1
girds:1 grains:1
[root@izbp1irxwqt7ei21awv6wvz ccc]# ./a.out 2
girds:2 grains:3
[root@izbp1irxwqt7ei21awv6wvz ccc]# ./a.out 3
girds:3 grains:7


递归

当我们需要记录很多中间变量或者状态时,最好使用递归

计算编程递归中,每次嵌套调用都会让函数体生成自己的局部变量

假设有 1,2,5,10 四个数字,求任意个数和为10的所有可能情况比如 (5,5) (10) (2,2,2,2,2)

即限定总和的情况下,求所有可能的加和方式

#include <stdio.h>
#include <stdlib.h>



typedef struct {
	int 	*arr;
	int 	cur;
} dl_arr;

int 	arr_g[] = {1, 2, 5, 10, 0};
int 	num_g;



void dump(dl_arr *arr)
{
	int i;
	printf("[");
	for (i = 0; i < arr->cur; i++) {
		printf("%d,", arr->arr[i]);
	}
	printf("]\n");
	return;

}

dl_arr *arr_copy(dl_arr *arr)
{
	int 	i;
	dl_arr 	*new_arr;

	new_arr = malloc(sizeof(dl_arr));
	new_arr->arr = calloc(sizeof(int), 100);
	new_arr->cur = arr->cur;

	for (i = 0; i < arr->cur; i++) {
		new_arr->arr[i] = arr->arr[i];
	}

	return new_arr;
}

void get(int num, dl_arr *arr)
{
	int 	i;
	dl_arr 	*new_arr;

	if (num == 0) {
		num_g++;
		dump(arr);
		return;
	}

	if (num < 0)
		return ;

	for (i = 0; i < 4; i++) {
		new_arr = arr_copy(arr);
		new_arr->arr[new_arr->cur++] = arr_g[i];
		get(num - arr_g[i], new_arr);
	}

	//全部复制完毕,释放
	free(arr);
}

int main()
{
	dl_arr 	*arr;
	arr = calloc(sizeof(dl_arr), 1);
	
	get(10, arr);

	printf("%d\n", num_g);

	return 0;
}
[root@izbp1irxwqt7ei21awv6wvz ccc]# ./a.out 
[1,1,1,1,1,1,1,1,1,1,]
[1,1,1,1,1,1,1,1,2,]
[1,1,1,1,1,1,1,2,1,]
[1,1,1,1,1,1,2,1,1,]
[1,1,1,1,1,1,2,2,]
[1,1,1,1,1,2,1,1,1,]
...
[5,2,1,1,1,]
[5,2,1,2,]
[5,2,2,1,]
[5,5,]
[10,]
129




上一篇: 余数
下一篇: 排列组合
作者邮箱: 203328517@qq.com