常用编程算法实战 - 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("对应的十进制数:%lfn", 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;
}
来看看结果:
未完待续。。。