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

指点

发布于 2019-01-18 15:13:49

1.4K0

发布于 2019-01-18 15:13:49

文章被收录于专栏：指点的专栏

引言

实际编程中，很多编程语言都帮我们实现了一些常用的较简单的算法，当然，在一些需求中，我们也需要自己实现一些算法，这里总结一些常用的算法，采用 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;
}

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;
}

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

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;
}

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;
}

有个地方要注意的是输入的数据不能超过 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;
    }
}

看看结果：

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;
}

来看看结果：

未完待续。。。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017年12月19日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度