# 计算11的1位数到N的幂

##### 问题描述投票：7回答：3

N = 2 11 ^ 2 = 121 d = 2

N = 3 11 ^ 3 = 1331 d = 2

algorithm
##### 3个回答
15

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

``````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
``````

``````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
``````

``````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
``````

``````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];
}
``````

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

``````        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;
}
``````