首页 > 代码库 > 常用基础算法C++实现
常用基础算法C++实现
2016年10月06日10:40:43
本文记录一些常用的基础算法，只为熟能生巧，内容多的话会建立索引的
素数（质数）判断
素数的定义：就是除它本身和1之外，没有其他任何约数的数
1 bool isPrime(int i)2 {3 for (int j = 2; j <= sqrt(i * 1.0); j++) {4 if (i % j == 0)5 return false;6 }7 return true;8 }
最大公约数
例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）=12
1 int gcd(int a, int b) // greatest common divisor 2 { 3 return （！b）?x:gdc(y,x%y); 4 } 5 6 //或者更容易理解的 7 int gcd(int a, int b) // greatest common divisor 8 { 9 while(a%b){10 int tmp = a;11 a = b;12 b = tmp%b;13 }14 return b;15 }
有了最大公约数，最小公倍数就很好求了，表示为 a*b / 最大公约数
大数相乘
大数的读入和输出都不同于正常数，读入是一字符串的方式读入的，相乘后的数存入到数组中，然后遍历数组输出数据。
下面看一下数相乘的原理
a = 34 b = 25
a和b相乘过程展示
b 2 5
a 3 4
----------------------------------------相乘过程，和我们认知中的乘法一样，只是没有进位
8(2X4) 20(4X5)
6(2X3) 15(3X5)
---------------------------------------------------------正常的乘法相加，依旧不进位
6 23 20
---------------------------------------------------------通过进位是不是就能得到我们熟悉的答案了 850
8 5 0
（6+2（进位）） （3+2（进位）） 进位的解释
通过上面的分析，我们知道了算法的核心思想，接下来就能把算法实现，实现方法如下：
1 void multiply(const char* a, const char* b){ 2 assert(a != NULL && b != NULL!); 3 int i, j ,la, lb; 4 la = strlen(a); 5 lb = strlen(b); 6 int s[la+lb] = {0}; 7 for(i = 0; i < la; i++){ //完成相乘，但是没有进位 8 for(j = 0; j < lb; j++){ 9 s[i+j] += (a[i] - ‘0‘)*(b[j]-‘0‘);10 }11 }12 for(i = 0; i < la+lb; i++){ //完成进位13 s[i+1] += s[i]/10;14 s[i] = s[i]%10;15 }16 for(i = la+lb; i >= 0; i-- ){17 if(s[i] != 0) cout << s[i];18 }19 }
常用基础算法C++实现