本文主要整理了几个常用的大整数的算法:
大整数加法
大整数乘法
大整数阶乘
大整数幂
其实大体的思路都差不多，都是用数组来存储大整数。以下的代码仅仅实现功能，并没有充分详细的参数判断，在实际运用中，肯定是需要考虑的。
大整数相加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include <stdio.h>
#include <string.h>
#define N 1000
void get_num(int *array)
{
char str[N] = {'\0'};
int loop = 0;
int length = 0;
scanf("%s", str);
length = strlen(str);
for (loop = 0; loop < length; ++loop) {
array[loop] = str[length - loop - 1] - '0';
}
array[loop] = -1;
}
void big_plus(int *num1, int *num2, int *result)
{
int num1_index = 0;
int num2_index = 0;
int result_index = 0;
int tmp_carry = 0;
int tmp_result = 0;
while (num1[num1_index] != -1 && num2[num2_index] != -1) {
tmp_result = num1[num1_index++] + num2[num2_index++] + tmp_carry;
result[result_index++] = tmp_result % 10;
tmp_carry = tmp_result / 10;
}
while (num1[num1_index] != -1) {
tmp_result = num1[num1_index++] + tmp_carry;
result[result_index++] = tmp_result % 10;
tmp_carry = tmp_result / 10;
}
while (num2[num2_index] != -1) {
tmp_result = num2[num2_index++] + tmp_carry;
result[result_index++] = tmp_result % 10;
tmp_carry = tmp_result / 10;
}
if (tmp_carry) {
result[result_index++] = tmp_carry;
}
result_index[result_index] = -1;
}
void print_result(int *array)
{
int i = 0;
int len = 0;
for (i = 0; array[i] != -1; ++i);
len = i;
for (i = len - 1; i >= 0; --i) {
printf("%d", array[i]);
}
if (len == 0) {
printf("0");
}
printf("\n");
}
int main(int argc, char **argv)
{
int num1[N] = {0};
int num2[N] = {0};
int result[N] = {0};
get_num(num1);
get_num(num2);
big_plus(num1, num2, result);
print_result(result);
return 0;
}
|
大整数相乘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <stdio.h>
#include <string.h>
#define N 1000
void get_num(int *array)
{
char str[N] = {'\0'};
int loop = 0;
int length = 0;
scanf("%s", str);
length = strlen(str);
for (loop = 0; loop < length; ++loop) {
array[loop] = str[length - loop - 1] - '0';
}
array[length] = -1;
}
void big_multi(int *num1, int *num2, int *result)
{
int num1_index = 0;
int num2_index = 0;
int result_index = 0;
int tmp_carry = 0;
int tmp_result = 0;
for (num1_index = 0; num1[num1_index] != -1; ++num1_index) {
for (num2_index = 0; num2[num2_index] != -1; ++num2_index) {
tmp_result = num1[num1_index] * num2[num2_index] + result[num1_index + num2_index] + tmp_carry;
result[num1_index + num2_index] = tmp_result % 10;
tmp_carry = tmp_result / 10;
}
result_index = num1_index + num2_index - 1;
if (tmp_carry) {
result[++result_index] = tmp_carry;
}
}
result[++result_index] = -1;
}
void print_result(int *array)
{
int i = 0;
int len = 0;
for (i = 0; array[i] != -1; ++i);
len = i;
for (i = len - 1; i >= 0; --i) {
printf("%d", array[i]);
}
if (len == 0) {
printf("0");
}
printf("\n");
}
int main(int argc, char **argv)
{
int num1[N] = {0};
int num2[N] = {0};
int result[2 * N] = {0};
get_num(num1);
get_num(num2);
big_multi(num1, num2, result);
print_result(result);
return 0;
}
|
大整数阶乘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <stdio.h>
#include <string.h>
#define N 10000
void print_result(int *array)
{
int i = 0;
int len = 0;
for (i = 0; array[i] != -1; ++i);
len = i;
for (i = len - 1; i >= 0; --i) {
printf("%d", array[i]);
}
if (len == 0) {
printf("0");
}
printf("\n");
}
void big_factor(int n, int *result)
{
int result_index = 0;
int carry = 0;
int tmp_result = 0;
int i = 0;
int j = 0;
result[0] = 1;
if (n <= 1) {
result[1] = -1;
return;
}
for (i = 1; i <= n; ++i) {
for (j = 0; j <= result_index; ++j) {
tmp_result = result[j] * i + carry;
result[j] = tmp_result % 10;
carry = tmp_result / 10;
}
while (carry) {
result[++result_index] = carry % 10;
carry = carry / 10;
}
}
result[++result_index] = -1;
}
int main(int argc, char **argv)
{
int n = 0;
int result[N] = {0};
scanf("%d", &n);
big_factor(n, result);
print_result(result);
return 0;
}
|
大整数幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <stdio.h>
#include <string.h>
#define N 10000
void print_result(int *array)
{
int i = 0;
int len = 0;
for (i = 0; array[i] != -1; ++i);
len = i;
for (i = len - 1; i >= 0; --i) {
printf("%d", array[i]);
}
if (len == 0) {
printf("0");
}
printf("\n");
}
int big_pow(int base, int power, int *result)
{
int result_index = 0;
int carry = 0;
int tmp_result = 0;
int i = 0;
int j = 0;
result[0] = 1;
if (base == 1 || power == 0) {
result[1] = -1;
}
for (i = 0; i < power; ++i) {
for (j = 0; j <= result_index; ++j) {
tmp_result = result[j] * base + carry;
result[j] = tmp_result % 10;
carry = tmp_result / 10;
}
while (carry) {
result[++result_index] = carry % 10;
carry = carry / 10;
}
}
result[++result_index] = -1;
}
int main(int argc, char **argv)
{
int base = 0;
int power = 0;
int result[N];
scanf("%d%d", &base, &power);
big_pow(base, power, result);
print_result(result);
return 0;
}
|
