计算11的1位数到N的幂

Question

我遇到了一个有趣的问题:你如何计算11的表示中的1位数到N的幂,0<N<=1000.

设d是1位数

N = 2 11 ^ 2 = 121 d = 2

N = 3 11 ^ 3 = 1331 d = 2

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

你计算数字和计算我得到最后一位数并除以10的1位数的简单方法不能很好地工作.11 ^ 1000甚至在任何标准数据类型中都不可重复.

有任何想法吗？

Answer 1

11的幂可以存储为字符串并以这种方式非常快速地计算,而不需要通用的任意精度数学包.你需要的只是乘以十并加.

例如,是.为了获得()的下一个幂,你乘以,这实际上是一个零加零的数字,加到数字:.1111111112(10 + 1)110 + 11 = 121

同样,可以计算为:.1131210 + 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(n2)

当然,考虑到这些限制,您可以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 ¹⁰⁰⁰中的1代码.