建立联系

每周挑战 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中文网其他相关文章！