4

テープの 0 番目のセルの数字が埋められ、残りはすべてスクラッチ セルとして使用されている場合 (つまり、それらはすべて 0 から始まり、一時的なものです。それらがどうなろうと気にしません)、置き換えたいと思います。 0 または 1 を持つ 0 番目のセル。偶数の場合は 0、奇数の場合は 1。

基本的に、私がやりたいことは（C風の擬似コードで）です：

cell[0] = (cell[0] % 2)

次のように定義されたdivmod アルゴリズムが存在することを知っています。

n を保持する必要がない場合は、次のバリアントを使用します。

# >n d
[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
# >0 d-n%d n%d n/d

ただし、X % 2 == X & 1つまり X mod 2 は X の右端のビットなので、計算の複雑さの点で divmod はやり過ぎかもしれないと思います。

セルが偶数かどうかを調べるためのより良いアルゴリズム/手法はありますか?

4

4 に答える 4

5

パリティのみを保持するアルゴリズムが必要です。次のように実行できます。

result=0
while(n > 0) {
  result++;
  n--;
  if(n > 0) {
    result--;
    n--;
  }
}

値を失うことなく n をテストするには、それをコピーする必要があります: A から B にコピーし、C を A にコピーしてから、C を A に移動します。B をテストして、n を A に保持することもできます。

[->+<] # move @0 to @1
> # goto @1
[-<+ # if @1 then decrements @1 and increments @0
 > # goto @1
 [->+>+<<] # if @1 then move @1 to @2 and @3
 >> # goto @3
 [-<<+>>] # if @3 then move @3 to @1
 < # goto @2
 [<-<->>[-]] # if @2 then decrements @0, decrements @1 and sets 0 into @2
 < # go to @1
] # continue loop if @1 is not null
< # goto @0

ライトフォーム:

[->+<]>[-<+>[->+>+<<]>>[-<<+>>]<[<-<->>[-]]<]<
于 2015-07-20T20:22:36.707 に答える
3

N 奇数または偶数:

>,             load m1 with N

[-[->]<]+      set m0 = 1 if odd
               set m1 = 1 if even
于 2016-01-22T20:10:17.697 に答える
2

P を完全に解決するバージョンを次に示します。

N は偶数か奇数か?

>,              ~load m1 with N (not counted for golf scoring)
>>+>+<<<        ~set 'trail of breadcrumbs' so we can figure out 
                   where P is
[-[->]<]+       ~if N is odd set m0 = 1
>>>[>]          ~figure out where P is
<[-<]<[-]<      ~go back to m1 and zero out if N is even

ポインター P は m0 で終了します 奇数: m0 = 1 偶数: m0 = 0

于 2016-02-06T16:29:15.007 に答える
0

モジュラスが偶数か奇数かを確認するには、モジュラスを確認する必要があります。最も簡単な方法です。しかし、あなたが投稿した divmod アルゴリズムには注意が必要です。modulo 2 をチェックするときに動作するはずですが、正しく覚えていれば、それを使用して 1 で除算しようとしないでください。

PC では、数値と 1 の AND を取ることができます (整数であると仮定します)。しかし、brainfuck には AND 演算子がないため、長い道のりを歩まなければなりません。コンピューターが数値を 2 進数で保存することは知っていますが、それは頭脳明晰の関心事ではありません。操作するバイナリ値の配列は提供されません。インクリメント、デクリメント、または 0 との比較のみが可能な数値の配列を提供します。

于 2015-07-18T07:49:08.553 に答える