论坛 › 算法交流 › 方幂圈问题

无心人 发表于 2008-3-6 20:51:20

方幂圈问题

对整数n， 进行如下操作
对n的每个十进位数字求其k次幂，再求和
得到新的n，循环
则当k在一定范围时
循环或者终止于某个数字， 或者进入一个圆圈

现在对k=20寻找所有终止数字和圈

:)
这个题目好做么?

gxqcn 发表于 2008-3-6 20:53:48

对单个数字好做，对环要难一点。

无心人 发表于 2008-3-6 21:11:46

可以的
对k=20 还是能计算出来的
再大也没多少k了

mathe 发表于 2008-3-7 08:41:32

这个相当于枚举10个和为21的非负整数的所有解的情况。

无心人 发表于 2008-3-7 09:15:28

mathe!!!

是对应还是解集合对应?

mathe 发表于 2008-3-7 09:53:41

只是一个复杂度的估计。
可以先计算出x0+x1+...+x9=21的解的数目(其中x0,x1,...,x9是非负整数)
然后我们可以构造出一个以这么多点为顶点的图，找图里面的强连通分支数目就可以了。
所以主要问题是估计一下上面方程解的数目，就可以知道问题的规模了。
同样，如果k改成其他数字，我们可以有类似的结论，只要计算x0+x1+...+x9=X(k)的解的数目
其中X(k)同k比较接近(k越大X(K)/K越小)

无心人 发表于 2008-3-7 10:02:25

哦
那不必了

解集合在这个序列里
{x1, x2, x3, x4, ...x21 |x(i) <= x(i+1), 0<= x(i)<=9 }

mathe 发表于 2008-3-7 12:51:35

原帖由 无心人 于 2008-3-7 10:02 发表 http://bbs.emath.ac.cn/images/common/back.gif
哦
那不必了

解集合在这个序列里
{x1, x2, x3, x4, ...x21 |x(i)

这个同我的描述基本等价。我写成
x0+x1+...+x9=21
其中x0就是你那个序列种1的数目,x1就是你那个序列中1的数目,...

无心人 发表于 2008-4-4 11:41:23

咱先把单个数字求出来
如何

mathe 发表于 2008-4-5 08:54:32

谁先来写个程序穷举一下方程
$x0+x1+...+x9=21$解的数目，这样我们就可以估计一下问题的规模了。
假设这个方程解的数目是N,那么问题的时间复杂度在O(N)
只是其常系数比较大，越为10k

查看完整版本: 方幂圈问题