阶乘最小的非零数字 [英] Least significant non-zero digit of a factorial
问题描述
我有计算一个阶乘中最不重要的非零数字。以下片段：
< script src =https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js> ;< / div>< div id =display>< / div>< div id =display2>< / div>< input type =textvalue = number>< input type =submitid =submit>
作为上述代码的一部分，为了计算最不重要的非零数字，我首先忽略了5的所有倍数，其次，在阶乘计算的每一步中，我将余数factorial2从10开始，以便在计算的每一步只保留非零数字。最后，我将 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的数字的麻烦，你不需要将它转换为字符串。）
<$ c $（$＃）$（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
< script src =https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js> ;< / div>< div id =display>< / div>< div id =display2>< / div>< input type =textvalue = number>< input type =submitid =submit>
I am trying to calculate the least significant non-zero digit in a factorial.
I have the following snippet :
$(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">
As part of the above code, to calculate the least significant non-zero digit, I am firstly ignoring all multiples of 5, and secondly, at each step of the factorial calculation,I am taking the remainder of factorial2 from 10 so as to only retain the non-zero digit at each step of the computation.Eventually, I multiply the final value of factorial2 with 5 and then convert it to a string and find the last occurrence of a non-zero digit in the string.
The above code seems to work fine for values of n=1,2........,8. But at n=9, the code returns the least significant non-zero digit as 3 whereas it should be returning 8.
For example : Factorial(9) = 362880 , hence least significant non-zero digit = 8.
What could the error be and how should I go about correcting it ? And is there another better performing method to compute this result ?
Note : I've included the code to calculate the factorial just for verification purposes, my ultimate aim is to just calculate the least significant non-zero digit and not the factorial for a worst possible case when n is a billion(when actually computing and reading the factorial is not feasible or advisable).
The problem is that 5's don't simply disappear. They combine with a 2 to create a 0. So you'll have problems after multiples of 5 (like 15 or 35) or after numbers with a lot of powers of 2 (like 24). The best thing might be to keep count of the number of 2's, and decrease that for each multiple of 5 (there's always more 2's than 5's). (Also, once you've gone to the trouble of finding the number without a 0, you don't need to convert it to a string.)
$(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">
这篇关于阶乘最小的非零数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
