数据结构算法(0)--大数运算
总结并记录学习数据结构过程中遇到的问题及算法.
一些常见算法：
Note:
- 大数四则运算.
加法
#include#include #include using namespace std;#define MAXSIZE 1000int num1[MAXSIZE], num2[MAXSIZE];void sum(char a[], char b[]){ int len1 = strlen(a); int len2 = strlen(b); int i, j; int lensum = len1 > len2 ? len1 : len2; //总计算长度 lensum++; for (i = len1 - 1, j = 0; i >= 0; --i) //逆序存储 { num1[j++] = a[i] - '0'; } for (i = len2 - 1, j = 0; i >= 0; --i) { num2[j++] = b[i] - '0'; } for (i = 0; i < lensum; ++i) { int temp = num1[i] + num2[i]; num1[i] = temp % 10; num1[i + 1] += temp / 10; } for (i = lensum - 1; i >= 0 && num1[i] == 0; --i); //去除前置0 if (i >= 0) { for (; i >= 0; --i) cout << num1[i]; } else cout << 0; cout << endl;}int main(){ char a[MAXSIZE], b[MAXSIZE]; int i, j; cin >> a >> b; sum(a, b); system("pause");}
减法
#include#include #include using namespace std;#define MAXSIZE 1000int num1[MAXSIZE], num2[MAXSIZE];bool myStrcmp(const char str1[], const char str2[]){ if (strlen(str1) > strlen(str2)) return true; if (strlen(str1) == strlen(str2)) return strcmp(str1, str2) >= 0; return false; }void sum(char a[], char b[]){ int len1 = strlen(a); int len2 = strlen(b); int i, j; int lensum = len1 > len2 ? len1 : len2; //总计算长度 lensum++; for (i = len1 - 1, j = 0; i >= 0; --i) //逆序存储 { num1[j++] = a[i] - '0'; } for (i = len2 - 1, j = 0; i >= 0; --i) { num2[j++] = b[i] - '0'; } for (i = 0; i < lensum; ++i) { num1[i] -= num2[i]; if (num1[i] < 0) { num1[i] += 10; num1[i + 1]--; } } for (i = lensum - 1; i >= 0 && num1[i] == 0; --i); //去除前置0 if (i >= 0) { for (; i >= 0; --i) cout << num1[i]; } else cout << 0; cout << endl;}int main(){ char a[MAXSIZE], b[MAXSIZE]; int i, j; cin >> a >> b; bool sign = myStrcmp(a, b); if (sign) { sum(a, b); } else { cout << '-'; sum(b, a); } system("pause");}
乘法
#include#include #include using namespace std;#define MAXSIZE 1000int num1[MAXSIZE], num2[MAXSIZE], num3[MAXSIZE*3];void sum(char a[], char b[]){ int len1 = strlen(a); int len2 = strlen(b); int i, j; int lensum = len1 + len2 +1; //总计算长度 for (i = len1 - 1, j = 0; i >= 0; --i) //逆序存储 { num1[j++] = a[i] - '0'; } for (i = len2 - 1, j = 0; i >= 0; --i) { num2[j++] = b[i] - '0'; } for (i = 0; i < len1; ++i) //计算 { for (j = 0; j < len2; ++j) { num3[i + j] += num1[i] * num2[j]; } } for (i = 0; i < lensum; ++i) //处理进位 { if (num3[i] >= 10) { num3[i + 1] += num3[i] / 10; num3[i] %= 10; } } for (i = lensum - 1; i >= 0 && num3[i] == 0; --i); //去除前置0 if (i >= 0) { for (; i >= 0; --i) cout << num3[i]; } else cout << 0; cout << endl;}int main(){ char a[MAXSIZE], b[MAXSIZE]; int i, j; cin >> a >> b; sum(a, b); system("pause");}
除法
#include#include #include using namespace std;#define MAXSIZE 5000char a[MAXSIZE], b[MAXSIZE];int result[MAXSIZE];void sub(char a[], char b[]) //正序相减{ int i=0, j; int len2 = strlen(b); while (true) { if (a[i] == 0) ++i; else { j = i; break; } } for (; i < len2; ++i) { a[i] = a[i] - b[i] + '0'; } for (i = len2 - 1; i > j; --i) { if (a[i] < '0') { a[i] += 10; a[i - 1]--; } }}int main(){ int i = 0, j, pos; cin >> a >> b; int len1 = strlen(a); int len2 = strlen(b); if (len1 < len2 || (len1 == len2 && strcmp(a, b) < 0)) { cout << i << " "; for (i = 0; i < len1; ++i) cout << a[i]; cout << endl; } else { pos = 0; //商的位数 while (true) { result[pos] = 0; while (strcmp(a, b) >= 0) //循环进行减法运算 { sub(a,b); result[pos]++; } ++pos; if (len1 == len2) break; for (i = len2 - 1; i >= 0; --i) b[i + 1] = b[i]; b[0] = '0'; //在除数前面补0，进行减法运算 ++len2; b[len2] = '\0'; } i = 0; while (result[i] == 0) //去除商的前面0 ++i; for (; i < pos; ++i) cout << result[i]; j = 0; //余数 while (a[j] == '0') ++j; if (j == len1) cout << " " << 0 << endl; else { cout << " "; for (; j < len1; ++j) cout << a[j] - '0'; cout << endl; } } system("pause");}