//思路: 大数问题的处理，通常都是以字符串的形式读入，再将字符转化为数字进行处理
//因为除法运算的实质是：被除数能够减去除数的多少倍；以7546 / 23 为例
// 开始时：7546 - 23 的 100倍可以减 3 次 等于 646 ；所以商增加 300
// 646 - 23 的 10 倍 可以减 2 次 等于 186 ；所以商增加 20
// 186 - 23 的 1 倍 可以减 8 次 等于 2； 所以商增加 8
//所以商最终为 328
//所以本题的关键是写一个减法算法
1
2#include <stdio.h>
3#include <stdlib.h>
4#include <string.h>
5#define MAXSIZE 101
6//减法操作函数:return -1时商为0；return 0时商为1；
7//当被除数比除数大时，两数相减，结果放在a1中，返回结果的长度；
8int subtract (int a1[MAXSIZE], int a2[MAXSIZE], int len1, int len2)
9
{
10
if ( len1 < len2 )
11 return -1;
12
13 //经典算法：逆置后如何判断2个数的大小
14 if ( len1 == len2)
15
{
16 bool tag = false;
17 for (int i = len1 - 1; i >= 0; i --)
18 {
19 if ( a1[i] > a2[i]) //被除数更大
20 tag = true;
21 else if ( a1[i] < a2[i]) //被除数小
22 {
23 if ( !tag )
24 return -1;
25
}
26 }
27 }
28
29 //被除数更大时：做减法运算 ,并且得到a1新的长度
30 for (int i = 0; i < len1; i++)
31 {
32 a1[i]-=a2[i];
33 if ( a1[i] < 0 )
34 {
35 a1[i] += 10;
36 a1[i+1] --;
37 }
38 }
39
40 for (int i = len1 - 1; i >= 0; i--)
41 if (a1[i])
42 return i + 1;
43
44 return 0;//巧妙之处：被除数和除数相等的时候，a1[]中为0
45
}
46
47int main ()
48{
49 int n;
50 char line1[MAXSIZE];//被除数
51 char line2[MAXSIZE];//除数
52 int a1[MAXSIZE];
53 int a2[MAXSIZE];
54 int result[MAXSIZE];
55 int len1, len2;
56
57 while ( scanf ("%d", &n) != EOF )
58 {
59 //一共有n组测试数据
60 for (int i = 0; i < n; i ++ )
61 {
62 scanf ("%s%s", line1, line2);
63
64 len1 = strlen (line1);
65 len2 = strlen (line2);
66 memset ( a1, 0, sizeof(a1) );
67 memset ( a2, 0, sizeof(a2) );
68 memset ( result, 0, sizeof(result));
69
70 //将字符转化为数字存储
71 int j = 0;
72 for (int i = len1 - 1; i >= 0; i--)
73 a1[j++] = line1[i] - '0';
74 int k = 0;
75 for (int i = len2 - 1; i >= 0; i--)
76 a2[k++] = line2[i] - '0';
77
78 //调用函数进行减法操作运算
79 //相减一次后得到新的a1的
80 len1 = subtract (a1, a2, len1, len2);
81
82 if ( len1 == -1)
83 {
84 printf( "%d\n", 0);
85 continue;
86 }
87
88 if (len1 == 0)
89 {
90 printf ("%d\n",1);
91 continue;
92 }
93
94 //减一次，商加1
95 result[0] ++;
96
97 //nTimes 确定补 0 的个数，使除数和被除数一样的长
98 int nTimes = len1 - len2;
99 if ( nTimes < 0)
100 goto Outputresult;
101
102 //确定如何向除数a2 中补0，同时改变a2
103 for (int i = len1 - 1; i >= 0; i--)
104 {
105 if ( i >= nTimes)
106 a2[i] = a2[i - nTimes];
107 else
108 a2[i] = 0;
109 }
110 len2 = len1;
111
112 //核心算法：难点：确定每次补0 后可以减多少次
113 for (int j = 0; j <= nTimes; j++)
114 {
115 int temp;
116 while ( ( temp = subtract (a1, a2 + j, len1, len2 - j ) ) >= 0 )
117 {
118 len1 = temp;
119 result[nTimes - j]++;
120 }
121 }
122
123Outputresult:
124 //商值的处理
125 for (int i = 0; i < MAXSIZE; i++)
126 {
127 if (result[i] >= 10 )
128 {
129 result[i + 1] += result[i] / 10;
130 result[i] = result[i] %10;
131 }
132 }
133
134 //输出处理
135 bool target = false;
136 for (int i = MAXSIZE - 1; i >= 0; i--)
137 {
138 if (target)
139 printf ("%d", result[i]);
140 else if ( result[i] )
141 {
142 printf("%d", result[i]);
143 target = true;
144 }
145
146 }
147 printf ("\n");
148 }
149 }
150 return 0;
151}
152
posted on 2010-08-09 13:11
雪黛依梦 阅读(1324)
评论(0) 编辑 收藏 引用 所属分类:
大数