方幂圈问题

无心人 · 发表于 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 发表哦那不必了解集合在这个序列里 {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

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 方幂圈问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。