3

2^15 = 32768，它的位数和是3 + 2 + 7 + 6 + 8 = 26。数字2^1000的位数和是多少？

我想解决 Project Euler 问题 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;
.....
.....

等等。请帮我。

4

8 回答 8

7

您应该遍历每个数字，从最低有效位开始，将其加倍并添加前一个数字的进位，将结果模 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 库。使用 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^1000是 1001 个二进制数字和大约 302（等于 1001*log(2)）十进制数字。根据 的要求，为可能的符号字符和NULL终止符添加两个字符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 回答
1

这是我的 Python 代码：

b = 2**1000
c = str(b)

d = [ ]

for dig in c :

    d.append(int(dig))

e = sum(d)

print e
于 2018-06-15T13:27:29.207 回答
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 回答
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

这是我解决问题 16 的 java 代码

于 2018-07-14T04:42:33.087 回答
0

在这个问题中，我们可以从先前数字的计算中受益。例如要计算pow(2,1000)我们可以使用的位数pow(2,999)，我们可以将前一个号码的位数存储在队列中。当前数字可以通过将前一个数字的数字一一乘以2来获得。

在下面的代码中使用了上面的方法：

using namespace std; 
#include<bits/stdc++.h>

int main() {

    queue<int> q;
    q.push(2);
    queue<int> q2;

    for (int i = 2; i <= 1000;i++) {

        int carry = 0;
        while (!q.empty())
        {
            int first = q.front();
            q.pop();
            int digit = (first * 2 + carry) % 10;
            carry = (first*2) / 10;
            q2.push(digit);
        }
        if(carry!=0) {
            q2.push(carry);
        }
        swap(q, q2);
    }

    int sum = 0;
    while(!q.empty()) {
        sum += q.front();
        q.pop();
    }
    cout << sum << endl;
}
于 2020-05-18T01:03:01.060 回答