|
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (1)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2007-06-11
longrm 写道
private static int offset(int n){ //表示第n个的起始位置
return n*(n-1)*(n-2)/6 + n;
}
这个是由Sum{i*(i-1)/2; 1<=i<=n}计算出来的么？偶怎么就算不出来  这个是我代码注释过少的缘故, ==,我在原来代码下面加些注释. |
| 返回顶楼 | |
|
发表时间：2007-06-11
看了一下还真是看不明白呀。。。。
5，0，0，0，0 ＝1 4，1，0，0，0 = 2 3，2. 0, 0, 0 =2 。。。。。 所有的可能性都遍历出来？ 头一个可以的就跳出来么？ |
| 返回顶楼 | |
|
发表时间：2007-06-11
抛出异常的爱 写道 看了一下还真是看不明白呀。。。。 哈哈，偶都明白啦，就是那个计算的还没看出怎么算来的（主要是偶太懒了，嘿嘿）
虽然你的代码长多了，但效率不见得就比他的差，不知道怎么测试 |
| 返回顶楼 | |
|
发表时间：2007-06-11
longrm 写道
public static boolean isSuit(int n,int k){
if(k<0||k>n*(n-1)/2) return false;
int off =offset(n);
if(isSolved.get(off+k)) return isSuit.get(off+k);
for(int i =1;i<n;i++)
if(isSuit(n -i,k -i*(n-i) ) ){
isSolved.set(off +k);
isSuit.set(off +k);
return true;
}
isSolved.set(off +k);
return false;
}
呵呵，这里用递归会影响性能，如果改成循环的话就更好了 这个,改成循环是很简单的时,但实际上事情不完全是这样滴. 对于动态规划,一般有两种形式: 一种是用递归;一种使用循环(递推) 这两种形式的代码都很容易写(前提是你已经得到状态转移方程) 而且两种形式各有所长(循环的不一定比递归的好): 递归形式的代码容易理解,而且可以减少不必要的计算,因为递归的时候只算要算的(后一点对于性能来说是比较重要的) 而如果能确定大多数子状态都需要计算的话,循环就会更快了(但循环会一次性把所有的状态都计算到,因为它知道那些不必要算). 当然,可以改成那种基于栈的循环算法,不过说实话,那种代码读起来就费劲多了. |
| 返回顶楼 | |
|
发表时间：2007-06-11
抛出异常的爱 写道 看了一下还真是看不明白呀。。。。
5，0，0，0，0 ＝1 4，1，0，0，0 = 2 3，2. 0, 0, 0 =2 。。。。。 所有的可能性都遍历出来？ 头一个可以的就跳出来么？ 注意我static{}里面的代码,那是初始状态,把所有的s[n,0]全设为true了. |
| 返回顶楼 | |
|
发表时间：2007-06-11
longrm 写道 抛出异常的爱 写道 看了一下还真是看不明白呀。。。。 哈哈，偶都明白啦，就是那个计算的还没看出怎么算来的（主要是偶太懒了，嘿嘿）
虽然你的代码长多了，但效率不见得就比他的差，不知道怎么测试 嘲笑别人没的好下场 罚你用这种方法作。。。。 http://www.iteye.com/post/309308 换零钱的程序。。。。 你不要说你没毕业不会作噢。。。 |
| 返回顶楼 | |
|
发表时间：2007-06-11
抛出异常的爱 写道 longrm 写道 抛出异常的爱 写道 看了一下还真是看不明白呀。。。。 哈哈，偶都明白啦，就是那个计算的还没看出怎么算来的（主要是偶太懒了，嘿嘿）
虽然你的代码长多了，但效率不见得就比他的差，不知道怎么测试 嘲笑别人没的好下场 罚你用这种方法作。。。。 http://www.iteye.com/post/309308 换零钱的程序。。。。 你不要说你没毕业不会作噢。。。 说句实话，你说的太对啦，偶刚大四，还差1个月毕业，嘿嘿 |
| 返回顶楼 | |
|
发表时间：2007-06-11
longrm 写道 抛出异常的爱 写道 看了一下还真是看不明白呀。。。。 哈哈，偶都明白啦，就是那个计算的还没看出怎么算来的（主要是偶太懒了，嘿嘿）
虽然你的代码长多了，但效率不见得就比他的差，不知道怎么测试 呵呵,我不知道你还记得组合数么. 就是那个C(n,k),从n个元素里面取k个的方法数. 然后有个公式: C(n+1,k+1) =C(n,k)+C(n,k+1) (可以这样理解:从n+1个东西取k+1个,计某个元素为A,那么每种取法都属于下面的两种情形之一: 1:包含A ......相当于从另n个里面取k个 2:不包含A ....相当于从另n个里面取k+1个 从而有 C(n+1,k+1) =C(n,k)+C(n,k+1) ) 注意到 m*(m-1)/2 =C(m,2) =C(m+1,2+1) -C(m,2+1)(用了上面的公式) 从而: Sum{m*(m-1)/2 : 0<=m<=n-1} = Sum{C(m+1,3)-C(m,3) :0<=m<=n-1} (注意,抵消了很多) = C(n,3) -C(0,3) = C(n,3) = n*(n-1)*(n-2)/3! |
| 返回顶楼 | |
|
发表时间：2007-06-11
我在写代码时不考虑效率。。。
我主要是为了给别人讲一个想法。 PS：java的所有的思想都与清析表达有关。。。 如果说我想的方式大约会达到O（n^2）左右的效率 比遍历要少1/2的时间而已 而你的想法是纯数学推导出来。。。 自然会比我想的要快一些 如果想要看明白先要过数学的关卡。。。（就是上面的数学式） |
| 返回顶楼 | |
|
发表时间：2007-06-11
这种问题的效率主要是由算法决定的.
只要算法对了,效率不会差到那儿去,至于用递归还是用递推关系不大. |
| 返回顶楼 | |
