4

鉴于磁带的第 0 个单元格中的一个数字已填充,其余的都只是用作暂存单元格(即它们都从 0 开始并且是临时的——我不在乎它们会发生什么),我想替换第 0 个带有 0 或 1 的单元格。如果是偶数,则为 0,如果是奇数,则为 1。

基本上,我想做的是(在 C-esque 伪代码中):

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,然后将 C 移动到 A。您可以测试 B 并将 n 保留在 A 中。下面是 Brainfuck 代码:

[->+<] # 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 算法。检查模2时它应该可以工作,但如果我没记错的话,不要尝试使用它除以1。

在 PC 上,您可以将数字与 1 相加(假设它是一个整数)。但是brainfuck 没有AND 运算符,所以你将不得不走很长的路。您知道计算机以二进制形式存储数字,但这与brainfuck 无关。它不会为您提供要操作的二进制值数组。它为您提供了一个数字数组,您只能递增、递减或与 0 进行比较。

于 2015-07-18T07:49:08.553 回答