求 5000 以内的所有“水仙花数” 解法

软件和网站开发以及相关技术探讨
回复
flyinflash
帖子: 2376
注册时间: 2006-09-21 14:28
送出感谢: 0
接收感谢: 0

求 5000 以内的所有“水仙花数” 解法

#1

帖子 flyinflash » 2009-02-11 20:31

求 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
http://zh.wikipedia.org/wiki/水仙花数

代码: 全选

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
@小天@
帖子: 1
注册时间: 2008-06-20 12:05
送出感谢: 0
接收感谢: 0

Re: 求 5000 以内的所有“水仙花数” 解法

#2

帖子 @小天@ » 2009-02-20 16:15

感觉是可以优化的。
首先,上界是可以优化,类似于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掉。
回复

回到 “软件/网站开发”