-1

我试图在项目 euler 上使用 C 来解决问题点击这里 是代码。它适用于 10 个值，但对于 1000 个值，它会给出错误的输出。我注意到它在 32 之前给出了正确的输出。我想我超出了内存或其他东西。如何为这么大的数组分配内存？

#include <stdio.h>
int main() { 
    int a[10], i, sum=1, b=0;

    for(i = 1; i < 10; i++) { 
        a[0] = 1;
        a[i] = sum + a[i-1];
        sum = sum + a[i-1];
    }

    for(int j = 1;j > 0; j++) {
        b = b + sum%10;

        if(sum<10)
            break;

        sum = sum/10;
     }

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

     return 0;
 }
4

2 回答 2

4

您可以尝试将 2 1000计算为 80-bit long double，然后使用sprintf将其转换为字符串，然后对该字符串的数字求和。

为什么这样有效：

浮点类型将数字存储为尾数乘以指数。指数始终是 2 的幂，尾数可以是 1。对于 a long double，指数最高可达 2 16383。 printf和朋友，在现代实现中，将正确打印出浮点数的数字。

代码：

int main() {
  char buf[1024]; int ans = 0;
  sprintf(buf, "%.0f", 0x1.0p1000);
  for (int i = 0; buf[i]; i++) ans += buf[i] - '0';
  printf("%i\n", ans);
}
于 2013-03-10T22:44:43.337 回答
2

I noticed that it gives a right output till 32

That is, because the integer type you're using has 32 bits. It simply can't hold larger numbers. You can't solve it the conventional way.

Here's what I'd suggest: First let's estimate how many digits that number will have. Every time a number gets 10-fold in decimal writing a new digit is required. So the number of digits for a number in decimal is given by ceil(log10(n)). So for 2^1000 you need ceil(log10(2^1000)) digits, but that is just ceil(1000*log10(2)) = 302, so you'll need 302 decimal digits to write it down.

This gives the next idea: Write down the number 1 in 302 digits, i.e. 301 times '0' and one '1' in a string. Then double the string 1000 times, by adding it to itself just like in elementary school, carrying the overflowing digits.

EDIT I think I should point out, that the problem encountered is the whole point of this Project Euler problem. Project Euler problems all have in common, that you can not solve them by using naive programming methods. You must get creative to solve them!

于 2013-03-10T22:56:58.637 回答