回归数

无心人

呵呵

计算到100位
我的代码都有输出
过了40, media2005的输出是空

medie2005

想要输出还不简单,打印0和1就好了.

无心人

反正40以下的搞明白了
咱继续算广泛意义下的
到64如何?

medie2005

对这个问题,我一直想找一个很快的算法,因为毕竟回归数很少,应当存在某种算法可以比较快的计算这些数,但是,最终只想到了10楼的那个垃圾算法.
我的程序稍微改动一下就可以算广义回归数,不过,我没兴趣了.

无心人

简化到只计算排列组合数字已经很优化了
毕竟计算大数的运算很麻烦
即便是64位整数乘法在32位机器上也是远超过
4个乘法的理论时间

medie2005

呵呵,其实10楼的程序最大的优点是利用了格雷码序,使得计算每个组合对应的值最多只需要两次大数加减法.(也许不用GMP会更好)
但是,缺点是所有组合都要遍历.
如果采用词典序法来生成组合,我们可以利用最大-最小值来跳过一些组合,但是,效率也不见得比10楼的算法好.

[ 本帖最后由 medie2005 于 2009-1-9 21:34 编辑 ]

无心人

跳不过的
我计算过
8，9只要出现一次，数字就能保证不会超出范围
所以仅能省略一两个位置的数字
那种大幅度简化的是完全搜索数字的程序
而不是按组合数字搜索

medie2005

另外,有一个相关问题:
$\sum_{i=1}^{k}{d_{i}^k}=\sum_{i=1}^{k}{c_{i}^k}$                 (1)
其中: $0<=d_{i}<=d_{i+1}<=9$, $0<=c_{i}<=c_{i+1}<=9$, $c_{1}...c_{k}$与$d_{1}...d_{k}$不完全相同.
对给定的k, 有多少的$c_{1}...c_{k}$与$d_{1}...d_{k}$满足(1)式?

medie2005

另外,根据运算的互换性,我们总可以用组合来减少计算.
比如,先前的"阶乘于素数个数"的帖子,其中我的算法也是利用了这个原理,只是,满足$\prod_{i=1}^{k}{d_{i}!}=\prod_{i=1}^{k}{c_{i}!}$的ci与di对比较多,可以通过排序,再去重,得到仅仅需要考虑的$\prod_{i=1}^{k}{d_{i}!}$值.

[ 本帖最后由 medie2005 于 2009-1-9 21:29 编辑 ]

无心人

如果你去我的方幂圈那个帖子里找源程序

修改下，应该能很快获得
k <= 17 的结果