计算11的1位数到N的幂

问题描述 投票:7回答:3

我遇到了一个有趣的问题:你如何计算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甚至在任何标准数据类型中都不可重复。

有任何想法吗?

algorithm
3个回答
15
投票

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

例如,11111。为了得到11112)的下一个力量,你乘以(10 + 1),这实际上是一个零加零的数字,加上数字:110 + 11 = 121

同样,113可以计算为: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(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秒内找到111000中的数量。


1
投票

这是我简洁的解决方案。

def count1s(N):
    # When 11^(N-1) = result, 11^(N) = (10+1) * result = 10*result + result
    result = 1
    for i in range(N):
        result += 10*result

    # Now count 1's
    count = 0
    for ch in str(result):
        if ch == '1':
            count += 1
    return count

0
投票

在c#中:

        private static void Main(string[] args)
    {
        var res = Elevento(1000);
        var countOf1 = res.Select(x => int.Parse(x.ToString())).Count(s => s == 1);
        Console.WriteLine(countOf1);
    }

    private static string Elevento(int n)
    {
        if (n == 0) return "1";
        //Otherwise, n <- n * 10 + n, once for each level of power.
        var num = "11";
        while (n > 1)
        {
            n--;
            // Make multiply by eleven easy.
            var ten = num + "0";
            num = "0" + num;
            //Standard primary school algorithm for adding.
            var newnum = "";
            var carry = 0;
            foreach (var dgt in Enumerable.Range(0, ten.Length).Reverse())
            {
                var res = int.Parse(ten[dgt].ToString()) + int.Parse(num[dgt].ToString()) + carry;
                carry = res/10;
                res = res%10;
                newnum = res + newnum;
            }

            if (carry == 1)
                newnum = "1" + newnum;
            // Prepare for next multiplication.
            num = newnum;
        }
        //There you go, 11^n as a string.
        return num;
    }