|
锁定老帖子 主题：对于这个题目，看看大家有什么效率更高的算法
精华帖 (0) :: 良好帖 (2) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-10-17
anderkey 写道 LZ去参加迅雷在广州的笔试了吧，结果如何？
呵呵，是啊，有些内容（比如：多线程）平时不太注意，这次考了很多。所以答题的时候答得不是很好，再加上可能因为我的这个编程题的算法的效率不好，所以笔试就被BS了。 |
| 返回顶楼 | |
|
发表时间：2010-10-17
rocketball 写道 母函数来解这来问题
正解，+1 
|
| 返回顶楼 | |
|
发表时间：2010-10-17
JE帐号 写道 shkailiao 写道 bastengao 写道 递归就不一定吃内存，不递归就不一定省内存。 这个问题，我以前也想过，我最早的想法跟楼主是一样的。 但说这句话的人，很可能针对的不是 java 语言。我曾经做过某个东西，最早也用的是递归的方法，我本以为效率会很差，我就换成非递归的，结果是效率更差。 其实，如果要是做的多了的话，楼主应该能够感觉到，在用非递归做是时候，其实是在模仿递归的方式，变量也是。也就是说，非递归的方式在内存使用上，很可能是与递归是一样的。 但话又说回来，java 语言是跟其他语言不一样，因为 java 的内存释放是由虚似机来完成的，不像 其他语言，严格按照 什么 堆啊，栈啊。
谢谢你的回复，C、C++写的程序，当一个变量需要释放内存的时候，可以调用相应的方法，而对于java来说，内存的管理很大部分都是由GC来管理的，程序员很难去控制，总算调用JVM的gc（）方法，也不一定可以实现释放内存。所以只要一个对象的引用数不为0，一般都还存在内存中，假如递归的时候，所有的对象的引用都不为0，并且所有对象使用的内存和超过内存时，就会发生溢出。对于将递归转变为while等的循环，可以将一些变量的时间效用会大大减短。所以，我觉得对于java来说，递归比while等之类的循环要吃内存。 和引用没多大关系. 递归是一个栈嵌套的问题.由于嵌套所以无法回收栈调用链上的内存,所以就要求尽量减少单个栈循环所使用的内存. 而且,你的代码不能承受所谓22这个限制,不是因为递归这个过程,而是你要把所有的结果都保存.你把调用addKindOfResultToList方法的代码注释掉试一试. 因为Integer内部封装了是int,而int这些基本数据类型是存在栈中的,而默认情况下,jvm的栈并不是很大,所以很容易OutOfMemoryError: Java heap space Integer将int打包后是对象，对象怎么会在栈中呢，加上程序的异常是Java heap（是堆，而不是stack栈） space |
| 返回顶楼 | |
|
发表时间：2010-10-17
最后修改：2010-10-17
kimmking 写道 ray_linn 写道 线性方程组而已，学点数学就成了
3阶斐波拉契数列 正解。 f(n) = f(n-1) + f(n-2) + f(n-3) f(1) = 1 f(2) = 2 f(3) = 4 ruby代码： 自底向上递推动态规划算法： def f(n) f = [1,2,4,7] return f[n] if n < 4 4.upto(n) do f[3] = f[0] + f[1] + f[2] f[0], f[1], f[2] = f[1], f[2], f[3] end return f[3] end |
| 返回顶楼 | |
|
发表时间：2010-10-17
最后修改：2010-10-17
fuliang 写道 kimmking 写道 ray_linn 写道 线性方程组而已，学点数学就成了
3阶斐波拉契数列 正解。 f(n) = f(n-1) + f(n-2) + f(n-3) f(1) = 1 f(2) = 2 f(3) = 4 ruby代码： 自底向上递推动态规划算法： def f(n) f = [1,2,4,7] return f[n] if n < 4 4.upto(n) do f[3] = f[0] + f[1] + f[2] f[0], f[1], f[2] = f[1], f[2], f[3] end return f[3] end +1 数学没学好.但是画了画,还是找到这个规律了.. |
| 返回顶楼 | |
|
发表时间：2010-10-17
fuliang 写道 kimmking 写道 ray_linn 写道 线性方程组而已，学点数学就成了
3阶斐波拉契数列 正解。 f(n) = f(n-1) + f(n-2) + f(n-3) f(1) = 1 f(2) = 2 f(3) = 4 ruby代码： 自底向上递推动态规划算法： def f(n) f = [1,2,4,7] return f[n] if n < 4 4.upto(n) do f[3] = f[0] + f[1] + f[2] f[0], f[1], f[2] = f[1], f[2], f[3] end return f[3] end 对于求出有多少种算法，这种方法应该是一个不错的方法，但对以只是求有多少种走法，用线性规划可能更好。但本题的关键就是要得到走法的种数，并将每一种走法记录下来，然会返回给调用者。 |
| 返回顶楼 | |
|
发表时间：2010-10-17
即该题的重点是怎么更好的将每一种走法记录下来，让调用者通过调用方法可以得到全部走法的详细的情况。
|
| 返回顶楼 | |
|
发表时间：2010-10-17
shkailiao 写道 即该题的重点是怎么更好的将每一种走法记录下来，让调用者通过调用方法可以得到全部走法的详细的情况。 建立历史数据。 还是用递归式。 对于任意的数N，其F(N)为分别用第1部走1加上F(N-1)所有走法序列，加上2，加上3。 这样，可以把序列都写入文件，每次内存中几乎不需要保持数据。 当然，如果序列集不大，可以存入内存。 这些，可以计算理论上，不超过硬盘容量的数据了。 |
| 返回顶楼 | |
|
发表时间：2010-10-18
喜羊羊与灰太狼 写道 rocketball 写道 母函数来解这来问题
正解，+1
正解, +2 |
| 返回顶楼 | |
|
发表时间：2010-10-18
最后修改：2010-10-18
这样够简单吧，两层循环，但是效率嘛，O(n^2)了。因为你是求所有解法，而不是求解法数量
#include <stdlib.h>
#include <stdio.h>
int main(int argc,char** argv)
{
int n=1000,a=1,b=2,c=3;
int num1,num2,num3,sum1,i,j;
num1=(int)(n/c);
for(i=0;i<=num1;i++)
{
sum1=n-i*c;
num2=(int)(sum1/b);
for(j=0;j<=num2;j++)
{
num3=sum1-j*b;
if((num3 % a)==0)
{
printf("%d*%d + %d*%d + %d*%d = %d\n",i,c,j,b,num3/a,a,n);
}
}
}
return 0;
}
|
| 返回顶楼 | |
