beta

never afraid of bugs.
随笔 - 3, 文章 - 0, 评论 - 4, 引用 - 0
数据加载中……

POJ Problem 1001 Solved!

本文使用 Google Docs 编辑,以网页形式发布。最新版本请看以下链接:

http://docs.google.com/View?id=df4r7psc_971cf4bpgc4

POJ Problem 1001 Solved!

  今晚终于让我的 problem 1001 代码得到 POJ *Accepted* 了。今天早上就写基本写好了,在本机上测试都没有发现问题,但提交时总是 *Wrong Anser*!

  POJ平台有个讨论页面,而 Problem 1001 的讨论最多的是一组测试数据,下午的时候没有多注意,只是找一些试试。晚上把程序改了一下,先读入所有的输入,再统一输出。而且用了所有的测试数据。这时候问题就出现了:
  首先是在大数乘法函数中出现了段错误,检查一下,发现是分配给结果的数组大小了;修正了这个错误后,发现除了第一组,其他数的结果明显是错误的,一看,突然发现有一个相当低级的错误,分配给输入字符串的空间小了一个字节!

  解决了这两个问题,提交,Accepted!前辈的话要多注意听!

  下面是代码:
  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4
  5 #define MAX_INPUT 7 低级错误出现了在这里!输入6个字节! -邱国钦 10-5-7 下午10:19 
  6 #define MAX_LENGTH 150 第一个错误在这里,之前是 125 -邱国钦 10-5-7 下午10:20 
  7 #define RADIX 10
  8
  9 // function decleration ========================================
 10 int *precise_multiplex (int A[], int B[], int C[]);
 11 void set_value(int A[], const size_t LENGTH, int value);
 12 void pretty_print (int A[], const size_t LENGTH,
 13                     const int num_of_fraction);
 14
 15 typedef struct input
 16 {
 17     char R[MAX_INPUT];
 18     int n;
 19     struct input *p_next; 为什么用 INPUT *p_next 编译不通过呢? -邱国钦 10-5-7 下午10:29 
 20 } INPUT;
 21
 22 int main(int argc, char **argv)
 23 {
 24     INPUT *input_list = (INPUT *) malloc (sizeof (INPUT));
 25     INPUT *p = input_list;
 26
 27     char R[MAX_INPUT];
 28     int n;
 29
 30     int k;
 31     while (scanf ("%s%d", R, &n) == 2)
 32     {
 33         p->p_next =  (INPUT *) malloc (sizeof (INPUT));
 34         p = p->p_next;
 35
 36         strcpy (p->R, R);
 37 //        for (k=0; k<MAX_INPUT; ++k)
 38 //            p->R[k] = R[k];
 39         p->n = n;
 40         p->p_next = NULL;
 41     }
 42
 43     int A[MAX_LENGTH];  // A * B = C
 44     int B[MAX_LENGTH];
 45     int C[MAX_LENGTH];
 46     int D[MAX_LENGTH];
 47
 48     int *m1, *m2, *product, *others;    // multipliers and product
 49     m1 = A;
 50     m2 = B;
 51     product = C;
 52     others = D;
 53
 54     size_t length;      // length of input string
 55     int i, j;              // loop variable
 56
 57     p = input_list->p_next;
 58     while (p)
 59     {
 60         for (i=0; i<MAX_INPUT; ++i)
 61             R[i] = p->R[i];
 62         n = p->n;
 63         p = p->p_next;
 64         
 65         // n is zero:
 66         if (!n)
 67         {
 68             printf ("1\n");
 69             continue;
 70         }
 71
 72         // initial *others* (=1) ====================================
 73         set_value (others, MAX_LENGTH-1, 0);
 74         others[MAX_LENGTH-1] = 1;
 75         
 76         // store R into m1 in integer format ========================
 77         set_value (m1, MAX_LENGTH, 0);
 78         length = strlen (R);
 79
 80         // figure out total number of input digits ------------------
 81         int start;      // where the storage *start*
 82         if (strchr (R, '.'))
 83         {
 84             // get ride of suffixing zeros
 85             for (i=length-1; i>=0; --i)
 86             {
 87                 if ('0' == R[i])
 88                 {
 89                     R[i] = '\0';
 90                     length -= 1;
 91                 }
 92                 else
 93                     break;
 94             }
 95             start = MAX_LENGTH - length + 1;
 96         }
 97         else
 98             start = MAX_LENGTH - length;
 99             
100         int dot_pos = -1;                   // position of the dot
101         for (i=0, j=0; i<length; ++i)
102         {
103             // skip the dot
104             if ('.' == R[i])
105             {
106                 dot_pos = i;
107                 continue;
108             }
109             m1[start+j] = (int)(R[i] - '1' + 1);
110             ++j;
111         }
112
113         // figure out number of fraction
114         int number_of_fraction = 0;
115         if (-1 != dot_pos)
116             number_of_fraction = n * (length - dot_pos - 1);  //
117         
118         if (n == 1)
119         {
120             pretty_print (m1, MAX_LENGTH, number_of_fraction);
121             continue;
122         }
123
124         int *temp;
125         
126         while (n>1)
127         {
128             if (n%2)
129             {
130                 set_value (product, MAX_LENGTH, 0);
131                 temp = others;
132                 others = precise_multiplex (m1, others, product);
133                 product = temp;
134                 // copy_array (B, others, MAX_LENGTH);
135                 n -= 1;
136                 continue;
137             }
138
139             // copy m1 to m2; reset product
140             for (i=0; i<MAX_LENGTH; ++i)
141             {
142                 m2[i] = m1[i];
143                 product[i] = 0;
144             }
145
146             temp = m1;
147             m1 = precise_multiplex (m1, m2, product);
148             product = temp;
149
150             n /= 2;
151         }
152
153         // compute final result
154         set_value (product, MAX_LENGTH, 0);
155         precise_multiplex (m1, others, product);
156
157         // print the result
158         pretty_print (product, MAX_LENGTH, number_of_fraction);
159     }
160
161     return 0;
162 }
163
164 // @func: set_value
165 // set all elements in array *A* of length *LENGTH* to *value*
166 // @param A: array to be set
167 // @param LENGTH: length of *A*
168 // @param value: the desire value
169 // TODO: may exsits a better way to do this
170 void set_value(int A[], const size_t LENGTH, int value)
171 {
172     int i;
173     for (i=0; i<LENGTH; ++i)
174     {
175         A[i] = value;
176     }
177 }
178
179 // @func: precise_multiplex
180 // calculate A*Bmalloc, and store the product into C
181 // @param A, B, C: integer array storing digits of radix-10
182 // @return: the product of A*B
183 int *precise_multiplex (int A[], int B[], int C[])
184 {
185     // find the length of A and B
186     int start_A, start_B;
187     for (start_A=0; start_A<MAX_LENGTH; ++start_A)
188     {
189         if (A[start_A])
190             break;
191     }
192     for (start_B=0; start_B<MAX_LENGTH; ++start_B)
193     {
194         if (B[start_B])
195             break;
196     }
197
198     int length_A, length_B;
199     length_A = MAX_LENGTH - start_A;
200     length_B = MAX_LENGTH - start_B;
201
202     int temp, remainder, carry;
203     int i, j, k;
204
205     // multiplex every digit
206     k = 0;      // 位置标志
207     for (i=MAX_LENGTH-1; i>=start_B; --i)
208     {
209         for (j=MAX_LENGTH-1; j>=start_A; --j)
210         {
211             temp = B[i] * A[j];
212             carry = temp / RADIX;
213             remainder = temp % RADIX;
214             // TODO: overflow?
215             C[j-k] += remainder;
216             C[j-1-k] += carry;
217         }
218         k++;
219     }
220
221     // 在最后处理每个数组元素
222     int start_C;
223     for (start_C=0; start_C<MAX_LENGTH; ++start_C)
224     {
225         if (C[start_C])
226             break;
227     }
228     for (i=MAX_LENGTH-1; i>=start_C; --i)
229     {
230         carry = C[i] / RADIX;
231         C[i] = C[i] % RADIX;
232         C[i-1] += carry;
233     }
234
235     return C;
236 }
237
238 void pretty_print (int A[], const size_t LENGTH,
239                     const int num_of_fraction)
240 {
241     int i;
242     // find the first nonzero element
243     for (i=0; i<LENGTH; ++i)
244         if (A[i])
245             break;
246
247     if ((LENGTH-i) < num_of_fraction)
248     {
249         printf (".");
250         i = LENGTH - num_of_fraction;
251         for (i; i<LENGTH; ++i)
252             printf ("%d", A[i]);
253     }
254     else
255     {
256         int num_of_int = LENGTH - num_of_fraction;
257         for (i; i<LENGTH; ++i)
258         {
259             if (i == num_of_int)
260                 printf (".");
261             printf ("%d", A[i]);
262         }
263     }
264     printf ("\n");
265 }

posted on 2010-05-07 22:32 beta 阅读(1136) 评论(1)  编辑 收藏 引用

评论

# re: POJ Problem 1001 Solved!  回复  更多评论   

我是奔着 cppblog 的编辑器来的,但发现似乎这个编辑器的问题也不少!
2010-05-07 22:33 | beta

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理