阶乘最小的非零数字

阶乘最小的非零数字

本文介绍了阶乘最小的非零数字的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述






我有计算一个阶乘中最不重要的非零数字。以下片段:

 < 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.

错误是什么,我应该怎么去关于纠正?还有另一种更好的执行方法来计算这个结果吗?


解决方案

问题是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.

What could the error be and how should I go about correcting it ? And is there another better performing method to compute this result ?

解决方案

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">

这篇关于阶乘最小的非零数字的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

09-02 14:37