如何在C++中表示2^1000的數字？

所以，我試圖做歐拉歐拉問題＃16，從http://projecteuler.net如果你還沒有看到它。它如下：如何在C++中表示2^1000的數字？

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26. 

What is the sum of the digits of the number 2^1000?

我很難搞清楚如何在C++中表示數字2^1000。我猜這有一個竅門，但我真的被卡住了。我真的不想要這個問題的答案，我只想知道如何將該數字表示爲一個變量，或者如果可能有一個竅門，也許有人可以讓我知道？

來源

2013-01-19 sand_storm_of_code.txt

您不必在C++中做它。關掉我的腦袋，PHP中的'bcpow'會讓你很容易做到這一點。 – zneak

我想過嘗試一個無符號的long long int，但是如果我沒有記錯的話，我只能讀取2^64-1。 –

看起來像來自數學奧林匹克的問題。可能是一個無需編碼就可以獲得它的技巧。 – thang

將其表示爲一個字符串。這意味着你需要寫兩段代碼：

你需要寫一段代碼翻番的數字，因爲數字作爲一個字符串。
您需要編寫一段代碼來總和表示爲字符串的數字的數字。

這兩件很容易。

來源

2013-01-19 00:16:12

不理會我以前的評論。對於那個很抱歉。 – zneak

3.你需要寫一段代碼來總結2個數字，因爲這些數字是字符串。 – maniek

@maniek：在這種情況下不需要。您可以從「1」開始並將其加倍1000倍。儘管編寫一個附加函數可能並不困難，並且通過將其添加到自身來使編號加倍。加倍可能會稍微簡單一些，因爲您不必處理數字具有不同數字位數的情況。 –

一個好的算法，值得了解了這個問題：

2^1 = 2 
2^2 = 2 x 2 = 2 + 2 
2^3 = 2 x (2 x 2) = (2 + 2) + (2 + 2) 
2^4 = 2 x [2 x (2 x 2)] = [(2 + 2) + (2 + 2)] + [(2 + 2) + (2 + 2)]

因此，我們有一個recursive定義在addition操作方面計算二的冪：just add together two of the previous power of two.

這link涉及這個問題很好。

來源

2013-01-19 00:30:44

誰降低了這個？這是解決問題方向的一個很好的暗示，提供了更多提示的鏈接（仍然沒有提供整個解決方案）。當人們來這裏要求解決Project Euler問題時，這正是人們應該發佈的信息。 – abarnert

偉大的方法！將這與大衛的答案結合起來，這個問題就變得很容易！ – Ranveer

-1

你需要一個1000位的機器整數來表示2^1000;我從來沒有聽說過這樣的機器。但是周圍有很多大的整數包，它們會根據需要進行儘可能多的機器字的算術運算。最簡單的解決方案可能是使用其中一種方法（雖然考慮到您需要的特定操作，像David Schwartz所建議的那樣對字符串進行算術可能是合適的，但在一般情況下，這不是一個好主意，但是因爲你所做的只是乘以2，然後取十進制數字，它可能工作得很好。）

來源

2013-01-19 01:00:12

-1

由於2^10約爲10^3，而2^1000 =（2^10）^ 100 =（10^3）^ 100 = 10^300（約）。所以分配等

char digits[ 300 ]; // may be too few

陣列並且在每個存儲炭0之間的值。9。

來源

2013-01-19 01:04:12

你爲什麼要這樣做而不是僅僅使用'string'？然後你不必嘗試它，調試你得到的崩潰，因爲300太少了，你砸了堆棧，然後再試一次......請記住，OP正試圖用C++解決這個問題，而不是C。 – abarnert

OP在問如何存儲太大的數字以適應機器數據類型。以上是爲了傳達多精度算法背後的基本思想，而無需額外的細節來混淆概念。 –

這個問題的關鍵在於想出一個不需要實際計算2^1000的方法。

但是，如果你做想計算2^1000，這可能是一個好主意，因爲它是測試你的其他算法是否正確 - 你會想一些「BIGNUM的好方法「庫，如gmp：

mpz_t two_to_1000; 
mpz_ui_pow_ui(two_to_1000, 2, 1000);

或者你可以使用C++ interface來gmp。它沒有做冪，所以第一部分被稍微複雜一些，而不是更少，但它使數字求和簡單：

mpz_class two_to_1000; 
mpz_ui_pow_ui(two_to_1000.get_mpz_t(), 2, 1000); 
mpz_class digitsum(0); 
while (two_to_1000) { 
    digitsum += two_to_1000 % 10; 
    two_to_1000 /= 10; 
}

（這事實上是沒有理由讓digitsum的mpz在那裏，所以你可能想弄清楚如何證明結果將裝入32位，加，作爲一個評論，只使用一個long爲digitsum。）

之所以這麼說，我可能就不會寫這gmp代碼測試它，當整個事情是Python中的一行：

print(sum(map(int, str(2**1000))))

而且，即使將bignum轉換爲字符串以將每個數字轉換爲int來總結它們可能是解決此問題的效率最低的方法，但在我擁有的最慢的計算機上，它仍需要200us以下的時間。而且實際上沒有必要用實際解決方案的相同語言進行雙重檢查。

來源

2013-01-19 01:17:07 abarnert

*「這個問題的關鍵在於想出一個不需要實際計算2^1000的方法。」 - 我不認爲是這樣。歐拉項目旨在通過數學，編程或其組合來解決以最方便的方式解決問題。如果你有一個強大的數學背景，並且可以想出一個方法來解決它而不需要實際計算2^1000，那麼很好，但我不認爲他們真的希望你這樣做。 –

@BenjaminLindley：如果那是真的，這將是一個可笑的簡單問題。它是Python中的一行代碼，並且是任何其他語言中的四行代碼，它們都是內置的或可用作庫的。但是這些問題的目的是要求「數學見解......和編程技巧」，而不是通過暴力來解決。如果你僅僅通過使用（或者模擬）牌來解決這個問題（以及問題13和其他問題），那麼你就錯過了這一點。 – abarnert

這是問題16的410.它應該很容易。當你走下坡路時，他們會越來越難。在早期階段，蠻力通常是足夠的，但後來事情變得更加棘手。也就是說，「數學見解......和編程技能」最終成爲絕對必要的。此外，這個問題對你來說似乎很容易，但對於一個年輕的孩子來說，並不是那麼重要。 –

這是一個完整的程序。數字保存在一個向量中。

#include <iostream> 
#include <numeric> 
#include <ostream> 
#include <vector> 

int main() 
{ 
    std::vector<unsigned int> digits; 
    digits.push_back(1);  // 2 ** 0 = 1 

    const int limit = 1000; 
    for (int i = 0; i != limit; ++i) 
    { 
     // Invariant: digits holds the individual digits of the number 2 ** i 

     unsigned int carry = 0; 
     for (auto iter = digits.begin(); iter != digits.end(); ++iter) 
     { 
      unsigned int d = *iter; 
      d = 2 * d + carry; 
      carry = d/10; 
      d = d % 10; 
      *iter = d; 
     } 
     if (carry != 0) 
     { 
      digits.push_back(carry); 
     } 
    } 

    unsigned int sum = std::accumulate(digits.cbegin(), digits.cend(), 0U); 
    std::cout << sum << std::endl; 

    return 0; 
}

來源

2013-01-19 02:56:10 user515430

如何在C++中表示2^1000的數字？

回答

相關問題