在看刘汝佳的入门白书,其中提到了高精度加法,上网参考了别人的做法后,写了高精度减法,高精度乘法,但除法仍没有解决。
本例高精度范围一千位的十进制大数加减乘。
基本结构:用大数组保留大数各个位上的数
关键点:
加法:保留本位和进位,处理方法本位保留之前进位的数后,若第一个数的对应位还有数(即没有超过最高位),加对应位的数,第二个数同理;
bign是自定义结构体,最后面会给出完整结构
bign fun(bign temp) { bign sum; sum.len = 0; for ( int i = 0, high = 0; high || i < max(len, temp.len); i++) { int standard = high; if (i < len) standard += s[i]; if (i < temp.len) standard += temp.s[i]; sum.s[sum.len++] = standard % 10; high = standard / 10; } return sum; }
减法:主要是借位的问题比较麻烦,用循环找到借位点,再向后加10,但开始始终想保证位上为正。后来发现没有利用数据可以为负的特性,我们可以用对象位相减,若结果为负,对应位-1,后面一位加10,思路并不难。
bign ( bign temp) { bign result; bign high; bign low; if(this->operator>(temp)) { high = *this; low = temp; } else { high = temp; low = *this; } result.len = high.len; for ( int i = 0; i < high.len; i++) { result.s[i] += high.s[i] - low.s[i]; if (result.s[i] < 0) { result.s[i] += 10; result.s[i+1]--; } } result.clean(); return result; }
乘法:模拟手工原理列竖式,对应位要移位(不是都从个位开始的),此时对应位存的不是一位数,再按照加法的思想,除10,和10取余。这里有一点需要注意,加减法的结果位数最大限度已知,而乘法位数不定,所以输出前要把前导0除去(预先用了很大的空间,全部置0了,所以结果前有很多0)
bign ( bign temp) { bign result; result.len = len + temp.len; for ( int i = 0; i < len; i++) for ( int j = 0; j < temp.len; j++) result.s[i+j] += s[i] * temp.s[j]; for ( int i = 0; i < result.len-1; i++) { result.s[i+1] += result.s[i] / 10; result.s[i] = result.s[i] % 10; } result.clean(); return result; }
为了方便,把它写成一个模板,其中加入了重载运算符,作用可以使大数的结构像普通数据结构一样,进行
<< >> += -= *= < > <= >= !=的操作
下面完整代码及测试
#include <iostream> #include <stdio.h> #include <string.h> #define MAX 1000 using namespace std; struct bign { int len, s[MAX]; bign() { memset(s, 0, sizeof(s)); len = 1; }; void clean() { while (len > 1 && !s[len-1]) len--; } bign operator = (const char *num) { len = strlen(num); for ( int i = 0; i < len; i++) s[i] = num[len-i-1] - '0'; return *this; } bign operator = (int num) { char s[MAX]; sprintf(s, "%d", num); *this = s; return *this; } string str() const { string res = ""; for ( int i = 0; i < len; i++) res = (char)(s[i] + '0') + res; if (res == "") res = "0"; return res; } bool end() { char s[100]; strcpy(s, str().c_str()); if (s[0] == '0') return true; else return false; } //加法 bign operator + (const bign &temp) const { bign sum; sum.len = 0; for ( int i = 0, high = 0; high || i < max(len, temp.len); i++) { int standard = high; if (i < len) standard += s[i]; if (i < temp.len) standard += temp.s[i]; sum.s[sum.len++] = standard % 10; high = standard / 10; } return sum; } //乘法 bign operator * (const bign &temp) { bign result; result.len = len + temp.len; for ( int i = 0; i < len; i++) for ( int j = 0; j < temp.len; j++) result.s[i+j] += s[i] * temp.s[j]; for ( int i = 0; i < result.len-1; i++) { result.s[i+1] += result.s[i] / 10; result.s[i] = result.s[i] % 10; } result.clean(); return result; } //减法 bign operator - (const bign &temp) { bign result; bign high; bign low; if(this->operator>(temp)) { high = *this; low = temp; } else { high = temp; low = *this; } result.len = high.len; for ( int i = 0; i < high.len; i++) { result.s[i] += high.s[i] - low.s[i]; if (result.s[i] < 0) { result.s[i] += 10; result.s[i+1]--; } } result.clean(); return result; } //除法 /* bign operator / (const bign &temp) { bign result; if (this->operator<(temp)) { result.operator=(0); return result; } else (this) } */ bign operator -= (const bign &temp) { *this = *this + temp; return *this; } bign operator += (const bign &temp) { *this = *this + temp; return *this; } bign operator *= (const bign &temp) { *this = *this * temp; return *this; } bool operator < (const bign &temp) const { if (len != temp.len) return len < temp.len; for ( int i = len-1; i >= 0; i--) if (s[i] != temp.s[i]) return s[i] < temp.s[i]; return false; } bool operator > (const bign &temp) const { return temp < *this; } bool operator <= (const bign &temp) const { return !(temp < *this); } bool operator >= (const bign &temp) const { return !(*this < temp); } bool operator != (const bign &temp) const { return temp < *this || temp > *this; } bool operator == (const bign &temp) const { return !(temp < *this) && !(*this < temp); } }; istream& operator >> (istream &in, bign &temp) { string s; in >> s; temp = s.c_str(); return in; } ostream& operator << (ostream &out, const bign &temp) { out << temp.str(); return out; } int main(int argc, char *argv[]) { bign x,y; while (cin >> x >> y) { cout << "x*y = " << y*x << endl; cout << "x+y = " << x+y << endl; cout << "x-y = "<< x-y << endl; } return 0; }
第一次写高精度,此代码没有优化,比如四位分段可以节省int数组的浪费等等,还有除法的问题,留到下一篇再写