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

晨曦之光 发布于 2012/03/09 14:12
阅读 114
收藏 0

本博客(http://blog.csdn.net/livelylittlefish)贴出作者(阿波)相关研究、学习内容所做的笔记,欢迎广大朋友指正!

 

 

Content

0.问题

1.一些方法

2.从数学的角度分析

3.能否编程计算?

4.一个改进的方法

5.再改进的方法

6.能否直接计算求出所有正确解?

7.一个更为简单的方法

7.1问题分析

7.2分解与搜索过程描述

7.3回溯法向普通编程的转化——简单的分解图

7.4讨论

8.所有代码的自动编译、运行

9.问题扩展

10.体会

11.总结

Reference

附录 1:数学分解的代码weight1.c

附录 2:数学分解程序weight1的运行结果

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

附录 4:再改进的方法的代码weight3.1.c/3.2.c/3.3.c

附录 5:再改进的方法的代码weight3.1.c/3.2.c/3.3.c的输出结果

附录 6:直接计算正确分解的代码weight4.c

附录 7:一个更简单的方法的代码weight5.1.c/5.2.c/5.3.c


7.一个更为简单的方法

 

2从数学的角度分析该问题的分解方法可知,分解方法的解是确定的,其解过程和解个数均是确定的。既然是确定的,那么很容易想到一个问题——哪种计算机算法能求出这些确定的解?

 

通过2的规则和解过程分析,可以确定,答案是肯定的。本节给出一个更为简单的方法分析分解方法的解过程。

 

7.1问题分析

 

2的称量过程可知,在每一次的称量中,对新产生的每一堆(实际上每次新产生2堆盐)盐都有5中可能的分解方法,如果3次称量后没有达到目标,则尝试下一个分解方法,当当前堆的5次分解方法全部尝试后仍没有达到目标,则尝试分解另一堆新产生的盐。

 

——这就是回溯法。

 

复习一下回溯法的基本思想:回溯法是基于对问题实例进行学习,有组织地检查和处理问题实例的解空间,并在此基础上对解空间进行归约和修剪的一种方法。对解空间很大的一类问题,这种方法特别有效。使用回溯法求解的问题特征:求解问题要分为若干步,且每一步都有几种可能的选择,而且往往在某个选择不成功时需要回头再试另外一种选择,如果到达求解目标则每一步的选择构成了问题的解,如果回头到第一步且没有新的选择则问题求解失败。

 

关于解空间,回溯法的详细叙述,可参考有关书籍和资料。关于回溯法的一个例子,可以参考经典算法(1——8皇后问题求解(回溯法)

 

对于2的讨论,假设保存称量结果,可以画出该问题的状态空间树(搜索树),第一次/第二次/第三次称量对应的节点分别为5/50/500个。因为太大,其中省略了部分向下分解,且对于第一次和第二次称量,只画出满足该次称量限制规则的分解,如下图(4.1节的图)

 

 

为什么第二次称量对应的节点由5变成了50个?第三次变成了500个?

——因为第一次只是对一堆盐进行分解(称量),即z=x+y,且该次分解可用5种砝码(请参考第2节砝码组合分析),故第一次称量对应5个节点。

第二次分解的时候可以对x或者y都进行分解,而每种分解又可以用5种砝码,因此第二次称量对应的节点数为5×2×5=50

同理,第三次称量对应的节点数为50×2×5=500。且这500个节点均是叶子节点。

 

7.2分解与搜索过程描述

 

分解与搜索过程如下。

 

(1)砝码的组合为:w0, w1, w2, ..., wn,满足w0,分解时按从小到大的顺序取砝码进行分解;

(2)wi(0<=i<=n)克的砝码将z克的盐分解为x克和y克的两堆,此处假设x<=y,有z=x+y

(3)wj(0<=j<=n)分解x,有x=x1+x2(假设x1<=x2)

(4)wk(0<=k<=n)分解x1,有x1=x11+x12(假设x11<=x12)

(5)x2+x11=heap1或者x2+x12=heap1,则该分解为正确的分解,输出该过程;否则,取下一个wk,继续分解x1

(6)wk已取完,则回溯分解x2(或者x2=x1,转(4))

(7)x2分解完毕,回溯取下一个wj,继续分解x

(8)wj已取完,则回溯分解y(或者x=y,转(2))

(9)y分解完毕,回溯取下一个wi,继续分解z

(10)直到wi也取完,分解过程结束。

 

7.3回溯法向普通编程的转化——简单的分解图

 

如果不保存称量结果,简单的分解图如下。注意,4对页节点不同时出现。

 

 

 

上述的分解与搜索过程即可转换为普通的编程,3个层次的嵌套调用即可解决问题,且无需保存每一次称量结果,即可输出全部正确的解。代码如下(文件名weight5.2.c)weight5.2.cweight5.1.c改进而来,weight5.3.cweight5.2.c改进而来,他们功能完全相同,可参考附录7

/** filename: weight5.2.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 direct-solving approach, that is, weight1()->weightx()->weightx1/weightx2
 */

#include <stdio.h>

int Max_Number = 5;
int ws[]={0, 4, 10, 14, 18};
int total = 280;
int heap1 = 100, heap2 = 180;

void weight1();
void weightx(int z, int x, int y);
void weighty(int z, int x, int y);
void weightxx(int z, int x, int y, int x1, int x2);
void weightyy(int z, int x, int y, int y1, int y2);
void print_result(int z, int x, int y, int _x, int x1, int x2, int _x1, int x11, int x12);


int main(/* int argc, char** argv */)
{
    printf("-------------------------------------\n");
    printf("the results of all correct divisions:\n");
    printf("-------------------------------------\n");
    weight1();
    return 0;
}

void weight1()  //divide z
{
    int k = 0, w = 0, x = 0, y = 0;
    int z = total;

    for (k = 0; k < Max_Number; k++)
    {
        w = ws[k];
        if ((z + w) % 2 != 0)
            continue;

        x = (z - w)/2;
        y = (z + w)/2;
        if (x % 2 != 0)
            continue;

        weightx(z, x, y);  //divide x
        if (y != x)
            weighty(z, x, y);  //divide y
    }    
}

void weightx(int z, int x, int y)  //divide x
{
    int k = 0, w = 0, x1 = 0, x2 = 0;

    for (k = 0; k < Max_Number; k++ )
    {
        w = ws[k];
        if ((x + w) % 2 != 0)
            continue;

        x1 = (x - w)/2;
        x2 = (x + w)/2;
        if (x1 %2 != 0)
            continue;

        weightxx(z, x, y, x1, x2);  //divide x1
        if (x2 != x1)
            weightxx(z, x, y, x2, x1);  //divide x2
    }
}

void weighty(int z, int x, int y)  //divide y
{
    int k = 0, w = 0, y1 = 0, y2 = 0;

    for (k = 0; k < Max_Number; k++ )
    {
        w = ws[k];
        if ((y + w) % 2 != 0)
            continue;

        y1 = (y - w)/2;
        y2 = (y + w)/2;
        if (y1 %2 != 0)
            continue;

        weightyy(z, x, y, y1, y2);  //divide y1
        if (y2 != y1)
            weightyy(z, x, y, y2, y1);  //divide y2
    }
}

//x=x1+x2, x1<=x2, divide x1 or x2
void weightxx(int z, int x, int y, int x1, int x2)
{
    int k = 0, w = 0, x11 = 0, x12 = 0;

    for (k = 0; k < Max_Number; k++ )
    {
        w = ws[k];
        if ((x1 + w) % 2 != 0)
            continue;

        x11 = (x1 - w)/2;
        x12 = (x1 + w)/2;
        if (x11 %2 != 0)
            continue;

        if (x11 + x2 == heap1 || x12 + x2 == heap1)
        {
            if (x1 <= x2)
                print_result(z, x, y, x, x1, x2, x1, x11, x12);
            else
                print_result(z, x, y, x, x2, x1, x1, x11, x12);
            break;
        }
    }
}

//y=y1+y2, y1<=y2, divide y1 or y2
void weightyy(int z, int x, int y, int y1, int y2)
{
    int k = 0, w = 0, y11 = 0, y12 = 0;

    for (k = 0; k < Max_Number; k++ )
    {
        w = ws[k];
        if ((y1 + w) % 2 != 0)
            continue;

        y11 = (y1 - w)/2;
        y12 = (y1 + w)/2;
        if (y11 %2 != 0)
            continue;

        if (y11 + y2 == heap1 || y12 + y2 == heap1)
        {
            if (y1 <= y2)
                print_result(z, x, y, y, y1, y2, y1, y11, y12);
            else
                print_result(z, x, y, y, y2, y1, y1, y11, y12);
            break;
        }
    }
}

/**
 * z = x + y, x <= y
 * _x = x1 + x2, x1 <= x2, _x represents x or y
 * _x1 = x11 + x12, x11 <= x12, _x1 represents x1 or x2
 */
void print_result(int z, int x, int y, 
    int _x, int x1, int x2, 
    int _x1, int x11, int x12)
{
    printf("%d = %d + %d\n", z, x, y);
    printf("%d = %d + %d\n", _x, x1, x2);
    printf("%d = %d + %d\n\n", _x1, x11, x12);
}
7.4 讨论

 

相比较前面几节的方法,本节的方法更为简单,只需要3层嵌套调用即可求出全部的正确解,且无需保存每一次称量结果即可输出这些正确的解。逻辑简单、直观,实现也简单,应该是首选的方法。

笔者将这个解法放在此处,其主要目的是希望通过循序渐进的思路来找到问题的最佳方法,同时希望能给读者一些启发。

 

附录7:一个更简单的方法的代码weight5.1.c/5.3.c

/** filename: weight5.1.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 direct-solving approach, that is, weight1()->weightx()->weightx1/weightx2
 */

#include <stdio.h>

int Max_Number = 5;
int ws[]={0, 4, 10, 14, 18};
int total = 280;
int heap1 = 100, heap2 = 180;

void weight1();
void weightx(int z, int x, int y);
void weighty(int z, int x, int y);
void weightx1(int z, int x, int y, int x1, int x2);
void weightx2(int z, int x, int y, int x1, int x2);
void weighty1(int z, int x, int y, int y1, int y2);
void weighty2(int z, int x, int y, int y1, int y2);
void print_result(int z, int x, int y, int _x, int x1, int x2, int _x1, int x11, int x12);


int main(/* int argc, char** argv */)
{
    printf("-------------------------------------\n");
    printf("the results of all correct divisions:\n");
    printf("-------------------------------------\n");
    weight1();
    return 0;
}

void weight1()  //divide z
{
    int k = 0, w = 0, x = 0, y = 0;
    int z = total;

    for (k = 0; k < Max_Number; k++)
    {
        w = ws[k];
        if ((z + w) % 2 != 0)
            continue;

        x = (z - w)/2;
        y = (z + w)/2;
        if (x % 2 != 0)
            continue;

        weightx(z, x, y);  //divide x
        if (y != x)
            weighty(z, x, y);  //divide y
    }    
}

void weightx(int z, int x, int y)  //divide x
{
    int k = 0, w = 0, x1 = 0, x2 = 0;

    for (k = 0; k < Max_Number; k++ )
    {
        w = ws[k];
        if ((x + w) % 2 != 0)
            continue;

        x1 = (x - w)/2;
        x2 = (x + w)/2;
        if (x1 %2 != 0)
            continue;

        weightx1(z, x, y, x1, x2);  //divide x1
        if (x2 != x1)
            weightx2(z, x, y, x1, x2);  //divide x2
    }
}

void weighty(int z, int x, int y)  //divide y
{
    int k = 0, w = 0, y1 = 0, y2 = 0;

    for (k = 0; k < Max_Number; k++ )
    {
        w = ws[k];
        if ((y + w) % 2 != 0)
            continue;

        y1 = (y - w)/2;
        y2 = (y + w)/2;
        if (y1 %2 != 0)
            continue;

        weighty1(z, x, y, y1, y2);  //divide y1
        if (y2 != y1)
            weighty2(z, x, y, y1, y2);  //divide y2
    }
}

void weightx1(int z, int x, int y, int x1, int x2)  //x=x1+x2, divide x1
{
    int k = 0, w = 0, x11 = 0, x12 = 0;

    for (k = 0; k < Max_Number; k++ )
    {
        w = ws[k];
        if ((x1 + w) % 2 != 0)
            continue;

        x11 = (x1 - w)/2;
        x12 = (x1 + w)/2;
        if (x11 %2 != 0)
            continue;

        if (x11 + x2 == heap1 || x12 + x2 == heap1)
        {
            print_result(z, x, y, x, x1, x2, x1, x11, x12);
            break;
        }
    }
}

void weightx2(int z, int x, int y, int x1, int x2)  //x=x1+x2, divide x2
{
    int k = 0, w = 0, x21 = 0, x22 = 0;

    for (k = 0; k < Max_Number; k++ )
    {
        w = ws[k];
        if ((x2 + w) % 2 != 0)
            continue;

        x21 = (x2 - w)/2;
        x22 = (x2 + w)/2;
        if (x21 %2 != 0)
            continue;

        if (x21 + x1 == heap1 || x22 + x1 == heap1)
        {
            print_result(z, x, y, x, x1, x2, x2, x21, x22);
            break;
        }
    }
}

void weighty1(int z, int x, int y, int y1, int y2)  //y=y1+y2, divide y1
{
    int k = 0, w = 0, y11 = 0, y12 = 0;

    for (k = 0; k < Max_Number; k++ )
    {
        w = ws[k];
        if ((y1 + w) % 2 != 0)
            continue;

        y11 = (y1 - w)/2;
        y12 = (y1 + w)/2;
        if (y11 %2 != 0)
            continue;

        if (y11 + y2 == heap1 || y12 + y2 == heap1)
        {
            print_result(z, x, y, y, y1, y2, y1, y11, y12);
            break;
        }
    }
}

void weighty2(int z, int x, int y, int y1, int y2)  //y=y1+y2, divide y2
{
    int k = 0, w = 0, y21 = 0, y22 = 0;

    for (k = 0; k < Max_Number; k++ )
    {
        w = ws[k];
        if ((y2 + w) % 2 != 0)
            continue;

        y21 = (y2 - w)/2;
        y22 = (y2 + w)/2;
        if (y21 %2 != 0)
            continue;

        if (y21 + y1 == heap1 || y22 + y1 == heap1)
        {
            print_result(z, x, y, y, y1, y2, y2, y21, y22);
            break;
        }
    }
}

/**
 * z = x + y, x <= y
 * _x = x1 + x2, x1 <= x2, _x represents x or y
 * _x1 = x11 + x12, x11 <= x12, _x1 represents x1 or x2
 */
void print_result(int z, int x, int y, 
    int _x, int x1, int x2, 
    int _x1, int x11, int x12)
{
    printf("%d = %d + %d\n", z, x, y);
    printf("%d = %d + %d\n", _x, x1, x2);
    printf("%d = %d + %d\n\n", _x1, x11, x12);
}

/** filename: weight5.3.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 direct-solving approach, that is, weight1()->weightx()->weightx1/weightx2
 */

#include <stdio.h>

#define DIVIDE(k, w, z, x, y)     \
        w = ws[(k)];                     \
        if (((z) + (w)) % 2 != 0)   \
            continue;                    \
                                               \
        x = ((z) - (w))/2;              \
        y = ((z) + (w))/2;              \
        if ((x) % 2 != 0)               \
            continue;

int Max_Number = 5;
int ws[]={0, 4, 10, 14, 18};
int total = 280;
int heap1 = 100, heap2 = 180;

void weight1();
void weightx(int z, int x, int y);
void weighty(int z, int x, int y);
void weightxx(int z, int x, int y, int x1, int x2);
void weightyy(int z, int x, int y, int y1, int y2);
void print_result(int z, int x, int y, int _x, int x1, int x2, int _x1, int x11, int x12);


int main(/* int argc, char** argv */)
{
    printf("-------------------------------------\n");
    printf("the results of all correct divisions:\n");
    printf("-------------------------------------\n");
    weight1();
    return 0;
}

void weight1()  //divide z
{
    int k = 0, w = 0, x = 0, y = 0;
    int z = total;

    for (k = 0; k < Max_Number; k++)
    {
        DIVIDE(k, w, z, x, y);

        weightx(z, x, y);  //divide x
        if (y != x)
            weighty(z, x, y);  //divide y
    }    
}

void weightx(int z, int x, int y)  //divide x
{
    int k = 0, w = 0, x1 = 0, x2 = 0;

    for (k = 0; k < Max_Number; k++ )
    {
        DIVIDE(k, w, x, x1, x2);

        weightxx(z, x, y, x1, x2);  //divide x1
        if (x2 != x1)
            weightxx(z, x, y, x2, x1);  //divide x2
    }
}

void weighty(int z, int x, int y)  //divide y
{
    int k = 0, w = 0, y1 = 0, y2 = 0;

    for (k = 0; k < Max_Number; k++ )
    {
        DIVIDE(k, w, y, y1, y2);

        weightyy(z, x, y, y1, y2);  //divide y1
        if (y2 != y1)
            weightyy(z, x, y, y2, y1);  //divide y2
    }
}

//x=x1+x2, x1<=x2, divide x1 or x2
void weightxx(int z, int x, int y, int x1, int x2)
{
    int k = 0, w = 0, x11 = 0, x12 = 0;

    for (k = 0; k < Max_Number; k++ )
    {
        DIVIDE(k, w, x1, x11, x12);

        if (x11 + x2 == heap1 || x12 + x2 == heap1)
        {
            if (x1 <= x2)
                print_result(z, x, y, x, x1, x2, x1, x11, x12);
            else
                print_result(z, x, y, x, x2, x1, x1, x11, x12);
            break;
        }
    }
}

//y=y1+y2, y1<=y2, divide y1 or y2
void weightyy(int z, int x, int y, int y1, int y2)
{
    int k = 0, w = 0, y11 = 0, y12 = 0;

    for (k = 0; k < Max_Number; k++ )
    {
        DIVIDE(k, w, y1, y11, y12);

        if (y11 + y2 == heap1 || y12 + y2 == heap1)
        {
            if (y1 <= y2)
                print_result(z, x, y, y, y1, y2, y1, y11, y12);
            else
                print_result(z, x, y, y, y2, y1, y1, y11, y12);
            break;
        }
    }
}

/**
 * z = x + y, x <= y
 * _x = x1 + x2, x1 <= x2, _x represents x or y
 * _x1 = x11 + x12, x11 <= x12, _x1 represents x1 or x2
 */
void print_result(int z, int x, int y, 
    int _x, int x1, int x2, 
    int _x1, int x11, int x12)
{
    printf("%d = %d + %d\n", z, x, y);
    printf("%d = %d + %d\n", _x, x1, x2);
    printf("%d = %d + %d\n\n", _x1, x11, x12);
}



上一节下一节

,,


原文链接:http://blog.csdn.net/livelylittlefish/article/details/6559840
加载中
返回顶部
顶部