Haben Sie jemals ein solches mathematisches Problem gesehen?
"Auf diesem Papier Die Nummer 1 ist ■, die Nummer 2 ist ■, Die Nummer 3 ist ■ Stück, andere Nummern als 1 bis 3 Die Nummer ist in ■ geschrieben. ""
Ein mysteriöses Stück Papier ist gefallen. Auf diesem Papier ist das Papier selbst geschrieben. Die vier in ■ geschriebenen Zahlen sind jedoch verschwunden und ich kann sie nicht lesen. Bitte geben Sie eine Zahl in ■ ein, um diesen Satz zu korrigieren.
Die Antworten sind 4, 1, 3, 1 in der Reihenfolge. Bitte wenden Sie die Zahlen tatsächlich an und überprüfen Sie Dies ist ein Kombinationsproblem auf Mathematikniveau der High School.
Seltsame Dinge passieren, wenn Sie sich auf diese Weise erwähnen.
Kann es ein Programm geben, das feststellt, ob das Programm eine Endlosschleife enthält?
Dies kann zu dem Problem führen. Ein solches Programm kann nicht existieren. Aber was ist mit dem nächsten Problem?
"Dieser Satz enthält () die Nummer 1"
Wenden wir 1 auf () an. Dann
"Dieser Satz enthält (1) die Nummer 1"
Es wird sein. Da 1 insgesamt zweimal im Text vorkommt, widerspricht dies der Bedeutung des Textes. Die Zahl in () ist nicht 1.
Wenden wir eine andere Ganzzahl als 1 an, die 9 oder weniger beträgt.
Dann erscheint 1 nur einmal im Text, aber () sollte anders als 1 sein, also ist es ein Widerspruch. Mit anderen Worten, es ist keine andere Ganzzahl als 1, die 9 oder weniger ist.
Also ist es 10 oder mehr? Auf keinen Fall. Es wäre nicht möglich.
Mit anderen Worten, es gibt keine Ganzzahl in ().
Ich konnte beweisen, dass es mathematisch unmöglich ist. Ja, das Ende
Existiert die Antwort wirklich? Nein existiert. Es ist endlos.
Klicken Sie hier für die Modellantwort
\frac{1}{2}+\frac{3}{2}
Die obige Formel enthält nur eine 1. Daher erscheint insgesamt 1 zweimal im Text. Wenn Sie die obige Formel berechnen, ist das Ergebnis 2.
Auf diese Weise sollte das Ergebnis der Berechnung zwischen reellen Zahlen mit der Anzahl der Einsen übereinstimmen, die in der Formel erscheinen.
Unten ist das Beispiel.
\lceil \sqrt{2} \rceil ,(6-5)
,\cos^2 49^ \circ +\sin^2 49^\circ, etc \cdots
Sicher fühlt es sich an wie. Aber ich mag es nicht wirklich Ich denke, es ist nur ein Ausdruck, keine Zahl.
"Es gibt $ 1/2 + 3/2 $ Äpfel" im Alltag Das sage ich nicht. Nur ein Computer reicht aus, um die Formel als Zahl zu behandeln.
Dann kam ich auf die binäre Notation von ganzen Zahlen. Wenden Sie beispielsweise 0010b auf () im Text an. Insgesamt 1 erscheint zweimal im Text. Da 0010b 2 in Dezimalschreibweise darstellt, konnte ich Sätze ohne Widerspruch verfassen.
In der binären Notation stellen nur 0s und 1s Zahlen dar, sodass diese Methode Zahlen aufzählen kann, die semantisch konsistent sind.
Und wenn Sie diese Ganzzahlzeichenfolge in das Online-Ganzzahlwörterbuch aufnehmen, wird sie möglicherweise populär ...
Ich habe das Programm sofort geschrieben. Es ist ein einfaches Programm, das ungefähr 3 Minuten dauert.
Abgesehen davon ist die interne Implementierung von Javas Integer.bitCount interessant, daher werde ich sie vorstellen.
public static int bitCount(int i) { i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; }
Allein damit können wir die Anzahl von 1 Bits von int zählen. Einfach Shift und logische Operationen ohne Verwendung von Steuerungssyntax wie Schleifen und Bedingungen Ich kann es umsetzen ... Der Berechnungsbetrag beträgt $ O (1) $, da keine Schleife verwendet wird. Beeindruckend Dies basiert auf einem String-Suchalgorithmus namens Wavelet Tree.
Kommen wir nun zum Hauptthema zurück. Führen Sie das Programm aus. Mit Aufregung ./test.out 2000 Was für ein Hit. Dann ist das Ausführungsergebnis
2 3
Das? nur das? Das Erhöhen der Anzahl ändert nichts am Ergebnis. Es scheint innen richtig zu funktionieren.
Korrekt. Wenn Sie darüber nachdenken, beträgt die Anstiegsrate der Anzahl der Bits von 1 in der Ganzzahl mindestens Da es unter $ \ log_2 n $ gehalten werden kann, kann es nicht mit $ n $ konkurrieren, das linear ansteigt.
Es ist mir peinlich, dass ich so etwas nicht realisiert habe
Der Beweis unten
Für eine ganze Zahl $ n $ größer oder gleich 0
Definieren Sie die Funktion $ B (n) $ wie folgt
$ B (n) $: = {Anzahl von 1 Bits, wenn $ n $ in binärer Notation ausgedrückt wird}
Das ist,
Per Definition ist $ B (n) $
Die Gleichung gilt für $ n = 4 $
Daraus wurde $ 0 \ le n \ le 4 $ angezeigt.
Daher erfüllen nur wenige ganze Zahlen die Gleichung.
Es war irgendwie natürlich.
Es war ein Problem, das ich für so interessant hielt, dass ich nachts nicht schlafen konnte, aber in Wirklichkeit Ein natürliches Ergebnis ohne Überraschungen.
Was ist es verbeult?
Lektion: Die meisten Ideen, die vor dem Schlafengehen auftauchen, haben Fallstricke.
das ist alles.