Наименьшая значащая ненулевая цифра факториала

Я пытаюсь вычислить наименьшую значащую ненулевую цифру в факториале.

У меня есть следующий фрагмент:

$(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, а во-вторых, на каждом шаге вычисления факториала я беру остаток factorial2 из 10, чтобы только сохранять ненулевую цифру на каждом шаге вычисления. В конце концов, я умножаю конечное значение factorial2 на 5, затем преобразовываю его в строку и нахожу последнее вхождение ненулевой цифры в строку.

Приведенный выше код работает нормально для значений n=1,2........,8. Но при n=9 код возвращает младшую значащую ненулевую цифру как 3, тогда как он должен возвращать 8.

Например: Factorial(9) = 362880, следовательно, наименьшая значащая ненулевая цифра = 8.

В чем может быть ошибка и как ее исправить? И есть ли другой более эффективный метод для вычисления этого результата?

Примечание. Я включил код для вычисления факториала только в целях проверки. Моя конечная цель — просто вычислить наименее значащую ненулевую цифру, а не факториал для наихудшего возможного случая, когда n равно миллиард (когда на самом деле вычисление и чтение факториала невозможно или нецелесообразно).


javascript html jquery performance factorial
person stark    schedule 02.02.2016    source источник
comment
В чем причина игнорирования чисел, кратных 5? Есть ли математическая причина, по которой числа, кратные 5, ведут себя странно?   -  person Marc    schedule 03.02.2016
comment
Вот скрипка, которая делает многие из них правильными, но есть определенные числа, на которых она сбивается; а именно 15, 24 и 35 (я тестировал от 1 до 40). Может быть, вы понимаете математику, почему эти цифры неприятны: jsfiddle.net/cwsoejLr Это очевидно там, где я попытался уродливо взломать определенные номера.   -  person Marc    schedule 03.02.2016
comment
@Marc Причина, по которой я игнорирую числа, кратные 5, заключается в том, что именно они приводят к нулям в факториале, но, поскольку мне нужна только ненулевая значащая цифра, я могу игнорировать числа, кратные 5, чтобы уменьшить вычисления, необходимые для проблема.   -  person stark    schedule 03.02.2016
comment
Вы можете попытаться разобраться в этой статье: mathpages.com/home/kmath489.htm   -  person Marc    schedule 03.02.2016

Ответы (1)


arrow_upward
1
arrow_downward

Проблема в том, что 5 просто так не исчезают. Они объединяются с 2, чтобы создать 0. Таким образом, у вас будут проблемы после кратных 5 (например, 15 или 35) или после чисел с большим количеством степеней двойки (например, 24). Лучше всего было бы вести подсчет количества двоек и уменьшать его для каждого числа, кратного 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">

person Teepeemm    schedule 07.02.2016