In thematischen Foren regelmäßig auftretende Streitigkeiten darüber, ob ein Programmierer Mathematik braucht, sind längst zu einem alltäglichen Ort und Bereich heiliger Kriege geworden. Da wir uns auf unserer (rechten) Seite der Grenze befinden, die das Gute vom Bösen trennt, möchte ich ein Beispiel nennen, das deutlich zeigt, wie viel es benötigt und sogar (wir werden keine Angst vor diesem Wort haben) notwendig ist.
Stellen Sie sich ein interessantes Programmierproblem vor, das einen etwas olympischen Charakter hat.
Pnp: Von diesem Punkt an können Befürworter der Idee, dass das Programmieren heute aus wunderschön gestalteten Webseiten besteht, aufhören zu lesen. Sie haben absolut Recht, Sie brauchen keine Mathematik ...
Nun, darauf müssen Sie nicht bestehen, Sie sind nicht schlechter als wir und Ihre Arbeit ist wirklich wichtig, weil ich bereits zugestimmt habe, dass wir unterschiedliche Vorstellungen von Programmierung haben ...
Ja, Sie haben absolut Recht, dass diese Olympiaden mit Hilfe des letzten Frameworks nicht in der Lage sind, sieben rote senkrechte Linien in einer Codezeile zu zeichnen ...
Trotzdem halte ich es für meine richtige Idee (dies ist eine fatale Eigenschaft hochorganisierter Materie in Form von Proteinkörpern), daher werde ich die Argumente in ihrer Unterstützung präsentieren.Ich formuliere das Problem - wie viele verschiedene Zahlen der Länge K, die mit einer bestimmten p-Taste enden, können auf der Telefontastatur (Tastatur) eingegeben werden, wenn wir die Tasten mit einem Schachritter bewegen müssen. Es versteht sich, dass Sie die Tastatur gesehen haben (ich habe immer noch ein normales Mobiltelefon, kein Smartphone, daher sehe ich es jeden Tag, ein fortgeschrittener Leser sollte sich an das Internet wenden, um Hilfe zu erhalten) und Sie wissen, wie ein Schachpferd läuft (einfach zu googeln). Mathematik hat bisher nichts damit zu tun, wenn Sie nicht daran denken, Optionen berechnen zu können.
Die erste Lösung liegt auf der Hand: Wir nehmen alle 10 Schaltflächen nacheinander (wir bezeichnen ihre Zahl der Allgemeinheit halber mit n), betrachten alle möglichen langen K-Zahlen und zählen diejenigen, die auf der gewünschten Schaltfläche enden. Die resultierenden Zahlen werden zusammengefasst und die Antwort ist fertig. Die Gesamtzahl der angezeigten Optionen wird ungefähr als n * B (K) ausgedrückt, wobei B (K) die Anzahl der möglichen Bewegungen der Länge K ist. Tatsächlich müssen Sie die Summe von n Positionen berücksichtigen, da B (p, K) ganz offensichtlich von der Schaltfläche abhängt aber als erste Schätzung kommen runter.
Bevor Sie mit der Suche B fortfahren, können Sie die Anzahl der Optionen erheblich reduzieren, indem Sie den gesunden Menschenverstand anwenden (nein, noch nicht mathematisch). Da die Bewegung der Tasten ein vom Hintergrund abhängt, können wir die Aufgabe umkehren und ab der gewünschten p-Taste nach allen Zahlen der Länge K suchen. Dann ist die Gesamtzahl der Optionen B (p, K), was n-mal weniger ist. Wow, wir haben gerade einen Weg gefunden, die Suche nach einer Lösung zehnmal zu beschleunigen - cool, mal sehen, wie viel noch übrig ist.
Wir müssen B (p, K) bewerten, für das wir bestimmen, dass wir bei jedem Zug 2 bis 3 Optionen für die Entwicklung von Ereignissen haben. Daraus folgt (im Allgemeinen ist dies kombinatorisch, aber intuitiv klar), dass die Gesamtzahl der Optionen zwischen 2 ** K und 3 ** K liegt (im Folgenden verwende ich K-1 als K). Wir können diese Schätzung sogar verbessern, indem wir zu einem Wahrscheinlichkeitsmodell übergehen. Wenn man bedenkt, dass das Vorhandensein eines Fingers in jeder Taste im Moment gleich wahrscheinlich ist (eine starke Aussage, höchstwahrscheinlich falsch, aber mit groben Schätzungen akzeptabel), können wir die durchschnittliche Anzahl der Bewegungsoptionen 7 * 2 + 2 (Tasten 4 und 6) * 3 = 20/9 ~ 2,22 berechnen . Dann beträgt die Schätzung 2,22 ** K, und wir wissen mit Sicherheit, dass wir mindestens 2 ** K haben. Dann erhalten wir für K = 100 eine Untergrenze 2 ** 100 = (2 ** 10) ** 10> (10 ** 3) ** 10 = 10 ** 30.
Wenn wir eine Option in einer Nanosekunde in Betracht ziehen (und dies ist selbst auf einem leistungsstarken Desktop-PC nicht einfach), benötigen wir 10 ** 30/10 ** 9 = 10 ** 21 Sekunden. Als nächstes erinnern wir uns an die wunderbare mnononische "π Sekunden sind gleich einem Jahrhundert" und die erforderliche Zeit wird 10 ** 21 / 3,14 * 10 ** 9 ~ 3 * 10 ** 11 Jahrhunderte betragen. Es scheint mir, dass nur wenige Leser das Ende der Berechnungen mit der vorgeschlagenen Methodik erleben werden. Der Aussteller ist schrecklich, nur Fakultät ist schlimmer als sie.
Wir werden die Lösung basierend auf der Tatsache verbessern, dass wir an der Anzahl der Optionen interessiert sind, aber nicht an den Optionen selbst. Sie können die offensichtliche Formel B (p, K) = die Summe von B (p ', K-1) für alle p' anbieten, in denen wir in 1 Zug von p erhalten. Wir beginnen mit der letzten Schaltfläche und weisen ihr eine Gewichtung von 1 zu. Führen Sie dann den Vorgang des Summierens der aktuellen Gewichte zur nächsten aus und wiederholen Sie den Vorgang bis zur gewünschten Tiefe.
Wir veranschaulichen das Gesagte anhand eines Beispiels, beginnend mit der Nummer 1 {1234567890}:
Anfangsgewicht {1000000000},
nach der ersten Übertragung {0000010100} (2 Optionen),
nach der zweiten Übertragung {2010001001} (5 Optionen),
nach dem dritten {0102040300} (10 Optionen) und so weiter.
Der Algorithmus ist einfach, er kann sogar mit Ihren Händen implementiert werden. Die allgemeine Schätzung der Ausführungszeit ist K Iterationen, bei denen wir für n Gewichte jeweils nicht mehr als n verwandte Gewichte modifizieren, insgesamt
n ** 2 * K. Für den zuvor betrachteten Fall ist 10 * 10 * 100 = 10 ** 4 - ziemlich viel.
Es bleibt nur die Dauer jeder Operation zu bewerten - dies ist eine Addition (Müllfrage), aber keine einfache Addition (von dieser Stelle aus detaillierter). Wir haben die Untergrenze der Antwort bereits auf 2 ** K gesetzt, dh wir benötigen definitiv mindestens K Bits, um das Ergebnis darzustellen. Die Obergrenze ist 3 ** K, für unseren Fall 3 ** 100 = (3 ** 5) ** 20 <(2 ** 8) * 20 = 2 ** 160, dh wir passen garantiert in 160 Bit. Wir können davon ausgehen, dass 128 Bit für uns ausreichen, da 2,2 ** 100 <2 ** 128, aber das Akzeptieren einer solchen Aussage über den Glauben ist beängstigend. Daher benötigen wir eine Zahl mit mindestens 160 Bit oder 49 Dezimalstellen, abhängig von Ihrer Zahlenbibliothek hohe Genauigkeit.
PNP: Bieten Sie keinen Gleitkomma an, wir benötigen ein vollständig genaues Ergebnis.In den akzeptierten Annahmen belegt die Additionsoperation 160/8 = 20 Bytes / 4 = 5 Additionen von 32 Bit langen Ganzzahlen, was die Zeitreihenfolge in keiner Weise beeinflusst (sie bleibt in K linear), kann jedoch die tatsächliche Berechnungszeit erheblich erhöhen (um ein Mehrfaches).
In jedem Fall ist das Ergebnis einfach großartig - wir haben die Aufgabe von grundlegend unlösbar in angemessener Zeit auf vollständig lösbar umgestellt: Wenn eine elementare Additionsoperation in einer Mikrosekunde durchgeführt wird (und dies ist auch auf der Arduino-Platine leicht sicherzustellen), wird die Gesamtzeit 10 ** 4 * 20 nicht überschreiten / 10 ** 6, weniger als eine Sekunde) und wir haben auf Mathe verzichtet.
Trotzdem und wenn wir ein größeres K benötigen - natürlich die lineare Reihenfolge der Berechnungen - ist dies großartig, aber es kann (und wird) zu erheblichen Zeitverlusten für große Werte führen. Es stellt sich heraus, dass Sie die erwartete Zeit erheblich verbessern können, achten Sie auf Ihre Hände.
Was wir bei jedem Berechnungsschritt machen (Pseudocode):
= 0;
1
2
* ( 1 2)
* 1 2.
=
2 ( 1 * )
0 1, . '=* =(...((*)*)...). , =***. , . **3,
***3 — , ? , …
— , **3 , , , ( ) ( ), . , 100 99 8. , 2*log2(), ( =100 1000/10=100 ) ,
2*log2()***3. , , , . , , log2(K), , , 100.
- ( , ), , , .