1

xx01101011xx (x は空文字) のテープがあるとします。0 または 1 が多いかどうかを判断するアルゴリズムのアイデアを教えてください。「ペアリング」という方法は聞いたことがありますが、使い方がわかりません。

よろしく。

4

2 に答える 2

2

1つのアプローチは、を削除し0、次に次を探してそれ1を削除し、シンボルが1つだけ残るまでそれを行ったり来たりすることです。これは、入力に終了マーカーがあることを前提としています。

于 2012-11-13T18:47:54.940 に答える
2

左端の空白以外の X 以外の文字が 0 の場合は、右から 1 を検索し、見つかった場合は両方を X に変更します。

左端の空白以外の X 以外の文字が 1 である場合は、右に 0 を検索し、見つかった場合は両方を X に変更します。

一致するものが見つからない場合は、一番左の空白以外の文字がより多く存在します。テープ全体が X で終わる場合、それらは同じ量で存在します。

EX: _ を空白、{0,1,X} のアルファベット:

__01101011__
     v
__XX101011__
     v
__XXXX1011__
     v
__XXXXXX11__
     v
No matching 0 found, more 1s
于 2012-11-13T18:47:29.720 に答える