//思路: 大數問題的處理，通常都是以字符串的形式讀入，再將字符轉化為數字進行處理
//因為除法運算的實質是：被除數能夠減去除數的多少倍；以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
雪黛依夢 閱讀(1366)
評論(0) 編輯 收藏 引用 所屬分類:
大數