1

这也是一个与数学相关的问题，但我想在 C++ 中实现它......所以，我有一个表单中的数字2^n，我必须计算它的数字总和（以 10;P 为底）。我的想法是用以下公式计算它：

sum = (2^n mod 10) + (floor(2^n/10) mod 10) + (floor(2^n/100) mod 10) + ...

对于它的所有数字：floor(n/floor(log2(10))).

第一项很容易用模幂计算，但我遇到了其他问题。由于n很大，而且我不想使用我的大整数库，pow(2,n)没有模数我无法计算。第一项的代码片段：

while (n--){
    temp = (temp << 1) % 10;
};

但第二个我不知道。我也不能floor单独使用它们，因为它会给出“0”（2/10）。有可能实现这一目标吗？（http://www.mathblog.dk/project-euler-16/更简单的解决方案。）当然，如果不能用这种方法完成，我会寻找其他方法。（例如将数字存储在字节数组中，如链接中的注释中所示）。

编辑：感谢现有的答案，但我正在寻找某种数学方法来解决它。我刚刚想出了一个想法，它可以在没有 bignum 或 digit-vectors 的情况下实现，我将测试它是否有效。

所以，我有上面的等式求和。但2^n/10^k可以写成2^n/2^(log2 10^k)which is 2^(n-k*log2 10)。然后我取它的小数部分和它的整数部分，并对整数部分进行模幂运算：2^(n-k*log2 10) = 2^(floor(n-k*log2 10)) * 2^(fract(n-k*log2 10)). 在最后一次迭代之后，我还将它与分数模 10 相乘。如果它不起作用或者我在上述想法的某个地方错了，我坚持使用向量解决方案并接受答案。

编辑：好的，似乎不可能用非整数模进行模幂运算（？）（或者我还没有找到任何关于它的东西）。所以，我正在做基于数字/矢量的解决方案。

代码不能完全工作！

它没有给出好的价值：（1390而不是1366）：

typedef long double ldb;

ldb mod(ldb x, ldb y){             //accepts doubles
    ldb c(0);
    ldb tempx(x);
    while (tempx > y){
        tempx -= y;
        c++;
    };
    return (x - c*y);
};

int sumofdigs(unsigned short exp2){
    int s = 0;
    int nd = floor((exp2) * (log10(2.0))) + 1;
    int c = 0;
    while (true){
        ldb temp = 1.0;
        int expInt = floor(exp2 - c * log2((ldb)10.0));
        ldb expFrac = exp2 - c * log2((ldb)10.0) - expInt;
        while (expInt>0){
           temp = mod(temp * 2.0, 10.0 / pow(2.0, expFrac)); //modulo with non integer b:
                //floor(a*b) mod m = (floor(a mod (m/b)) * b) mod m, but can't code it
            expInt--;
        };
        ldb r = pow(2.0, expFrac);
        temp = (temp * r);
        temp = mod(temp,10.0);
        s += floor(temp);
        c++;
        if (c == nd) break;
    };
    return s;
};
4

3 回答 3

2

您可以使用其他问题中提到的一些技术创建数字向量（C++ 获取 int 中的每个数字），然后迭代该向量并将所有内容相加。

于 2014-01-23T00:04:58.133 回答
1

在您提到的链接中，您的答案对于 n <= 63 的任何数字都可以正常工作。那么...您为什么要问？

如果您必须自己编写所有内容，那么您需要知道如何计算二进制除法并处理非常大的数字。如果您不必对所有内容进行编程，请获取一个用于大整数的库并应用链接中显示的算法：

BigNumber big_number;
big_number = 1;
big_number <<= n;
int result = 0;
while(big_number != 0) {
    result += big_number % 10;
    big_number /= 10;
}
return result;

现在，实现 BigNumber 会很有趣。从算法中我们看到需要赋值、左移、不等、取模和除法。BigNumber 类可以是完全动态的并分配整数缓冲区以使所述大数适合。它也可以用固定大小编写（例如作为模板）。但如果你没有时间，也许这个会做：

https://mattmccutchen.net/bigint/

于 2014-01-23T03:28:46.523 回答
0

我在 JavaScript 中实现了这个，用于查找 2^1000 的数字总和：（查看工作中的 CodePen）

function calculate(){
  var num = 0, totalDigits = 1,exponent =0,sum=0,i=0,temp=0, carry;  
  var arr = ['1'];

  //Logic to implement how we multiply in daily life using carry forward method
  while(exponent<1000){ //Mention the power
    carry=0;
    for(var j=arr.length-1;j>=0;j--){
      temp = arr[j]*2 + carry;
      arr[j]= temp%10;
      carry = parseInt(temp/10);
      if(carry && !j){
        arr = [carry].concat(arr); //if the last nth digit multiplication with 2 yields a carry, increase the space!
      }
    }
    exponent++;
  }
  
  for(var i=0;i<arr.length;i++){
    sum = sum+parseInt(arr[i]);
  }
  document.getElementById('result').value = sum; //In my HTML code, I am using result textbox with id as 'result'
  //console.log(arr);
  //console.log(sum);
}

于 2017-08-11T17:57:08.313 回答