首页 > 其他 > 详细

【面试】大整数四则运算

时间:2018-09-21 22:12:46      阅读:224      评论:0      收藏:0      [点我收藏+]

面试手写代码,当时只写出了加减乘,还写的漏洞百出。下面是加减法:

  1 #include<iostream>
  2 using namespace std;
  3 
  4 struct BigN {
  5     int data[1000]; //设最长1000位,数组的每个数字代表一位,data[0]存最低位
  6     int len;
  7     int sign;//0为负,1为正
  8     BigN() {
  9         memset(data, 0, sizeof(data));
 10         len = 0;
 11         sign = 1;
 12     }
 13 };
 14 BigN subFun(BigN a, BigN b);
 15 void output(BigN a) {
 16     if (a.len == 0) cout << "0";
 17     for (int i = a.len-1; i >=0; i--) {
 18         if (a.sign != 1 && i == a.len - 1) cout << "-";
 19         cout << a.data[i];
 20     }
 21     cout << endl;
 22 }
 23 bool com(BigN a, BigN b) { //仅比较绝对值,a<b返回true
 24     if (a.len < b.len) return true;
 25     else if (a.len > b.len) return false;
 26     else {
 27         int tmp = a.len - 1;
 28         while (a.data[tmp]==a.data[tmp]&&tmp>0) {
 29             tmp--;
 30         }
 31         if (a.data[tmp] < a.data[tmp]) return true;
 32         else return false;
 33     }
 34 
 35 }
 36 BigN addFun(BigN a, BigN b) {//同号数相加
 37     BigN c;
 38     int carry = 0;
 39     for (int i = 0; i<a.len || i<b.len; i++) {
 40         int temp = a.data[i] + b.data[i] + carry;
 41         c.data[c.len++] = temp % 10;
 42         carry = temp / 10;
 43     }
 44     if (carry != 0) {
 45         c.data[c.len++] = carry;
 46     }
 47     c.sign = a.sign;
 48     return c;
 49 }
 50 BigN subFun(BigN a, BigN b) {//非负大数减非负小数a-b
 51     BigN c;
 52     for (int i = 0; i<a.len || i<b.len; i++) {
 53         int temp = a.data[i] - b.data[i];
 54         if (temp < 0) {
 55             temp += 10;
 56             a.data[i + 1]--;
 57         }
 58         c.data[c.len++] = temp;
 59     }
 60     while (c.data[c.len - 1] == 0 && c.len >= 1) {  //高位为0注意修正长度
 61         c.len--;
 62     }
 63     return c;
 64 }
 65 BigN add(BigN a, BigN b) {
 66     BigN c;
 67     if (a.sign != b.sign) {
 68         if (com(a, b)) {
 69             if (a.sign == 0) {
 70                 a.sign = 1;
 71                 return subFun(b,a);
 72             }
 73             else {
 74                 b.sign = 1;
 75                 c = subFun(b, a);
 76                 c.sign = 0;
 77                 return c;
 78             }
 79         }
 80         else {
 81             if (a.sign == 0) {
 82                 a.sign = 1;
 83                 c = subFun(a, b);
 84                 c.sign = 0;
 85                 return c;
 86             }
 87             else {
 88                 b.sign = 1;
 89                 c = subFun(a, b);
 90                 return c;
 91             }
 92         }
 93     }
 94     else{
 95         return addFun(a, b);
 96     }
 97     
 98 }
 99 
100 BigN sub(BigN a, BigN b) {
101     BigN c;
102     if (a.sign != b.sign) {
103         b.sign = a.sign;
104         return addFun(a, b);
105     }
106     else {
107         b.sign = (b.sign+1)%2;
108         return add(a, b);
109     }
110 
111 }
112 int main() {
113     BigN a, b;
114     for (int i = 0; i < 3; i++) {
115         a.data[i] = i + 1;
116     }
117     a.len = 3;
118 
119     for (int i = 0; i < 2; i++) {
120         b.data[i] = 7;
121     }
122     b.len = 2;
123 
124 
125     BigN aN = a;
126     aN.sign = 0;
127     BigN bN = b;
128     bN.sign = 0;
129 
130     cout << "a:";
131     output(a);
132     cout << "b:";
133     output(b);
134     cout << "-a:";
135     output(aN);
136     cout << "-b:";
137     output(bN);
138 
139     BigN c = add(a, b);
140     cout << "a+b:";
141     output(c);
142     cout << "a+ -b:";
143     c = add(a, bN);
144     output(c);
145     cout << "-a+b:";
146     c = add(aN, b);
147     output(c);
148     cout << "-a + -b:";
149     c = add(aN, bN);
150     output(c);
151 
152     cout << "a-b:";
153     c = sub(a, b);
154     output(c);
155     cout << "a- -b:";
156     c = sub(a, bN);
157     output(c);
158     cout << "-a -b:";
159     c = sub(aN, b);
160     output(c);
161     cout << "-a- -b:";
162     c = sub(aN, bN);
163     output(c);
164 }

 

【面试】大整数四则运算

原文:https://www.cnblogs.com/yuchi328/p/9688609.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!