最も迷惑な面接の質問

痛ましい面接の質問

昨日、面接の質問が 2 つありました。最初の質問には多くの人が答えましたが、2 番目の質問にはほとんど答えられませんでした。最近 PHP を勉強しているので、この記事では PHP をベースにして 2 回目の分析をお届けします。

添付の面接質問は 2 つです:

1: ホールには 100 個の照明があり、それぞれの照明には 1 ～ 100 の番号が付いています。 。各ライトはスイッチによって制御されます。 （スイッチを1回押すとライトが点灯し、もう一度押すと消灯します。スイッチの番号は制御されているライトと同じです。） 最初はすべてのライトが消灯しています。次のルールに従ってスイッチを押してください。
初めてすべてのライトを点灯します。
2 回目は、2 の倍数のスイッチをすべて押します。
3 回目は、3 の倍数のスイッチをすべて押します。
など。 N 回目は、N の倍数のスイッチをすべて押します。
ボタンを 100 回押した後、ホールにまだ点灯している照明が何個あるかを尋ねます。


2:27cmの細い木の棒があり、3cm、7cm、11cm、17cm、23cmの5つの位置にそれぞれアリがいます。木の棒は非常に細いので、同時にアリを通過することはできません。初めは、アリの頭が左を向いているか右を向いているかは任意で、アリは前進するか振り向くだけで、後退することはありませんでした。二匹のアリが出会うと、向きを変えて同時に反対方向に歩きます。アリが毎秒 1 センチメートル移動できると仮定します。すべてのアリが木の棒から離れる最小時間と最大時間を見つけるプログラムを作成してください。

1 つ目は比較的単純なので詳しくは説明しませんが、2 つ目は見ているだけで頭痛がしてしまいます。

この質問を簡単に分析してみましょう。

質問自体から判断すると、5 匹のアリの位置を同時に考えるのは非常に混乱しているようです。幸いなことに、質問の最後の文は、すべてのアリが木の棒から離れる最大時間と最小時間 にまだ役立ちます。細い棒を水平軸として使用します。アリの位置が指定されています。最後に離れるアリの位置が =27 の場合、すべてのアリが木の棒から離れます。 （これはナンセンスのようです。）

秒速1メートル、この問題設定は人々を快適にするのに十分です。結局のところ、アリがここで移動する時間は、アリが移動する距離と数値的に同じです。 (すべてのアリが木の棒から離れ、元の速度で移動し続けるとみなした場合)。そしてそれらは同時に動いています。

アリの移動方向は左右の 2 方向のみです。座標軸の実際の状況を考慮して、右への移動を 1 とすると、同等の左への移動は -1 となります。このステップをコンピューターのバイナリの世界で考えることが重要です。

さて、ここからが伏線ですが、理解できるかどうかは別として、より重要な内容は次のとおりです。

最大時間と最小時間を見つけることは、多数の数値の中から最大値と最小値を見つけるのと同じです。この種のことは難しいことではありません。重要なのは、最後に比較を行った時期を見つけることです。 時間は何かと何の関係があるのでしょうか？タイトルデザインから判断すると、各アリ

の初期動作ステータスのみに関係しているはずです。期間中のある瞬間における、あるアリの移動状況については、気にする必要があるでしょうか？必要なし。それは問題を複雑にするだけです。

アリの初期状態はいくつありますか? 2^5=32。明らかに、これら 32 種類の時間をそれぞれ計算する必要があり、単純なループを使用できます。

アリの移動状況に注目すると、

位置と方向の 2 つの変数にすぎません。したがって、ここでは単純に 2 つの配列 $arr と $b を導入します。前者は特定の点の現在位置を表すために使用され、後者は現在の方向を表すために使用されます。 $b[i]

前述したように、値は -1 または 1 のみである必要があります。

これを考慮すると、考え方に従って、配列 '$arr' と '$b' に初期値を割り当てることができます。時間 '$i' を使用してループを作成し、各アリが毎秒移動した後、'$arr[$k]==$arr[$k-1]' のときに、一致する状態値 '$b[k ]' を変更します。価値。 すべての「$arr」の「値」が =27 の場合、ループを停止し、「$i」を返します。ループトラバーサルが多用されます。もちろん、簡単にするために、'$arr[$k]' がポール上になくなったら、unset() 関数を使用してそれを削除できます。最後に、'$arr'が空であると判断してループを終了します。

メインの内容を話した後は、

アリの移動状況を記述する配列 "$b" を生成する方法?

手動で生成することはできません。 5 アリの場合は 32 の状況があり、10 アリの場合は 1024 の状況があります。手動で生成するのは非常に面倒です。ただし、32 個の配列を生成する必要があることは明らかなので、それを使用する必要があります。したがって、10 進数を長さ 5 の 2 進数に変換することは容易に考えられます。次に、この 2 進数の 0 を -1 に置き換えます。置換された文字列を配列に変換します。

対応するコードを貼り付けます:

<span style="color: #000000;">php</span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$j</span>=0;<span style="color: #800080;">$j</span>$j++<span style="color: #000000;">){    </span><span style="color: #800080;">$var</span>=<span style="color: #008080;">sprintf</span>("%05b", <span style="color: #800080;">$j</span><span style="color: #000000;">);    </span><span style="color: #800080;">$var</span>=<span style="color: #008080;">str_replace</span>('1', '1|', <span style="color: #800080;">$var</span><span style="color: #000000;">);    </span><span style="color: #800080;">$var</span>=<span style="color: #008080;">str_replace</span>('0', '-1|', <span style="color: #800080;">$var</span><span style="color: #000000;">);    </span><span style="color: #800080;">$b</span>=<span style="color: #008080;">explode</span>('|',<span style="color: #800080;">$var</span><span style="color: #000000;">);    </span><span style="color: #800080;">$res</span>=getRes(<span style="color: #800080;">$b</span><span style="color: #000000;">);    </span><span style="color: #0000ff;">if</span> (<span style="color: #0000ff;">isset</span>(<span style="color: #800080;">$min</span><span style="color: #000000;">)) {        </span><span style="color: #0000ff;">if</span> (<span style="color: #800080;">$res</span>$min<span style="color: #000000;">) {            </span><span style="color: #800080;">$min</span>=<span style="color: #800080;">$res</span><span style="color: #000000;">;        }    }</span><span style="color: #0000ff;">else</span><span style="color: #000000;">{        </span><span style="color: #800080;">$min</span>=<span style="color: #800080;">$res</span><span style="color: #000000;">;    }    </span><span style="color: #0000ff;">if</span> (<span style="color: #0000ff;">isset</span>(<span style="color: #800080;">$max</span><span style="color: #000000;">)) {        </span><span style="color: #0000ff;">if</span> (<span style="color: #800080;">$res</span>><span style="color: #800080;">$max</span><span style="color: #000000;">) {            </span><span style="color: #800080;">$max</span>=<span style="color: #800080;">$res</span><span style="color: #000000;">;        }    }</span><span style="color: #0000ff;">else</span><span style="color: #000000;">{        </span><span style="color: #800080;">$max</span>=<span style="color: #800080;">$res</span><span style="color: #000000;">;    }    </span><span style="color: #008080;">print_r</span>(<span style="color: #800080;">$b</span><span style="color: #000000;">);    </span><span style="color: #0000ff;">echo</span> "此次结果是".<span style="color: #800080;">$res</span>.'   $max='.<span style="color: #800080;">$max</span>.'  $min='.<span style="color: #800080;">$min</span><span style="color: #000000;">;    </span><span style="color: #0000ff;">echo</span> "<hr>"<span style="color: #000000;">;}</span><span style="color: #0000ff;">echo</span> "最大值是".<span style="color: #800080;">$max</span>."最小值是".<span style="color: #800080;">$min</span><span style="color: #000000;">;</span><span style="color: #008000;">//</span><span style="color: #008000;">获得某种情况下的时间</span><span style="color: #0000ff;">function</span> getRes(<span style="color: #800080;">$b</span><span style="color: #000000;">){    </span><span style="color: #800080;">$arr</span>=<span style="color: #0000ff;">array</span>(3,7,11,17,23<span style="color: #000000;">);    </span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span>=1;<span style="color: #800080;">$i</span>$i++<span style="color: #000000;">){        </span><span style="color: #0000ff;">foreach</span> (<span style="color: #800080;">$arr</span> <span style="color: #0000ff;">as</span> <span style="color: #800080;">$k</span> => <span style="color: #800080;">$val</span><span style="color: #000000;">) {            </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>]=<span style="color: #800080;">$val</span>+<span style="color: #800080;">$b</span>[<span style="color: #800080;">$k</span><span style="color: #000000;">];            </span><span style="color: #0000ff;">if</span> (<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>]==@<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>-1<span style="color: #000000;">]) {                </span><span style="color: #800080;">$b</span>[<span style="color: #800080;">$k</span>]=-<span style="color: #800080;">$b</span>[<span style="color: #800080;">$k</span><span style="color: #000000;">];                </span><span style="color: #800080;">$b</span>[<span style="color: #800080;">$k</span>-1]=-@<span style="color: #800080;">$b</span>[<span style="color: #800080;">$k</span>-1<span style="color: #000000;">];            }            </span><span style="color: #0000ff;">if</span> ((<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>]>=27)||(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>])) {                <span style="color: #0000ff;">unset</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span><span style="color: #000000;">]);            }        }        </span><span style="color: #0000ff;">if</span> (<span style="color: #0000ff;">empty</span>(<span style="color: #800080;">$arr</span><span style="color: #000000;">)) {            </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$i</span><span style="color: #000000;">;        }    }}</span>

これはルーチンであり、ルールに従い、段階的に進めていきますが、確かに非常に困難です。

------------------------------------- ---华丽的分隔线-------------------------------------------------------------------------------------------

　

　　　在我一本正经地胡说八道后，就没有更加好的想法？

　　那就是相遇的时候，两只蚂蚁开始掉头。如果不掉头直接走呢？和他们掉头后有什么差别？结果是没有差别！每只蚂蚁开头拿一个接力棒，碰头后，两人交换接力棒，虽然蚂蚁掉头了，但接力棒可是一直往初始方向走哦~所以解题前景变得无比明朗。知道某只蚂蚁的初始状态，就知道他开始拿的接力棒最后走了多久！至于接力棒是不是亲生的，那你管哩。反正最后一个接力棒离开杆子，最后一只蚂蚁也离开杆子。

　　因而获得某种初始状态下的时间还可以这样写：

<span style="color: #0000ff;">function</span> getRes(<span style="color: #800080;">$b</span><span style="color: #000000;">){    </span><span style="color: #800080;">$arr</span>=<span style="color: #0000ff;">array</span>(3,7,11,17,23<span style="color: #000000;">);    </span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span>=1;;<span style="color: #800080;">$i</span>++<span style="color: #000000;">){        </span><span style="color: #0000ff;">foreach</span> (<span style="color: #800080;">$arr</span> <span style="color: #0000ff;">as</span> <span style="color: #800080;">$k</span> => <span style="color: #800080;">$val</span><span style="color: #000000;">) {            </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>]=<span style="color: #800080;">$val</span>+<span style="color: #800080;">$b</span>[<span style="color: #800080;">$k</span><span style="color: #000000;">];            </span><span style="color: #0000ff;">if</span> ((<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>]>=27)||(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>])) {                <span style="color: #0000ff;">unset</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span><span style="color: #000000;">]);            }        }        </span><span style="color: #0000ff;">if</span> (<span style="color: #0000ff;">empty</span>(<span style="color: #800080;">$arr</span><span style="color: #000000;">)) {            </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$i</span><span style="color: #000000;">;        }    }}</span>

------------------------------------- ---华丽的分隔线------------------------------------------------------------------------------------------- 　　

　　

　　当然问题可以更加简化，连上面的代码都用不到了。

　　通过上面分析可以看做每只蚂蚁直接走互不影响。到最后求最大值最小值的时候实际上可以先算出每只蚂蚁到两端的距离。形成五组数字。(3,24),(7,20),(11,16),(10,17),(4,23)在五组数每组数中较小值形成的5个数中最大的一个是最后结果的最小值。  五组数每组数中较大的5个数中最大的那个是结果的最大值。很容易看出来是11和24。为什么呢？典型的木桶效应啊。最后一只蚂蚁走出去了才能算完成整个事情。五只蚂蚁全部最短路径出去，得到结果才可能是最快的，五只蚂蚁全部最长路径出去，耗时才能是最慢的。

　　ps:应该不会有更快的想法了吧。

　　　最后感谢@randeng在本问题上的指点~

 

7 階gw2010

プログラミングをせずに最初の問題を解く方法は? , 上記の 2 番目の質問に対する答えを見ました。

Re: DeanChopper

@gw2010、ごめんなさい、私も知りません。 。しかし、数学を学ぶには、もっと単純なことを考慮する必要があると感じています。

6 階軽い事故

最短: ←3 ←7 ←11 →17 →23 、最長: 3→ 7→ 11→ ←17 ←23

5th FloorDCD

実はそれほど問題ではありません、最小時間は、最も理想的な条件での時間、つまり、11cm のアリが左に歩く場合、11 秒で完了します。 , 最大時間は、実際には、2 匹のアリが出会ったときに、反対方向に進むのではなく、お互いを通過するものとして理解できます。次に、3cm のアリが右に移動します (27-3=24 秒)。

4 階Ariex

最初の 1 つは、奇数の因数を持つ数値を計算することです。

Re: MrNice

@Ariex、はい、最終的には完全二乗数のようです

Re: DeanChopper

@Ariex、これは最も直感的なアイデアであり、私もそう思います。他に良いアルゴリズムを知りません

3階randeng

2番目の質問、「プログラミングの美しさ」で入手可能。 2匹のアリが出会って向きを変えるとき、2匹のアリがすれ違い、影響し合っているように見えます。 2 匹のアリ A、B、A-gt;、Blt;- がいて、それらが出会ったとき、Alt;-、B-gt;、遭遇後の A は遭遇前の B、B は遭遇前の A とみなすことができます。 、だから彼らはまだ前に進み続けました。必要なのは、配列を 1 回走査し、移動時間を調べ、サイズを調べることだけです。

Re: DeanChopper

@randeng、ありがとうございます、必ずまたチェックします~~

2階空笑い

それぞれのアリの歩き方をシミュレーションしてみた。愚かな方法で、最速のトラックはわずか 23 で、最も遅いトラックはわずか 35 であることがわかりました。両端の間の距離は少し大きいです。計算が間違っていたでしょうか。

Re: DeanChopper

@空に向かって笑う、最短の場合、最初の 3 匹のアリは左に進み、最後の 2 つは右に進みます。 11秒かかりました。最も遅いケースでは、すべてが右に移動するため、24 秒かかります。

1 階ビジネスが上昇する

2 番目の質問は、5 匹のアリがそれぞれに影響を与えないと直接仮定しています。その他、最小時間はすべてのアリが最も近い端を歩いたとき、最大時間はすべてのアリが最も遠い端を歩いたときです。プログラムを書くことは、2 つの端から各アリの特定の距離を決定することです。最小時間は最も近いものの最大値 ((つまり 11)、最大時間は最も遠いものの最大値 (24 に等しい) になります。ループは 1 つで十分です。

Re: DeanChopper

@风生水气、実際の分析はまさにこのようなものです。主な理由は、5 つのアリがそうでないと考えるのは簡単ではないということです。このステップに影響を与える場合、上記の最初のメソッドと同様になります。