3

2^15 = 32768 で、その桁数の合計は 3 + 2 + 7 + 6 + 8 = 26 です。数値 2^1000 の桁数の合計は何ですか?

プロジェクト オイラーの問題 No. 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]には 1arr[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;
.....
.....

等々。私を助けてください。

4

8 に答える 8

7

最下位の桁から始めて各桁を調べ、それを 2 倍にして前の桁からのキャリーを追加し、結果をモジュロ 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余談ですが、バイナリでは計算が非常に簡単です。 11000 が続くだけ0です。結果を 10 進数表現に変換するのは少し難しいですが、効率的なバイナリから BCD への変換方法が存在します。ただし、代わりに GNU MP ライブラリを使用することをお勧めします。GNU MP を使用して 2^1000 を計算するのに 6 行しかかかりません (#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^10002 進数で 1001 桁、10 進数で約 302 (1001*log(2) に等しい)であることに注意してください。の必要に応じて、可能な記号文字とNULLターミネータ文字の 2 文字を追加しmpz_get_str()ます。

これで、得られた数字をstrで調べ、それらを整数に変換し、それらをすべて合計するだけで済みます。

于 2012-06-19T15:42:30.193 に答える
1 
#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;
}
于 2012-06-19T23:01:06.070 に答える
1 
#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;
            }
于 2014-04-09T00:51:41.263 に答える
0

これが私のコードです

#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;
}
于 2015-03-03T09:01:42.277 に答える
0 
    //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;
}
于 2012-06-20T06:54:10.780 に答える