JavaScript: Рассчитать расширенный алгоритм Евклида или расширенный GCD

Последнее обновление 23 мая 2019 09:15:49 (UTC / GMT +8 часов)

script1adsense2code

script1adsense3code

JavaScript Math: Упражнение 47 с решением

Напишите функцию JavaScript для вычисления расширенного алгоритма Евклида или расширенного GCD.

В математике евклидов алгоритм [a], или алгоритм Евклида, является эффективным методом вычисления наибольшего общего делителя (GCD) из двух чисел, наибольшего числа, которое делит их оба, не оставляя остатка. Он назван в честь древнегреческого математика Евклида, который впервые описал его в стихиях Евклида. Это пример алгоритма, пошаговая процедура для выполнения расчета в соответствии с четко определенными правилами, и является одним из старейших широко используемых алгоритмов. Он может использоваться для приведения дробей к их простейшей форме и является частью многих других теоретико-числовых и криптографических вычислений.

Иллюстрированная презентация:

$«JavaScript:$

Пример решения: -

HTML-код:

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>JavaScript function to calculate the extended Euclid Algorithm or extended GCD</title>
</head>
<body>
</body>
</html>

Код JavaScript:

function Euclid_gcd(a, b) {
  a = +a;
  b = +b;
  if (a !== a || b !== b) {
    return [NaN, NaN, NaN];
  }
  
  if (a === Infinity || a === -Infinity || b === Infinity || b === -Infinity) {
    return [Infinity, Infinity, Infinity];
  }
  // Checks if a or b are decimals
  if ((a % 1 !== 0) || (b % 1 !== 0)) {
    return false;
  }
  var signX = (a < 0) ? -1 : 1,
    signY = (b < 0) ? -1 : 1,
    x = 0,
    y = 1,
    u = 1,
    v = 0,
    q, r, m, n;
  a = Math.abs(a);
  b = Math.abs(b);
  while (a !== 0) {
    q = Math.floor(b / a);
    r = b % a;
    m = x - u * q;
    n = y - v * q;
    b = a;
    a = r;
    x = u;
    y = v;
    u = m;
    v = n;
  }
  return [b, signX * x, signY * y];
}
console.log(Euclid_gcd(17, 4));

Пример вывода:

 [1,1, -4]

Блок - схема:

$«Блок-схема:$

Демонстрация в реальном времени:

См. Pen javascript-math-упражнение-47 от w3resource ( @ w3resource ) на CodePen .

Улучшите этот пример решения и опубликуйте свой код через Disqus

Предыдущий: Напишите функцию JavaScript для вычисления делителя и модуля двух целых чисел.
Далее: напишите функцию JavaScript для вычисления падающего факториала числа.