項目歐拉沒有。 16

Question

2^15 = 32768且其數字之和是3 + 2 + 7 + 6 + 8 = 26. 數字2^1000的數字之和是多少？

我想解決項目歐拉問題16號。我試圖將數組中的2的能力。假設2^6 = 128。然後

int arr[1000]; 
arr[0] = 1 // or 8 (In other way also) 
arr[1] = 2 
arr[2] = 8 // or 1 
// and so on.... 

但現在問題是如何解決這個問題。

我在將數字轉移到下一個數組位置時遇到問題。現在假設 ，

arr[0] = 8; 

在下一迭代

arr[0] = 1; and array[1] = 6; 

這裏arr[0]包含1和arr[1]包含6. 接着

arr[0] = 3; 
arr[1] = 2; 
.... 
.... 
//2^6 
arr[0] = 1; 
arr[1] = 2; 
arr[2] = 8; 
... 
... 
//2^10 
arr[0] = 1; 
arr[1] = 0; 
arr[2] = 2; 
arr[3] = 4; 
..... 
..... 

等。請幫幫我。

Answer 1

您應該檢查每個數字，從最低有效位開始，加倍並加上前一個進位，將結果模10存儲爲新數字值，如果結果大於9，則設置攜帶1，否則爲0（或只是10執行結果的整數除法）：

carry = 0 
for i = 0 to MAX_DIGITS-1: 
    tmp = 2 * digits[i] + carry 
    digits[i] = tmp % 10 
    carry = tmp/10 

（這是僞代碼 - 它自己使用轉換爲C）只是

---

作爲一個方面說明，計算2^1000在二進制文件中非常容易 - 它僅僅是1，然後是1000 0。將結果轉換爲十進制表示法有點棘手，但存在一種有效的二進制BCD轉換方法。但我仍然建議您改用GNU MP庫。只需要6行使用GNU MP來計算2^1000（在#define線和所有空白線不計算在內）：

#include <gmp.h> 

#define MAX_DIGITS 302 

mpz_t bignum; 
char str[MAX_DIGITS+2]; 

mpz_init2(bignum, 1001); 
mpz_ui_pow_ui(bignum, 2, 1000); // set the integer object to 2^1000 
mpz_get_str(str, 10, bignum); // convert to base 10 

注意2^1000爲1001個的二進制數字與約302（等於1001 *日誌（ 2））十進制數字。爲可能的符號字符和mpz_get_str()要求的終止符字符添加兩個字符。

現在你只需要檢查str中的結果數字，將它們轉換爲整數並將它們總和。

Answer 2

#include <stdio.h> 

void mul2(int *n){ 
    int c = 0, v; 
    while(*n>=0){ 
     v = c + *n * 2; 
     c = v/10; 
     *n++ = v % 10; 
    } 
    if(c) *n++ = c;//1 
    *n = -1;//stopper 
} 

int sum(int *n){ 
    int sum=0; 
    while(*n>=0) 
     sum += *n++; 
    return sum; 
} 

int main(void){ 
    int arr[1000] = {1, -1};//need 302 + 1, -1 is stoper 
    int i; 
    for(i=0;i<1000;i++) 
     mul2(arr); 
    printf("%d\n", sum(arr)); 
    return 0; 
} 

Answer 3

//Finally I did it. 


    #include <stdio.h> 
#include <stdlib.h> 
//2^1000 
int main() 
{ 
    int array[1000] = { 0 }; 
    array[0] = 1; 
    int i, j, cnt, div, carry, temp, sum; 
    for(i = 0, cnt = 1; i < 1000; i++) 
    { 
     div = carry = 0; 
     for(j = 0; j < 1000; j++) 
     { 
      if(carry != 0) 
      { 
       array[j] = (array[j] * 2) + carry; 
       div = array[j] % 10; 
       temp = array[j]/10; 
       array[j] = div ;//+ carry; 
       carry = temp; 
       //array[j] = (array[j] * 2) + 1; 
       //carry = 0; 
      } 
      else 
      { 
       array[j] = array[j] * 2; 
       if (array[j] > 9) 
       { 
        div = array[j] % 10; 
        carry = array[j]/10; 
        array[j] = div; 
       } 
      } 

     } 

    } 
    sum = temp = 0; 
    printf("The value of 2^1000 is : "); 
for(i = 999; i >= 0; i--) 
{ 
    if(array[i] || (temp)) 
    { 
     temp++; 
     sum = sum + array[i]; 
     printf("%d", array[i]); 
    } 

} 
    printf("\nThe sum is : %d \n", sum); 
    printf("\nThe number of digits are : %d \n", temp); 
    return 0; 
} 

Answer 4

#include <stdio.h> 

#define POWER 1000 

int digits[(POWER * 302 + 999)/1000] = {1}; // > log10(2 ** POWER) 
int ndigits = 1; 

int main(void) 
{ 
    for (int i = 0; i < POWER; i++) 
     for (int n = 0, j = 0;; j++) 
     { 
      n += digits[j] * 2; 
      digits[j] = n % 10; 
      n /= 10; 
      if (j == ndigits - 1) 
      { 
       if (!n) break; 
       ndigits++; 
      } 
     } 

    int sum = 0; 
    for (int i = 0; i < ndigits; i++) 
     sum += digits[i]; 

    printf("%d\n", sum); 

    return 0; 
} 

編輯：一個可能更快，但更晦澀內部塊：

  n += digits[j] * 2; 
      if (n >= 10) 
      { 
       digits[j] = n - 10; 
       n = 1; 
       if (j == ndigits - 1) 
        ndigits++; 
      } 
      else 
      { 
       digits[j] = n; 
       if (j == ndigits - 1) 
        break; 
       n = 0; 
      } 

Answer 5

這裏是我的代碼

#include <iostream> 
#include <cstdio> 
using namespace std; 

int main() { 

int a[10000]={0}; 
int m=1; 
int carry=0; 
a[0]=1; 
long long int sum=0; 
for(int i=1;i<=1000;i++) 
{ 
    for(int j=0;j<m;j++) 
    { 
     int x=a[j]*2+carry; 
     a[j]=x%10; 
     carry=x/10; 
    } 
    while(carry!=0) 
    { 
     a[m++]=carry%10; 
     carry/=10; 
    } 
    } 
    for(int i=m-1;i>=0;i--) 
    sum+=a[i]; 
    printf("%lld",sum); 
    return 0; 
}