阶乘

在数学上, 自然数n的阶乘写作n!。一个正整数 n 的阶乘, 就是所有小于等于 n 的正整数的乘积，0的阶乘为1。比如:

5！ = 5 4 3 2 1 = 120

n n!
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5 040
8 40 320
9 362 880
10 3 628 800
11 39 916 800
12 479 001 600
13 6 227 020 800
14 87 178 291 200
15 1 307 674 368 000

问题： 求自然数n的阶乘 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number} number
 * @return {number}
 */
export default function factorial(number) {
  let result = 1;
  // 0 或 1 返回 1
  if (number === 0 || number === 1) {
    return 1;
  }
  // 大于等于2时循环相乘
  for (let i = 2; i <= number; i++) {
    result *= i;
  }

  return result;
}

使用尾递归的方法

1
2
3
4
5
6
7
8
/**
 * @param {number} n
 * @param {number} total
 * @return {number}
 */
export default function factorial(n, total = 1) {
  return n === 1 ? total : factorial(n - 1, n * total);
}

斐波那契

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。

n Fibonacci (n)
1 1
2 1
3 2
4 3
5 5
6 8
7 13

问题： 求斐波那契数列的第n个数字 

1
2
3
4
5
6
7
8
9
10
// 采用递归方法
export default function Fibonacci (n) {
   if(n === 1 || n === 2) {
        // 递归结束的条件，求前两项
        return 1;
    } else {
        // 如果是求其它项，先要求出它前面两项，然后做和。
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}
1
2
3
4
5
6
7
// 使用尾递归优化
export default function Fibonacci (n , prev = 1 , curr = 1) {
    if(n === 1 || n === 2) {
        return curr;
    };
    return Fibonacci (n - 1, curr, prev + curr);
}
1
2
3
4
5
6
7
8
9
10
11
// 使用解构赋值+循环
export default function Fibonacci (n){
    if (n === 1 || n === 2) {
        return 1;
    }
    let prev = 1, curr = 1;
    for (let i = 2; i = n; i++){
        [prev, curr] = [curr, prev + curr];
    }
    return curr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 使用生成器
// fibonacci generator
function * fibonacci () {
    yield 1;
    yield 1;
    let [prev, curr] = [1, 1];
    while (true) {
        [prev, curr] = [curr, prev + curr];
        yield curr;
    }
}
// fibonacci function
export default function Fibonacci (n){
    let ac = 0;
    const fibo = fibonacci();
    for (let i = 1; i <= n; i++) {
      ac = fibo.next()
    }
    return ac.value;
}

素数

素数（又叫质数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
例如： 2，3，5，7，11，13，17，19，23，29，31，37…

问题： 判断自然数n是否是素数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * @param {number} number
 * @return {boolean}
 */
export default function trialDivision(number) {
  // Check if number is integer.
  if (number % 1 !== 0) {
    return false;
  }

  if (number <= 1) {
    // If number is less than one then it isn't prime by definition.
    return false;
  }

  if (number <= 3) {
    // All numbers from 2 to 3 are prime.
    return true;
  }

  // If the number is not divided by 2 then we may eliminate all further even dividers.
  if (number % 2 === 0) {
    return false;
  }

  // If there is no dividers up to square root of n then there is no higher dividers as well.
  const dividerLimit = Math.sqrt(number);
  for (let divider = 3; divider <= dividerLimit; divider += 2) {
    if (number % divider === 0) {
      return false;
    }
  }

  return true;
}

欧几里得算法

在数学中，欧几里德算法，是计算两个数的最大公约数（GCD）的一种有效方法。两个数的最大公约数是指不留余数即可将两个数整除的数中最大的数。
欧几里德算法是基于如果用大数与小数的差代替大数，两个数的最大公约数不变的原理。例如，21 是 252（21 21） 与 105 （21 5）的最大公约数，那么 21 同时也是 105 和 252 - 105 = 147 的最大公约数。由于这个替换减少了两个数字中较大的一个，重复这个过程会连续地给出较小的一对数字，直到两个数字相等为止。当出现这种情况时，它们是原始两个数字的GCD。
通过颠倒这些步骤，GCD可以表示为每个原始数乘以正整数或负整数的和，例如21=5×105+（-2）×252。GCD总是可以用这种方式表达的事实被称为裴蜀定理。

问题： 利用欧几里得算法求两个数的最大公约数

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Recursive version of Euclidean Algorithm of finding greatest common divisor (GCD).
 * @param {number} originalA
 * @param {number} originalB
 * @return {number}
 */
export default function euclideanAlgorithm(originalA, originalB) {
  // Make input numbers positive.
  const a = Math.abs(originalA);
  const b = Math.abs(originalB);

  // To make algorithm work faster instead of subtracting one number from the other
  // we may use modulo operation.
  return (b === 0) ? a : euclideanAlgorithm(b, a % b);
}

循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Iterative version of Euclidean Algorithm of finding greatest common divisor (GCD).
 * @param {number} originalA
 * @param {number} originalB
 * @return {number}
 */
export default function euclideanAlgorithmIterative(originalA, originalB) {
  // Make input numbers positive.
  let a = Math.abs(originalA);
  let b = Math.abs(originalB);

  // Subtract one number from another until both numbers would become the same.
  // This will be out GCD. Also quit the loop if one of the numbers is zero.
  while (a && b && a !== b) {
    [a, b] = a > b ? [a - b, b] : [a, b - a];
  }

  // Return the number that is not equal to zero since the last subtraction (it will be a GCD).
  return a || b;
}

最小公倍数

在算术和数论中，两个整数a和b的最小公倍数、最小公倍数或最小公倍数，通常用LCM（a，b）表示，是可被a和b整除的最小正整数。由于整数被零除是未定义的，只有当a和b都不等于0时，这个定义才有意义。但也有些人定义 lcm(a, 0) = 0

最小公倍数可以这样计算 lcm(a, b) = |a * b| / gcd(a, b) 

1
2
3
4
5
6
7
8
9
10
11
import euclideanAlgorithm from './euclideanAlgorithm';

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */

export default function leastCommonMultiple(a, b) {
  return ((a === 0) || (b === 0)) ? 0 : Math.abs(a * b) / euclideanAlgorithm(a, b);
}

##