项目欧拉没有.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二进制计算极其简单 - 只需要11000就可以了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终结符字符添加两个字符作为requried mpz_get_str().

现在你只需要查看结果数字str,将它们转换为整数并将它们全部加起来.