有没有有效的方法将一元数转换为二进制数？

Question

让这些数据类型分别代表一元和二元自然数:

data UNat = Succ UNat | Zero
data BNat = One BNat | Zero BNat | End

u0 = Zero
u1 = Succ Zero
u2 = Succ (Succ Zero)
u3 = Succ (Succ (Succ Zero))
u4 = Succ (Succ (Succ (Succ Zero)))

b0 = End                   //   0
b1 = One End               //   1
b2 = One (Zero End)        //  10
b3 = One (One End)         //  11
b4 = One (Zero (Zero End)) // 100

(Alternatively, one could use `Zero End` as b1, `One End` as b2, `Zero (Zero End)` as b3...)

我的问题是:有没有办法实现这个功能:

toBNat :: UNat -> BNat

这可以O(N),只做一次通过UNat？

Answer 1

我喜欢其他答案,但我发现它们的渐近分析很复杂.因此,我提出了另一个具有非常简单的渐近分析的答案.基本思想是实现divMod 2一元数.从而:

data UNat = Succ UNat | Zero
data Bit = I | O

divMod2 :: UNat -> (UNat, Bit)
divMod2 Zero = (Zero, O)
divMod2 (Succ Zero) = (Zero, I)
divMod2 (Succ (Succ n)) = case divMod2 n of
    ~(div, mod) -> (Succ div, mod)

现在我们可以通过迭代转换为二进制divMod.

toBinary :: UNat -> [Bit]
toBinary Zero = []
toBinary n = case divMod2 n of
    ~(div, mod) -> mod : toBinary div

渐近分析现在非常简单.给出一n元数字的数字,divMod2需要花费O(n)时间来产生一半大的数字 - 比如说,它需要的c*n时间足够大n.因此,迭代此过程需要花费很多时间:

c*(n + n/2 + n/4 + n/8 + ...)

众所周知,这个系列会聚到c*(2*n),所以toBinary在O(n)中也见证了常数2*c.

Answer 2

如果我们有一个增加a的函数BNat,我们可以通过沿着每个步骤UNat递增a来非常容易地做到这一点BNat:

toBNat :: UNat -> BNat
toBNat = toBNat' End
    where
    toBNat' :: BNat -> UNat -> BNat
    toBNat' c Zero     = c
    toBNat' c (Succ n) = toBNat' (increment c) n

现在,这O(NM)其中M是最坏的情况increment.所以如果我们能increment在O(1)中做,那么答案是肯定的.

这是我实施的尝试increment:

increment :: BNat -> BNat
increment = (reverse End) . inc' . (reverse End)
    where
    inc' :: BNat -> BNat
    inc' End      = One End
    inc' (Zero n) = One n
    inc' (One n)  = Zero (inc' n)

    reverse :: BNat -> BNat -> BNat
    reverse c End = c
    reverse c (One n) = reverse (One c) n

这个实现是O(N)因为你必须reverse在BNat看至少显著位,它给你O(N)的整体.如果我们认为BNat类型代表反向二进制数,我们不需要反转BNat,并且,正如@augustss所说,我们有O(1),它给你O(N)整体.

Answer 3

要递增二进制数字,您必须翻转数字末尾的第一个零和前面的所有数字.此操作的成本与输入结束时的1的数量成正比(为此,您应该将数字表示为从右到左的列表,例如列表[1; 0; 1; 1]代码为13) .

设a(n)为n末尾的数字1:

a(n) = 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ...

然后让

s(k) = a(2^k) + a(2^k+1) + ... + a(2^(k+1)-1) 

是两个2的幂之间的元素之和.你应该能够通过注意到s(k + 1)= 2*s(k)+ 1(s(0)= 1)来说服自己

    a(2^(k+1)) ..., a(2^(k+2) - 1) 

通过连接获得

    a(2^k) + 1, ..., a(2^(k+1) - 1) and   a(2^k), ..., a(2^(k+1) - 1)

因此,作为几何级数,s(k)= 2 ^ k - 1.

现在增加N倍数的成本应该是成正比的

    a(0) + a(1) + ... + a(N)
  = s(0) + s(1) + s(2)  + ... + s(log(N)) 
  = 2^0 - 1 + 2^1 -1 + 2^2-1 + ... + 2^log(N) - 1
  = 2^0 + 2^1 + 2^2 + ... + 2^log(N) - log(N) - 1
  = 2^(log(N) + 1) - 1 - log(N) - 1 = 2N - log(N) - 2

因此,如果你从你的代表数的护理从右到左,那么天真的算法是线性的(请注意,您可以执行列出的逆转,并保持线性的,如果你真的需要你的号码的其他方式).