杂七杂八算法

一些杂七杂八的小算法，长期不用挺容易忘的，顺手记录一下。

本文主要记录四种算法：

• 最小公倍数

• 最大公约数

• 开平方根

• 进制转换

最小公倍数

定理: 两个数的乘积等于这两个数的最大公约数与最小公倍数的乘积。

因此，找最小公倍数只需要找出最大公约数就可以了。

最大公约数算法

求最大公约数的方法为辗转相除法。算法描述如下:

设两数为a、b(a≥b)，求a和b最大公约数(a, b)的步骤如下：
(1)用 a 除以 b(a≥b)，得 a / b = q 余 r1.
(2)若 r1为0，则最大公约数为 b;
(3)若 r1不为0，则再用b除以 r1，得 b / r1 = q 余 r2.
(4)若 r2为0，则最大公约数为 r1；
(5)若 r2不为0，则继续用 r1 除以 r2，......，如此下去，直到能整除为止。
其最后一个余数为0的除数即为(a, b)的最大公约数。

C++ 实现算法如下:

int greatestCommonDivisor(int a, int b){
    if (a < b) swap(a, b);
    int tail = a % b;
    while (tail != 0){
        a = b;
        b = tail;
        tail = a % b;
    }
    return b;
}

开平方根

主要采用牛顿迭代法：

求出数字 a 的平方根近似值：首先随便猜一个近似值 x，然后令 x 等于 x 和 a/x 的平均数，不断迭代精度就会不断接近。

C++ 实现的算法如下：

//precision为精度, 如 0.00001
double nd_sqrt(int num, double precision){
    double x = double(num) / 2;
    x = (x + double(num) / x) / 2;
    double lastX = x;
    while (true){
        x = (x + double(num) / x) / 2;
        if (abs(lastX - x) < precision)
            break;
        lastX = x;
    }
    return lastX;
}

进制转换

进制转换很简单，就是 除数取余法.看一下实现，一目了然。

C++ 实现如下：

// num 为数字, bit 为转换为几进制
vector<int> bitConvert(int num, int bit){
    if(num <= 1)
        return vector<int> (1, num);
    vector<int> result;
    while(num > 0){
        int tail = num % bit;
        result.push_back(tail);
        num = num / bit;
    }
    reverse(result.begin(), result.end());
    return result;
}