Eine schmerzhafte Interviewfrage

Ich habe gestern zwei Fragen im Vorstellungsgespräch gesehen. Es gab zwei Fragen, die die erste Frage beantworteten, aber nur wenige Leute beantworteten die zweite Frage. Ich lerne kürzlich PHP, daher verwendet dieser Artikel PHP als Grundlage für die heutige zweite Analyse.

Anbei sind zwei Interviewfragen:

1: Es gibt 100 Lichter in der Halle, und jedes Licht ist nummeriert, von 1 bis 100. Jedes Licht wird durch einen Schalter gesteuert. (Drücken Sie den Schalter einmal, um das Licht einzuschalten, und drücken Sie ihn erneut, um das Licht auszuschalten. Die Nummer des Schalters ist dieselbe wie die des gesteuerten Lichts.) Zu Beginn sind alle Lichter ausgeschaltet. Drücken Sie nun den Schalter gemäß den folgenden Regeln.
Zünden Sie zum ersten Mal alle Lichter an.
Drücken Sie zum zweiten Mal alle Schalter, die ein Vielfaches von 2 sind.
Drücken Sie zum dritten Mal alle Schalter, die ein Vielfaches von 3 sind.
Und so weiter. Drücken Sie zum N-ten Mal alle Schalter, die ein Vielfaches von N sind.
Fragen Sie, wie viele Lichter in der Halle nach dem 100. Tastendruck noch brennen.
2: Es gibt eine 27 cm dünne Holzstange und an jeder der fünf Positionen befindet sich eine Ameise: 3 cm, 7 cm, 11 cm, 17 cm und 23 cm. Die Holzstange ist sehr dünn und kann nicht gleichzeitig an einer Ameise vorbeikommen. Zu Beginn war es willkürlich, ob die Köpfe der Ameisen nach links oder rechts zeigten. Sie gingen nur vorwärts oder drehten sich um, zogen sich aber nicht zurück. Wenn sich zwei Ameisen treffen, drehen sie sich um und gehen gleichzeitig in entgegengesetzte Richtungen. Angenommen, Ameisen können sich einen Zentimeter pro Sekunde bewegen. Schreiben Sie ein Programm, um die minimale und maximale Zeit zu ermitteln, die alle Ameisen benötigen, um den Holzpfahl zu verlassen.

Das erste ist relativ einfach und ich werde nicht näher darauf eingehen, aber das zweite löst schon beim bloßen Anblick Kopfschmerzen aus.

Lassen Sie uns diese Frage kurz analysieren.

Der Frage selbst nach zu urteilen, scheint es wirklich verwirrend zu sein, die Positionen von fünf Ameisen gleichzeitig zu betrachten. Glücklicherweise ist der letzte Satz der Frage immer noch sehr nützlich. Es handelt sich um die maximale und minimale Zeit, die alle Ameisen benötigen, um den Holzpfahl zu verlassen. Verwenden Sie den dünnen Stab als horizontale Achse. Die Positionen der Ameisen sind angegeben. Wenn die Position der letzten verlassenden Ameise <=0 oder >=27 ist, verlassen alle Ameisen den Holzpfahl. (Das scheint Unsinn zu sein.)

1 Meter pro Sekunde, diese Fragestellung reicht aus, um es den Menschen bequem zu machen. Schließlich ist die Zeit, die die Ameise hier zurücklegt, numerisch gleich der Entfernung, die die Ameise zurücklegt. (Wenn man davon ausgeht, dass alle Ameisen den Holzstab verlassen und sich mit der ursprünglichen Geschwindigkeit weiterbewegen). Und sie bewegen sich gleichzeitig.

Es gibt nur zwei Bewegungsrichtungen von Ameisen, links oder rechts. Wenn wir unter Berücksichtigung der tatsächlichen Situation der Koordinatenachsen davon ausgehen, dass die Bewegung nach rechts 1 beträgt, beträgt die entsprechende Bewegung nach links -1. Es ist wichtig, diesen Schritt in der binären Welt der Computer zu berücksichtigen.

Okay, hier ist die Vorahnung, ob Sie es verstehen oder nicht, hier ist der wichtigere Inhalt.

Das Ermitteln der maximalen und minimalen Zeit ist genauso wie das Ermitteln der maximalen und minimalen Zahlen in einer Reihe von Zahlen. So etwas sollte nicht schwierig sein. Der Schlüssel liegt darin, den letzten Zeitpunkt für den Vergleich zu finden. Was hat Zeit mit irgendetwas zu tun? Dem Titeldesign nach zu urteilen, sollte es sich nur auf den anfänglichen Bewegungsstatus jeder Ameise beziehen. Müssen wir uns über den Bewegungsstatus einer bestimmten Ameise zu einem bestimmten Zeitpunkt während des Zeitraums Sorgen machen? Keine Notwendigkeit. Das würde das Problem nur verkomplizieren.

Wie viele Ausgangszustände gibt es für Ameisen? Offensichtlich muss jede dieser 32 Zeitarten berechnet werden, und es kann eine einfache Schleife verwendet werden.

Die Konzentration auf den Bewegungsstatus von Ameisen besteht aus nichts anderem als zwei Variablen: Position und Richtung. Deshalb stelle ich hier einfach zwei Arrays vor: $arr und $b . Ersteres wird verwendet, um die aktuelle Position eines bestimmten Punktes zu beschreiben, und letzteres wird verwendet, um die aktuelle Richtung zu beschreiben. $b[i]

Wie zuvor beschrieben sollte der Wert nur -1 oder 1 sein.

In Anbetracht dessen können wir unserer Überlegung folgen und den Arrays „$arr“ und „$b“ einen Anfangswert zuweisen. Verwenden Sie die Zeit '$i', um eine Schleife zu erstellen, nachdem sich jede Ameise jede Sekunde bewegt, wenn '$arr[$k]==$arr[$k-1]' ist, ändern Sie den passenden Statuswert '$b[k ]'. Wert. Wenn der „Wert“ aller „$arr“ <=0 oder >=27 ist, beenden Sie die Schleife und geben Sie „$i“ zurück. Es wird viel Schleifendurchquerung verwendet. Der Einfachheit halber können Sie „$arr[$k]“ natürlich mit der Funktion unset() löschen, wenn es sich nicht mehr auf der Stange befindet. Abschließend wird beurteilt, dass „$arr“ leer ist, um die Schleife zu beenden.

Nachdem wir über den Hauptinhalt gesprochen haben, müssen wir uns noch mit einem kleinen Detail befassen. Wie generiert man das Array „$b“, das den Bewegungsstatus von Ameisen beschreibt?

Das geht nicht Es gibt 32 Situationen für 5 Ameisen, es ist wirklich mühsam, 1024 Situationen für 10 Ameisen zu generieren. Aber Sie wissen offensichtlich, dass 32 Arrays generiert werden müssen, also müssen Sie es verwenden. Daher können wir uns leicht vorstellen, eine Dezimalzahl in eine Binärzahl der Länge 5 umzuwandeln. Ersetzen Sie dann die 0 in dieser Binärzahl durch -1. Konvertieren Sie die ersetzte Zeichenfolge in ein Array.

Fügen Sie abschließend den entsprechenden Code ein:

<?<span>php
</span><span>for</span>(<span>$j</span>=0;<span>$j</span><32;<span>$j</span>++<span>){

    </span><span>$var</span>=<span>sprintf</span>("%05b", <span>$j</span><span>);

    </span><span>$var</span>=<span>str_replace</span>('1', '1|', <span>$var</span><span>);
    </span><span>$var</span>=<span>str_replace</span>('0', '-1|', <span>$var</span><span>);

    </span><span>$b</span>=<span>explode</span>('|',<span>$var</span><span>);

    </span><span>$res</span>=getRes(<span>$b</span><span>);


    </span><span>if</span> (<span>isset</span>(<span>$min</span><span>)) {
        </span><span>if</span> (<span>$res</span><<span>$min</span><span>) {
            </span><span>$min</span>=<span>$res</span><span>;

        }
    }</span><span>else</span><span>{
        </span><span>$min</span>=<span>$res</span><span>;
    }
    </span><span>if</span> (<span>isset</span>(<span>$max</span><span>)) {
        </span><span>if</span> (<span>$res</span>><span>$max</span><span>) {
            </span><span>$max</span>=<span>$res</span><span>;
        }
    }</span><span>else</span><span>{
        </span><span>$max</span>=<span>$res</span><span>;
    }
    </span><span>print_r</span>(<span>$b</span><span>);
    </span><span>echo</span> "此次结果是".<span>$res</span>.'   $max='.<span>$max</span>.'  $min='.<span>$min</span><span>;
    </span><span>echo</span> "<hr/>"<span>;

}


</span><span>echo</span> "最大值是".<span>$max</span>."最小值是".<span>$min</span><span>;


</span><span>//</span><span>获得某种情况下的时间</span><span>function</span> getRes(<span>$b</span><span>){
    </span><span>$arr</span>=<span>array</span>(3,7,11,17,23<span>);
    </span><span>for</span>(<span>$i</span>=1;<span>$i</span><100;<span>$i</span>++<span>){

        </span><span>foreach</span> (<span>$arr</span><span>as</span><span>$k</span> => <span>$val</span><span>) {
            </span><span>$arr</span>[<span>$k</span>]=<span>$val</span>+<span>$b</span>[<span>$k</span><span>];
            </span><span>if</span> (<span>$arr</span>[<span>$k</span>]==@<span>$arr</span>[<span>$k</span>-1<span>]) {
                </span><span>$b</span>[<span>$k</span>]=-<span>$b</span>[<span>$k</span><span>];
                </span><span>$b</span>[<span>$k</span>-1]=-@<span>$b</span>[<span>$k</span>-1<span>];
            }

            </span><span>if</span> ((<span>$arr</span>[<span>$k</span>]>=27)||(<span>$arr</span>[<span>$k</span>]<=0<span>)) {
                </span><span>unset</span>(<span>$arr</span>[<span>$k</span><span>]);
            }
        }


        </span><span>if</span> (<span>empty</span>(<span>$arr</span><span>)) {
            </span><span>return</span><span>$i</span><span>;
        }


    }

}</span>

PHP ist nicht gut in mathematischen Operationen, und ich bin nicht gut in mathematischen Operationen. Ich habe das Gefühl, dass der Code, den ich oben geschrieben habe, die Aufgabe kaum erledigen kann. Ich hoffe auch, Ihre Anleitung zu bekommen.

Das Obige führt eine schmerzhafte Interviewfrage ein, einschließlich der relevanten Aspekte. Ich hoffe, dass sie für Freunde hilfreich ist, die sich für PHP-Tutorials interessieren.