C++博客-betahttp://www.cppblog.com/beta/never afraid of bugs.zh-cnTue, 07 Apr 2026 22:55:09 GMTTue, 07 Apr 2026 22:55:09 GMT60POJ Problem 1002 Solved!http://www.cppblog.com/beta/archive/2010/05/08/114854.htmlbetabetaSat, 08 May 2010 08:37:00 GMThttp://www.cppblog.com/beta/archive/2010/05/08/114854.htmlhttp://www.cppblog.com/beta/comments/114854.htmlhttp://www.cppblog.com/beta/archive/2010/05/08/114854.html#Feedback1http://www.cppblog.com/beta/comments/commentRss/114854.htmlhttp://www.cppblog.com/beta/services/trackbacks/114854.html本文使用 Google Docs 编辑，以网页形式发布。最新版本请看以下链接：

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

POJ 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) 除去最顶节点 -邱国钦 10-5-8 下午2:41 
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 }




beta 2010-05-08 16:37 发表评论
]]>POJ Problem 1001 Solved!http://www.cppblog.com/beta/archive/2010/05/07/114793.htmlbetabetaFri, 07 May 2010 14:32:00 GMThttp://www.cppblog.com/beta/archive/2010/05/07/114793.htmlhttp://www.cppblog.com/beta/comments/114793.htmlhttp://www.cppblog.com/beta/archive/2010/05/07/114793.html#Feedback1http://www.cppblog.com/beta/comments/commentRss/114793.htmlhttp://www.cppblog.com/beta/services/trackbacks/114793.html本文使用 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 低级错误出现了在这里！输入６个字节！ -邱国钦 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 }



beta 2010-05-07 22:32 发表评论
]]>test this blog systemhttp://www.cppblog.com/beta/archive/2010/05/06/114561.htmlbetabetaThu, 06 May 2010 01:50:00 GMThttp://www.cppblog.com/beta/archive/2010/05/06/114561.htmlhttp://www.cppblog.com/beta/comments/114561.htmlhttp://www.cppblog.com/beta/archive/2010/05/06/114561.html#Feedback1http://www.cppblog.com/beta/comments/commentRss/114561.htmlhttp://www.cppblog.com/beta/services/trackbacks/114561.htmland 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 }


beta 2010-05-06 09:50 发表评论
]]>