优草派  >   Python

判断水仙花数

周文博            来源:优草派

水仙花数是指一个三位数,其各位数字的立方和等于该数本身。例如,153是一个水仙花数,因为1^3+5^3+3^3=153。那么如何判断一个数是否是水仙花数呢?本文从多个角度进行分析。

一、暴力枚举法

判断水仙花数

最直接的方法是暴力枚举所有的三位数,然后判断其是否是水仙花数。具体实现如下:

```python

for i in range(100, 1000):

a = i // 100 # 百位

b = i % 100 // 10 # 十位

c = i % 10 # 个位

if a**3 + b**3 + c**3 == i:

print(i)

```

这种方法虽然简单易懂,但是效率很低,需要枚举900个数才能找到所有的水仙花数。

二、数学方法

观察水仙花数的定义式,可以发现一个规律:每个水仙花数的个位、十位、百位数字的立方和都是它自己。也就是说,如果一个数满足这个规律,那么它一定是水仙花数。因此,可以通过数学方法判断一个数是否满足这个规律。

具体实现如下:

```python

for i in range(100, 1000):

a = i // 100 # 百位

b = i % 100 // 10 # 十位

c = i % 10 # 个位

if a**3 + b**3 + c**3 == (a*100 + b*10 + c):

print(i)

```

这种方法只需要枚举900个数,效率比暴力枚举法要高得多。

三、递归算法

递归是一种常用的算法思想,可以用来判断一个数是否是水仙花数。具体实现如下:

```python

def is_narcissistic_number(n):

if n < 100 or n > 999:

return False

a = n // 100 # 百位

b = n % 100 // 10 # 十位

c = n % 10 # 个位

return a**3 + b**3 + c**3 == n

for i in range(100, 1000):

if is_narcissistic_number(i):

print(i)

```

这种方法也只需要枚举900个数,效率比暴力枚举法要高,而且代码可读性更好。

四、时间复杂度分析

暴力枚举法需要枚举900个数,时间复杂度为O(n);数学方法和递归算法都只需要枚举900个数,时间复杂度也是O(n)。因此,三种方法的时间复杂度是一样的,但是数学方法和递归算法的效率更高。

五、

【原创声明】凡注明“来源:优草派”的文章,系本站原创,任何单位或个人未经本站书面授权不得转载、链接、转贴或以其他方式复制发表。否则,本站将依法追究其法律责任。
TOP 10
  • 周排行
  • 月排行