标尺函数的迭代实现（1,2,1,3,1,2,1,4,1,2,1,3，...）

Question

什么是ruler function的迭代实现？

This website声称“标尺函数可以非递归地生成”但从未显示示例。

Python中的递归实现（来自同一网页）如下所示：

def ruler(k):
  for i in range(1, k+1):
    yield i
    for x in ruler(i-1): yield x

Answer 1

查找表和钻头可以让您有效地解决这个问题。

ruler = dict((1<<i, i+1) for i in xrange(63))

for i in xrange(1, 20):
    print ruler[i & ~(i-1)],

Answer 2

对于每个数字n，ruler(n)等于1 +（二进制n中的尾随0的数量）。

我认为（这是未经处理的）它可以有效地实施

def ruler(n):
    return (x ^ (x - 1)).bit_length()

因为在二进制中，拖尾数字看起来像

...mno1000    # x
...mno0111    # x - 1
...0001111    # x XOR (x - 1)

那么你想要1s的数量，.bit_length()给你。

Answer 3

我可能在这里遗漏了一些东西，但是根据标尺函数的描述......

def ruler(k):
    pow = 1
    while ((2*k) % (2**pow)) == 0:
        pow += 1
    return pow-1

for x in range(1, 10):
     print ruler(x)

1
2
1
3
1
2
1
4
1

不知道，也许我不理解这个问题。

Answer 4

使用Hugh Bothwell所说的，你可以做以下事情（对于n > 0）：

def ruler(n):
  return len(bin(n).split('1')[-1]) + 1

Answer 5

我正在尝试这个问题并使用一些旧的方法。请检查一次。我没有完全建立起来。但显然它正在发挥作用。很少有未完成的破码。

提前道歉。

#!/usr/bin/env python
import os
def ruler():
    print("Initiating ruler function...")
    num = int(input("Enter the value to Eval::  "))

    expNumrange = 1234567890

    if num%2 == 0:
        for i in range(num):
            print(expNumrange,end='----')

    else:
        rem = num%2
        remLen = len(str(abs(rem)))
        expNumrangelen = len(str(abs(expNumrange)))
        finval = len(str(abs(expNumrange - remLen)))
        setVal = expNumrange - finval
        #rem2 = (str(expNumrange) - str(remLen))
        for i in range(num):
            print(expNumrange, end=(str(setVal) + '--'))



if __name__ == '__main__':
    ruler()

现在，请检查输出。

对于“8”

1234567890----1234567890----1234567890----1234567890----1234567890----1234567890----1234567890----1234567890----

对于“5”

12345678901234567880--12345678901234567880--12345678901234567880--12345678901234567880--12345678901234567880--