3

キー 0 ～ 9 を入力して「金庫を破る」アルゴリズムを見つけようとしています。コードの長さは 4 桁です。入力の部分文字列としてコードを識別する金庫が開きます。つまり、コードが「3456」の場合、次に入力すると金庫が開きます：「123456」。(これは、金庫が 4 つのキー入力ごとに再起動しないことを意味します)。

シーケンスに 1 桁を追加するたびに、新しい 4 桁の数字 (シーケンス \ 文字列の最後の 4 桁の新しい組み合わせ) を作成するアルゴリズムはありますか?

ありがとう、キロ。

編集 (何年も前に投稿しました): 問題は、入力 (1 桁) を金庫に設定するたびに、以前に生成されなかった新しい 4 桁のコードを生成する方法です。たとえば、金庫が 3 桁の長さのバイナリ コードを取得する場合、これが入力シーケンスになります。

0001011100

すべての入力に対して、以前に生成されなかった新しいコード (3 桁の長さ) を取得するためです。

000 -> 000
1 -> 001
0 -> 010
1 -> 101
1 -> 011
1 -> 111
0 -> 110
0 -> 100
4

3 に答える 3

2

あなたの問題の軽減を見つけました：

有向グラフ G = (V,E) を次のように定義します。

V = {コードのすべての可能な組み合わせ}.

E = {< u,v > | v は、u に (最後に) 1 桁を追加し、最初の桁を削除することによって取得できます}。

|V| = 10^4。

10 に等しいすべての頂点の Din と Dout => |E| = 10^5。

G にハミルトン サイクルがあることを証明する必要があります。証明できれば、解の存在を証明できます。

EDIT1：

アルゴリズム:

  1. 上記のように有向グラフ G を作成します。

  2. ハミルトン サイクルを計算します - {v1,v2,..,vn-1,v1}。

  3. v1 のすべての数字を押します。

  4. X <- v1.

  5. 金庫が開いていない間：

    5.1 X <- X の後のハミルトン パスの次の頂点。

    5.2 X の最後の桁を押します。

ハミルトン サイクルを使用しているため、同じ部分文字列が繰り返されることはありません。(最後の 4 回のプレス)。

EDIT2：

もちろんハミルトンパスで十分です。

于 2012-07-03T19:59:58.663 に答える
1

要約すると、あなたが解決しようとしていると思われる問題と、それを解決する方法についての説明です。http://www.cs.swan.ac.uk/~csharold/cpp/SPAEcpp.pdf

ただし、中国の郵便配達員の問題に適合させるには、多少の工夫が必要です... 2進数、3桁の文字列についてこの問題を解決することを想像してください。最初の 2 桁を持っていると仮定して、移動先の選択肢は何ですか? (次の 2 桁の文字列に関しては?) 有向グラフが残ります。

 /-\
/   V    
\-  00 ----> 01
      ^  /   ^|
       \/    ||
       /\    ||
      V  \   |V
 /-- 11 ---> 10 
 \   ^         
  \-/

中国の郵便屋さんを解いてください。すべての組み合わせがあり、1 つの文字列を形成します。問題は、中国の郵便屋さんが解けるかどうかです。DAG が CPP で解けるかどうかを判断するアルゴリズムがありますが、この特定のグラフが問題だけに基づいて解ける必要があるかどうかはわかりません。そう判断するのは良いことです。ただし、アルゴリズムによって解決可能であることがわかり、その場合は、その論文 (私が思うに) とオンラインで利用可能なアルゴリズムを使用して解決できることを知っています。

ここのすべての頂点には、2 つの入力エッジと 2 つの出力エッジがあります。4 (2^2) 個の頂点があります。

フルサイズの問題には19683( 3 ^ 9 )頂点があり、すべての頂点には512 ( 2 ^ 9 )出て行く頂点と入ってくる頂点があります。合計で

19683( 3 ^ 9 ) x 512 (2 ^ 9) = 10077696 edges in your graph.

解決へのアプローチ:

1.) Create list of all 3 digit numbers 000 to 999.
2.) Create edges for all numbers such that last two digits of first number match first
two digits of next number. 

ie 123 -> 238 (valid edge) 123 -> 128 (invalid edge)

3.) use Chinese Postman solving algorithmic approaches to discover if solvable and
solve
于 2012-07-03T20:39:52.663 に答える
0

新しい数字を挿入するたびに更新する必要があるサブシーケンスの配列を作成します。したがって、あなたの例では、次のように始まります。

array = {1}

それから

array = {1,2,12}

それから

array = {1,2,12,3,13,23,123}

それから

array = {1,2,12,3,13,23,123,4,14,24,124,34,134,234,1234}

すでにlength=4のシーケンスがある場合は、連結を続行する必要はありません。シーケンスの最初の桁を削除し、最後に新しい桁を挿入します。たとえば、最後の項目を使用します1234。追加5すると次のようになり2345ます。

array = {1,2,12,3,13,23,123,4,14,24,124,34,134,234,1234,5,15,25,125,35,135,235,1235,45,145,245,1245,345,1345,2345,2345}

これは、特定のシーケンスのすべてのサブシーケンスを調べる非常に複雑な方法ではないと思います。

于 2012-07-03T20:24:08.760 に答える