当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 2 篇帖子 ] 
作者 内容
1 楼 
 文章标题 : 求 5000 以内的所有“水仙花数” 解法
帖子发表于 : 2009-02-11 20:31 
头像

注册: 2006-09-21 14:28
帖子: 2376
送出感谢: 0 次
接收感谢: 0 次
求 5000 以内的所有“水仙花数”。

备注:在数论中,水仙花数是指这样一个数,其各个数之立方和等于该数。如,1^3+5^3+3^3=153。
* 十进制中的这样的数有:0、1、2、3、4、5、6、7、8、9、153、370、371,
* 三进制中的这样的数有:0、1、2、12、122
* 四进制中的这样的数有:0、1、2、3、313

http://en.wikipedia.org/wiki/Narcissistic_number
[url]http://zh.wikipedia.org/wiki/水仙花数[/url]

代码:
int i, tmp, k, sum;
for ( k = 3; k <= MAX_VAL ; k ++ )
{
   for ( i = k, tmp = i % 10, sum = 0; i != 0 && i > 0; i /= 10, tmp = i % 10 )
      sum += tmp * tmp * tmp;
   if (sum == k)
      printf("%d \n", sum);
}


更优解是? :em01


_________________
http://lee.youxu.info/


页首
 用户资料  
 
2 楼 
 文章标题 : Re: 求 5000 以内的所有“水仙花数” 解法
帖子发表于 : 2009-02-20 16:15 

注册: 2008-06-20 12:05
帖子: 1
送出感谢: 0 次
接收感谢: 0 次
感觉是可以优化的。
首先,上界是可以优化,类似于5000以内,那么在这之内的各个位上立方和最大为4^3+9^3+9^3+9^3=2251(4999),显然比5000小,所以上界可以改进。
类似的,如果是6987这类的限制,就去5999的立方和比较,取其中最大的作为上界。可以看出上界约束虽然对1000以内的约束不强,可是对5000以上有很好的改进。因为就算是1亿以内的数字,最大不过是8*9^3=5832。
还有,我觉得在循环求和那里是不是也可以优化一下,因为,类似于993这类的数字,在得到前两个9的立方和后就可以排除了,在for循环里加个判断条件早点continue掉。


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 2 篇帖子 ] 

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:没有注册用户 和 2 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译