|
|
2010年5月8日
本文使用 Google Docs 编辑，以网页形式发布。最新版本请看以下链接：
http://docs.google.com/View?id=df4r7psc_973ccmbxncnPOJ Problem 1002 Solved! 这个题目的解题思路与上次写的英文单词自动补全、纠错很相似。先将电话号码用有根树的形式保存，每个节点表示一个号码，从根到叶节点就是一个完整的号码。记录每个叶子节点的出现在次数，若大于2，就表示有重复的号码了。 POJ平台对输出的要求十分严格，一点差别都不能有。比如今天遇到的是多输出了一个 '\0'，这是个不可见字符，测试根本看不出问题。 因为有根树的代码大量借鉴了之前写的，所以这次基本上没有遇到什么大问题，只是有些细节上，出现了些低级错误（如 == 写成了 =，函数参数列表中 , 写成了 ;）。 下面是代码：
1 #include <string.h>
2 #include <stdlib.h>
3 #include <stdio.h>
4 #include <ctype.h>
5
6 #define NUM_OF_CHILD 10
7
8 typedef struct NumberNode
9 {
10 char number;
11 struct NumberNode *child[NUM_OF_CHILD]; // 0 ~ 9
12 struct NumberNode *parent;
13
14 long counter; // number of occurence
15 } NUMBER;
16
17 // function decleration ===================================
18 NUMBER *build_tree ();
19 // for build_tree() -------------------------------
20 void parse_input (char input[], char entry[]);
21 NUMBER *init_root ();
22 NUMBER *add_entry (NUMBER *root, char *entry);
23 NUMBER *add_node (NUMBER *cur_node, char c);
24 NUMBER *has_child (NUMBER *cur_node, char c);
25
26 void leaf_walk (NUMBER *root);
27 // for leaf_walk()
28 int has_no_child (NUMBER *cur_node);
29 void print_entry (NUMBER *leaf);
30
31 // @func: build_tree
32 // 从输入字符串建立有根树
33 // @return 返回有根树的根节点
34 NUMBER *build_tree ()
35 {
36 int num_of_input;
37 scanf ("%d", &num_of_input);
38
39 char input[100];
40 char entry[8];
41 // TODO: build root
42 NUMBER *root = init_root();
43
44 int i;
45 for (i=0; i<num_of_input; ++i)
46 {
47 scanf ("%s", input);
48 // procee *input* to number format
49 parse_input (input, entry);
50
51 // TODO: add this entry to root
52 add_entry (root, entry);
53 }
54
55 return root;
56 }
57
58 // @func init_root
59 // 申请根节点内存，初始化根节点
60 // @return 返回指向根节点的指针
61 NUMBER *init_root ()
62 {
63 NUMBER *root = (NUMBER *) malloc (sizeof (NUMBER));
64 root->number = '\0';
65 int i;
66 for (i=0; i<NUM_OF_CHILD; ++i)
67 root->child[i] = NULL;
68 root->parent = NULL;
69 root->counter = 0;
70
71 return root;
72 }
73
74 // @func parse_input
75 // parse string *input* to 7 digits and then store them in *entry*
76 // @param input: unformat string
77 // @param entry: storage for the 7 digits
78 const char A2iTable[26] =
79 {'2','2','2', '3','3','3', '4','4','4', '5','5','5', '6','6','6',
80 '7','7','7','7', '8','8','8', '9','9','9','9'};
81 void parse_input (char input[], char entry[])
82 {
83 size_t length = strlen (input);
84 int i, j, index;
85 for (i=0, j=0; i<length; ++i)
86 {
87 if (isdigit(input[i]))
88 {
89 entry[j++] = input[i];
90 }
91 else if (input[i] == '-')
92 continue;
93 else if (isupper(input[i]) && input[i]!='Q' && input[i]!='Z')
94 {
95 index = (int)input[i] % (int)('A');
96 entry[j++] = A2iTable[index];
97 }
98 }
99 entry[j] = '\0';
100
101 // debug: exam entry
102 // printf ("%s\n", entry);
103
104 }
105
106
107 // @func add_entry
108 // 往 root 加电话号码条目 entry
109 // @para root 树的根节点
110 // @para entry 待加入单词
111 // @return 返回树的根节点
112 NUMBER *add_entry (NUMBER *root, char *entry)
113 {
114 NUMBER *cur_node = root;
115
116 int i;
117 for (i=0; i<strlen(entry); ++i)
118 cur_node = add_node (cur_node, *(entry+i));
119
120 return root;
121 }
122
123 // @func add_node
124 // 往当前节点 cur_node 添加 c 节点
125 // @para cur_node 当前节点
126 // @para c 要添加的节点字母
127 // @return 返回新节点
128 NUMBER *add_node (NUMBER *cur_node, char c)
129 {
130 NUMBER *child = has_child (cur_node, c);
131 // if *c* already exist
132 if (child)
133 {
134 ++ child->counter;
135 return child;
136 }
137 // otherwise, create a new node
138 child = (NUMBER *) malloc (sizeof (NUMBER));
139 child->number = c;
140 child->counter = 1;
141 // maintain the tree
142 cur_node->child[c-'0'] = child;
143 child->parent = cur_node;
144 int i;
145 for (i=0; i<NUM_OF_CHILD; ++i)
146 {
147 child->child[i] = NULL;
148 }
149
150 return child;
151 }
152
153 // @func has_child
154 // 判断节点 cur_node 是否拥有一级子节点 c
155 // @para cur_node
156 // @para c 字节点字母
157 // @return 如果有则返回该子节点，无则返回 NULL
158 NUMBER *has_child (NUMBER *cur_node, char c)
159 {
160 if (!cur_node)
161 return NULL;
162 return cur_node->child[c-'0'];
163 }
164
165 int has_no_child (NUMBER *cur_node)
166 {
167 int i;
168 for (i=0; i<NUM_OF_CHILD; ++i)
169 if (cur_node->child[i])
170 return 0;
171 return 1;
172 }
173
174 int flag_no_duplicte = 1;
175 int hyphen_counter = 0;
176 void print_entry (NUMBER *leaf)
177 {
178 if (leaf->parent && leaf->parent->parent)
179 {
180 print_entry (leaf->parent);
181 }
182 printf ("%c", leaf->number);
183 if (2 == hyphen_counter++)
184 printf ("-");
185 }
186
187 void leaf_walk (NUMBER *root)
188 {
189 if (!root)
190 return;
191 if (has_no_child (root) && (root->counter > 1))
192 {
193 print_entry (root);
194 printf (" %ld\n", root->counter);
195 hyphen_counter = 0;
196 flag_no_duplicte = 0;
197 return;
198 }
199 int i;
200 for (i=0; i<NUM_OF_CHILD; ++i)
201 leaf_walk (root->child[i]);
202 }
203
204 int main (int argc, char **argv)
205 {
206 NUMBER *root = build_tree ();
207
208 leaf_walk(root);
209 if (flag_no_duplicte)
210 printf ("No duplicates.\n");
211 return 0;
212 }
2010年5月7日
本文使用 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 }
2010年5月6日
This an English sentence. and another English sentence. 这是中文。 下面是代码： 1 // @file: poj_1000.c
2
3 #include <stdio.h>
4
5 int main(int argc, char **argv)
6 {
7 int a, b;
8 scanf ("%d %d", &a, &b);
9 printf ("%d\n", a+b);
10 return 0;
11 }
|