Tính số lượng kết quả là 11^n

Question

Vấn đề sau được hỏi trong một cuộc phỏng vấn. Được cung cấp số 11 ⁿ (trong đó n ∈ [0, 1000]), nhận số lượng kết quả là 1. Ví dụ, n = 3, 11 = 1331, do đó kết quả dự kiến ​​sẽ là 2. Hoặc cho n = 6, 11 = 1.771.561, kết quả dự kiến ​​sẽ là 3.

Suy nghĩ đầu tiên của tôi là rằng nó phải làm điều gì đó với pascal's triangle và binomial coefficients (bởi vì như chúng ta biết chỉ cần tính toán pow(11, 1000) không hoạt động, ít nhất là trong C).

Tôi nghĩ bằng cách đơn giản lặp qua các cột trong tam giác của pascal sẽ cho tôi kết quả, nhưng điều đó rõ ràng không hoạt động.

Vì vậy, tôi đã bị kẹt ngay bây giờ. Suy nghĩ tiếp theo của tôi là sử dụng một số loại bignum library để giải quyết vấn đề, nhưng theo ý kiến ​​của tôi phải có một cách khác để giải quyết loại nhiệm vụ này.

Cập nhật Tôi quên đề cập rằng tôi phải giải quyết nhiệm vụ này với C/Objective-C.

Answer 1

Giống như Bartosz đề nghị, tôi sẽ giải quyết điều này bằng cách chỉ đơn giản là thực hiện các tính toán trong cơ sở 10. Một nhân 11 trong 10 cơ sở có thể được thực hiện với một sự thay đổi trái và một bổ sung. Đây là một chương trình C hoạt động trên các chuỗi ASCII. Lưu ý rằng chữ số ít quan trọng nhất xuất hiện đầu tiên trong mỗi chuỗi.

#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

Họ có cho bạn biết hiệu quả của thuật toán không?

Tôi sẽ thực hiện nó đơn giản trên các chuỗi; nhân với 11 chỉ đơn giản là tạo một bản sao với một dấu 0 được thêm vào và sau đó thêm, vì vậy tất cả những gì bạn phải làm là triển khai thêm các số được viết dưới dạng chuỗi.

Answer 3

giả sử K (i) là một chuỗi được tạo ra từ hàng thứ k của tam giác pascal.

11^0 = 1,11^1 = 11,11^2 = 121. Nhưng 11^i = k (i) là giả định sai. Bởi vì 11^i = (10 + 1)^i &

====>

như vậy cho số nhỏ đó là sự thật vì 10^i là rất lớn hơn a [i] cho số lượng lớn nó có thể có một tràn cho lý do sau đây.

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 

vì vậy khi xảy ra tình trạng tràn a[i]*10^(n-i+1) < a[i+1]*10^(n-i). Bằng cách đơn giản hóa chúng, bạn nhận được (n-i+1)/i >10 đó là khi xảy ra tràn.
bạn nên tính toán các số lượng tràn này trong thuật toán của mình.

Answer 4

Một phiên bản chuỗi trong Haskell dường như làm việc khá tốt:

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)