1 #include<iostream>
2 #include<
string>
3
4 using namespace std;
5
6 const unsigned
int MAX =
10000;
//整型数组的最大长度
7 const long long WIDTHMAX =
1000000000;
//整型数组val[MAX]的元素上限
8 const unsigned
int WIDTH =
9;
//输出整型数组val[MAX]的元素时的格式宽度，即整型数组val[MAX]的元素的最多位数
9
10 typedef
struct node
11 {
12 long long val[MAX];
//用来存储高精度整数
13 unsigned
int size;
//整型数组的实际长度
14 } BigInt;
15
16 BigInt StrToBigInt(
string s);
17 void PrintBigInt(
const BigInt &
a);
18 int ComPareBigInt(
const BigInt & a,
const BigInt &
b);
19 BigInt MulBigInt(
const BigInt & a,
const BigInt &
b);
20 BigInt AddBigInt(
const BigInt & a,
const BigInt &
b);
21 BigInt SubBigInt(BigInt a, BigInt b);
22 BigInt DivBigInt(
const BigInt & a,
const BigInt &
b);
23 BigInt FacBigInt(unsigned
int n);
24 void PowBigInt(BigInt & c,
const BigInt & a, unsigned
int n);
25 void PowBigInt_2(BigInt & c,
const BigInt & a, unsigned
int n);
26 BigInt HalfBigInt(BigInt a);
27
28 int main()
29 {
30 string s;
31 BigInt a, b, c;
32
33 cin >>
s;
34 a =
StrToBigInt(s);
35 cin >>
s;
36 b =
StrToBigInt(s);
37
38 cout <<
" ";
39 PrintBigInt(a);
40 cout <<
"+ ";
41 PrintBigInt(b);
42 c =
AddBigInt(a, b);
43 cout <<
"= ";
44 PrintBigInt(c);
45 cout <<
endl;
46
47 cout <<
" ";
48 PrintBigInt(a);
49 cout <<
"- ";
50 PrintBigInt(b);
51 c =
SubBigInt(a, b);
52 cout <<
"= ";
53 PrintBigInt(c);
54 cout <<
endl;
55
56 cout <<
" ";
57 PrintBigInt(a);
58 cout <<
"* ";
59 PrintBigInt(b);
60 c =
MulBigInt(a, b);
61 cout <<
"= ";
62 PrintBigInt(c);
63 cout <<
endl;
64
65 cout <<
" ";
66 PrintBigInt(a);
67 cout <<
"/ 2 " <<
endl;
68 c =
HalfBigInt(a);
69 cout <<
"= ";
70 PrintBigInt(c);
71 cout <<
endl;
72
73 cout <<
" ";
74 PrintBigInt(a);
75 cout <<
"/ ";
76 PrintBigInt(b);
77 c =
DivBigInt(a, b);
78 cout <<
"= ";
79 PrintBigInt(c);
80 cout <<
endl;
81
82 unsigned
int n;
83 cin >>
n;
84 //cout << n << "! = ";
85 // c = FacBigInt(n);
86 // PrintBigInt(c);
87 // cout << c.size << endl;
88 cout <<
endl;
89
90 cout <<
" ";
91 PrintBigInt(a);
92 cout <<
"^" << n <<
" = ";
93 PowBigInt(c, a, n);
94 PrintBigInt(c);
95 cout <<
endl;
96
97 cout <<
" ";
98 PrintBigInt(a);
99 cout <<
"^" << n <<
" = ";
100 PowBigInt_2(c, a, n);
101 PrintBigInt(c);
102 cout <<
endl;
103
104 system(
"pause");
105 return 0;
106 }
107 /*
108 函数名称：PrintBigInt
109 函数功能：输出用整型数组表示的高精度整数
110 输入参数：const BigInt & a：用整型数组表示的高精度整数
111 输出参数：无
112 */
113 void PrintBigInt(
const BigInt &
a)
114 {
115 cout << a.val[a.size-
1];
116 for (
int i=a.size-
2; i>=
0; i--
)
117 {
118 unsigned w = WIDTHMAX /
10;
119 while (w >
0)
120 {
121 if (a.val[i] >=
w)
122 break;
123 cout <<
0;
124 w /=
10;
125 }
126 cout <<
a.val[i];
127 }
128 cout <<
endl;
129 }
130 /*
131 函数名称：StrToBigInt
132 函数功能：把元素为数字的字符串转换为用整型数组表示的高精度整数
133 输入参数：string s：存储数字的字符串
134 输出参数：BigInt：返回用整型数组表示的高精度整数
135 */
136 BigInt StrToBigInt(
string s)
137 {
138 BigInt a;
139 a.size =
0;
140 int i =
s.size();
141 unsigned
long long sum =
0;
142 while ( i>=
WIDTH)
143 {
144 for (
int j=i-WIDTH; j<i; j++
)
145 sum = sum *
10 + (s[j] -
'0');
146 a.val[a.size++] =
sum;
147 sum =
0;
148 i -=
WIDTH;
149 }
150 if (i >
0)
151 {
152 for (
int j=
0; j<i; j++
)
153 sum = sum *
10 + (s[j] -
'0');
154 a.val[a.size++] =
sum;
155 }
156 return a;
157 }
158 /*
159 函数名称：AddBigInt
160 函数功能：高精度整数加法
161 输入参数：const BigInt & a：用整型数组表示的高精度整数加数
162 const BigInt & b：用整型数组表示的高精度整数加数
163 输出参数：BigInt：返回用整型数组表示的高精度整数和
164 */
165 BigInt AddBigInt(
const BigInt & a,
const BigInt &
b)
166 {
167 //逆序计算a+b，则从低位开始计算
168 BigInt c;
169 unsigned
long long carry =
0;
170 unsigned
int i =
0;
171 c.size =
0;
172 while (i < a.size && i <
b.size)
173 {
174 c.val[c.size++] = (a.val[i] + b.val[i] + carry) %
WIDTHMAX;
175 carry = (a.val[i] + b.val[i] + carry) /
WIDTHMAX;
176 i++
;
177 }
178 while (i <
a.size)
179 {
180 c.val[c.size++] = (a.val[i] + carry) %
WIDTHMAX;
181 carry = (a.val[i] + carry) /
WIDTHMAX;
182 i++
;
183 }
184 while (i <
b.size)
185 {
186 c.val[c.size++] = (b.val[i] + carry) %
WIDTHMAX;
187 carry = (b.val[i] + carry) /
WIDTHMAX;
188 i++
;
189 }
190 if (carry >
0)
191 c.val[c.size++] =
carry;
192 return c;
193 }
194 /*
195 函数名称：SubBigInt
196 函数功能：高精度整数减法
197 输入参数：BigInt a：用整型数组表示的高精度整数被减数
198 BigInt b：用整型数组表示的高精度整数减数
199 输出参数：BigInt：返回用整型数组表示的高精度整数差
200 */
201 BigInt SubBigInt(BigInt a, BigInt b)
202 {
203 BigInt c;
204 c.size =
0;
205 if (ComPareBigInt(a, b) ==
0)
206 {
207 c.size =
1;
208 c.val[
0] =
0;
209 return c;
210 }
211 bool flag =
false;
212 if (ComPareBigInt(a, b) <
0)
//交换，并得到一个负号
213 {
214 flag =
true;
215 BigInt temp =
a;
216 a =
b;
217 b =
temp;
218 }
219 unsigned
int i =
0;
220 while (i <
b.size)
221 {
222 if (a.val[i] >=
b.val[i])
223 c.val[c.size++] = a.val[i] -
b.val[i];
224 else
225 {
226 a.val[i+
1] -=
1;
227 c.val[c.size++] = a.val[i] + WIDTHMAX -
b.val[i];
228 }
229 i++
;
230 }
231 while (i <
a.size)
232 {
233 if (a.val[i] <
0)
234 {
235 a.val[i+
1] -=
1;
236 a.val[i] +=
WIDTHMAX;
237 }
238 c.val[c.size++] =
a.val[i];
239 i++
;
240 }
241 //消除多余的高位0
242 while (c.val[c.size-
1] ==
0)
243 c.size--
;
244
245 if (flag)
//如果是负数，加上负号
246 c.val[c.size-
1] = -c.val[c.size-
1];
247 return c;
248 }
249 /*
250 函数名称：ComPareBigInt
251 函数功能：比较两个高精度整数的大小
252 输入参数：BigInt a：用整型数组表示的高精度整数被减数
253 BigInt b：用整型数组表示的高精度整数减数
254 输出参数：int：a > b返回1，a = b返回0，a < b返回-1
255 */
256 int ComPareBigInt(
const BigInt & a,
const BigInt &
b)
257 {
258 if (a.size >
b.size)
259 return 1;
260 if (a.size <
b.size)
261 return -
1;
262
263 for (
int i=a.size-
1; i>=
0; i--
)
264 {
265 if (a.val[i] >
b.val[i])
266 return 1;
267 if (a.val[i] <
b.val[i])
268 return -
1;
269 }
270 return 0;
271 }
272 /*
273 函数名称：MulBigInt
274 函数功能：高精度整数乘法
275 输入参数：const BigInt & a：用整型数组表示的高精度整数被乘数
276 const BigInt & b：用整型数组表示的高精度整数乘数
277 输出参数：BigInt：返回用整型数组表示的高精度整数乘积
278 */
279 BigInt MulBigInt(
const BigInt & a,
const BigInt &
b)
280 {
281 if (a.size ==
1 && a.val[
0] ==
0)
282 return a;
283 if (b.size ==
1 && b.val[
0] ==
0)
284 return b;
285
286 BigInt c;
287 for (
int i=
0; i<MAX; i++)
//全部赋初值为0
288 c.val[i] =
0;
289 for (
int i=
0, j=
0; i<b.size; i++
)
290 {
291 for (j=
0; j<a.size; j++
)
292 {
293 c.val[i+j] += a.val[j] *
b.val[i];
294 c.val[i+j+
1] += c.val[i+j] /
WIDTHMAX;
295 c.val[i+j] %=
WIDTHMAX;
296 }
297 c.size = i +
j;
298 if (c.val[c.size] !=
0)
//最高位有进位
299 c.size++
;
300 }
301 return c;
302 }
303 /*
304 老版本：
305 BigInt MulBigInt2(const BigInt & a, const BigInt & b)
306 {
307 if (a.size == 1 && a.val[0] == 0)
308 return a;
309 if (b.size == 1 && b.val[0] == 0)
310 return b;
311
312 BigInt c, tc;
313 unsigned long long carry = 0;
314 c.size = 0;
315 for (int i=0, j=0; i<b.size; i++)
316 {
317 for (j=0; j<i; j++)//先在临时和tc的低位补足0
318 tc.val[j] = 0;
319 carry = 0;
320 for (j=0; j<a.size; j++)
321 {
322 tc.val[i+j] = (a.val[j] * b.val[i] + carry) % WIDTHMAX;
323 carry = (a.val[j] * b.val[i] + carry) / WIDTHMAX;
324 }
325 tc.size = i + j;
326 if (carry > 0)
327 tc.val[tc.size++] = carry;
328 //累加到c中
329 c = AddBigInt(tc, c);
330 }
331 return c;
332 }
333 */
334
335 /*
336 函数名称：FacBigInt
337 函数功能：高精度整数阶乘
338 输入参数：unsigned int n：正整数
339 输出参数：BigInt：返回用整型数组表示的高精度整数阶乘
340 */
341 BigInt FacBigInt(unsigned
int n)
342 {
343 BigInt s, c;
344 c.size = s.size =
1;
345 s.val[
0] =
1;
346 for (unsigned
long long i=
2; i<=n; i++
)
347 {
348 c.val[
0] =
i;
349 s =
MulBigInt(s, c);
350 }
351 return s;
352 }
353
354 /*
355 函数名称：PowBigInt
356 函数功能：递归高效算法求高精度整数幂
357 输入参数：BigInt & c：存储高精度整数幂的整型数组
358 const BigInt & a：用整型数组表示的高精度整数底数
359 long long n： 指数
360 */
361 void PowBigInt(BigInt & c,
const BigInt & a, unsigned
int n)
362 {
363 if (n ==
1)
364 {
365 c =
a;
366 return ;
367 }
368 if (n ==
0 || (a.size ==
1 && a.val[
0] ==
1))
369 {
370 c.size = c.val[
0] =
1;
371 return ;
372 }
373
374 PowBigInt(c, a, n/
2);
//递归求高精度整数幂
375
376 c = MulBigInt(c, c);
//a^n = a^(n/2)*a^(n/2)*f(a)
377 if (n %
2 ==
1)
//其中f(a) = 1(n%2==0)或f(a) = a(n%2==1)
378 c =
MulBigInt(a, c);
379 }
380
381 /*
382 函数名称：PowBigInt_2
383 函数功能：非递归高效算法求高精度整数幂
384 输入参数：BigInt & c：存储高精度整数幂的整型数组
385 const BigInt & a：用整型数组表示的高精度整数底数
386 long long n： 指数
387 */
388 void PowBigInt_2(BigInt & c,
const BigInt & a, unsigned
int n)
389 {
390 int stack[MAX] = {
0};
391 int top =
0;
392 while (n >
0)
//利用一个栈来存储n的状态：奇数还是偶数
393 {
394 stack[top++] = n %
2;
395 n /=
2;
396 }
397 c.size = c.val[
0] =
1;
398 for (
int i=top-
1; i>=
0; i--
)
399 {
400 c = MulBigInt(c, c);
//a^n = a^(n/2)*a^(n/2)*f(a)
401 if (stack[i] ==
1)
//其中f(a) = 1(n%2==0)或f(a) = a(n%2==1)
402 c =
MulBigInt(a, c);
403 }
404 }
405
406 /*
407 函数名称：DivBigInt
408 函数功能：二分法实现高精度整数除法
409 输入参数：const BigInt & a：用整型数组表示的高精度整数被除数
410 const BigInt & b：用整型数组表示的高精度整数除数
411 输出参数：BigInt：返回用整型数组表示的高精度整数商
412 */
413 BigInt DivBigInt(
const BigInt & a,
const BigInt &
b)
414 {
415 BigInt high, low, mid, one, c;
416 if ((a.size ==
1 && a.val[
0] ==
0) || (b.size ==
1 && b.val[
0] ==
0))
417 {
418 c.size =
1;
419 c.val[
0] =
0;
420 return c;
421 }
422
423 one.size =
1;
//值为1的高精度整数
424 one.val[
0] =
1;
425 high = a;
//上界
426 low.size =
1;
//下界
427 low.val[
0] =
0;
428 while (ComPareBigInt(low, high) <
0)
429 {
430 mid = HalfBigInt(AddBigInt(high, low));
//中间数
431 c =
MulBigInt(mid, b);
432 if (ComPareBigInt(c, a) ==
0)
433 return mid;
434 else if (ComPareBigInt(c, a) <
0)
435 low =
AddBigInt(mid, one);
436 else
437 high =
SubBigInt(mid, one);
438 }
439 c =
MulBigInt(low, b);
440 if (ComPareBigInt(c, a) <=
0)
441 return low;
442 else
443 return SubBigInt(low, one);
444 }
445
446 /*
447 函数名称：HalfBigInt
448 函数功能：高精度整数求半
449 输入参数：BigInt a：用整型数组表示的高精度整数
450 输出参数：BigInt：返回用整型数组表示的高精度整数的一半
451 */
452 BigInt HalfBigInt(BigInt a)
453 {
454 BigInt c;
455 c.size =
a.size;
456 for (
int i=a.size-
1; i>
0; i--
)
457 {
458 c.val[i] = a.val[i] /
2;
459 if (a.val[i] %
2 ==
1)
460 a.val[i-
1] +=
WIDTHMAX;
461 }
462 c.val[
0] = a.val[
0] /
2;
463 if (c.size >
0 && c.val[c.size-
1] ==
0)
464 c.size--
;
465
466 return c;
467 }
View Code
转载于:https://www.cnblogs.com/Skyxj/p/3185064.html
相关资源：信息化高效课堂点滴谈.doc
