暴力穷举、辗转相除法、更相减损法、stein算法算法

暴力穷举是一种简单但不高效的算法，用于解决某些问题的尝试。它通过遍历所有可能的解来寻找正确的答案。然而，由于它的复杂性较高，当问题规模增大时，暴力穷举算法的执行时间会指数增长。因此，它主要适用于规模较小的问题。

辗转相除法是一种被广泛应用于求解最大公约数的算法。它通过反复用较小数去除较大数，直到余数为0为止。最后，被除数即为最大公约数。辗转相除法的优点是它的执行速度相对较快，适用于解决大数的问题。

更相减损法也是一种用于求解最大公约数的算法。它通过反复用两个数的差值去替换原来的两个数，直到两个数相等为止。最后，相等的数即为最大公约数。更相减损法与辗转相除法相比，更适用于解决较大数值问题，但它的执行时间会受到较大数值差异的影响。

Stein算法是一种高效的求解最大公约数的算法，同时也被称为二进制法。它结合了辗转相除法和更相减损法的优点，并通过移位和减法操作等来加速计算过程。相较于传统的算法，Stein算法的执行速度更快，尤其适用于大数运算。

总结来说，暴力穷举适用于规模较小的问题，而辗转相除法、更相减损法和Stein算法则更适合解决求解最大公约数的问题。鉴于每个算法的特点和优缺点，我们可以根据具体问题的要求选择合适的算法来解决。

相关问题

分别使用辗转相除法和穷举法求两个整数的最大公约数和最小公倍数

【辗转相除法】

辗转相除法又叫欧几里得算法，是求两个正整数的最大公约数的一种方法。它的基本思想是用较小的数除较大的数，再用出现的余数去除除数，不断重复这个过程，直到余数为零为止。最后的除数就是这两个数的最大公约数。

求两个整数a和b的最大公约数的辗转相除法公式如下：

gcd(a,b) = gcd(b,a%b)

其中，a%b表示a除以b所得的余数，gcd(a,b)表示a和b的最大公约数。

代码实现：

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

【穷举法】

穷举法是一种简单直观的方法，它的基本思想是列举出所有可能的公约数，然后找出其中最大的一个。求两个整数a和b的最大公约数的穷举法公式如下：

gcd(a,b) = max({i | i是a的因数 且 i是b的因数})

其中，i是a和b的公约数，max表示取其中的最大值。

代码实现：

def gcd(a, b):
    res = 1
    for i in range(1, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            res = i
    return res

最小公倍数的求法：

根据最大公约数的定义，有以下公式：

lcm(a,b) = a * b / gcd(a,b)

其中，lcm表示a和b的最小公倍数。

代码实现：

def lcm(a, b):
    return a * b // gcd(a, b)

js穷举法写24点游戏算法

首先，需要明确一下24点游戏的规则：给定4个数字，可以通过加减乘除和括号的运算，使得最终的结果为24。

穷举法的思路就是将所有可能的组合都尝试一遍，看看是否有符合要求的。以下是一个JavaScript实现的例子：

function game24(arr) {
  if (arr.length == 1) {
    return Math.abs(arr[0] - 24) < 0.00001;  // 判断结果是否为24
  }

  // 枚举所有可能的情况
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i == j) continue;

      let newArr = [];
      for (let k = 0; k < arr.length; k++) {
        if (k != i && k != j) {
          newArr.push(arr[k]);
        }
      }

      // 加法
      newArr.push(arr[i] + arr[j]);
      if (game24(newArr)) return true;
      newArr.pop();

      // 减法
      newArr.push(arr[i] - arr[j]);
      if (game24(newArr)) return true;
      newArr.pop();

      // 乘法
      newArr.push(arr[i] * arr[j]);
      if (game24(newArr)) return true;
      newArr.pop();

      // 除法
      if (arr[j] != 0) {
        newArr.push(arr[i] / arr[j]);
        if (game24(newArr)) return true;
        newArr.pop();
      }
    }
  }

  return false;
}

console.log(game24([4, 6, 8, 9]));  // true
console.log(game24([1, 2, 3, 4]));  // false

该算法的时间复杂度为 $O(4^3 \times 3^3 \times 2^2 \times 1)$，即 $O(13824)$，在数字比较少的情况下还是很快的。但是随着数字数量的增加，时间复杂度会呈指数级增长，不适用于大规模数据的处理。