联机算法:
在任意时刻,算法对要操作的数据只读入(扫描)一次,一旦被读入并处理,它就不需要在被记忆了。而在此处理过程中算法能对它已经读入的数据立即给出相应子序列问题的正确答案。具有这种特性的算法叫做联机算法(on-line algorithm)。
该算法仅需要常量空间并以线性时间运行,因此联机算法几乎是完美的算法。
递归调用的准则:
1. 基准情形。 不用递归就能求解的情形。
2.不断推进。
3.合成效益法则。 在一次求解中,对同一示例,切勿在不同递归中 做重复行工作。 如下:
求factorial
方法一:
long factorial(int n)
{
if(n <= 1)
return 1;
else
return n*factorial(n-1);
}
方法二:
long factorial(int n)
{
if(n <= 1)
return 1;
else
return factorial(n-1)+ factorial(n-2);
}
方法二中 factorial(n-1)+ factorial(n-2) 做重复性工作,不符合第三条准则。
测试代码,求一个 序列中 最大的子序列之和
#include <iostream>
#include <vector>
using namespace std;
//递归调用 解决
int max(int x, int y, int z)
{
int m = x>y? x:y;
int n = m>z? m:z;
return n;
}
int MaxSub(const vector<int>& a, int left, int right)
{
if (left == right) //基准情形
{
if (a[left]>0)
return a[left];
else
return 0;
}
int mid = (left+right)/2;
int maxLeftSum = MaxSub(a, left, mid);//左右子序列递归
int maxRightSum = MaxSub(a, mid+1, right);
int maxLeftBorder = 0, tmpLeft = 0;
for (int i = mid; i >= left; i--)
{
tmpLeft += a[i];
if (tmpLeft > maxLeftBorder)
{
maxLeftBorder = tmpLeft;
}
}
int maxRightBorder = 0, tmpRight = 0;
for (int i = mid+1; i <= right; i++)
{
tmpRight += a[i];
if (tmpRight > maxRightBorder)
{
maxRightBorder = tmpRight;
}
}
return max(maxLeftSum, maxRightSum, maxRightBorder+maxLeftBorder);
}
//联机算法
int Max_sub(const vector<int>& a, int left, int right)//left right 分别指下标
{
int tmp = 0, maxSum = 0;
for (int i = left; i <= right; i++)
{
tmp += a[i];
if (tmp > maxSum)
maxSum = tmp;
else if (tmp < 0) //必定遇到负数
tmp = 0;
}
return maxSum;
}
int main()
{
int arr[ ] = {1, 4, 3, 5, -1 , -4, 5, 6,-2};
vector<int> a(arr, arr+9);;
cout<<MaxSub(a, 0, a.size()-1)<<endl;
cout<<Max_sub(a, 0, a.size()-1);
return 0;
}
通过上例可看出
联机算法
优点:占用空间少,所用时间少
缺点:不宜设计,正确性不易观察,同时附加保留信息较少
递归:
优点:思路清晰
缺点:占用大量的栈
联机算法不仅在 代码量上 远远 少于递归的方法,同时 在占用空间(递归占用大量的栈)和运行时间上都远远优于递归的方法。
分享到:
相关推荐
.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法
递归调用详解,代码详细讲解了如递归调用以及调用中应该注意的一些问题
递归算法与循环算法的分析
算法进阶 01 递归调用 打表
递归调用详解,分析递归调用的详细过程[参考].pdf
18.递归算法与递归算法应用.ppt
牛顿迭代算法与递归算法的概念和区别 很有帮助
递归算法详解递归算法详解递归算法详解递归算法详解
计算机算法与分析试验递归调用快速排序 全排列仅供参考
函数递归调用堆栈分析.doc
快速选择非递归与递归算法实现
3、递归下降分析法实验设计思想及算法 为G的每个非终结符号U构造一个递归过程,不妨命名为U。 U的产生式的右边指出这个过程的代码结构: (1)若是终结符号,则和向前看符号对照, 若匹配则向前进一个符号;否则出错。 ...
3、C语言规定,程序中各函数之间 (A)A) 既允许直接递归调用也允许间接递归调用 B) 不允许直接递归调用也不允许间接递归调用 C) 允许直接递归调用不允许间接递归调用 D) 不允许直接递归调用允许间接递归调用
在找钱算法中运用递归,程序简单明了。可以进一步帮你理解递归的好处。
VB6.0过程的递归调用:在调用一个子程序或函数的过程中又出现直接或间接调用该子程序或函数本身,称为过程的递归调用。
这是一个相当齐全的算法课件 里面包含了很多的内容和实例 使我们上课时老师的课件 希望对大家有帮助
一个简单的递归调用方法,实现目录树的调用,.NET项目
C语言递归调用举例,可直接复制粘贴。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。...
在一个2的k次方乘以2的k次方个方格的棋盘中,恰有一个方格与其他方格不同为特殊方格,棋盘称为特殊棋盘,用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
递归与分治策略是学习计算机算法设计与分析的基础,掌握了这样的思想才能良好地高效率地去解决一些问题