砝码分盐问题——从数学和计算机的角度分析(4)

00001: / **
00002: * the proble of dividing salt using weight.
00003: * a heap of salt with 280g, divide it into two small heaps of salt with 100g and 180g
00004: * respectively, in 3 steps. the weights are 4g and 14g. there is a balance of course.
00005: *
00006: * this is an improved search method based on the pure mathematical method.
00007: */
00008: #include <stdio.h>
00009: #include <stdlib.h>
00010: #include <string.h>
00011:
00012: #define Max_Num 5
00013: #define To_Be_Devided 2
00014:
00015: #define total 280 //the total weight of the heap of salt
00016: int ws[]={0, 4, 10, 14, 18}; //all cases of the weights combination
00017: int heap1 = 100, heap2 = 180; //the target weight of the two samll heaps of salt
00018:
00019: struct Division_Node
00020: {
00021:    int parent_be_divided_; //array to_be_divided_[] divided from its parent with this index
00022:    int step_;              //the node step in the division process
00023:    int heap_[Max_Num - 1]; //all divisions of its parent position for all weights
00024:    int to_be_divided_[2];  //salt heap index to be divided in next step
00025:    struct Division_Node *next_[2* Max_Num]; //all pointers to all child divisions
00026:    int child_;            //the numbe of children (not NULL in array next_)
00027: };
00028:
00029: //the root, for step 1, heap_[0] will be divided
00030: static struct Division_Node root = {0, 0, {total}, {0}, {NULL}, 0};

当前节点保存其父节点被分解后的结果，heap_[]数组中，下标为to_be_divided_[0]和to_be_divided_[1]的元素保存了新生成的两个值，parent_be_divided_表示这两个值是由其父节点的heap_[]数组中第parent_be_divided_个元素被分解的结果。

例如，父亲节点parent，儿子节点为child，其关系为：parent.heap_[child.parent_be_divided_]被分解为两个值，分别为child.heap_[child.to_be_divided_[0]]和child.heap_[child.to_be_divided_[1]]，且有parent.next_[k]=&child，表示child是parent的第k个儿子。对于child的下一次分解，就依次分解这两个新生成的值。

4.3 分解过程描述

按广度优先的顺序，求得如上图的每一次称量的节点，即可完成所有有结果的称量。当然要避免重复，并使用限制规则来减小搜索空间。

从根节点root.heap_[4]={280}开始分解，初始时root.to_be_divided_[2]={0}，即开始时只有root.heap_[0]=280需要分解，以分解x及x1为例说明该分解过程。

(1) 第一次称量：step=1，z=x+y，x保存在heap_[0]，y保存在heap_[step]，to_be_divided_[2]={0,step}。

(2) 第二次称量：step=2，x=x1+x2，x1保存在heap_[0]，x2保存在heap_[step]，to_be_divided_[2]={0,step}。

(3) 第三次称量：step=3，x1=x11+x12，x11保存在heap_[0]，x12保存在heap_[step]，to_be_divided_[2]={0,step}。

该过程从上图也能看到。此处仅给出第三次称量过程的代码，如下，其他省略，具体请参考附录3。

00119: /** the third division, according to
00120:    x1=x11+x12, y1=y11+y12, x11<=x12, y11<=y12
00121:    x2=x21+x22, y2=y21+y22, x21<=x22, y21<=y22
00122:    but, x1 or x2 or y1 or y2 is saved in heap_ of each node2 with index node2- >to_be_divided_[0]
00123:    and node2- >to_be_divided_[1]. so, unify them to be as x1.
00124: */
00125: void weight3()
00126: {
00127:    int div = 0, i = 0, j = 0, k = 0, w = 0;
00128:    struct Division_Node *cur = &root;
00129:
00130:    int step = 3;
00131:    for (i = 0; i < cur->child_; i++) //for each node1 in step1
00132:    {
00133:       struct Division_Node *node1 = cur->next_[i];
00134:       for (j = 0; j < node1->child_; j++) //for each node2 of node1 in step2
00135:       {
00136:          struct Division_Node *node2 = node1->next_[j];
00137:
00138:          //to avoid repeatance
00139:          int to_be_divided = To_Be_Devided;
00140:          if (node2->heap_[node2->to_be_divided_[0]] == node2->heap_[node2->to_be_divided_[1]])
00141:             to_be_divided--;
00142:
00143:          int child = 0;
                //for step 3, will divide x1=heap_[0], x2=heap_[2] of node2
00144:          for (div = 0; div < to_be_divided; div++) 
00145:          {
00146:             int curpos = node2->to_be_divided_[div];
00147:             int x1 = node2->heap_[curpos];//the current heap to be divided, x1,or x2,or y1,or y2
00148:
00149:             for (k = 0; k < Max_Num; k++)
00150:             {
00151:                w = ws[k];
00152:                int x11 = (x1 - w)/2; //divide x or y, use x in order to be in a uniform
00153:                int x12 = (x1 + w)/2;
00154:                if (x11 % 2!= 0) //no need to judge x12
00155:                   continue;
00156:
00157:                //new a node in step 3
00158:                struct Division_Node *node3 = (struct Division_Node*)malloc(sizeof(
                           struct Division_Node));
00159:                memset(node3, 0, sizeof(struct Division_Node));
00160:                memcpy(node3->heap_, node2->heap_, (Max_Num-1)*sizeof(int));//copy from its parent
00161:                node3->parent_be_divided_ = curpos;
00162:                node3->step_ = step;
00163:                node3->heap_[curpos] = x11;
00164:                node3->heap_[step] = x12;
00165:                node3->to_be_divided_[0] = curpos; //in fact, this array in step3 needed for dump
00166:                node3->to_be_divided_[1] = step;
00167:                node2->next_[child++] = node3; //link current node2 and node3
00168:             }
00169:          }
00170:
00171:          node2->child_ = child;
00172:       }
00173:    }
00174: }

4.4 如何输出？

广度遍历该树，即可输出所有结果。如果加入判断，即可输出正确分解结果。此处列出输出正确结果的代码。具体过程不再解释，可参考代码注释进行理解。

00204: void dump_correct_results(struct Division_Node* node)
00205: {
00206:    int i = 0, j = 0, k = 0;
00207:    struct Division_Node *cur = node;
00208:
00209:    for (i = 0; i < cur->child_; i++) //for each node1 in step1
00210:    {
00211:       struct Division_Node *node1 = cur->next_[i];
00212:       for (j = 0; j < node1->child_; j++) //for each node2 of node1 in step2
00213:       {
00214:          struct Division_Node *node2 = node1->next_[j];
00215:          for (k = 0; k < node2->child_; k++) //for each node3 of node2 in step 3
00216:          {
00217:             struct Division_Node *node3 = node2->next_[k];
00218:
00219:             /** unify them into the following equations
00220:                z = x + y, x <= y
00221:                x = x1 + x2, x1 <= x2
00222:                x1 = x11 + x12, x11 <= x12
00223:             */
00224:             int x11 = node3->heap_[node3->to_be_divided_[0]];
00225:             int x12 = node3->heap_[node3->to_be_divided_[1]];
00226:             int x2index = 0;
00227:             if (node3->parent_be_divided_ == node2->to_be_divided_[0])
00228:                x2index = node2->to_be_divided_[1];
00229:             else
00230:                x2index = node2->to_be_divided_[0];
00231:             int x2 = node2->heap_[x2index];
00232:
00233:             if (x11 + x2 == heap1 || x12 + x2 == heap1)
00234:             {
00235:                printf("%d = %d + %d\n", total, node1->heap_[node1->to_be_divided_[0]],
00236:                   node1->heap_[node1->to_be_divided_[1]]);
00237:                printf("%d = %d + %d\n", node1->heap_[node2->parent_be_divided_],
00238:                   node2->heap_[node2->to_be_divided_[0]],
00239:                   node2->heap_[node2->to_be_divided_[1]]);
00240:                printf("%d = %d + %d\n\n", node2->heap_[node3->parent_be_divided_], x11, x12);
00241:             }
00242:          }
00243:       }
00244:    }
00245: }

4.5 输出结果

该方法的输出结果与第3节的输出结果完全相同。此处省略，有兴趣的读者可以自行验证。具体的输出结果请参考附录2。

4.6 讨论

比起第3节数学的方法，该方法不需要那么多的数组定义，定义数组的方法(第3节)如果加上别的条件，例如再多一次称量，很难扩展。很显然，该方法数据结构统一、简单，且节省大量空间。但该方法也有缺点，例如，最终的正确解只有5个，但该方法同第3节的数学方法一样，计算了所有的有结果的解，共37个，也比较浪费。

那么，有没有一种方法，直接在第2次称量和第3次称量的时候直接判断这个分解是否正确或者直接计算这个正确的解呢？——有。下面介绍这种方法。

附录3：树结构分解的代码weight2.c

/** * the proble of dividing salt using weight. * a heap of salt with 280g, divide it into two small heaps of salt with 100g and 180g * respectively, in 3 steps. the weights are 4g and 14g. there is a balance of course. * * this is an improved search method based on the pure mathematical method. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define Max_Num 5 #define To_Be_Devided 2 #define total 280 //the total weight of the heap of salt int ws[]={0, 4, 10, 14, 18}; //all cases of the weights combination int heap1 = 100, heap2 = 180; //the target weight of the two samll heaps of salt struct Division_Node { int parent_be_divided_; //array to_be_divided_[] divided from its parent with this index int step_; //the node step in the division process int heap_[Max_Num - 1]; //all divisions of its parent position for all weights int to_be_divided_[2]; //salt heap index to be divided in next step struct Division_Node *next_[2 * Max_Num]; //all pointers to all child divisions int child_; //the numbe of children (not NULL in array next_) }; //the root, for step 1, heap_[0] will be divided static struct Division_Node root = {0, 0, {total}, {0}, {NULL}, 0}; /** the first division, according to z=x+y, x <= y */ void weight1() { int div = 0, k = 0, w = 0; struct Division_Node *cur = &root; int child = 0; int step = 1; for (div = 0; div < To_Be_Devided - 1; div++) //for step 1, only divide heap_[0] { int curpos = cur->to_be_divided_[div]; int z = cur->heap_[curpos]; //the current heap to be divided for (k = 0; k < Max_Num; k++) { w = ws[k]; int x = (z - w)/2; //divide z int y = (z + w)/2; if (x % 2 != 0) //no need to judge y[k] continue; //new a node in step 1 struct Division_Node *node1 = (struct Division_Node*)malloc(sizeof(struct Division_Node)); memset(node1, 0, sizeof(struct Division_Node)); node1->parent_be_divided_ = curpos; node1->step_ = step; node1->heap_[curpos] = x; node1->heap_[step] = y; node1->to_be_divided_[0] = curpos; node1->to_be_divided_[1] = step; cur->next_[child++] = node1; //link root and node1 } } cur->child_ = child; } /** the second division, according to x=x1+x2, y=y1+y2, x1<=x2, y1<=y2 but, x and y are saved in node1->to_be_divided_[0] and node1->to_be_divided_[1]. so, unify them to be as x. */ void weight2() { int div = 0, i = 0, k = 0, w = 0; struct Division_Node *cur = &root; int step = 2; for (i = 0; i < cur->child_; i++) //for each node1 in step1 { struct Division_Node *node1 = cur->next_[i]; //step 2 will use all nodes created in step 1 //to avoid repeatance int to_be_divided = To_Be_Devided; if (node1->heap_[node1->to_be_divided_[0]] == node1->heap_[node1->to_be_divided_[1]]) to_be_divided--; int child = 0; for (div = 0; div < to_be_divided; div++) //for step 2, will divide x=heap_[0], y=heap_[1] of node1 { int curpos = node1->to_be_divided_[div]; int x = node1->heap_[curpos]; //the current heap to be divided for (k = 0; k < Max_Num; k++) { w = ws[k]; int x1 = (x - w)/2; //divide x or y, use x in order to be in a uniform int x2 = (x + w)/2; if (x1 % 2 != 0) //no need to judge x2 continue; //new a node in step 2 struct Division_Node *node2 = (struct Division_Node*)malloc(sizeof(struct Division_Node)); memset(node2, 0, sizeof(struct Division_Node)); memcpy(node2->heap_, node1->heap_, (Max_Num - 1) * sizeof(int)); //copy from its parent node2->parent_be_divided_ = curpos; node2->step_ = step; node2->heap_[curpos] = x1; node2->heap_[step] = x2; node2->to_be_divided_[0] = curpos; node2->to_be_divided_[1] = step; node1->next_[child++] = node2; //link current node1 and node2 } } node1->child_ = child; } } /** the third division, according to x1=x11+x12, y1=y11+y12, x11<=x12, y11<=y12 x2=x21+x22, y2=y21+y22, x21<=x22, y21<=y22 but, x1 or x2 or y1 or y2 is saved in heap_ of each node2 with index node2->to_be_divided_[0] and node2->to_be_divided_[1]. so, unify them to be as x1. */ void weight3() { int div = 0, i = 0, j = 0, k = 0, w = 0; struct Division_Node *cur = &root; int step = 3; for (i = 0; i < cur->child_; i++) //for each node1 in step1 { struct Division_Node *node1 = cur->next_[i]; for (j = 0; j < node1->child_; j++) //for each node2 of node1 in step2 { struct Division_Node *node2 = node1->next_[j]; //to avoid repeatance int to_be_divided = To_Be_Devided; if (node2->heap_[node2->to_be_divided_[0]] == node2->heap_[node2->to_be_divided_[1]]) to_be_divided--; int child = 0; for (div = 0; div < to_be_divided; div++) //for step 3, will divide x1=heap_[0], x2=heap_[2] of node2 { int curpos = node2->to_be_divided_[div]; int x1 = node2->heap_[curpos]; //the current heap to be divided, x1, or x2, or y1, or y2 for (k = 0; k < Max_Num; k++) { w = ws[k]; int x11 = (x1 - w)/2; //divide x or y, use x in order to be in a uniform int x12 = (x1 + w)/2; if (x11 % 2 != 0) //no need to judge x12 continue; //new a node in step 3 struct Division_Node *node3 = (struct Division_Node*)malloc(sizeof(struct Division_Node)); memset(node3, 0, sizeof(struct Division_Node)); memcpy(node3->heap_, node2->heap_, (Max_Num - 1) * sizeof(int)); //copy from its parent node3->parent_be_divided_ = curpos; node3->step_ = step; node3->heap_[curpos] = x11; node3->heap_[step] = x12; node3->to_be_divided_[0] = curpos; //in fact, this array in step3 needed for dump node3->to_be_divided_[1] = step; node2->next_[child++] = node3; //link current node2 and node3 } } node2->child_ = child; } } } //visit each leaf node (all leaf nodes are the division result) void dump_all_results(struct Division_Node* node) { int i = 0, j = 0, k = 0; struct Division_Node *cur = node; for (i = 0; i < cur->child_; i++) //for each node1 in step1 { struct Division_Node *node1 = cur->next_[i]; for (j = 0; j < node1->child_; j++) //for each node2 of node1 in step2 { struct Division_Node *node2 = node1->next_[j]; for (k = 0; k < node2->child_; k++) //for each node3 of node2 in step 3 { struct Division_Node *node3 = node2->next_[k]; printf("%d = %d + %d/n", total, node1->heap_[node1->to_be_divided_[0]], node1->heap_[node1->to_be_divided_[1]]); printf("%d = %d + %d/n", node1->heap_[node2->parent_be_divided_], node2->heap_[node2->to_be_divided_[0]], node2->heap_[node2->to_be_divided_[1]]); printf("%d = %d + %d/n/n", node2->heap_[node3->parent_be_divided_], node3->heap_[node3->to_be_divided_[0]], node3->heap_[node3->to_be_divided_[1]]); } } } } void dump_correct_results(struct Division_Node* node) { int i = 0, j = 0, k = 0; struct Division_Node *cur = node; for (i = 0; i < cur->child_; i++) //for each node1 in step1 { struct Division_Node *node1 = cur->next_[i]; for (j = 0; j < node1->child_; j++) //for each node2 of node1 in step2 { struct Division_Node *node2 = node1->next_[j]; for (k = 0; k < node2->child_; k++) //for each node3 of node2 in step 3 { struct Division_Node *node3 = node2->next_[k]; /** unify them into the following equations z = x + y, x <= y x = x1 + x2, x1 <= x2 x1 = x11 + x12, x11 <= x12 */ int x11 = node3->heap_[node3->to_be_divided_[0]]; int x12 = node3->heap_[node3->to_be_divided_[1]]; int x2index = 0; if (node3->parent_be_divided_ == node2->to_be_divided_[0]) x2index = node2->to_be_divided_[1]; else x2index = node2->to_be_divided_[0]; int x2 = node2->heap_[x2index]; if (x11 + x2 == heap1 || x12 + x2 == heap1) { printf("%d = %d + %d/n", total, node1->heap_[node1->to_be_divided_[0]], node1->heap_[node1->to_be_divided_[1]]); printf("%d = %d + %d/n", node1->heap_[node2->parent_be_divided_], node2->heap_[node2->to_be_divided_[0]], node2->heap_[node2->to_be_divided_[1]]); printf("%d = %d + %d/n/n", node2->heap_[node3->parent_be_divided_], x11, x12); } } } } } void free_all_nodes(struct Division_Node* node) { int i = 0, j = 0, k = 0; struct Division_Node *cur = node; for (i = 0; i < cur->child_; i++) //for each node1 in step1 { struct Division_Node *node1 = cur->next_[i]; for (j = 0; j < node1->child_; j++) //for each node2 of node1 in step2 { struct Division_Node *node2 = node1->next_[j]; for (k = 0; k < node2->child_; k++) //for each node3 of node2 in step 3 { struct Division_Node *node3 = node2->next_[k]; free(node3); } free(node2); } free(node1); } } int main(/* int argc, char** argv */) { weight1(); weight2(); weight3(); printf("-----------------------------/n"); printf("the results of all divisions:/n"); printf("-----------------------------/n"); dump_all_results(&root); printf("-------------------------------------/n"); printf("the results of all correct divisions:/n"); printf("-------------------------------------/n"); dump_correct_results(&root); free_all_nodes(&root); return 0; }