Lösen der Gleichung mit ganzzahliger Division ohne rohe Gewalt

Kürzlich wurde eine Frage zum Toaster gestellt , die mich ernsthaft berührt hat. Es wurzelt in einer Aufgabe, die ich hier in einer etwas anderen Interpretation geben werde:

Sobald die Programmierer das Projekt pünktlich bestanden und Preise erhalten hatten. Um zu feiern, warfen sie sich direkt in Mon und kauften mit dem ganzen Geld Bier. Sie tranken alles am selben Tag und beschlossen bei BT, weiterzumachen, aber es war kein Geld mehr übrig. Dann haben sie die Flaschen übergeben, das gestrige Wechselgeld hinzugefügt und wieder alles auf Lager gebracht, wie gestern. Das gleiche wurde in SR und Chet gemacht. Und in PT war Geld genau eine Flasche. Denken - erinnerte sich an den Preis einer Flasche, wie viel sie Behälter nahmen (Preise waren ohne Cent), und niemand konnte nennen, wie viel Geld ursprünglich war. Das Projekt bestand aus großen Boni - es lohnt sich also nicht. Was war das Mindestbudget in PN, damit sich die Ereignisse auf diese Weise entwickeln konnten?

Über sie wie folgt nachdenken


Ich bin zu einer Gleichung gekommen, die abstrakt so aussieht (1):

$$

$$x = a (x // b) + c$$

Als ich versuchte, einen Ansatz zu finden, ohne erschöpfend nach der Lösung solcher Gleichungen zu suchen, verbrachte ich mehr als eine Stunde, aber am Ende fand ich eine wirklich wunderbare Lösung , aber die Ränder des Buches sind zu eng ;)

Ohne Illusionen über die Überlegenheit in dieser Angelegenheit möchte ich nur die Freude teilen, die ich dabei habe. Wenn jemand eine alternative Methode oder einen alternativen Namen dafür kennt, klären Sie mich auf; Ich fordere diejenigen wie mich auf, darüber zu diskutieren, und die ungeduldigen lade ich Sie unter Katze ein.

Betrachten Sie die resultierende Gleichung in dieser Form (2):

$$

$$(x-c) / a = x // b$$

Da die rechte Seite nur ganzzahlige Werte annehmen kann, ist der gesamte Ausdruck nur dann sinnvoll, wenn der Zähler ein Vielfaches des Nenners auf der linken Seite ist. Daraus ist ersichtlich, dass x Werte ab c und dann mit einem Schritt a haben könnte .

Dann betrachtete ich Gleichung (1) als zwei Funktionen $$$y1 = x$und $$$y2 = a (x // b) + c$. Bei welchem ​​Argument sie sich überschneiden, das ist die Lösung. Zum Beispiel habe ich kleine Werte der Parameter so gewählt, dass das Bild so gut wie möglich angezeigt wird. Also sei a = 3, b = 7, c = 9.


Aufgrund der schrittweisen Natur der zweiten Funktion schneiden sich die Graphen y1 und y2 an zwei Punkten: für x1 = 12 und x2 = 15, aber je nach Bedingung interessiert uns der erste Wert als der kleinere. Um den Schnittbereich ohne erschöpfende Suche zu bestimmen, habe ich eine dritte Funktion eingeführt - es ist nur eine gerade Linie, die die Funktion y2 von unten begrenzt und die Gleichung hat $$$y3 = a / b (x - (b-1)) + c$.

Nun bleibt es, den Schnittpunkt der beiden Linien ( y1 und y3 ) zu finden und die Antwort aus der Beschränkung auf das gewünschte x anzupassen. In der Tat kann es auf der Basis der Bedingung nur diejenigen Werte annehmen, bei denen die Bedingung des Multiplikators des Zählers für den Nenner in Gleichung (2) erfüllt ist, d.h. $$$x = c + na$, wobei n ein bestimmter natürlicher Faktor ist. Dazu lösen wir eine einfache Gleichung $$$x = a / b (x - (b-1)) + c$und wenn die resultierende Wurzel nicht unseren Anforderungen entspricht, werden wir sie zur nächstgelegenen geeigneten verschieben. Da die Hilfsfunktion y3 eine positive Steigung aufweist und alle Werte von y2 darüber liegen, sollte die Wurzel immer nach oben eingestellt werden. In unserem Fall schneiden sich die Linien also bei x = 11,25 (schwarzer Punkt im Diagramm), und der nächste große Wert, der die Bedingung erfüllt, ist 12 (roter Punkt), was die Antwort ist.

Da die Frage auf dem Toaster ein Python-Tag enthielt, werde ich unten ein Skript zur Lösung dieses Problems mithilfe der Funktion geben, um das Budget des aktuellen Tages basierend auf dem Budget des nächsten Tages zu ermitteln. Wir wenden die Funktion so oft an, wie es nötig ist, und voila, wir bekommen die Antwort!

def this_day_budget(next_day_budget): a = bottle_price - tare_return_price b = bottle_price c = next_day_budget x = (a - a*b + b*c)/(b - a) if (x - c) % a: # value does not match the increment x = ((xc)//a + 1) * a + c return x bottle_price = 7 tare_return_price = 4 party_duration_days = 5 last_day_budget = bottle_price for days_to_party_end in range(party_duration_days): if days_to_party_end == 0: current_budget = last_day_budget else: current_budget = this_day_budget(current_budget) print('first day budget was - %d' % current_budget) 

Anstelle einer Schlussfolgerung:

Die Aufgabe in diesem Beispiel wurde als Parameterwert bestimmt $$$a <b <c <x$und die Gleichung selbst $$$x = a (x // b) + c$;; Der vorgeschlagene Ansatz mit geringfügigen Änderungen ist in anderen ähnlichen Fällen anwendbar - der Zweck der Veröffentlichung bestand nur darin, das Prinzip zu beschreiben, ohne eine universelle Lösung für den allgemeinen Fall abzuleiten - daher nicht streng zu urteilen (Python-Code, inkl.), und einen schönen Freitag zu haben!