找回密码
 欢迎注册
查看: 46777|回复: 73

[讨论] 方幂圈问题

[复制链接]
发表于 2008-3-6 20:51:20 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有账号?欢迎注册

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

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


这个题目好做么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-6 20:53:48 | 显示全部楼层
对单个数字好做,对环要难一点。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-6 21:11:46 | 显示全部楼层
可以的
对k=20 还是能计算出来的
再大也没多少k了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-7 08:41:32 | 显示全部楼层
这个相当于枚举10个和为21的非负整数的所有解的情况。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-7 09:15:28 | 显示全部楼层
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 }
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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 | 显示全部楼层
咱先把单个数字求出来
如何
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-5 08:54:32 | 显示全部楼层
谁先来写个程序穷举一下方程
$x0+x1+...+x9=21$解的数目,这样我们就可以估计一下问题的规模了。
假设这个方程解的数目是N,那么问题的时间复杂度在O(N)
只是其常系数比较大,越为10k
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-19 15:03 , Processed in 0.069973 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表