algorithm - 统计 11 中 1 的 N 次方个数

Question

我遇到了一个有趣的问题:

你如何计算11的N次方表示中1位的个数，0<N<=1000 .

设d为1位数

N=2 11^2 = 121 d=2

N=3 11^3 = 1331 d=2

预计最差时间复杂度O(N^2)

计算数字并计算 1 位数的数量的简单方法，我得到最后一位并除以 10，这种方法效果不佳。 11^1000 甚至不能用任何标准数据类型表示。

Answer 1

十一的幂可以存储为字符串并以这种方式计算得非常快，没有通用的任意精度数学包。您只需乘以 10 并相加。

例如 11<sup>1</sup> 是 11 。要获得 11 ( 11<sup>2</sup> ) 的 next 能力，您可以乘以 (10 + 1) ，它实际上是在末尾加上零的数字，加上数字:110 + 11 = 121。

类似地，11<sup>3</sup> 可以计算为:1210 + 121 = 1331。

等等:

11^2   11^3    11^4     11^5      11^6

 110   1210   13310   146410   1610510
 +11   +121   +1331   +14641   +161051
 ---   ----   -----   ------   -------
 121   1331   14641   161051   1771561

这就是我的处理方式，至少在最初阶段是这样。

---

例如，这里有一个 Python 函数，使用描述的方法来计算 11 的 n 次方(我知道 Python 支持任意精度，记住我'我只是用它来演示如何用算法来做这个，这就是问题的标记方式):

def elevenToPowerOf(n):
    # Anything to the zero is 1.

    if n == 0: return "1"

    # Otherwise, n <- n * 10 + n, once for each level of power.

    num = "11"
    while n > 1:
        n = n - 1

        # Make multiply by eleven easy.

        ten = num + "0"
        num = "0" + num

        # Standard primary school algorithm for adding.

        newnum = ""
        carry = 0
        for dgt in range(len(ten)-1,-1,-1):
            res = int(ten[dgt]) + int(num[dgt]) + carry
            carry = res // 10
            res = res % 10
            newnum = str(res) + newnum
        if carry == 1:
            newnum = "1" + newnum

        # Prepare for next multiplication.

        num = newnum

    # There you go, 11^n as a string.

    return num

并且，为了测试，一个小程序可以计算出您在命令行上提供的每种能力的这些值:

import sys

for idx in range(1,len(sys.argv)):
    try:
        power = int(sys.argv[idx])
    except (e):
        print("Invalid number [%s]" % (sys.argv[idx]))
        sys.exit(1)

    if power < 0:
        print("Negative powers not allowed [%d]" % (power))
        sys.exit(1)

    number = elevenToPowerOf(power)
    count = 0
    for ch in number:
        if ch == '1':
            count += 1

    print("11^%d is %s, has %d ones" % (power,number,count))

当你运行它时:

time python3 prog.py  0 1 2 3 4 5 6 7 8 9 10 11 12 1000

你可以看到它既准确(通过 bc 检查)又快速(大约半秒内完成):

11^0 is 1, has 1 ones
11^1 is 11, has 2 ones
11^2 is 121, has 2 ones
11^3 is 1331, has 2 ones
11^4 is 14641, has 2 ones
11^5 is 161051, has 3 ones
11^6 is 1771561, has 3 ones
11^7 is 19487171, has 3 ones
11^8 is 214358881, has 2 ones
11^9 is 2357947691, has 1 ones
11^10 is 25937424601, has 1 ones
11^11 is 285311670611, has 4 ones
11^12 is 3138428376721, has 2 ones
11^1000 is 2469932918005826334124088385085221477709733385238396234869182951830739390375433175367866116456946191973803561189036523363533798726571008961243792655536655282201820357872673322901148243453211756020067624545609411212063417307681204817377763465511222635167942816318177424600927358163388910854695041070577642045540560963004207926938348086979035423732739933235077042750354729095729602516751896320598857608367865475244863114521391548985943858154775884418927768284663678512441565517194156946312753546771163991252528017732162399536497445066348868438762510366191040118080751580689254476068034620047646422315123643119627205531371694188794408120267120500325775293645416335230014278578281272863450085145349124727476223298887655183167465713337723258182649072572861625150703747030550736347589416285606367521524529665763903537989935510874657420361426804068643262800901916285076966174176854351055183740078763891951775452021781225066361670593917001215032839838911476044840388663443684517735022039957481918726697789827894303408292584258328090724141496484460001, has 105 ones

real    0m0.609s
user    0m0.592s
sys     0m0.012s

这可能不一定是 O(n<sup>2</sup>)，但对于您的域限制来说它应该足够快。

---

当然，考虑到这些限制，您可以使用我称为预生成的方法使其成为 O(1)。只需编写一个程序来生成一个数组，您可以将其插入包含合适函数的程序中。以下 Python 程序正是这样做的，计算从 1 到 100 的 11 的幂:

def mulBy11(num):
    # Same length to ease addition.

    ten = num + '0'
    num = '0' + num

    # Standard primary school algorithm for adding.

    result = ''
    carry = 0
    for idx in range(len(ten)-1, -1, -1):
        digit = int(ten[idx]) + int(num[idx]) + carry
        carry = digit // 10
        digit = digit % 10
        result = str(digit) + result

    if carry == 1:
        result = '1' + result

    return result

num = '1'

print('int oneCountInPowerOf11(int n) {')
print('  static int numOnes[] = {-1', end='')
for power in range(1,101):
    num = mulBy11(num)
    count = sum(1 for ch in num if ch == '1')
    print(',%d' % count, end='')
print('};')
print('  if ((n < 0) || (n > sizeof(numOnes) / sizeof(*numOnes)))')
print('    return -1;')
print('  return numOnes[n];')
print('}')

这个脚本输出的代码是:

int oneCountInPowerOf11(int n) {
  static int numOnes[] = {-1,2,2,2,2,3,3,3,2,1,1,4,2,3,1,4,2,1,4,4,1,5,5,1,5,3,6,6,3,6,3,7,5,7,4,4,2,3,4,4,3,8,4,8,5,5,7,7,7,6,6,9,9,7,12,10,8,6,11,7,6,5,5,7,10,2,8,4,6,8,5,9,13,14,8,10,8,7,11,10,9,8,7,13,8,9,6,8,5,8,7,15,12,9,10,10,12,13,7,11,12};
  if ((n < 0) || (n > sizeof(numOnes) / sizeof(*numOnes)))
    return -1;
  return numOnes[n];
}

当插入 C 程序时，它应该快得令人眼花缭乱。在我的系统上，Python 代码本身(当您将范围扩大到 1..1000 时)运行大约 0.6 秒，而 C 代码在编译时在 0.07 秒内找到 11¹⁰⁰⁰ 中的个数。