3. 能否编程计算？
对于第2节的分析结果，能否编程计算？该如何写程序？本节从纯数学的角度给出上述分解方法的程序。
3.1 基本思想
该方法的基本思想如下图。
该图只画出了其中的分解x并在第三次称量时分解x1的分解图，图中每个节点中的数组及程序中用来保存该次称量分解的结果。省略分解x2、分解y并在第三次称量时分解y1或者y2的节点。
完整的代码请参考附录1，下面介绍相关数据结构和三次称量过程。
3.2 数据结构描述
图中的一维、二维、三维数组定义如下。
00001: / **注1：编译该代码时会出现如下警告，是因为在Linux平台，有内建的函数名为y1，命名冲突，故出现该警告，可通过"man y1"命令查看该函数的说明。如果想消除该警告，请将代码中y1数组重新命名。
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 a pure mathematical method.
00007: */
00008: #include
00009:
00010: #define Max_Num 5
00011:
00012: int total = 280; //the total weight of the heap of salt
00013: int heap1 = 100, heap2 = 180; //the target weight of the two samll heaps of salt
00014: int ws[]={0, 4, 10, 14, 18}; //all cases of the weights combination
00015:
00016: /* the first division result */
00017: int x[Max_Num] = {0}, y[Max_Num] = {0};
00018:
00019: /* the second division result */
00020: int x1[Max_Num][Max_Num] = {0}, x2[Max_Num][Max_Num] = {0};
00021: int y1[Max_Num][Max_Num] = {0}, y2[Max_Num][Max_Num] = {0};
00022:
00023: /* the third division result */
00024: int x11[Max_Num][Max_Num][Max_Num] = {0}, x12[Max_Num][Max_Num][Max_Num] = {0};
00025: int x21[Max_Num][Max_Num][Max_Num] = {0}, x22[Max_Num][Max_Num][Max_Num] = {0};
00026: int y11[Max_Num][Max_Num][Max_Num] = {0}, y12[Max_Num][Max_Num][Max_Num] = {0};
00027: int y21[Max_Num][Max_Num][Max_Num] = {0}, y22[Max_Num][Max_Num][Max_Num] = {0};
weight3.c:21: warning: built-in function ‘y1’ declared as non-function
注2：gcc编译器对上述的x1/x2/x11/x12/x21/x22/y11/y12/y21/y22数组初始化会出现如下警告。
# make
gcc -g -Wall -Wextra -c weight1.c
weight1.c:20: warning: missing braces around initializer
weight1.c:20: warning: (near initialization for ‘x1[0]’)
weight1.c:20: warning: missing braces around initializer
weight1.c:20: warning: (near initialization for ‘x2[0]’)
weight1.c:21: warning: built-in function ‘y1’ declared as non-function
weight1.c:21: warning: missing braces around initializer
weight1.c:21: warning: (near initialization for ‘y1[0]’)
weight1.c:21: warning: missing braces around initializer
weight1.c:21: warning: (near initialization for ‘y2[0]’)
weight1.c:24: warning: missing braces around initializer
weight1.c:24: warning: (near initialization for ‘x11[0]’)
weight1.c:24: warning: missing braces around initializer
weight1.c:24: warning: (near initialization for ‘x12[0]’)
weight1.c:25: warning: missing braces around initializer
weight1.c:25: warning: (near initialization for ‘x21[0]’)
weight1.c:25: warning: missing braces around initializer
weight1.c:25: warning: (near initialization for ‘x22[0]’)
weight1.c:26: warning: missing braces around initializer
weight1.c:26: warning: (near initialization for ‘y11[0]’)
weight1.c:26: warning: missing braces around initializer
weight1.c:26: warning: (near initialization for ‘y12[0]’)
weight1.c:27: warning: missing braces around initializer
weight1.c:27: warning: (near initialization for ‘y21[0]’)
weight1.c:27: warning: missing braces around initializer
weight1.c:27: warning: (near initialization for ‘y22[0]’)
...
若要消除这些警告，可将其中的数组初始化为0的元素加上花括号。一维数组加1个花括号，二维数组加2个花括号，三维数组加3个花括号，即初始化一个具体的元素，其他的元素会被自动初始化为0.如下。
00016: /* the first division result */3.3 第一次分解过程
00017: int x[Max_Num] = {0}, y[Max_Num] = {0};
00018:
00019: /* the second division result */
00020: int x1[Max_Num][Max_Num] = {{0}}, x2[Max_Num][Max_Num] = {{0}};
00021: int y1[Max_Num][Max_Num] = {{0}}, y2[Max_Num][Max_Num] = {{0}};
00022:
00023: /* the third division result */
00024: int x11[Max_Num][Max_Num][Max_Num] = {{{0}}}, x12[Max_Num][Max_Num][Max_Num] = {{{0}}};
00025: int x21[Max_Num][Max_Num][Max_Num] = {{{0}}}, x22[Max_Num][Max_Num][Max_Num] = {{{0}}};
00026: int y11[Max_Num][Max_Num][Max_Num] = {{{0}}}, y12[Max_Num][Max_Num][Max_Num] = {{{0}}};
00027: int y21[Max_Num][Max_Num][Max_Num] = {{{0}}}, y22[Max_Num][Max_Num][Max_Num] = {{{0}}};
第一次分解即将z分解为z=x+y，过程如下，很简单，不解释。
00030: /** the first division, according to z=x+y, x <= y */3.4 第二次称量过程
00031: void weight1()
00032: {
00033: int z = total;
00034: int i = 0, j = 0, k = 0, w = 0;
00035:
00036: for (k = 0; k < Max_Num; k++)
00037: {
00038: w = ws[k];
00039: x[k] = (z - w)/2;
00040: y[k] = (z + w)/2;
00041: if (x[k] % 2!= 0) //no need to judge y[k]
00042: x[k] = y[k] = 0;
00043: }
00044: }
第二次称量过程如下。注意其中的限制规则，简化了后续的搜索过程，也避免了后续的重复搜索。代码中的注释已经很清楚，此处不再解释。
00046: /** the second division, according to x=x1+x2, y=y1+y2, x1<=x2, y1<=y23.5 第三次称量过程
00047: for x[i], x[i] = x1[i][k] + x2[i][k]
00048: for y[i], y[i] = y1[i][k] + y2[i][k]
00049: do them in the same loop to reduce the occurrence time of for- loop
00050: */
00051: void weight2()
00052: {
00053: int i = 0, j = 0, k = 0, w = 0;
00054:
00055: for (i = 0; i < Max_Num; i++)
00056: {
00057: if (x[i] == 0) //no need to judge y[i]
00058: continue;
00059:
00060: for (k = 0; k < Max_Num; k++)
00061: {
00062: w = ws[k];
00063:
00064: x1[i][k] = (x[i] - w)/2;
00065: x2[i][k] = (x[i] + w)/2;
00066: if (x1[i][k] % 2!= 0) //no need to judge x2[i][k]
00067: x1[i][k] = x2[i][k] = 0;
00068:
00069: if (x[i] == y[i]) //to avoid repeatance
00070: continue;
00071:
00072: y1[i][k] = (y[i] - w)/ 2;
00073: y2[i][k] = (y[i] + w)/2;
00074: if (y1[i][k] % 2!= 0) //no need to judge y2[i][k]
00075: y1[i][k] = y2[i][k] = 0;
00076: }
00077: }
00078: }
第三次称量过程如下。注意其中的限制规则，可以简化后续的搜索过程。同上，此处不再解释。
00079:3.6 如何输出？
00080: /** the third division, according to
00081: x1=x11+x12, y1=y11+y12, x11<=x12, y11<=y12
00082: x2=x21+x22, y2=y21+y22, x21<=x22, y21<=y22
00083: for x1[i][j], x1[i][j] = x11[i][j][k] + x12[i][j][k]
00084: for x2[i][j], x2[i][j] = x21[i][j][k] + x22[i][j][k]
00085: for y1[i][j], y1[i][j] = y11[i][j][k] + y12[i][j][k]
00086: for y2[i][j], y2[i][j] = y21[i][j][k] + y22[i][j][k]
00087: do them in the same loop to reduce the occurrence time of for- loop
00088: */
00089: void weight3()
00090: {
00091: int i = 0, j = 0, k = 0, w = 0;
00092:
00093: for (i = 0; i < Max_Num; i++)
00094: {
00095: if (x[i] == 0) //no need to judge y[i]
00096: continue;
00097:
00098: for (j = 0; j < Max_Num; j++)
00099: {
00100: for (k = 0; k < Max_Num; k++)
00101: {
00102: w = ws[k];
00103:
00104: if (x1[i][j] != 0) //divide x1[i][j]
00105: {
00106: x11[i][j][k] = (x1[i][j] - w)/2;
00107: x12[i][j][k] = (x1[i][j] + w)/2;
00108: if (x11[i][j][k]%2!= 0) //x11[i][j][k] and x12[i][j][k] must be even
00109: x11[i][j][k] = x12[i][j][k] = 0;
00110: }
00111:
00112: if (x2[i][j] != 0 && x1[i][j] != x2[i][j]) //divide x2[i][j], and to avoid repeatance
00113: {
00114: x21[i][j][k] = (x2[i][j] - w)/2;
00115: x22[i][j][k] = (x2[i][j] + w)/2;
00116: if (x21[i][j][k]%2!= 0) //x21[i][j][k] and x22[i][j][k] must be even
00117: x21[i][j][k] = x22[i][j][k] = 0;
00118: }
00119:
00120: if (y1[i][j] != 0) //divide y1[i][j]
00121: {
00122: y11[i][j][k] = (y1[i][j] - w)/2;
00123: y12[i][j][k] = (y1[i][j] + w)/2;
00124: if (y11[i][j][k]%2!= 0) //y11[i][j][k] and y12[i][j][k] must be even
00125: y11[i][j][k] = y12[i][j][k] = 0;
00126: }
00127:
00128: if (y2[i][j] != 0 && y1[i][j] != y2[i][j]) //divide y2[i][j], and to avoid repeatance
00129: {
00130: y21[i][j][k] = (y2[i][j] - w)/2;
00131: y22[i][j][k] = (y2[i][j] + w)/2;
00132: if (y21[i][j][k]%2!= 0) //y21[i][j][k] and y22[i][j][k] must be even
00133: y21[i][j][k] = y22[i][j][k] = 0;
00134: }
00135: }
00136: }
00137: }
00138: }
为什么要设计这样的数据结构，主要的目的是为了保存称量过程中的分解结果，但保存分解结果的目的也是为了程序输出，能够将整个分解步骤都输出。代码请参考附录1。
3.7 输出结果
结果如下，程序可以同时输出所有的分解结果和正确的分解结果，此处只列出正确的结果，完整打印结果请参考附录2。
-------------------------------------可以看出，这个程序的输出结果和第2节从数学角度分析得到的结果完全相同。
the results of all correct divisions:
-------------------------------------
280 = 140 + 140
140 = 70 + 70
70 = 30 + 40
280 = 138 + 142
138 = 62 + 76
62 = 24 + 38
280 = 138 + 142
138 = 62 + 76
76 = 38 + 38
280 = 138 + 142
142 = 66 + 76
66 = 24 + 42
280 = 138 + 142
142 = 62 + 80
80 = 38 + 42
3.8 讨论
至此，一个纯数学的计算程序介绍已经结束，该方法使用若干个一维、二维、三维数组保存分解结果。该方法数组定义较多，如果加上别的条件，例如再多一次称量，很难扩展。下面介绍另一种数据结构比较简单的方法，从本节的方法改进而来。
上一节 下一节
最新评论