跟yoyo@home合作的新子项目：搜索奇异奇数

dianci

我已经开跑了

fwjmath

refla 发表于 2013-9-3 09:49
这个问题我没问清楚。

求解子集元素的总和，我也搞过。我当时的想法是这样的：

现在算法是这样的：首先，对于每一个数我都已经有它的素因数分解了，就直接用它来生成所有真因数的集合，然后排序；然后用回溯法解子集和数问题。瓶颈其实不是特别明显，我自己测定过时间，生成约数集合、排序和回溯法都占用了一定比例的时间。可能是因为真因数集合有些结构，一般回溯法解起来很快。

其实求解子集和数问题一般还是回溯法，就是逐一尝试某个元素是不是在所求子集之中，然后递归解决变得更小的问题。

refla

fwjmath 发表于 2013-9-3 14:03
现在算法是这样的：首先，对于每一个数我都已经有它的素因数分解了，就直接用它来生成所有真因数的集合， ...

好的，那怎么样确定“某个元素是不是在所求子集之中”呢？

fwjmath

refla 发表于 2013-9-3 14:29
好的，那怎么样确定“某个元素是不是在所求子集之中”呢？

比如说现在集合是S，目标数是n，我要求S的一个子集T，使得T的元素的和是n。

那么，对于S中的元素a，它有两种可能：在T中，或者不在T中。

如果a在T中，那么只需要在剩余的元素S\{a}中求一个子集T1，使得T1的元素的和是n-a，那么T就是T1并上{a}。

如果a不在T中，那么只需要在剩余的元素S\{a}中求子集T，使得T的元素的和是n。

这两个子问题都是子集和数问题，而且规模变小了，递归解决即可。可以先探索一种可能性，不成再回来探索另一种，这就是回溯法的由来。

虽然复杂度不好算，但是在实践中这个算法表现还是可以的。

refla

refla 发表于 2013-9-3 14:29
好的，那怎么样确定“某个元素是不是在所求子集之中”呢？

哎呀，这个问题我问得太快了

我知道该怎么做了，N=100，其全体约数的集合为{1, 2, 4, 5, 10, 20, 25, 50}，则
1+2+4+5+10+20+25+50=117>100

那么我就退掉 25，得到
1+2+4+5+10+20+50=92<100

再取回25，并退掉10、5、4，得到
1+2+20+25+50=98<100

重新取回4，退掉2，得到
1+4+20+25+50=100

大概是这么个思路吧？

fwjmath

refla 发表于 2013-9-3 14:48
哎呀，这个问题我问得太快了

我知道该怎么做了，N=100，其全体约数的集合为{1, 2, 4, 5, 10, 20, ...

其实一般是这样：

100=?
100=50+?=50+?
100=50+25+?=75+?
100=50+25+20+?=95+?
100=50+25+20+10+?=105+? XXX
100=50+25+20+5+?=100+?

100=50+25+20+5

refla

fwjmath 发表于 2013-9-3 14:53
其实一般是这样：

100=?

太好了！我们快点算，算好了不要告诉 OProject，等他们傻傻地算完，再给他们看 paper

arthur200000

考虑到大部分有x86_64的CPU带SSE3和以下版本的SSE，倒是可以考虑加上。
说不定有啥好处呢。

litimetal

arthur200000 发表于 2013-9-4 17:29
考虑到大部分有x86_64的CPU带SSE3和以下版本的SSE，倒是可以考虑加上。
说不定有啥好处呢。 ...

SSE 对这种整数运算有帮助吗？
当然，加上也没坏处

muclemanxb

做为TC的队友，只有迟到，没有缺席～加入f版的项目。

w2xcn

refla 发表于 2013-9-3 09:49
这个问题我没问清楚。

求解子集元素的总和，我也搞过。我当时的想法是这样的：

有点高深。不过看你说的算法，确实效率很低