那天闲来无聊,突然从网上看到一google面试题,比较有意思,于是整理了下先写下来,算法大概是这样的:
T(0) = T(1) = 1;
T(2) = 2;
T(N) = T(N-1) + T(N-2) + T(N-3);
算法前提不考虑溢出,于是我写下了最常规的递归算法:
public class Tribonacci {
public static int method(int n) {
if( 0 == n || 1 == n) {
return 1;
} else if( 2 == n) {
return 2;
} else {
return method(n - 1) + method(n - 2) + method(n - 3);
}
}
}
但是仔细琢磨了下,当n >= 3 事, 条件进入最后的else,这里其实进行了多次递归,其中 在递归n-1的时候其实已经计算出了n-2、n-3, 所以这个算发,很显然重复计算了后便的method(n-2)、method(n-3),所以这里可以在计算method(n-1)的时候记住n-2、与n-3的值,百般思索后写出了如下的程序:
public class Tribonacci {
public static int method2(int n) {
if( n < 0) {
return 0;
}
if( 0 == n || 1 == n ) {
return 1;
}
if( 2 == n ) {
return 2;
}
ReferenceInt mid = new ReferenceInt();
ReferenceInt last = new ReferenceInt();
int max_subset = sub_recursion( n, mid, last);
return max_subset + mid.getValue() + last.getValue();
}
public static int sub_recursion(int n, ReferenceInt mid, ReferenceInt last) {
if ( 3 == n ) {
mid.setValue(1);
last.setValue(1);
return 2;
} else {
ReferenceInt temp = new ReferenceInt();
//这里做了参数移位,原来的last变为n-1的mid, 启用新的变量带出n-1的last
mid.setValue(sub_recursion( n - 1, last, temp));
return mid.getValue() + last.getValue() + temp.getValue();
}
}
/**
* 由于Java讨厌的自动封包机制,这里自己定义一个int的包装类型
*/
class ReferenceInt {
private int value;
public ReferenceInt(int value) {
this.value = value;
}
public ReferenceInt() {
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public String toString() {
return String.valueOf(this.value);
}
}
}
算法的思想就是在计算n-1的时候,用参数带出n-2与n-3的值,去掉重复的计算,减少递归的次数,达到优化算法的效果,这里我简单说一下:
T(N) = T(N-1) + T(N-2) + T(N-3);
mas_sub mid last
话说一个哥们,用list来缓存n-2 -> 0 之间的结果,随说有点吃内存,不过看起来比上边这个算法,好看多了,呵呵,都说是G内存的时代了,我一听乐了,不过也算是懒人有懒办法吧,贴出来大家看下:
public class Tribonacci {
public static List<Integer> list = new ArrayList<Integer>();
static {
list.add(1);
list.add(1);
list.add(2);
}
public static int method3(int n) {
if(n<list.size()){
return list.get(n).intValue();
}else{
for(int i=list.size();i<=n;i++){
list.add(method3(i - 1) + method3(i - 2) + method3(i - 3));
}
return method3(n);
}
}
}
呵呵,下边测试一下3个算法的性能吧:
public class Tribonacci {
public static void main(String[] args) {
final int TEST_NUMBER = 35;
long start = System.currentTimeMillis();
System.out.print(Tribonacci.method1(TEST_NUMBER));
long end = System.currentTimeMillis();
System.out.println("->method1(" + TEST_NUMBER + ") cost:" + (end-start) + "ms");
start = System.currentTimeMillis();
System.out.print(Tribonacci.method2(TEST_NUMBER));
end = System.currentTimeMillis();
System.out.println("->method2(" + TEST_NUMBER + ") cost:" + (end-start) + "ms");
start = System.currentTimeMillis();
System.out.print(Tribonacci.method3(TEST_NUMBER));
end = System.currentTimeMillis();
System.out.println("->method3(" + TEST_NUMBER + ") cost:" + (end-start) + "ms");
}
}
1132436852->method1(35) cost:10468ms
1132436852->method2(35) cost:0ms
1132436852->method3(35) cost:0ms
分享到:
相关推荐
.net递归算法优化源码案例
c#扫雷。递归算法扫雷。分为3个等级。待完善的项目
【GA-ELMAN回归预测】基于遗传算法优化递归神经网络神经网络实现数据预测 【GA-ELMAN回归预测】基于遗传算法优化递归神经网络神经网络实现数据预测 【GA-ELMAN回归预测】基于遗传算法优化递归神经网络神经网络实现...
•缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 •解决方法:在递归算法中消除递归调用,使其转化为非递归算法。 ◦采用一个用户定义的栈来模拟系统的递归调用工作栈...
循环递归, 算法设计,PPT内容包括3.1循环与递归 3.3 算法优化基本技巧3.2 算法与数据结构 3.4 优化算法的数学模型
基于优化递归算法的分子量分解问题.doc
递归优化算法: 某人手中有2000元钱,通过计算选择一种存钱方案,使得钱存入银行20年后得到的利息最多 (假定银行对超过存款期限的那一部分时间不付利息)。为了得到最多的利息,存入银行的钱 应在到期时马上取出来,...
数学建模-基于递归算法的建筑外表面光伏电池布局优化分析与设计.zip
代码实现了二叉树的非递归的中序遍历,在VC++6.0环境下调试通过
智能优化算法优化递归神经网络ELMAN预测系列程序定制或科研合作方向: 4.4.1 遗传算法GA/蚁群算法ACO优化ELMAN 4.4.2 粒子群算法PSO/蛙跳算法SFLA优化ELMAN 4.4.3 灰狼算法GWO/狼群算法WPA优化ELMAN 4.4.4 鲸鱼算法...
智能优化算法优化递归神经网络ELMAN预测系列程序定制或科研合作方向: 4.4.1 遗传算法GA/蚁群算法ACO优化ELMAN 4.4.2 粒子群算法PSO/蛙跳算法SFLA优化ELMAN 4.4.3 灰狼算法GWO/狼群算法WPA优化ELMAN 4.4.4 鲸鱼算法...
智能优化算法优化递归神经网络ELMAN预测系列程序定制或科研合作方向: 4.4.1 遗传算法GA/蚁群算法ACO优化ELMAN 4.4.2 粒子群算法PSO/蛙跳算法SFLA优化ELMAN 4.4.3 灰狼算法GWO/狼群算法WPA优化ELMAN 4.4.4 鲸鱼算法...
智能优化算法优化递归神经网络ELMAN预测系列程序定制或科研合作方向: 4.4.1 遗传算法GA/蚁群算法ACO优化ELMAN 4.4.2 粒子群算法PSO/蛙跳算法SFLA优化ELMAN 4.4.3 灰狼算法GWO/狼群算法WPA优化ELMAN 4.4.4 鲸鱼算法...
Matlab技术的使用教程、使用方法、使用技巧、使用注意事项、使用中常见问题
基于粒子群算法优化卷积神经网络(PSO-CNN)的回归预测预测,多变量输入模型 优化参数为:学习率,批大小,正则化系数。 评价指标包括:R2、MAE、MSE、RMSE和MAPE等,代码质量极高,方便学习和替换数据。 ------------...
利用贪心策略进行优化,基本在15ms即可出结果,采用的是非递归算法
为了确保生成无向图割集的递归收缩算法的正确性和稳定性,对算法中种子顶点是支点的情形进行了分析,并采取了新的处理策略。分析了支点具有一个非可吸簇的情形,引进附加吸入的概念,修正了种子顶点的BFSO值取值规则...
用分治法设计一个算法,使得:用若干个L型条块可以覆盖住B的除一个特殊方格外的所有方格。其中,一个L型条块可以覆盖3个方格。且任意两个L型条块不能重叠覆盖棋盘。 例如:如果n=2,则存在4个方格,其中,除一个方...
斐波那契算法的各种实现,详情请看:http://blog.csdn.net/u012346890/article/details/17882813