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

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

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

 

 

Content

0. 问题

1. 一些方法

2. 从数学的角度分析

3. 能否编程计算?

4. 一个改进的方法

5. 再改进的方法

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

7. 一个更为简单的方法

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

 

11. 总结

 

本文首先给出各种答案 ,并从数学的角度分析该问题的分解方法 ( 2 ) ,且在 3 给出一个纯数学的计算程序 weight1.c ,该方法使用若干个一维、二维、三维数组保存分解结果。该方法数组定义较多,如果加上别的条件,例如再多一次称量,很难扩展。

 

4 介绍了一种利用树型结构来保存称量过程 ( 分解结果 ) 的方法。比起 3 数学的方法,该方法不需要那么多的数组定义, 数据结构统一、简单,且节省大量空间。但该方法也有缺点,例如,最终的正确解只有 5 个,但该方法同 3 的数学方法一样,计算了所有的有结果的解,共 37 个,也比较浪费。

 

5 是第 4 节树型结构保存称量过程方法的改进版本,即对第 3 次分解结果进行判断,只有当该称量过程满足目标时,才建立节点,包括第 2 层和第 3 层的节点。这样,没有分解结果的节点 ( 包括第 2 层和第 3 层的节点 ) 就不会被建立, 叶子节点全部是正确的分解结果。问题更直观,且节省了空间

 

6 从直接计算满足目标的第 3 次称量出发,即第 2 次分解 ( 称量 ) 后,直接将满足目标的第 3 次称量解求出,判断这个计算出来的第 3 次称量所用的砝码是否在砝码组合内。如果在,表明该次称量过程为所求的正确解;否则,放弃,继续判断。 该方法直接计算满足目标的第 3 次分解,更好理解,也进一步简化了分解过程。

 

7 从不保存每一称量结果的角度出发,利用回溯法对该问题进行分析,并将回溯法转化为普通编程。相比较前面几节的方法,本节的方法更为简单,只需要 3 层嵌套调用即可求出全部的正确解,且无需保存每一次称量结果即可输出这些正确的解。逻辑简单、直观,实现也简单, 应该是首选的方法

 

8 从程序编译、运行等方面,讨论了本文所有例子程序的自动编译、自动运行并保存运行结果的方法。

 

9 简单讨论了该问题的扩展。 10 简单讨论了笔者写作本文的体会。 11 ,即本文最后一节总结全文及本文讨论的各种方法。

 

Reference

< 计算机算法设计与分析 >

砝码称重问题 ( 阿波 )

编写 makefile ( 阿波 )

驾驭 makefile ( 李云 )

跟我一起写 makefile ( 陈皓 )

经典算法( 1 )—— 8 皇后问题求解(回溯法) ( 阿波 )


上一节

, ,


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