|
本文使用 Google Docs 编辑,以网页形式发布。最新版本请看以下链接: http://docs.google.com/View?id=df4r7psc_971cf4bpgc4POJ 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 #define MAX_LENGTH 150 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; 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 }
|