水仙花数问题

来自Wikipedia

数论中,水仙花Narcissistic number[1][2],也被称为超完全数字不变数pluperfect digital invariant, PPDI[3]自恋自幂数阿姆斯壮阿姆斯特朗数Armstrong number[4] ,用来描述一个N位非负整数,其各位数字的N次方和等于该数本身。

 

对于一个三位数,即个、十、百位的三次幂相加等于自身的数即为水仙花数。例如:

153 = 1^3+5^3+3^3 = 1+125+27

而求水仙花数也是编程当中的一个经典问题(确实经典,经典的打击我玩了两天FIFA……),对于比较笨的菜鸟,连怎么得到每一位数字都不知道(比如我),更别说算法了。在偷偷瞄了眼答案之后,才想起这世界上有种运算叫地板除。

首先以三位水仙花数为例。

我的v0是这样的:

for i in range(100, 1000):
    if ((i // 100) ** 3) + (((i // 10) - ((i //100)) * 10) ** 3) + (((i - (i // 10) * 10)) ** 3) == i:
        print(i)

嗯,只有三行,看起来不赖。

等等……这括号……拖出去打死(报了五次错之后我才把括号打对……)。

为了让可读性不为零,需要稍微改进一下:

for i in range(100,1000):
    j = i // 100
    k = i // 10 % 10
    l = i % 10
    if j ** 3 + k ** 3 + l ** 3 == i:
        print(i)

这样看起来就顺眼多了。j,k,l分别为百十个位。

对于j:地板除是直接截断结果的(比如199//100=1),所以一个三位数地板除100即是它的百位数。

对于k:地板除10之后即是前两位数,除10之后的余数即是十位数。

对于l:同上。

这种写法易于理解,但写起来比较复杂,一旦扩展到更多位数尤为如此。例如扩展到四位数:

for i in range(1000,10000):
    a = i // 1000     #千位
    b = i // 100 % 10 #百位
    c = i // 10 % 10  #十位
    d = i % 10        #个位
    if a ** 4 + b ** 4 + c ** 4 + d ** 4 == i:
        print(i)

在经过一番Google之后,找到了另一种写法:

for i in range(100,1000):
    sum = 0
    temp = i
    while temp:
        sum = sum + (temp % 10) ** 3
        temp //= 10
    if sum == i:
        print(i) 

这段代码第一眼看上去可能令人一头雾水……但其实原理都是类似的,可以拿153这个数试试。

第一轮循环,temp==153 sum==0+(153%10)**3==27

第二轮循环,temp==15 sum==27+5**3==152

第三轮循环,temp==1 sum==152+1**3==153

最后,1//10=0,循环结束。

不难发现,temp % 10的运算就是在求temp的最后一位数,而temp  //= 10就是在下一轮循环中去掉最后一位数。

这种写法很容易推广,对于n位的情况:

choose = input("输入位数")
while not choose.isdigit:
    choose = input("重新输入位数")
else:
    range0 = int("1" + (int(choose) - 1) * "0")    #此处有没有更好的实现?
    range1 = int("1" + int(choose) * "0")
    for i in range(range0,range1):
        sum = 0
        temp = i
        while temp:
            sum = sum + (temp % 10) ** int(choose)
            temp //= 10
        if sum == i:
            print(i)

虽然对range的操作有点绕,不过暂时没想到更好的办法……

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注