一些杂七杂八的小算法,长期不用挺容易忘的,顺手记录一下。本文主要记录四种算法:最小公倍数、最大公约数,开平方根,进制转换。

最小公倍数

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

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

最大公约数算法

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

设两数为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;
}

标签: 算法

添加新评论