建立聯繫

每週挑戰 285

穆罕默德·S·安瓦爾 (Mohammad S. Anwar) 每週都會發出“每週挑戰”，讓我們所有人都有機會為兩週的任務提出解決方案。我的解決方案先用Python編寫，然後轉換為Perl。這對我們所有人來說都是練習編碼的好方法。

挑戰，我的解決方案

任務 1：無連接

任務

您將獲得路線列表，@routes。

編寫一個腳本來找出目的地，而無需進一步的傳出連結。

我的解決方案

這非常簡單，因此不需要太多解釋。我計算兩個列表，出發地具有路線列表中的第一個值，而目的地具有第二個值。

然後，我使用清單理解來尋找不在起始清單中的目的地，並將其儲存為 dead_ends。如果此列表中不存在一項，我會發出錯誤。

def no_connection(routes: list) -> str:
    origins = [v[0] for v in routes]
    destinations = [v[1] for v in routes]
    dead_ends = [d for d in destinations if d not in origins]

    if len(dead_ends) > 1:
        raise ValueError(
            'There are multiple routes with no outgoing connection')

    if len(dead_ends) == 0:
        raise ValueError('All routes have an outgoing connection')

    return dead_ends[0]

範例

$ ./ch-1.py B C C D D A
A

$ ./ch-1.py A Z
Z

任務 2：做出改變

任務

計算給定金額（以美分為單位）找零的方式數量。透過使用硬幣，例如便士、鎳幣、一毛幣、四分之一美元和半美元，有多少種不同的方式可以使總價值等於給定金額？硬幣選擇順序並不重要。

• 一便士 (P) 等於 1 分。
• 一鎳 (N) 等於 5 分。
• 一毛錢 (D) 等於 10 美分。
• 四分之一 (Q) 等於 25 美分。
• 半美元 (HD) 等於 50 美分。

我的解決方案

由於我的程式碼中存在一個（現在已修復）錯誤，這比我希望的要花更長的時間才能完成。我知道 Python 和 Perl 都有調試器，但有時你無法擊敗列印語句:)

我們已經有一段時間沒有任務需要使用遞歸函數了。對於這個任務，我有一個名為making_change的遞歸函數，它取得剩餘的零錢和最後使用的硬幣。第一個呼叫將剩餘的變更值設為輸入，並將最後的硬幣值設為 None（Perl 中的 undef）。

每次呼叫都會迭代可能的硬幣，並執行以下三件事之一：

1. 如果硬幣值大於last_coin值，我們會跳過它。這可以確保我們不會重複可能的組合。
2. 如果硬幣值與剩餘零錢相同，我們就有一個有效的解決方案，所以我在組合值上加一。
3. 如果硬幣價值小於剩餘價值，我會再次呼叫該函數，剩餘價值會減去所使用的硬幣。

組合值被傳遞到上游，因此最終回傳將具有正確的組合數量。

def making_change(remaining: int, last_coin: int | None = None) -> int:
    combinations = 0

    for coin in [1, 5, 10, 25, 50]:
        if last_coin and last_coin < coin:
            continue
        if coin == remaining:
            combinations += 1
        if coin < remaining:
            combinations += making_change(remaining-coin, coin)

    return combinations

遞歸是有限制的。當遞歸達到（100 深度）時，Perl 會發出警告[https://perldoc.perl.org/perldiag#Deep-recursion-on-subroutine-%22%25s%22]。該值只能透過重新編譯 Perl 來更改。預設情況下，Python 將在 995 次遞歸後引發 (ResursionError)[https://docs.python.org/3/library/exceptions.html#RecursionError]，儘管該值可以在運行時修改。

範例

$ ./ch-2.py 9
2

$ ./ch-2.py 15
6

$ ./ch-2.py 100
292

以上是建立聯繫的詳細內容。更多資訊請關注PHP中文網其他相關文章！