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

引言

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

来看看结果:

未完待续。。。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券