codewars（python）練習(xí)筆記三：獲取多位數(shù)字的乘法持久性
題目：
Write a function, persistence, that takes in a positive parameter num and returns its multiplicative persistence, which is the number of times you must multiply the digits in num until you reach a single digit.
persistence(39) => 3 Because 39 = 27, 27 = 14, 14=4 , 4 has only one digit.
persistence(999) => 4
Because 999 = 729, 729 = 126,126 = 12, and finally 12 = 2.
persistence(4) => 0 # Because 4 is already a one-digit number.
題目大意：
編寫一個(gè)函數(shù)persistence，它接受一個(gè)正數(shù)參數(shù)num并返回它的乘法持久性，這是您必須將num中的數(shù)字相乘直到達(dá)到結(jié)果為一個(gè)個(gè)位數(shù)的次數(shù)。
例如：輸入一個(gè)多位數(shù)字，例如39，（1）讓3和9相乘，變成27，（2）2和7之間相乘，變成14，（3）1和4相乘，變成4。 整個(gè)過程需要3步，那么就返回3。
輸入999，（1）999 = 729, （2）729 = 126,（3） 126 = 12,并且最終，（4）1*2 = 2.整個(gè)過程需要4步，返回4。
輸入4，因?yàn)?4 已經(jīng)是一個(gè)個(gè)位數(shù)了，所以直接返回0.
我的解法：
#!/usr/bin/python
case_total_num = 0
def persistence(n):
global case_total_num
if n > 9:
case_total_num += 1
n_str = str(n)
temp = 1
for i in n_str:
temp = temp * int(i)
if temp > 9:
return persistence(temp)
# python的遞歸調(diào)用，也是需要return 的
else:
temp = case_total_num
case_total_num = 0
return temp
else:
return case_total_num
其實(shí)這個(gè)就是一個(gè)常規(guī)的遞歸算法，有遞歸意識(shí)，這個(gè)算法就能自然而然的寫出來。函數(shù)需要遞歸的次數(shù)，就設(shè)定一個(gè) case_total_num ，存儲(chǔ)遞歸的次數(shù)。
兩個(gè)坑
我在寫這個(gè)函數(shù)的過程中，遇到了兩個(gè)坑：
- 一個(gè)是python的遞歸調(diào)用，也是需要return 的，即：return persistence(temp)。否則的話，函數(shù)執(zhí)行完，會(huì)直接返回None。
- 另一個(gè)是codewars 的測(cè)試case 是依次執(zhí)行的，如果不在遞歸完成后，將global case_total_num清零的話，上一個(gè)case 的結(jié)果會(huì)帶入到下一次的測(cè)試case 中去，導(dǎo)致第一次是正確的，之后的全是錯(cuò)誤的。
一點(diǎn)疑問
算法執(zhí)行完之后的一點(diǎn)疑問：我將case_total_num 定義在def persistence(n): 之前，執(zhí)行四個(gè)測(cè)試case 的速度為
Time: 538ms Passed: 4 Failed: 0
但是將case_total_num 定義在def persistence(n): 之后，執(zhí)行四個(gè)測(cè)試case 的速度就會(huì)大大延長(zhǎng)，測(cè)試case 的速度為
Time: 720ms Passed: 4 Failed: 0
當(dāng)然兩者相差不多，但后者的平均速度要比前者慢一些確實(shí)事實(shí)。
一點(diǎn)疑問的測(cè)試結(jié)論：
但后來在，我寫了這么一個(gè)demo 來測(cè)試具體時(shí)間時(shí)，缺沒有提現(xiàn)出足夠的差別：
begin = datetime.datetime.now()
for i in range(1000,9999999):
persistence(i)
end = datetime.datetime.now()
k = end - begin
print k
執(zhí)行結(jié)果：
理論上應(yīng)該是沒差別的，無論global在上面聲明還是在函數(shù)之后聲明，函數(shù)內(nèi)一執(zhí)行到global 馬上就去模塊全局去找的，不應(yīng)該會(huì)因?yàn)檫@個(gè)產(chǎn)生明顯的差別。
優(yōu)化解法一：
去掉 global case_total_num
因?yàn)椋热豢梢詒eturn persistence(temp) ，那在return 的時(shí)候，讓persistence(temp)直接加1，就是的引用次數(shù)
#!/usr/bin/python
def persistence(n):
case_total_num = 0
if n > 9:
case_total_num += 1
n_str = str(n)
temp = 1
for i in n_str:
temp = temp * int(i)
if temp > 9:
return persistence(temp) + 1
else:
return case_total_num
else:
return case_total_num
優(yōu)化解法二：
def persistence(n):
if str(n) == 1:
return 0
count = 0
while len(str(n)) > 1:
total = 1
for i in str(n):
total *= int(i)
n = total
count += 1
return count
這種方法，利用while循環(huán)來替換掉遞歸循環(huán)，降低了算法的復(fù)雜度，也是一種很不錯(cuò)的算法。
優(yōu)化解法三：
def persistence(n):
ni = 0
while n >= 10:
n = reduce(lambda x, y: x * y, [int(i) for i in str(n)])
ni += 1
return ni
Python reduce() 函數(shù)
reduce() 函數(shù)會(huì)對(duì)參數(shù)序列中元素進(jìn)行累積。
函數(shù)將一個(gè)數(shù)據(jù)集合（鏈表，元組等）中的所有數(shù)據(jù)進(jìn)行下列操作：用傳給 reduce 中的函數(shù) function（有兩個(gè)參數(shù)）先對(duì)集合中的第 1、2 個(gè)元素進(jìn)行操作，得到的結(jié)果再與第三個(gè)數(shù)據(jù)用 function 函數(shù)運(yùn)算，最后得到一個(gè)結(jié)果。
reduce() 函數(shù)語法：
reduce(function, iterable, [initializer])
參數(shù):
function -- 函數(shù)，有兩個(gè)參數(shù)
iterable -- 可迭代對(duì)象
initializer -- 可選，初始參數(shù)
以下實(shí)例展示了 reduce() 的使用方法：
>>>def add(x, y) : # 兩數(shù)相加
... return x + y
...
>>> reduce(add, [1,2,3,4,5]) # 計(jì)算列表和：1+2+3+4+5
15
>>> reduce(lambda x, y: x+y, [1,2,3,4,5]) # 使用 lambda 匿名函數(shù)
15
優(yōu)化解法四：
import operator
def persistence(n):
i = 0
while n>=10:
n=reduce(operator.mul,[int(x) for x in str(n)],1)
i+=1
return i
這個(gè)是在reduce()函數(shù)的基礎(chǔ)上，引用operator模塊的mul(x,y)
operator模塊介紹
http://www.cnblogs.com/nju2014/p/5568139.html
codewars上大神多啊?。?/p>
