目錄
- 題目描述：
- 思路：
- 代碼：
- 改良版
- 采用遞歸
- 數(shù)學(xué)方法
題目描述：
編寫(xiě)一個(gè)算法來(lái)確定一個(gè)數(shù)字是否“快樂(lè)”。 快樂(lè)的數(shù)字按照如下方式確定：從一個(gè)正整數(shù)開(kāi)始，用其每位數(shù)的平方之和取代該數(shù)，并重復(fù)這個(gè)過(guò)程，直到最后數(shù)字要么收斂等于1且一直等于1，要么將無(wú)休止地循環(huán)下去且最終不會(huì)收斂等于1。能夠最終收斂等于1的數(shù)就是快樂(lè)的數(shù)字。
例如：19是一個(gè)快樂(lè)數(shù)字，計(jì)算過(guò)程如下：
1^2+9^2=82
8^2+2^2=68
6^2+8^2=100
1^2+0^2+0^2=1
要求：當(dāng)輸入快樂(lè)的數(shù)字時(shí)，輸出True，否則輸出False。
思路：
1. 當(dāng)輸入的不是快樂(lè)數(shù)字時(shí)，會(huì)陷入一個(gè)無(wú)限循環(huán)，因此增加一個(gè)計(jì)數(shù)器 count 用來(lái)統(tǒng)計(jì)計(jì)算次數(shù)。設(shè)定當(dāng) count 達(dá)到2000次時(shí)，認(rèn)為該數(shù)字不是快樂(lè)數(shù)字，跳出循環(huán)結(jié)束計(jì)算。
2. 因?yàn)椴淮_定輸入的數(shù)字會(huì)是幾位數(shù)，因此不采用除法和取模的方法來(lái)獲得數(shù)字的每一位數(shù)，而是利用 for 循環(huán)獲取字符串類(lèi)型數(shù)字的每一位來(lái)計(jì)算平方和。
代碼：
#快樂(lè)的數(shù)字
def getSumofSquares(num):
numStr=str(num) #將待計(jì)算的數(shù)字轉(zhuǎn)換成字符串類(lèi)型
sum=0
digitls=[int(x) for x in numStr] #從字符串中提取出每一位數(shù)字存入一個(gè)列表
#注：該步略顯多余，因?yàn)閜ython中字符串可以和列表一樣切片取值或循環(huán)，見(jiàn)下方更新部分
#print(digitls)
for i in digitls:
sum += i**2
return sum
def main():
n = input() #輸入一個(gè)正整數(shù)
sumofSqrs = eval(n)
count = 0
while sumofSqrs != 1:
sumofSqrs = getSumofSquares(sumofSqrs)
count += 1
if count > 2000: #當(dāng)計(jì)算次數(shù)超過(guò)2000次時(shí)，跳出循環(huán)結(jié)束計(jì)算
print("False")
break
else:
print("True")
main()
改良版
根據(jù)網(wǎng)友在評(píng)論區(qū)提出的不快樂(lè)的數(shù)字最終會(huì)在 [4,16,37,58,89,145,42,20] 這些數(shù)字中無(wú)限循環(huán)，因此可以加入判斷，當(dāng)數(shù)字變?yōu)檫@些數(shù)字里的任意一個(gè)（比如4）時(shí)就結(jié)束循環(huán)，輸出False，從而避免無(wú)限循環(huán)的產(chǎn)生。
修改后的代碼：
#（新）快樂(lè)的數(shù)字
def getSumofSquares(num):
numStr=str(num)
sum=0
for i in numStr:
sum += int(i)**2
return sum
def main():
n = input() #n為一個(gè)正整數(shù)
sumofSqrs = eval(n)
while sumofSqrs != 1 and sumofSqrs != 4: #或 while sumofSqrs not in [1,4,16,37,58,89,145,42,20]
sumofSqrs = getSumofSquares(sumofSqrs)
else:
if sumofSqrs == 1:
print("True")
else:
print("False")
main()
采用遞歸
def happy(n):
try:
if n==1:
print('True')
else:
new = str(n)
sum = 0
for c in new:
sum += int(c)**2
return happy(sum)
except Exception as e:
print('False')
# print(e)
n = eval(input())
happy(n)
數(shù)學(xué)方法
d = {}
while True:
m = 0
while n > 0:
m += (n%10)**2
n //= 10
if m in d:
return False
if m == 1:
return True
d[m] = m
n = m
優(yōu)化過(guò)的
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
record = []
sq_sum = 0
se_n = n
while se_n != 1:
sq_sum = 0
while se_n > 0:
sq_sum += (se_n % 10) * (se_n % 10)
se_n = se_n / 10
if sq_sum in record:
return False
record.append(sq_sum)
se_n = sq_sum
return True
以上就是python 算法題——快樂(lè)數(shù)的多種解法的詳細(xì)內(nèi)容，更多關(guān)于python 算法題快樂(lè)數(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
您可能感興趣的文章:- python使用ProjectQ生成量子算法指令集
- Python機(jī)器學(xué)習(xí)算法之決策樹(shù)算法的實(shí)現(xiàn)與優(yōu)缺點(diǎn)
- Python集成學(xué)習(xí)之Blending算法詳解
- python3實(shí)現(xiàn)Dijkstra算法最短路徑的實(shí)現(xiàn)
- Python實(shí)現(xiàn)K-means聚類(lèi)算法并可視化生成動(dòng)圖步驟詳解
- Python自然語(yǔ)言處理之切分算法詳解
- python入門(mén)之算法學(xué)習(xí)
- Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法的分類(lèi)
