阶乘的最小有效非零位

Least significant non-zero digit of a factorial

本文关键字：零位 有效 阶乘      更新时间：2023-09-26

我正在尝试计算阶乘中最低有效的非零位。

我有以下代码片段： 

$(document).ready(function() {
  $('#submit').click(function() {
    var n = $('#number').val();
    get_result(n);
  });
});
function get_result(n) {
  var factorial = 1;
  var factorial2 = 1;
  for (i = 1; i <= n; i++) {
    factorial = factorial * i;
  }
  var count_5 = 0;
  for (j = 1; j <= n; j++) {
    if (j % 5 != 0) {
      factorial2 = factorial2 * (j % 10);
      factorial2 = factorial2 % 10;
    } else if (j % 5 == 0) {
      count_5 = 1;
    }
  }
  if (count_5 == 1) {
    factorial2 = factorial2 * 5;
  }
  console.log(factorial2);
  factorial2 = factorial2.toString();
  var digit = 0;
  for (i = 0; i < factorial2.length; i++) {
    if (factorial2[i] != '0') {
      digit = factorial2[i];
    }
  }
  $('#display').text("Factorial of " + n + " is " + factorial);
  $('#display2').text("Least significant digit of Factorial of " + n + " is " + digit);
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="display">
</div>
<div id="display2">
</div>
<input type="text" value="" id="number">
<input type="submit" id="submit">

作为上述代码的一部分，为了计算最低有效非零数字，我首先忽略 5 的所有倍数，其次，在阶乘计算的每一步，我从 10 中获取阶乘 2 的其余部分，以便在计算的每一步只保留非零数字。最后，我将 factorial2 的最终值乘以 5，然后将其转换为字符串并找到字符串中最后一个出现的非零数字。

上面的代码似乎适用于 n=1,2........，8 的值。但是在 n=9 时，代码返回最低有效的非零数字为 3，而它应该返回 8。

例如：阶乘(9( = 362880，因此最小有效非零位数 = 8。

错误可能是什么，我应该如何纠正它？有没有另一种性能更好的方法来计算这个结果？

注意：我包含计算阶乘的代码只是为了验证目的，我的最终目标是只计算最低有效非零数字，而不是当 n 是十亿时最坏情况下的阶乘(当实际计算和读取阶乘是不可行或不可取的(。

问题是 5 不会简单地消失。 它们与 2 组合以创建 0。 因此，在 5 的倍数(如 15 或 35(或 2 的很多次幂的数字(如 24(之后，您会遇到问题。 最好的办法可能是保持 2 的数量，并减少 5 的每个倍数(2 总是比 5 多(。 (此外，一旦您找到了没有 0 的数字，就不需要将其转换为字符串。

$(document).ready(function() {
  $('#submit').click(function() {
    var n = $('#number').val();
    get_result(n);
  });
});
function get_result(n) {
  var factorial = 1;
  var factorial2 = 1;
  for ( var i = 1; i <= n; i++ ) {
    factorial = factorial * i;
  }
  var extra2s = 0;
  for ( var j = 1; j <= n; j++ ) {
    var jcopy = j;
    while( jcopy%10 == 0 ) {
      jcopy /= 10;
    }
    while( jcopy%2==0 ) {
      extra2s++;
      jcopy /= 2;
    }
    while( jcopy%5==0 ) {
      extra2s--;
      jcopy /= 5;
    }
    jcopy %= 10;
    factorial2 = (factorial2 * jcopy)%10;
  }
  for ( var k = 0 ; k < extra2s ; k++ ) {
    factorial2 = (factorial2 * 2)%10;
  }
  var digit = factorial2;
  $('#display').text("Factorial of " + n + " is " + factorial);
  $('#display2').text("Least significant digit of Factorial of " + n + " is " + digit);
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="display">
</div>
<div id="display2">
</div>
<input type="text" value="" id="number">
<input type="submit" id="submit">

相关文章：