9

重複の可能性：
効率的な全数検索アルゴリズムの構築に支援が必要

キーパッドに正しい4桁のコードを入力して、施錠されたドアを開ける必要があると想像してみてください。キーを押すたびに、ロックは入力された最後の4桁のシーケンスを評価します。つまり、入力することにより、、、およびの1234563つのコードを評価しました。123423453456

  • 10^4すべての異なる組み合わせを評価するためのキー押下の最短シーケンスは何ですか？
  • 人間がたどるのに十分簡単に​​空間全体を横断する方法はありますか？

私の友人が冬に屋外で夜を過ごす必要がないように、そのようなロックを総当たり攻撃しなければならなかったので、私は時々これを熟考しました。

頭を包み込む弱々しい試み

長さの数字のコードとL=4サイズの数字の「アルファベット」ではD=10、最適なシーケンスの長さを。より短くすることはできませんD^L + L - 1。私よりも小さいサイズのシミュレーションでは[L,D] = [4,10]、空間を半ランダムに検索することで最適な結果が得られました。ただし、任意のペアのソリューションが存在するかどうかはわかりません。また、ソリューション[L,D]を使用する必要があった場合、そのソリューションを思い出せません。

これまでに学んだ教訓

別の町の友達の家で夜を過ごすことを計画しているとき、その人がパーティーに出かけていて彼女の携帯電話が聞こえない場合は、午前1時に到着しないようにしてください。

4

2 に答える 2

5

http://en.wikipedia.org/wiki/De_Bruijn_sequence-"Aの長さnのすべての可能なサブシーケンスが1回だけ連続する文字のシーケンスとして表示される、サイズkの特定のアルファベットAの循環シーケンスが必要だと思います。」

于 2012-11-05T18:03:05.663 に答える
3

Evgenyが提供するリンクは、両方のクエストに答えるはずです。この答えは少しオフトピックですが、あなたは人間のための解決策を求めています。

現実の世界では、おそらくソーシャルエンジニアリングやヒューリスティックに依存し、その後は数学に依存する必要があります。私は実際の生活についてケースを挙げます：

アパートに行ってみると、携帯が死んでいることがわかりました。今、訪問をしている人に連絡する方法。0 - 9ドアがキーパッドとを使用しているのを見たとき、私は帰ろうとしていましたA B。私はいくつかの仮定をしました：

  1. コードの長さは5桁です。長さはあなたがいる地域に応じてかなり標準的です。私はこの仮定を以前にアクセスした建物に基づいています（合法的に：D）。
  2. コードは数字で始まり、次にAまたはB（私自身の建物に基づく）のいずれかで始まります。
  3. キーパッドは新品ではありませんでした。結論として、コードで使用されている数字は少し破損しています。私は、どの番号がコードに含まれておらず、4つの番号のうち3つがコードに含まれているかを確実に知っていました（以前の仮定を前提としています）
  4. 損傷したキーの量から、コードに繰り返しキーが含まれていないと想定しました（7つが損傷した、使用された、使用されなかったことがA明らかB）

最後に、確かにコードに含まれている3つの番号、最後の番号の2つの候補があり、最後にあると確信Aしていました。オンキーは他のものと比較してわずかに損傷していました。

私は、より損傷しているように見える候補から始めて順列を列挙する必要がありました。それは私に4! + 4! = 48試みを与えます。私を信じてください、5回目の試みでドアが開かれました。私が2セントを与えることができれば、古いput a key and open the doorものが建物へのアクセスを制限するための最も信頼できる方法です。

于 2012-11-05T15:36:12.293 に答える