首页 > 代码库 > 经典算法宝典——迭代思想(二)(1)

经典算法宝典——迭代思想(二)(1)

迭代法(Iteration)也称“辗转法”,是一种不断用变量的旧值递推出新值的解决问题的方法。

说明:

迭代算法一般用于数值计算,比如累加、累乘都是迭代算法策略的基础应用。

利用迭代算法策略求解问题,设计工作主要有3步。

(1)确定迭代模型

根据问题描述,分析得出前一个(或几个)值与其下一个值的迭代关系数学模型。当然这样的迭代关系,最终会迭代出求解的目标。确定迭代模型是解决迭代问题的关键。

(2)建立迭代关系式

递推数学模型一般是带下标的字母,算法设计中要将其转化为“循环不变式”——迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式,存储新值的变量称为迭代变量。迭代关系式的建立是迭代算法设计的主要工作。

(3)对迭代过程进行控制

确定在什么时候结束迭代过程,是设计迭代算法时必须考虑的问题,迭代过程的控制通常可分为两种情况:一种是已知或可以计算出来所需迭代次数,这时可以构建一个固定次数的循环来实现对迭代过程的控制。另一种是所需的迭代次数无法确定,需要分析出迭代过程的结束条件,甚至于要考虑有可能得不到目标解(迭代不收敛)的情况,避免出现迭代过程的死循环。

总结:

迭代模型是通过小规模问题的解逐步求解大规模问题的解,表面看正好与递归算法设计相反,但也找到了大规模问题与小规模问题的关系。

1、递推法

(1)兔子繁殖问题

一对兔子从出生后第三个月开始,每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死,一月份抱来一对刚出生的小兔子,问1年中每个月各有多少只兔子。

数学建模:

y(1) = y(2) = 1,y(n) = y(n-1) + y(n-2),n = 3, 4, 5...到此发现这个数列就是著名的斐波那契数列。当n趋于无穷时,斐波那契数列前后两项的商(y(n-1) / y(n))趋于黄金分割数0.618。

算法实现:

#include<stdio.h>

void main()
{
	int i, c, a = 1, b = 1;
	printf("%d\n", a);
	printf("%d\n", b);
	
	for(i = 1; i <= 10; i++) 
	{
		c = a + b;
		printf("%d\n", c);
		a = b;
		b = c;
	}
}

结果输出:


总结:

递推(Recursion)算法是迭代算法的最基本的表现形式。一般来讲,一种简单的递推方式,是从小规模的问题推解出大规模问题的一种方法,也称其为“正推”。


2、倒推法

(1)猴子吃桃问题

一只小猴子摘了若干桃子,每天吃现有桃子的一半多一个,到第10天时就只有一个桃子了,求原有多少个桃子?

数学模型:

a(i) = (1 + a(i+1)) * 2, i = 9, 8, 7, 6, ..., 1

说明:

a(i)表示第i天的桃子数。

算法实现:

#include<stdio.h>

void main()
{
	int i, a = 1;
	for(i = 9; i >= 1; i--)
		a = (a+1) * 2;

	printf("%d\n", a);
}
结果输出:

总结:

倒推法(Inverted Recursion)是对某些特殊问题所采用的违反通常习惯的,从后向前推解问题的方法。