Рассчитать количество единиц в результате 11^n

Question

В интервью была задана следующая проблема. Учитывая число 11 ⁿ (где n ∈ [0, 1000]), получите результат 1 s. Так, например, п = 3, 11 = 1331, так что ожидаемый результат будет 2. Или дано п = 6, 11 = 1771561, ожидаемый результат будет 3.

Моя первая мысль была что он должен был что-то сделать с pascal's triangle и binomial coefficients (потому что, как мы знаем, просто вычисление pow(11, 1000) не работает, по крайней мере, в C).

Я думал, что просто перебирать столбцы в треугольнике паскаля должен дать мне результат, но это явно не работает.

Так что я сейчас застрял. Моя следующая мысль заключалась в том, чтобы использовать какой-то bignum library для решения проблемы, но, на мой взгляд, должен быть другой способ решить эту задачу.

Обновление Я забыл упомянуть, что я должен был решить эту задачу с помощью C/Objective-C.

Answer 1

Как Бартош предложил, я бы решить эту проблему, просто выполняя расчеты в базе 10. Умножение на 11 в основании 10 может быть сделано с сдвиг влево и добавление. Вот C-программа, которая работает с строками ASCII. Обратите внимание, что наименьшая значащая цифра начинается в каждой строке.

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

char *multiply_by_11(const char *num, int *num_ones_ptr) 
{ 
    size_t len = strlen(num); 
    char *result = (char *)malloc(len + 3); 
    int carry = 0; 
    int num_ones = 0; 
    size_t i; 

    for (i = 0; i <= len; ++i) { 
     int digit = carry; 

     if (i < len) { 
      digit += num[i] - '0'; 
     } 
     if (i > 0) { 
      digit += num[i-1] - '0'; 
     } 

     if (digit < 10) { 
      carry = 0; 
     } 
     else { 
      digit -= 10; 
      carry = 1; 
     } 

     if (digit == 1) { 
      ++num_ones; 
     } 
     result[i] = digit + '0'; 
    } 

    if (carry) { 
     result[i++] = '1'; 
     ++num_ones; 
    } 

    result[i] = '\0'; 

    *num_ones_ptr = num_ones; 
    return result; 
} 

int main() 
{ 
    char *num = (char *)malloc(2); 
    int i; 

    strcpy(num, "1"); 

    for (i = 1; i <= 1000; ++i) { 
     int num_ones; 

     char *product = multiply_by_11(num, &num_ones); 
     printf("11^%4d: %3d ones\n", i, num_ones); 

     free(num); 
     num = product; 
    } 

    free(num); 
    return 0; 
} 

Answer 2

Сообщили ли они, насколько эффективен алгоритм?

Я бы выполнил его прямо на струнах; умножение на 11 - это просто сделать копию с добавлением одного добавочного 0, а затем добавить, так что все, что вам нужно сделать, это реализовать добавление чисел, записанных в виде строк.

Answer 3

Предположим, что K (i) - это строка, которая создается из k-й строки треугольника паскаля.

11^0 = 1,11^1 = 11,11^2 = 121. Но 11^i = k (i) является ложным предположением. Поскольку 11^я = (10 + 1)^я &

====>

так что для малых чисел это верно, так как 10^я очень больше, чем [я] для больших чисел возможно, имеет переполнение по следующей причине.

a[i+1]=((n-i+1)/a[i])*a[i]  
     & 
suppose that: a[i]*10^(n-i+1) and a[i+1]*10^(n-i) are two Consecutive numbers 

поэтому когда a[i]*10^(n-i+1) < a[i+1]*10^(n-i) переполнение происходит. Упротив их, вы получаете (n-i+1)/i >10, когда происходит переполнение.
Вы должны рассчитать эти переполнения в своем алгоритме.

Answer 4

версия строки в Haskell, кажется, работает очень хорошо:

Prelude> let f n = length . filter (=='1') . show . (11^) $ n 
Prelude> f 1000 
105 
(0.00 secs, 1129452 bytes) 
Prelude> f 1000000 
104499 
(2.64 secs, 69393408 bytes)