Oblicz liczbę z nich w wyniku 11^n

Question

Poniższy problem został zadany w wywiadzie. Biorąc pod uwagę liczbę 11 ⁿ (gdzie n ∈ [0, 1000]), uzyskaj w wyniku liczbę 1. Na przykład, n = 3, 11 = 1331, a więc oczekuje się, że wynik podano lub 2. n = 6, 11 = 1771561, oczekiwany wynik byłby 3.

My pierwsza myśl była że musiało coś zrobić z pascal's triangle i binomial coefficients (ponieważ, jak wiemy, po prostu obliczanie pow(11, 1000) nie działa, przynajmniej w C).

Pomyślałem, że proste powtarzanie kolumn w trójkącie paskowym powinno dać mi wynik, ale to oczywiście nie działa.

Tak więc utknąłem w tej chwili. Moja następna myśl polegała na użyciu pewnego rodzaju bignum library, aby rozwiązać problem, ale moim zdaniem musi istnieć inny sposób rozwiązania tego rodzaju zadania.

Aktualizacja Zapomniałem wspomnieć, że miałem rozwiązać to zadanie za pomocą C/Objective-C.

Answer 1

Podobnie jak Bartosz zaproponował, by rozwiązać ten problem, po prostu wykonując obliczenia w bazie 10. mnożenie przez 11 w bazie 10 można zrobić z lewa zmiana i dodatek. Oto program C, który działa na łańcuchach ASCII. Zauważ, że najmniej znacząca cyfra pojawia się jako pierwsza w każdym ciągu.

#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

Czy powiedzieli Ci, jak skuteczny powinien być algorytm?

Zaimplementowałbym go bezpośrednio na łańcuchach; pomnożenie przez 11 to po prostu zrobienie kopii z jednym dodawanym przed końcem 0, a następnie dodanie, więc wszystko, co musisz zrobić, to zaimplementować dodawanie liczb zapisanych jako ciągi.

Answer 3

załóżmy, że K (i) jest ciągiem, który jest wytwarzany z k-tego rzędu trójkąta pascalowego.

11^0 = 1,11^1 = 11,11^2 = 121. Ale 11^i = k (i) jest fałszywym założeniem. Ze względu 11^I = (10 + 1)^i &

====>

tak małych ilościach, że przez to prawdziwe, ponieważ 10^I jest bardzo większy niż [I] do dużych ilościach być może ma przepełnienie z następującego powodu.

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 

, więc gdy wystąpi przepełnienie a[i]*10^(n-i+1) < a[i+1]*10^(n-i). Upraszczając je, uzyskujesz (n-i+1)/i >10, czyli gdy wystąpi przepełnienie.
należy obliczyć te przepełnienia w swoim algorytmie.

Answer 4

Wersja ciąg w Haskell wydaje się działać całkiem dobrze:

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)