一,迭代与递推
1)迭代法也称“辗转法”,是一种不断用变量的旧值递推出新值的解决问题的方法。迭代算法一般用于数值计算。迭代法应该是我们早已熟悉的算法策略,程序设计语言课程中所学的累加、累乘都是迭代算法策略的基础应用。例如:斐波那契数列
例子:兔子繁殖问题
一对兔子从出生后第三个月开始,每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死,一月份抱来一对刚出生的小兔子,问一年中每个月各有多少只兔子。
•问题分析
因为一对兔子从出生后第三个月开始每月生产一对小兔子,则每月新下生的小兔子的对儿数显然由前两个月的小兔子的对儿数决定。则繁殖过程如下:
一月 二月 三月四月 五月 六月……
1 11+1=2 2+1=3 3+2=5 5+3=8 ……
•数学建模(斐波那契数列)
y1=y2=1,yn=yn-1+yn-2,n=3,4,5,……
2)倒推法的概念
•倒推法:是对某些特殊问题所采用的违反通常习惯的,从后向前推解问题的方法。例如,在不知前提条件的情况下,由结果倒过来推解它的前提条件,从而求解问题。又如,由于存储的要求,而必须从后向前进行推算。另外,在对一些问题进行分析或建立数学模型时,从前向后分析问题感到比较棘手,而采用倒推法,则问题容易理解和解决。
例子:穿越沙漠问题
用一辆吉普车穿越1000公里的沙漠。吉普车的总装油量为500加仑,耗油率为1加仑/公里。由于沙漠中没有油库,必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠,应在什么地方建油库,以及各处的贮油量。
•问题分析
贮油点问题要求要以最少的耗油量穿越沙漠,即到达终点时,沙漠中的各临时油库和车的装油量均为0。这样只能从终点开始向前倒着推解贮油点和贮油量。
•数学模型
根据耗油量最少目标的分析,下面从后向前分段讨论。
第一段长度为500公里且第一个加油点贮油为500加仑。
第二段中为了贮备油,吉普车在这段的行程必须有往返。
下面讨论怎样走效率高:
1)首先不计方向这段应走奇数次(保证最后向前走)。
2)每次向前行进时吉普车是满载。
3)要能贮存够下一加油点的贮油量,路上耗油又最少。
•综上分析
从终点开始分别间隔
500,500/3,500/5,500/7,……(公里)设立贮油点,直到总距离超过1000公里。每个贮油点的油量为500,1000,1500,……。
•终极解释:
1)从终点推,到终点必须正好没油,且中途加油站也耗光。所以距离终点500公里有一个500加仑储油点
2)第二个,要想把第一个储油点,储500加仑,最少需要三次,且汽车需要满载油,则距离为500*2 - 3X=500 得距离X=500/3 储油量:500*2=1000
3)第三个,距离计算公式:500*3 -5x =1000 -->x=500/7 储油量:3*500=1500
二,分治与递归
1)分治法在每一层递归上都有三个步骤:
(1)划分:把输入的问题实例划分为若干子问题,尽量使子问题的规模大致相同。
(2)求解:若子问题规模较小而容易被解决则直接解,否则,当问题的规模大于某个预定义的阀值时,求解步骤由个递归调用组成。
(3)合并:将各个子问题的解合并为原问题的解。
分治和递归的关系
分治与递归像一对孪生兄弟,经常同时应用在算法设计之中。因为从分治法的算法框架中可以看出,分治法设计出的算法一般是一个递归过程。
2)二分治的基本思想
在算法设计中每次一个问题分解成的子问题个数一般是固定的,每个子问题的规模也是平均分配的。当每次都将问题分解为原问题规模的一半时,称为二分治法。二分法是分治法较常用的分解策略,数据结构课程中的折半查找、归并排序等算法都是采用此策略实现的。
例题:二分治法求最大、最小值
#include <iostream>
using namespace std;
void FindMaxAndMin(int a[], int begin, int end, int* pmax,int* pmin)
{
if(end-begin <=1) //递归出口
{
if(a[begin] <= a[end])
{
*pmax = a[end];
*pmin = a[begin];
return;
}
else
{
*pmin = a[end];
*pmax = a[begin];
return;
}
}
int min1, min2, max1, max2;
int mid = (begin+end)/2;
FindMaxAndMin(a, begin, mid, &max1, &min1);
FindMaxAndMin(a,mid+1, end,&max2, &min2);
*pmin = min1 < min2 ? min1 : min2;
*pmax = max1 < max2 ? max2 : max1;
}
int main()
{
int a[] = {1,2,3,4,5,9,41,8,12,20,98};
int max,min;
FindMaxAndMin(a,0,10,&max,&min);
cout<<"the max num is:"<<max<<", the min num is:"<<min<<endl;
return 0;
}
例题:线性时间求数组,第k小元素
•
问题分析
这个问题可以通过排序来解决,最好的排序算法的复杂性是O(n*log(n)),下面我们要利用分治法,找到复杂性为O(n)的算法。但这个问题不能用简单的二分法分解成完全独立、相似的两个子问题。因为在选出分解后第一组的第k小的数据和第二组的第k小的数据,不能保证在这两个数据之一是原问题的解。
•
例如:
求一组数据中的第2小数据:(-2,11,-4,13,-5,-3)
若用二分法将实例中的数据分解为两组(-2,11,-4),(13,-5,-3),第一个子问题的解是-2,第二个子问题的解是-3,两个子问题的解不能简单地得到原问题的解。原问题的解是-4。
•
解决方法
方案一,新建一个k数组,对k数组排序,然后每次将最大数跟余下数组中每一个数比较,“余下数”小则删除k数组中最大,然后将“余下数”插入k数组,遍历到最后,k数组中最大数为所求。
方案二,分治算法求解(******)
#include <iostream>
using namespace std;
class QuickSort
{
private:
int *arr;//待排序数组
int length;//数组长度
public:
//构造函数
QuickSort(int length)
{
arr=new int[length+1];
this->length=length;
}
//交换函数
void swap(int i,int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
//输入数据
void input()
{
int i=1;
cout<<"please input 10 number:"<<endl;
while(i<=length)
{
cin>>arr[i];
++i;
}
}
//输出函数
void display()
{
int i=1;
while(i<=length)
{
cout<<arr[i]<<" ";
++i;
}
cout<<endl;
}
//随机化划分函数
int randomizedPartition(int start,int end)
{
int i=start+rand()%(end-start+1);//产生随机数start~end
swap(i,start);//交换元素
return partition(start,end);//返回划分位置
}
//划分函数
int partition(int start,int end)
{
int key=arr[start];//arr[start]作为划分关键字
int i=start;
int j=end;
//交换元素
while(true)
{
while(arr[i]<key)
{
++i;
}
while(arr[j]>key)
{
--j;
}
//寻找两个可以交换的元素
//如果j<=i,说明arr[j]在左半域,arr[i]在右半域,划分完成,在j,j+1之间划分
if(i<j)
{
swap(i,j);
++i;
--j;
}
else
{
return j;
}
}
}
//快速排序
void quickSort(int start,int end)
{
if(start<end)//起码有2个元素
{
int middle;
middle=randomizedPartition(start,end);
quickSort(start,middle);
quickSort(middle+1,end);
}
}
//线性时间选择第k小元素
int randomizedSelect(int start,int end,int k)
{
if(start==end)//如果有两个元素的段被随机化划分之后,则应该有此等式成立,即找到了第K小元素
{
return arr[start];
}
else
{
int middle=randomizedPartition(start,end);
int left=middle-start+1;
if(k<=left)//
{
return randomizedSelect(start,middle,k);//在划分后的左侧寻找第k小元素
}
else
{
return randomizedSelect(middle+1,end,k-left);//在划分后的右侧寻找第k-左段长度小的元素
}
}
}
};
int main()
{
QuickSort test(10);
test.input();
test.display();
cout<<test.randomizedSelect(1,10,3)<<endl;//寻找第3小元素
test.quickSort(1,10);//随机化快速排序
test.display();//打印结果
return 0;
}
分享到:
相关推荐
递归小结 •优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的...◦通过Cooper变换、反演变换能将一些递归转化为尾递归,从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善,但其适用范围有限。
枚举算法,递归与分治策略,递归与迭代的思想、求最大值最小值、线性查找、二分查找与冒泡排序以及选择与交换排序、插入和希尔排序。本课程除了强调经典的算法理论和模型,亦兼顾编程实践能力。力图使得学员面对复杂...
算法设计是一件非常困难的工作,经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外,为了更简洁的形式设计和藐视算法,在算法设计时又常常采用递归技术,用...
递归和分治递归定义直接或间接调用自身基本思想递推回归与迭代的区别递归与栈的关系分治分治算法就是具有递归结构的算法使用条件当问题规模缩小到一定程度时可以快速解决问
1、理解和实现递归、迭代、分治、贪婪等算法思想; 2、学会应用试探法和模拟方法解决问题; 3、掌握一些常见的数据结构,了解它们的特性和应用场景; 4、提高解决问题的能力,培养算法思维。 5、在实际编程中,这些...
常用的算法设计技术有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法和动态规划法等。另外,为了以更简洁的形式设计和描述算法,在设计算法时常采用递归技术,用递归描述算法。 本讲中,主要介绍分治法。
1、二叉树三种遍历的非递归算法 16 1.先序遍非递归算法 16 2.中序遍历非递归算法 17 3.后序遍历非递归算法 18 4.层次遍历算法 19 2、线性表 20 4、串 23 5、多维数组和广义表 24 6、树与二叉树 24 7、图 26 8、查找...
用递推算法 迭代算法 公式法计算求第N个Fibonacci数,计算机能算出最大Fibonacci时N的值,计算1分钟内能计算几个Fibonacci,用公式法计算Fibonacci,当出现错误时,N为多少。
枚举算法,递归与分治策略,递归与迭代的思想、求最大值最小值、线性查找、二分查找与冒泡排序以及选择与交换排序、插入和希尔排序。本课程除了强调经典的算法理论和模型,亦兼顾编程实践能力。力图使得学员面对复杂...
枚举算法,递归与分治策略,递归与迭代的思想、求最大值最小值、线性查找、二分查找与冒泡排序以及选择与交换排序、插入和希尔排序。本课程除了强调经典的算法理论和模型,亦兼顾编程实践能力。力图使得学员面对复杂...
第4章基本的算法策略4.1迭代算法 4.1.1递推法 4.1.2倒推法 4.1.3迭代法解方程 4.2蛮力法 4.2.1枚举法 4.2.2其他范例 4.3分治算法 4.3.1分治算法框架 4.3.2二分法 4.3.3二分法变异 4.3.4其他分治方法 4.4贪婪算法 ...
迭代法、穷举搜索法、递推法、递归、回溯法、贪婪法、分治法、动态规划法
大学教师的课件,主要内容包含:算法概述、递归与分治策略、算法分析、算法基本工具、贪心算法、迭代-蛮力、回溯法、递归与分治策略等,经典算法。其中还包含背包问题、活动安排问题、币种统计问题等。
枚举算法,递归与分治策略,递归与迭代的思想、求最大值最小值、线性查找、二分查找与冒泡排序以及选择与交换排序、插入和希尔排序。本课程除了强调经典的算法理论和模型,亦兼顾编程实践能力。力图使得学员面对复杂...
枚举算法,递归与分治策略,递归与迭代的思想、求最大值最小值、线性查找、二分查找与冒泡排序以及选择与交换排序、插入和希尔排序。本课程除了强调经典的算法理论和模型,亦兼顾编程实践能力。力图使得学员面对复杂...
本文档给出算法设计与分析中的迭代、穷举搜索、递归分治、回溯等常用的算法设计思想及经典题例。
算法设计是一件非常困难的工作,经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外,为了更简洁的形式设计和描述算法,在算法设计时又常常采用递归技术,用...
第2章 递归与分治策略 2.1 速归的概念 2.2 分治法的基本思想 2.3 二分搜索技术 2.4 大整数的乘法 2.5 Strassen矩阵乘法 2.6 棋盘覆盖 2.7 合并排序 2.8 快速排序 2.9 线性时间选择 2.10 最接近点对问题 2.11 循环赛...
我们发现,与对递归式进行迭代相比,画出递归树后出错的可能性小了。但是,我们也指出了递归树的最佳用途,即利用它来产生猜测,再利用替代方法对猜测进行验证。 ·快速排序(第7.1节)中用到的划分方法与期望线性...
枚举算法,递归与分治策略,递归与迭代的思想、求最大值最小值、线性查找、二分查找与冒泡排序以及选择与交换排序、插入和希尔排序。本课程除了强调经典的算法理论和模型,亦兼顾编程实践能力。力图使得学员面对复杂...