Darstellbarkeit mit zwei teilerfremden Münzen prüfen

Die Münzwerte müssen teilerfremd sein, wodurch sich die Aufgabe exakt mit modularer Arithmetik lösen lässt. Ist das Ziel darstellbar, enthält das Ergebnis ein genaues Paar von Münzanzahlen; andernfalls wird eindeutig gemeldet, dass kein solches Paar existiert. Das Werkzeug eignet sich für numerische Versuche, Aufgaben der diskreten Mathematik, die Gestaltung von Stückelungen und die Prüfung exakter Mengenkombinationen ohne vollständige Suche.

Formulieren Sie die Aufgabe mit zwei Münzen genau

Geben Sie zwei positive ganzzahlige Münzwerte als coin_a und coin_b sowie anschließend ein nichtnegatives ganzzahliges Ziel ein. Der Prüfer sucht nichtnegative ganze Zahlen count_a und count_b, sodass die Anzahl der ersten Münzen mal coin_a plus die Anzahl der zweiten Münzen mal coin_b exakt dem Ziel entspricht. Darstellbar bedeutet somit weder einen nahe gelegenen Wert noch eine Kombination unterhalb eines Budgets: Die Gleichheit muss genau gelten und keine Anzahl darf negativ sein. Null ist ein gültiges Ziel, da es durch jeweils null Münzen entsteht. Auch ein Münzwert von eins ist zulässig und macht jedes nichtnegative Ziel darstellbar. Alle drei Eingaben müssen sichere Ganzzahlen sein. Dezimalwerte, Zahlentexte, unendliche Werte und Ganzzahlen außerhalb des exakten JavaScript-Bereichs werden abgewiesen, statt unbemerkt gerundet zu werden. Zusätzlich müssen beide Münzwerte teilerfremd sein; ihr größter gemeinsamer Teiler muss also eins betragen. Diese Voraussetzung kontrolliert der Prüfer vor der Berechnung.

Verstehen Sie die modulare Berechnung

Da die Münzwerte teilerfremd sind, besitzt der erste Wert ein multiplikatives Inverses modulo des zweiten. Der Prüfer berechnet dieses Inverse mit dem erweiterten euklidischen Algorithmus und bestimmt damit den eindeutigen Kandidaten für count_a zwischen null und coin_b minus eins, der die erforderliche Kongruenz erfüllt. Nach Abzug des Beitrags dieser ersten Münzen vom Ziel bleibt ein Rest. Ist er nichtnegativ, ist er durch coin_b teilbar und ergibt einen gültigen Wert für count_b; die Antwort enthält beide Anzahlen als konkreten Nachweis. Ist der Rest negativ, gibt es keine nichtnegative Darstellung. Diese Aussage ist vollständig und keine Näherung: Jede andere ganzzahlige Lösung verändert count_a um ein ganzzahliges Vielfaches von coin_b und count_b in Gegenrichtung um ein ganzzahliges Vielfaches von coin_a. Weil die Berechnung mit dem kleinsten nichtnegativen Kandidaten für count_a beginnt, lässt sich ein negativer Rest nicht beheben, ohne count_a negativ zu machen. Das Verfahren benötigt logarithmische Laufzeit und probiert nicht zahlreiche Münzanzahlen nacheinander aus.

Deuten Sie Ergebnisse und Eingabefehler

Eine Antwort mit wahrem representable enthält count_a und count_b. Multiplizieren Sie beide Anzahlen mit ihrem jeweiligen Münzwert, erhalten Sie wieder exakt das Ziel. Das ausgegebene Paar ist ein gültiger Nachweis; für ein hinreichend großes Ziel kann es mehrere Darstellungen geben, die der Prüfer weder vollständig aufzählt noch optimiert. Bei einer falschen Antwort fehlen die Anzahlen, da kein passendes Paar existiert. Unterscheiden Sie einen Fehler wegen nicht teilerfremder Münzen von einem falschen Ergebnis. Falsch bedeutet, dass die Eingabe dem Vertrag entspricht, das konkrete Ziel aber nicht gebildet werden kann. Ein Fehler bedeutet, dass das Münzpaar außerhalb des festgelegten Bereichs dieser Funktion liegt und daher keine Entscheidung ausgegeben wird. Beispielsweise haben die Münzen 6 und 9 den gemeinsamen Faktor 3 und werden selbst dann abgewiesen, wenn das Ziel durch 3 teilbar ist. So wird eine unzulässige Eingabe nicht mit mathematischer Unmöglichkeit verwechselt. Die Berechnung ist deterministisch, nutzt keinen Netzwerkdienst und liefert im Browser sowie über die API bei denselben exakten Ganzzahlen dasselbe Ergebnis.