欧几里得算法 | 陌名如初

在 codewars 遇到一道题, 题目大概意思是: 有 Bob, Charles 两个慢跑者, 二者从同一起点出发, 以相同的速度慢跑, 但是所跑的的圈数和圈的大小不同(如下图). 问两人从起点出发后, 最少要各自跑多少圈才能再次相遇?

1. The length of Bob’s lap (larger than 0).
2. The length of Charles’ lap (larger than 0).
3. The first number is the number of laps that Bob has to run.
4. The second number is the number of laps that Charles has to run.

Examples:

nbrOfLaps(5, 3); // returns [3, 5]
nbrOfLaps(4, 6); // returns [3, 2]

思路: 这是一个求取最大公约数的问题, 二者各跑的圈数除以最大公约数, 即得到二人至少要跑的圈数.

欧几里德算法又称辗转相除法，用于计算两个整数 a,b 的最大公约数。其计算原理依赖于下面的定理：
定理： gcd(a,b) = gcd(b,a mod b)
证明：
a 可以表示成 a = kb + r，则 r = a mod b.
假设 d 是 a,b 的一个公约数，则有 d|a, d|b，而 r = a - kb，因此 d|r.
因此 d 是(b,a mod b)的公约数
假设 d 是(b,a mod b)的公约数，则
d|b , d |r ，但是 a = kb +r
因此 d 也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等.

代码如下:

const gcd = function (a, b) {
  if (b === 0) return a;
  return gcd(b, a % b);
};
const nbrOfLaps = (x, y) => [y, x].map(item => item / gcd(x, y));

The MIT License (MIT)
Copyright (c) 2019, Roojay.
本文链接：https://roojay.com/pages/b511dfae/