编程常用算法 --- C/C++ 语言实现（不定期更新）

矫情吗；* 2022-06-03 05:44 259阅读 0赞

# 引言 #

实际编程中，很多编程语言都帮我们实现了一些常用的较简单的算法，当然，在一些需求中，我们也需要自己实现一些算法，这里总结一些常用的算法，采用 C/C++ 语言实现，不定期更新。

**这里的代码假设输入数据都是符合要求的，没有对输入的数据的合理性进行检测，这里要注意一下。**

### 1、判断回文数/回文字符串 ###

回文串即为正着读和倒着读都一样的字符串。这算是一个比较简单的问题了，数字和字符串是一样的，把数字也当成字符串输入就好了，当然也可以采用数字转字符串算法，之后会介绍。下面是代码：

/**
     * Judge whether string is a palindrome string
     * Environment: Dev-C++ 5.11
     * Author: 指点 
     */
    #include <iostream>
    #include <cstring>
    #define MAXN 10010
    using namespace std;
    
    
    bool judgePalindrome(char *str, int len) {
        // 判断第 i 个字符是否和倒数第 i 个字符相等 
        for (int i = 0; i < len/2; i++) {
            if (str[i] != str[len-1-i]) {
                return false;
            }
        }
        return true;
    }
    
    int main() {
        char str[MAXN];
        // 采用这种输入方式可以录入空格
        while (cin.getline(str, MAXN)) {
            cout << (judgePalindrome(str, strlen(str)) ? "true" : "false") << endl; 
        }
    
        return 0;
    }

![这里写图片描述][SouthEast]

### 2、十进制数字转换为字符串 ###

对于这个问题，其实标准库里面就有实现，C++ 中 cstdlib （C语言里面对应的是 stdlib.h ）头文件中的 itoa函数就是其中一个例子，当然 cstdio （C语言里面对应的是 stdio.h）头文件中的 sprintf 函数也算是一种比较灵活的实现，读者可以查一下其相关用法。那么如果要我们自己实现呢？  
处理这个问题步骤多了点，但是逻辑并不复杂：如果是正常的数字，那么就分为正数和负数，注意一下负数的处理，再注意一下小数部分和整数部分分开处理就好了：

/**
     * translate demical number to string 
     * Environment: Dev-C++ 5.11
     * Author: 指点 
     */
    #include <iostream>
    #include <cstring>
    #define MAXN 100
    using namespace std;
    
    /**
     * 递归分解整数，使得字符串中储存的数字顺序和整数各位数字顺序一样 
     * 请注意这里参数 currentIndex 必须传引用(或者也可以用指针)
     */ 
    void sloveInteger(char *result, int& currentIndex, int integer) {
        if (!integer) {
            return ;
        }
        sloveInteger(result, currentIndex, integer/10);
        result[currentIndex++] = integer%10 + '0';
    }
    
    // 分解小数 
    void sloveDemical(char *result, int& currentIndex, double demical) {
        // 如果存在小数，那么储存一个小数点 
        if (demical) {
            result[currentIndex++] = '.';
        }
        // 不断把最接近小数点的那位小数变成整数(乘 10)并且储存，直到小数部分为 0 
        while (demical) {
            demical *= 10;
            result[currentIndex++] = (int)demical + '0';
            // 除去当前数字的整数部分 
            demical -= (int)demical;
        }
    } 
    
    char *transNumberToString(double number) {
        char *result = new char[MAXN];
        memset(result, 0, sizeof(char)*MAXN);
        int currentIndex = 0;
    
        // 如果数字为负数，那么先储存负号，然后转为正数处理 
        if (number < 0) {
            result[currentIndex++] = '-';
            number = -number;
        }
        // 处理整数部分
        sloveInteger(result, currentIndex, (int) number);
        // 处理小数部分 
        sloveDemical(result, currentIndex, number-(int) number);
    
        return result;
    }
    
    int main() {
        double number;
        while (cin >> number) {
            cout << transNumberToString(number) << endl;
        }
    
        return 0;
    }

![这里写图片描述][SouthEast 1]

对照结果，不对啊，浮点数的结果对不上？？其实这是计算机小数部分的储存特点造成的，因为计算机内部以二进制保存数据，在对十进制小数的转换成二进制小数的过程中，对于某些十进制的小数并不能完全精确的表示，只能精确到小数点后多少位。那是不是所有的小数都不能精确的表示？其实也不尽然，读者可以试试数字： 12.5。关于这个，这里不过多介绍，可以参考一下这篇文章：[浮点数为什么不精确？][Link 1]。

### 3、字符串转换为十进制数 ###

和第二点类似，标准库中依然有实现方法，atoi/atof 函数（cstdlib/stdlib.h 头文件）和 sscanf (cstdio/stdio.h 头文件) 函数。如果要我们自己处理也挺简单，就是将字符串中的每个字符表示对应的 int / double 值求出来，然后按位乘以 10 / 除以 10 (小数)的对应权值再把每一位处理的结果相加就好了。这里假设输入数据都是合理的，没有检测输入数据是否合法。

/**
     * Convert a string to a decimal number
     * Environment: Dev-C++ 5.11
     * Author: 指点 
     */
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #define MAXN 10010
    using namespace std;
    
    // 将字符串小数转换为 10 进制小数 
    double getDecimalByString(char *decimal, int currentIndex) {
        // 如果遇到字符串结束符，那么结束递归 
        if (!decimal[currentIndex]) {
            return 0;
        }
        return (decimal[currentIndex]-'0')/10.0 + 
               getDecimalByString(decimal, currentIndex+1)/10.0;
    }
    
    // 将字符串转换为 10 进制数 
    double getNumberByString(char *str) {
        int length = strlen(str);
        int result = 0;
        int i = 0;
        // 检测负数 
        if (str[0] == '-') {
            i = 1;
        }
        // 计算整数部分并且记录小数点位置 
        for (; i < length && str[i] != '.'; i++) {
            result *= 10;
            result += str[i] - '0';
        }
        // 如果整数部分长度等于整个字符串长度，证明没有小数 
        if (i == length) {
            return str[0]=='-' ? (-result) : (result);
        // 否则证明有小数 
        } else {
            return str[0]=='-' ? (-result-getDecimalByString(str+i+1, 0)) :
                               (result+getDecimalByString(str+i+1, 0));
        }
    }
    
    int main() {
        char str[MAXN];
        while(~scanf("%s", str)) {
            printf("对应的十进制数：%lf\n", getNumberByString(str));
        }
    
        return 0;
    }

![这里写图片描述][SouthEast 2]

### 4、m 进制数转换为 n 进制数（正数） ###

关于进制转换，这其实是一个很常见的问题了。记得大一的时候最初接触的是 2 进制数字和 10进制数字的相互转换，当时的思路是：2转10： 整数部分按位相乘再各位相加，小数部分按位相除再各位相加。10转2：整数除2取余，小数乘2取整。  
那么对于 m 转 n 也是差不多，可以先把 m 进制的数转换为 10 进制，然后再把这个 10 进制数转换为 n 进制。

/**
     * Converting the number of m to the number of n
     * Environment: Dev-C++ 5.11
     * Author: 指点 
     */
    #include <iostream>
    #include <cstring>
    #include <cmath>
    #define MAXN 10010
    using namespace std;
    const int MAX_STEP = 10;
    
    // 把 m 进制的数的整数部分转换为 10 进制 
    int covertIntegerToTen(char *integerStr, int m) {
        int length = strlen(integerStr);
        int res = 0;
        int currentInt;
        for (int i = 0; i < length; i++) {
            currentInt = integerStr[i]>'9' ? (integerStr[i]-'A'+10) : 
                       (integerStr[i]-'0');
            res += currentInt*pow(m, length-1-i);
        }
    
        return res;
    } 
    
    // 将 m 进制的数的小数部分转换为 10 进制 
    double covertDemicalToTen(char *mDemicalStr, int m) {
        double result = 0;
        int length = strlen(mDemicalStr);
        int currentNum;
        for (int i = 0; i < length; i++) {
            currentNum = mDemicalStr[i]>'9' ? 
                       (mDemicalStr[i]-'A'+10) : 
                       (mDemicalStr[i]-'0');
            // 取出整数并进行运算 
            result += currentNum / pow(m, i+1);
        }
        return result;
    }
    
    /**
     * 递归将 10 进制数的整数部分转换为 n 进制数（除 n 取余，结果逆序读） 
     * 并将结果储存在 result 字符串中
     */ 
    void covertIntegerToN(int integer, int n, int& currentIndex, char *result) {
        if (!integer) {
            return ;
        }
        covertIntegerToN(integer/n, n, currentIndex, result); 
        int currentInt = integer%n;
        result[currentIndex++] = currentInt>9 ? (currentInt-10+'A') : (currentInt+'0');
    } 
    
    // 将 10 进制数的小数部分转换为 n 进制的小数（乘 n 取整）,结果储存在 result 字符串中 
    void covertDemicalToN(double demical, int n, char *result) {
        int currentInt;
        int i = 0;
        // 如果有小数部分，那么储存小数点 
        if (demical) {
            result[i++] = '.';
        }
        for (; demical; i++) {
            demical *= n;
            // 如果有整数，那么取出保存 
            if (demical >= 1) {
                currentInt = (int) demical;
                result[i] = currentInt > 9 ? (currentInt-10+'A') : (currentInt+'0');
                // 除去当前数的整数部分 
                demical -= (int) demical;
            // 没有整数则存 0  
            } else {
                result[i] = '0';
            }
        }
    }
    
    int main() {
        int m, n;
        char str[MAXN];
        char integerResult[2*MAXN];
        char demicalResult[MAXN];
    
        while (1) {
            memset(str, 0, sizeof(char)*MAXN);
            memset(integerResult, 0, sizeof(char)*2*MAXN);
            memset(demicalResult, 0, sizeof(char)*MAXN);
            cout << "输入待转换的进制和要转换的进制(m 和 n)：";
            cin >> m >> n;
            cout << "输入要转换的数(正数)：";
            cin >> str;
            if(str[0] == '-') {
                continue;
            }
            // 找出小数点的位置 
            int demicalStartIndex = -1;
            for (int i = 0; str[i]; i++) {
                if (str[i] == '.') {
                    demicalStartIndex = i;
                    break; 
                }
            }
            // 证明有小数部分 
            if (demicalStartIndex != -1) {
                str[demicalStartIndex] = 0;
                // 转换小数部分 
                covertDemicalToN(covertDemicalToTen(str+demicalStartIndex+1, m),
                                 n, demicalResult);
    
            } 
            // 转换整数数部分 
            int integerIndex = 0;
            covertIntegerToN(covertIntegerToTen(str, m), n, integerIndex, integerResult);
            cout << integerResult << demicalResult << endl; 
        }
    
        return 0;
    }

![SouthEast 3][]

有个地方要注意的是输入的数据不能超过 int 类型的最大范围（0~2^31），不然会发生错误。

### 5、求两个数的最小公倍数和最大公约数 ###

最基本的算法之一了。我们知道：两个数的最小公倍数等于两个数的乘积除以他们的最大公约数（a\*b / gcd(a,b)），那么问题就剩下怎么求出两个数的最大公约数了。记得经典的算法是使用辗转相除法。其算法描述可以写成如下形式：

如果 a == 0，则 gcd(a, b) = b;
    否则令 temp = b % a，此时 gcd(a, b) = gcd(temp, a);

来看一下代码实现：

/**
     * Calculate the GCD and LCM of two numbers 
     * Environment: Dev-C++ 5.11
     * Author: 指点 
     */
    
    #include <iostream>
    using namespace std; 
    
    // 求两个数的最大公约数 
    int gcd(int a, int b) {
        if (a == 0) {
            return b;
        }
        return gcd(b%a, a);
    }
    
    // 求两个数的最小公倍数 
    int lcm(int a, int b) {
        int lcmValue;
        // 先求出最大公约数 
        int gcdValue = gcd(a, b);
        // 确保除数不为 0  
        if (gcdValue != 0) {
            lcmValue = a*b / gcdValue;
        } else {
            exit(1); 
        }
        return lcmValue;
    }
    
    int main() {
        int a, b;
    
        while (cin >> a >> b) {
            cout << "最大公约数：";
            cout << gcd(a, b) << endl;
            cout << "最小公倍数：";
            cout << lcm(a, b) << endl;
        }
    }

看看结果：

![这里写图片描述][SouthEast 4]

### 6、判断一个数是否为素数 ###

这又是一个简单的问题，素数即为除了能被 1 和本身整除之外，不能被其他的数整除，根据这个我们也可以很快写出代码，这里给出两种代码实现，思想略有不同：

/**
     * Judge whether a number is a prime number 
     * Environment: Dev-C++ 5.11
     * Author: 指点 
     */
    #include <iostream>
    using namespace std;
    
    // 如果 n 是素数，函数返回 true，否则函数返回 false 
    bool isPrime_1(int n) {
        if (n == 1) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        for (int i = 2; i < n; i++) {
            if (n % 2 == 0) {
                return false;
            }
        }
        return true;
    }
    
    // 如果 n 是素数，函数返回 true，否则函数返回 false 
    bool isPrime_2(int n) {
        // 如果能被 2 整除，证明 n 不是素数（2 本身除外） 
        if (n != 2 && n % 2 == 0) {
            return false;
        }
        // 如果不能被 2 整除，那么 n 即为奇数，判断其是否能被奇数整除，
        // 假设 d 为 n 的约数，那么 n/d 也是 n 的约数，
        // 因为有: n = d * (n/d)，即：min(d, n/d) <= sqrt(n)，
        // 因此我们只要检测 2 ~ sqrt(n) 范围内所有的整数就可以了，
        // 前面我们已经处理了 2 和 2 的倍数，因此这个循环的范围就是 [3, sqrt(n)]
        for (int i = 3; i*i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        // 1 既不是素数也不是合数 
        return n != 1;
    }
    
    int main() {
        for (int i = 0; i < 100; i++) {
            // 这里对两个函数都进行了测试，事实上只需要使用一个判断函数就可以完成素数的测试
            if (isPrime_1(i) && isPrime_2(i)) {
                cout << i << " 是素数" << endl; 
            } else {
                cout << i << " 不是素数" << endl; 
            }
        } 
    
        return 0;
    }

来看看结果：

![这里写图片描述][SouthEast 5]

未完待续。。。

[SouthEast]: /images/20220603/16b0f5d1c77a4c88833694e1b7dad530.png
[SouthEast 1]: /images/20220603/b3baf7a9f2f542be96091a50d8e78ac6.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzAxOTc0NzExNg==&mid=2665513140&idx=1&sn=565517e977ac56904305a4a9f9d65012#rd
[SouthEast 2]: /images/20220603/b8323367ddff4349b5fe2bb5566b7fc0.png
[SouthEast 3]: /images/20220603/b28673eea7c247e681c7e474d69d39b3.png
[SouthEast 4]: /images/20220603/0c5790bf0a4441b2af1ba9c0b88cb9f1.png
[SouthEast 5]: /images/20220603/27bcf513a4274dd19df2b84c4e068966.png