Verbindungen herstellen

Wöchentliche Herausforderung 285

Jede Woche verschickt Mohammad S. Anwar die Weekly Challenge, eine Chance für uns alle, Lösungen für zwei wöchentliche Aufgaben zu finden. Meine Lösungen werden zunächst in Python geschrieben und dann in Perl konvertiert. Es ist eine großartige Möglichkeit für uns alle, etwas Codierung zu üben.

Herausforderung, meine Lösungen

Aufgabe 1: Keine Verbindung

Aufgabe

Sie erhalten eine Liste mit Routen, @routes.

Schreiben Sie ein Skript, um das Ziel ohne weitere ausgehende Verbindung zu finden.

Meine Lösung

Das ist ziemlich einfach und bedarf daher keiner allzu großen Erklärung. Ich berechne zwei Listen. „Ursprünge“ hat die ersten Werte aus der Routenliste, während „Ziele“ den zweiten Wert haben.

Ich verwende dann das Listenverständnis, um Ziele zu finden, die nicht in der Ursprungsliste enthalten sind, und speichere diese als dead_ends. Ich melde eine Fehlermeldung, wenn diese Liste nicht genau ein Element enthält.

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]

Beispiele

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

$ ./ch-1.py A Z
Z

Aufgabe 2: Veränderung herbeiführen

Aufgabe

Berechnen Sie die Anzahl der Möglichkeiten, Wechselgeld für einen bestimmten Betrag in Cent herauszugeben. Durch die Verwendung der Münzen z.B. Penny, Nickel, Dime, Quarter und Half-Dollar, auf wie viele verschiedene Arten kann der Gesamtwert dem gegebenen Betrag entsprechen? Die Reihenfolge der Münzauswahl spielt keine Rolle.

• Ein Penny (P) entspricht 1 Cent.
• Ein Nickel (N) entspricht 5 Cent.
• Ein Cent (D) entspricht 10 Cent.
• Ein Viertel (Q) entspricht 25 Cent.
• Ein halber Dollar (HD) entspricht 50 Cent.

Meine Lösung

Aufgrund eines (jetzt behobenen) Fehlers in meinem Code hat die Fertigstellung etwas länger gedauert, als ich gehofft hatte. Ich weiß, dass sowohl Python als auch Perl einen Debugger haben, aber manchmal sind print-Anweisungen unschlagbar :)

Es ist schon eine Weile her, seit wir eine Aufgabe haben, die die Verwendung einer rekursiven Funktion erfordert. Für diese Aufgabe habe ich eine rekursive Funktion namens making_change, die das verbleibende Wechselgeld und die zuletzt verwendete Münze übernimmt. Der erste Aufruf setzt den restlichen_change-Wert auf die Eingabe und den last_coin-Wert auf None (undef in Perl).

Jeder Aufruf durchläuft die möglichen Münzen und führt eines von drei Dingen aus:

1. Wenn der Münzwert größer als der last_coin-Wert ist, überspringen wir ihn. Dadurch wird sichergestellt, dass wir mögliche Kombinationen nicht duplizieren.
2. Wenn der Münzwert mit dem verbleibenden Wechselgeld übereinstimmt, haben wir eine gültige Lösung, also füge ich eins zum Kombinationswert hinzu.
3. Wenn der Münzwert geringer ist als der Restwert, rufe ich die Funktion erneut auf, wobei der Restwert um die verwendete Münze reduziert wird.

Der Kombinationswert wird vorgelagert übergeben, sodass die endgültige Rückgabe die richtige Anzahl von Kombinationen aufweist.

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

Es gibt Grenzen für die Rekursion. Perl warnt, wenn eine Rekursion (100 tief) ist[https://perldoc.perl.org/perldiag#Deep-recursion-on-subroutine-%22%25s%22]. Dieser Wert kann nur durch eine Neukompilierung von Perl geändert werden. Standardmäßig löst Python nach 995 Rekursionen einen (ResursionError)[https://docs.python.org/3/library/Exceptions.html#RecursionError] aus, obwohl dieser Wert zur Laufzeit geändert werden kann.

Beispiele

$ ./ch-2.py 9
2

$ ./ch-2.py 15
6

$ ./ch-2.py 100
292

Das obige ist der detaillierte Inhalt vonVerbindungen herstellen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!