有没有办法找到100的数字总和!？

Question

我知道有一种方法可以使用Python找到100个数字的总和!(或任何其他大数字的阶乘).但是我觉得在C++方面真的很难,因为即使是LONG LONG的规模还不够.

我只是想知道是否还有其他方法.

我知道它是不可能的,因为我们的处理器通常是32位.我所指的是其他一些棘手的技术或算法,可以使用相同的资源完成相同的工作.

Answer 1

使用带有标准的纸上乘法方法的数字数组.例如,在C中:

#include <stdio.h>

#define DIGIT_COUNT 256

void multiply(int* digits, int factor) {
  int carry = 0;
  for (int i = 0; i < DIGIT_COUNT; i++) {
    int digit = digits[i];
    digit *= factor;
    digit += carry;
    digits[i] = digit % 10;
    carry = digit / 10;
  }
}

int main(int argc, char** argv) {
  int n = 100;

  int digits[DIGIT_COUNT];
  digits[0] = 1;
  for (int i = 1; i < DIGIT_COUNT; i++) { digits[i] = 0; }

  for (int i = 2; i < n; i++) { multiply(digits, i); }

  int digitSum = 0;
  for (int i = 0; i < DIGIT_COUNT; i++) { digitSum += digits[i]; }
  printf("Sum of digits in %d! is %d.\n", n, digitSum);

  return 0;
}

Answer 2

你怎么会找到100的数字之和!如果计算100!首先,然后找到总和,然后是什么意思.您将不得不使用一些智能逻辑来找到它而不实际计算100!删除所有五个因子,因为它们只会添加零.从这个方向思考,而不是考虑大数字.此外,我确信最后的答案,即数字的总和将在LONG LONG内.

有C++大型int库,但我认为这里的重点是算法而不是库.

Answer 3

如果您指的是Project Euler问题,那么我对它的解读是它希望您编写自己的任意精度整数库或可以乘以数字的类.

我的建议是存储一个数字的10位数字,与你正常编写它们的方式相反,因为无论如何你最终都需要将数字转换为10.在我看来,以相反的顺序存储数字使得添加和乘法程序稍微容易一些.然后编写加法和乘法例程,模拟如何手动添加或乘以数字.

Answer 4

long long不是C++的一部分.g ++将其作为扩展名提供.

Arbitrary Precision Arithmetic是您正在寻找的东西.查看维基页面中给出的伪代码.

而且long long不能存储如此大的值.因此,您可以创建BigInteger类,也可以使用GMP或C++ BigInteger等第三方库.

Answer 5

观察到将任何数字乘以10或100不会改变数字的总和.

一旦你意识到这一点,看到乘以2和5,或乘以20和50,也不会改变总和,因为2x5 = 10和20x50 = 1000.

然后请注意,当你的当前计算以0结束时,你可以简单地除以10,并继续计算你的阶乘.

再做一些关于快捷方式的观察,以消除1到100之间的数字,我认为您可以将答案纳入标准整数.