iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 10
2
Software Development

活用python- 路遙知碼力,日久練成精系列 第 10

Day10- 幾個程式經典問題,一亮出第一屠龍刀,彷彿開著坦克車攻打原始人,太逆天啦 (談切片語法的應用)

路遙知碼力,日久練成精-只要在程式之路鑽研的夠深,便能夠充分發揮程式碼的力量; 練習的日子夠久,便能夠練成寫出精簡代碼的能力。

大家好,我是心原一馬,內心原來一心喜歡打程式碼。
Day8中給大家講解了切片運算與range()函數的基礎語法,
今天來看看有了切片運算,
如何能夠精簡的解決經典問題呢?

範例10-1: 天才發明的倒裝句

文字充滿著奧妙,不論中、英文,
有些字倒著看也具有意思,
例如:

刷牙<->牙刷
國王<->王國
dog<->god
desserts(甜點) <-> stressed(壓力)
live(生命) <-> evil(邪惡)

你能否利用切片運算符實現字串倒轉的函數呢?

其實很簡單,要倒著取字只要步長設為負數即可,
又因要取整個字串,切片的第一、二個參數都可以省略。
實作如下:

def reverseStr(s):
    return s[::-1]

print(reverseStr("desserts")) # stressed
print(reverseStr("刷牙")) #刷牙

範例10-2: 判斷迴文字串

中、英文單字或句子有些是倒著讀和正著讀都相同的,
例如: level, 上海自來水來自海上
請用程式判斷一個字串是否為迴文。

有了範例10-1的程式,
這個問題應該是小菜一碟了吧?
既然迴文是倒著讀和正著讀都相同,
那麼只要用比較字串跟字串倒轉的結果是否相同即可,
程式如下:

def isPalindrome(s):
    return s==s[::-1]

print(isPalindrome("level")) # True
print(isPalindrome("deep")) #False
print(isPalindrome("上海自來水來自海上")) # True

範例10-3: 完美洗牌程序

完美洗牌問題是這樣的:
有一個長度為2n 的列表[a1,a2,a3,…an,b1,b2,b3,…,bn],
希望經過重排之後變成[a1,b1,a2,b2,…,an,bn]。
也就是模擬把牌平均分成兩堆,
上面一副牌([a1,a2,…an])放到左手,
下面一副牌([b1,b2,…,bn])放到右手,
然後左手一張,右手一張交錯洗牌的過程。
這個問題乍看簡單,但是在一般程式語言中,
好像還沒有很簡單的寫法。

純樸的解法

小馬想到一個很純樸的寫法,
既然是第一副牌和第二副牌要交錯發牌,
便直接把上、下兩副牌取出來,
用一個布林值變數nextIsFirst
記錄下一張要發的牌是第一副牌還是第二副。
因為總共要發2n張牌,
用一個for 迴圈遍歷2n次,如下:

def pefectShuffle(deck):
    n= len(deck)//2
    first = deck[:n]  #取出前n個數字當做第一副牌
    second = deck[n:] #取出後n個數字當做第二副牌
    nextIsFirst= True  #記錄下一張要發的牌是第一副牌還是第二副
    firstIdx=0        #記錄下一張要發的牌的index
    secondIdx=0       #記錄下一張要發的牌的index
    for i in range(2*n):
        if nextIsFirst:
            deck[i]=first[firstIdx]
            firstIdx+=1
        else:
            deck[i]=second[secondIdx]
            secondIdx+=1
        nextIsFirst= not nextIsFirst

我們再寫一段程式碼驗證結果:

deck=list(range(1,9)) #[1,2,3,4,5,6,7,8]
pefectShuffle(deck)
print(deck)

結果為[1, 5, 2, 6, 3, 7, 4, 8]
有達到我們想要的結果。
注意因為pefectShuffle(deck)函數是直接在函數中修改deck的值,
並沒有回傳值,
故驗證的程式應為:

pefectShuffle(deck)
print(deck)

而非平常較常見的

print(pefectShuffle(deck))

好了,寫完長長的程式總算達到我們想要的結果了。
可是身為追求python之美的小馬來說,
要宣告這麼多變數來解未免也太冗長了,
能不能把程式碼寫的更精簡一些呢?

高級切片語法

仔細觀察原問題,
把牌平均分成兩堆交錯洗牌的過程,
不就是把上面一堆牌放到奇數位置,
下面一堆牌放到偶數位置嗎?
而在Day8的切片教學中,
我們已經學會如何取出奇、偶數位置的元素了,
因此上述程式其實兩行就可以解完了:

def pefectShuffle(deck):
    n= len(deck)//2
    deck[::2], deck[1::2]= deck[:n], deck[n:]

直接用deck[::2]取出奇數位置,用第一副牌(deck[:n])把它填滿;
用deck[1::2] 取出偶數位置,用第二副牌(deck[n:])把它填滿。
是不是非常簡單明瞭呢?

驗證一下結果:

deck=list(range(1,9)) #[1,2,3,4,5,6,7,8]
pefectShuffle(deck)
print(deck)

結果依然為[1, 5, 2, 6, 3, 7, 4, 8]

本篇結語

在程式的算法世界中,
字串倒轉判斷迴文完美洗牌這幾類問題可說是經典問題,
目前也可以找到很多文章在探討這類算法的問題,
詳見:

參考資料

  1. 回文判斷問題
  2. 完美洗牌算法

然而在經典程式語言的特性(如c/c++)中,
並沒有非常簡單的方法可以解開這樣的問題。
然而我們今天看到python有切片運算符,
大大簡化了我們處理這類問題所需的程式碼。
回顧一下,

字串倒轉 => s[::-1],一行解
判斷迴文 => s==s[::-1],一行解
完美洗牌 => n= len(deck)//2,
deck[::2], deck[1::2]= deck[:n], deck[n:],兩行解。

看到這邊,讀者們是否慢慢感受到python語言的魔力了呢?
預計兩天後會傳授第二屠龍刀給大家-
也就是更具魔幻色彩的列表生成式語法,敬請期待。
(明天會先介紹一些關於python容器的特性)

課後練習- 關於切片高級語法

關於切片高級語法的解說,
我們就留待課後練習來講解吧。
記得在完美洗牌問題中,
我們看到了這樣的語法:

deck[::2], deck[1::2]= deck[:n], deck[n:]

在這個語法中,
等式的左右兩側都是切片,
意思就是把等式左邊對應的位置,換成等式右邊的值。

給大家看個範例:

A = [1,2,3,4,5,6]
B = [1,2,3,4,5,6]
C = ['A','B','C']

A[::2] = C[:] #把A的偶數項換成'A','B','C'
B[1:3] = C[:]
print(A)
print(B)

結果為
['A', 2, 'B', 4, 'C', 6]
[1, 'A', 'B', 'C', 4, 5, 6]

注意若等式左邊的切片不是連續的資料,
右邊的個數一定要等於左邊的個數,
譬如這支程式:

A = [1,2,3,4]
C = ['A','B','C']

A[::2] = C[:] #ValueError

這樣會出現ValueError
因為左側取A[::2]共有2個元素,
右側取C[:]卻有3個元素,數量不對。

習題

試問下列程式執行後,
列表A裡面有幾個1呢?
歡迎在留言區討論你的想法或答案哦。
(你想用數學解或直接用程式驗證皆可)

A = [0] * 30
A[::3] = [1] * len(A[::3])
A[::5] = [1] * len(A[::5])

上一篇
Day9- 中秋特輯: 月餅店攬客花招,「名偵探柯馬」出馬,亂丟骰子馬欸通?
下一篇
Day11- 讓我們優雅泡咖啡般地選擇容器吧,認識int(), float(), str(), list(), tuple(), dict(), set()
系列文
活用python- 路遙知碼力,日久練成精30

尚未有邦友留言

立即登入留言