文章目录
- 一、迭代算法简介
- 二、设计工作步骤
-
三、迭代--递推法
- 题目及运行
-
四、迭代--倒推法
- 题目及运行
- 五、总结
前言
算法语言--C语言
一、迭代算法简介
迭代算法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。
迭代算法一般用于数值的计算，是读者早就熟悉的一种算法策略，程序设计语言课程中所学的累加、累乘都是迭代算法策略的基础应用。
二、设计工作步骤
利用迭代算法策略求解问题，设计工作主要有3步：
1、确定迭代模型
根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。当然这样的迭代关系，最终会迭代出求解的目标。
2、建立迭代关系式
递推数学模型一般是代下标的字母，算法设计中要将其转换为“循环不变式”----迭代关系式。
迭代关系式就是一个直接或间接地不断由旧值推出新值的表达式，存储新值的变量称为迭代变量。
3、对迭代过程进行控制
确定在什么时候结束迭代过程，是迭代算法时必须考虑的问题。
三、迭代--递推法
1、递推法简介
递推算法是迭代算法的最基本的表现形式。
一般来讲，一种简单的递推方式，是从小规模的问题推解出大规模问题的一种方式，也称其为：正推。如累加过程就是在前n-1项和的基础上推出前n项的和，递推公式为：Sn = Sn-1 + An。
由于无需保留每次的累加结果，这样递推公式就抽象成了s = s + a。
2-1递推举例
1、兔子繁殖问题：一对兔子，从出生后第三个月起每个月都生一对小兔子，小兔子长到第三个月后又每个月又生一对小兔子，求第10个月有多少对兔子？
为了寻找题目的规律。最基本的分析方法之一就是 “枚举”，也就是将各种不同的情况一一列举出来，从中发现解决问题的方法。
下列表格中：加法前面代表老兔子，加法后面下划线的代表出生的新兔子。
| 1月 | 2月 | 3月 | 4月 | 5月 | 6月 | 7月 |
| 1 | 1 | 1+1=2 | 2+1=3 | 3+2=5 | 5+3=8 | 8+5=13 |
通过列举我们发现，新出生的兔子数量刚好是上上个月的兔子总数，老兔子数量是上个月的兔子总数。到此我们发现这个数列就是著名的斐波那契数列！
f(n) = f(n-1) + f(n-2);
2-1代码实现
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a=1,b=1;
int c,i;
for(i=3;i<=10;i++){
c = a+b;//第三个月为前两个月之和
a = b;//之后的第一个月
b = c;//之后的第二个月
}
printf("10个月后的总兔子为：%d",c);
return 0;
}
2-2递推举例
辗转相除法求两个正整数的最大公约数。（a=18,b=12）
不妨设两个整数a>b且a除以b余c，不难看出a，b的最大公约数与b，c的最大公约数相同！同样方法推出b，c的最大公约数等于c和b%c的最大公约数。直到推解出两个数据相除的余数为0时，除数即为所求的最大公约数！
2-2代码实现
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a = 18,b = 12;
int c = a%b;//c为余数
while(c>0){
a = b;//小数替换成大数
b = c;//余数替换成小数
c = a%b;//继续求余数
}
printf("最大公约数为：%d",b);//最大公约数为较小的数
return 0;
}
四、迭代--倒推法
1、倒推法简介
所谓倒推法是对某些特殊问题所采取的违反通常习惯的，从后向前推解问题的方法。
2-1倒推举例
猴子吃桃问题：一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第10天只有一个桃子了，求原有多少个桃子？
数学模型：a10 = 1, a10 = a9/2-1 -- >a9 = (a10+1)*2,a8 = (a9+1)*2.........
递推公式：ai = (ai+1)*2 (i = 9,8,7...)
2-1代码实现
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a = 1;
int i;
for(i=9;i>0;i--){
a = (a+1)*2;
}
printf("原有的桃子数为：%d",a);
return 0;
}
2-2倒推举例
穿越沙漠问题：用一辆吉普车穿越2000公里的沙漠。吉普车的总装油量为600加仑，耗油率为1加仑/公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。
2-2代码实现
#include <stdio.h>
#include <stdlib.h>
int main()
{
int dis,k,oil;
dis=600;k=1;oil=2000;
do{
k=k+1;
dis = dis+600/(2*k-1);
oil = 600*k;
}while(dis<2000);
oil=600*(k-1)+(2000-dis)*(2*k-1);
printf("%d %d %d\n",k,oil,dis);
return 0;
}
五、总结
迭代算法主要是：在已知的基础上推出下一轮，反复循环！
主要步骤：1、确定是迭代的模型，2、建立迭代关系式，3、对迭代过程进行控制文章来源：https://www.toymoban.com/news/detail-708468.html
多算多敲多理解！文章来源地址https://www.toymoban.com/news/detail-708468.html
到了这里，关于算法设计与分析--迭代算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
