Tính tổng cộng 2^1000 mà không sử dụng BigInt

Question

Vì một số bạn có thể nhận thấy câu hỏi này là problem 16 từ Project Euler. Tôi đã giải quyết nó bằng cách sử dụng tính năng "bigInt" mới của C# 4.0 khá đơn giản nhưng cũng không thực sự học được mọi thứ tôi nên làm. Tôi giả định rằng kể từ khi nó là 2^1000 sẽ có một số loại giải pháp chuyển bit nhưng tôi không thể tìm ra cách chính xác nó sẽ làm việc.

Không ai biết cách tính 2^1000 mà không sử dụng bigint?

Answer 1

Dưới đây là một cách khá ngây thơ để làm điều đó trong python chỉ sử dụng một danh sách (hoặc mảng) các chữ số

digits = [1] 
for n in range(1000): 
    newdigits = [] 
    carry = 0 
    for digit in digits: 
     s = 2*digit+carry 
     carry = s/10 
     s = s%10 
     newdigits.append(s) 
    if carry: 
     newdigits.append(carry) 
    digits = newdigits 
print "".join(map(str,reversed(digits))) 

Answer 2

Bạn có thể ngụ ý BigInt chính mình, có khả năng giới thiệu lỗi và có khả năng dẫn đến một giải pháp chậm hơn nhiều. Việc thực hiện điển hình là tự thực hiện các phép toán (trên cơ sở mỗi chữ số), với một số cơ sở cao, chẳng hạn như số cơ sở 2^16.

Answer 3

OK ở đây đi:

1 << 1000 

Trên một lưu ý nghiêm trọng hơn, mức cao nhất bạn có thể giữ trong một số nguyên x-bit là 1<<x-1. Để thực sự tính toán 1<<1000 bạn cần một bộ xử lý 1000 bit (kỹ thuật 1001-bit, nhưng ai đang đếm tại thời điểm này). Vì điều đó không khả thi, lựa chọn duy nhất của bạn là thi đua nó (và đó là những gì bigint làm).

Answer 4

Không có gì để tính toán thực sự là: 2^1000 = (1000...[994]...000)[Base2]. Đó là một 'kết quả' rồi.

Nếu bạn muốn biết cách lưu trữ, máy của bạn không có độ chính xác để lưu trữ giá trị chính xác của nó. Vì vậy, đó là số BigInt hoặc giá trị gần đúng gấp đôi Math.Pow(2, 1000).

Chỉnh sửa: Tôi thấy bây giờ bạn từ các nhận xét chỉ muốn tổng các chữ số. Xem một trong các giải pháp.

Answer 5

Phần khó nhất của vấn đề này không phải là tính toán (chỉ cần bắt đầu bằng 1 và nhân đôi nó 1000 lần), nhưng hiển thị câu trả lời theo thập phân. Với điều này trong tâm trí, bạn có thể thấy nó dễ dàng hơn để thực hiện tính toán trong một số dạng biểu diễn BCD, chẳng hạn như base-1000. Sau đó thực hiện phép nhân dài 2 nghìn lần. Dưới đây là một giải pháp Python:

def mul2(n): 
    result = [] 
    carry = 0 
    for i in n: 
     i = i * 2 + carry 
     carry = 0 if i < 1000 else 1 
     result.append(i % 1000) 
    if carry: result.append(1) 
    return result 

n = [1] 
for _ in range(1000): 
    n = mul2(n) 

print ''.join('{0:03}'.format(i) for i in reversed(n)).lstrip('0') 

Answer 6

Vấn đề là thực sự chuyển đổi của 2^1000 đến cơ sở 10. Một cách dễ dàng có thể thực hiện một số loại BCD (Binary Coded Decimal) chiều dài tùy ý và tính toán 2^1000 BCD. Một mảng 250 byte sẽ là quá đủ. Sau đó, bạn chỉ cần viết phương thức để thực hiện * 2 trên một số BCD có độ dài tùy ý và gọi nó là 1000 lần). Sau đó, giải nén và tổng hợp các chữ số là dễ dàng.

Điều đó rất dễ thực hiện ngay cả trong các ngôn ngữ như C.

Answer 7

Tôi sẽ thử và trả lời mà không cần đưa ra nhiều mã ...

1) Sử dụng một String để giữ sản phẩm

2) Thực hiện lâu Phép nhân (như bạn đã làm trong trường)

Prod = "1" 
for n = 1 to 1000 
     carry = 0 
     newprod = "" 
     for i = strlen(prod) - 1 to 0 step - 1 
       digit = int(prod[i]) 
       p = digit * 2 + carry 
       newprod = (p % 10) & newprod // append 
       carry = p/10 
     next 
     if(carry > 0) newprod = carry & newprod 
     prod = newprod 
next 

in prod

Notepad-Mã hóa ở đây ... do đó nếu có ai phát hiện lỗi, hãy sửa chúng.

Answer 8

class Program 
{ 
    static void Main(string[] args) 
    { 
     double sum=0; 
     for (int i = 1000; i <=1000; i++) 
     { 
      double pow = Math.Pow(2, i); 
      string power = pow.ToString(); 
      for (int j = 0; j < power.Length; j++) 
      { 
       sum = sum+pow % 10; 
       StringBuilder t = new StringBuilder(pow.ToString()); 
       int len = t.Length; 
       if (len != 1) 
       { 
        t.Remove(len - 1, 1); 
       } 
       pow = Convert.ToDouble(t.ToString()); 
      } 
      Console.WriteLine(sum); 
       Console.WriteLine(); 

     } 
    } 
}