没有合适的资源?快使用搜索试试~ 我知道了~
分酒问题
资源推荐
资源详情
资源评论
1 / 44
目录
一、问题重述 .................................................. 4
问题背景 ........................................................ 4
问题一 .......................................................... 4
问题二 .......................................................... 4
问题三 .......................................................... 4
二、符号说明 .................................................. 5
三、问题分析 .................................................. 6
3.1 问题一 ....................................................... 6
3.2 问题二 ....................................................... 6
3.3 问题三 ....................................................... 7
四、基本假设 .................................................. 7
五、模型的建立与求解 ........................................... 8
5.1 问题一 ....................................................... 8
5.1.1 模型的建立 ............................................... 8
5.1.1.1 有向网络模型的建立 ................................... 8
5.1.1.2
E
的划分 ............................................. 8
5.1.1.3 算法设计 ............................................. 9
5.1.2 模型求解及结果分析 ...................................... 10
5.1.2.1 目标为(4, 4, 4, 0)的求解 ............................ 10
5.1.2.2 目标为(3, 3, 3, 3)的求解 ............................ 16
5.1.2.3 目标为(5, 3, 2, 2)的求解 ............................ 18
5.2 问题二 ...................................................... 18
2 / 44
5.2.1 进制移位算法模型的建立 .................................. 18
5.2.2 实例效果展示 ............................................ 19
5.2.3 验证问题一中的结果 ...................................... 22
5.2.4 进行其他参数的尝试计算 .................................. 23
5.2.4.1 4 个瓶子的其他参数 .................................. 23
5.2.4.2 5 个瓶子 ............................................ 24
5.2.4.3 6 个瓶子 ............................................ 25
5.3 问题三 ...................................................... 26
5.3.1 猜想的提出 .............................................. 26
六、模型优缺点分析 .............................................27
6.1 问题一模型 .................................................. 27
优点 ......................................................... 27
缺点 ......................................................... 27
6.2 问题二模型 .................................................. 27
优点 ......................................................... 27
缺点 ......................................................... 27
七、模型推广和改进 .............................................28
7.1 问题一模型 .................................................. 28
7.2 问题二模型 .................................................. 28
八、参考文献 ..................................................28
附录:程序代码 .................................................29
MODEL PROJECT .................................................... 29
model.h ...................................................... 29
BFS.h ........................................................ 36
DFS.h ........................................................ 39
main.c ....................................................... 40
4 / 44
一、问题重述
问题背景
分酒问题是一个十分著名的智力问题。该问题是:给出酒瓶个数、各个酒瓶
容量、初始状态与目标状态,建立模型并设计算法求出倒酒的最少步数与所有采
用最少步数完成的方式。
问题一
已知酒瓶个数为 4,各个酒瓶容量为
(12,10,6,3)
,初始状态为
(12,0,0,0)
。建
立模型并设计算法实现目标状态为
(4,4,4,0)
、
(3,3,3,3)
和
(5,3,2,2)
并步数最少。
给出所有采用最少步数完成的方式。
问题二
设有
n
个酒瓶,各个酒瓶容量为
12
( , , , )
n
x x x
,初始状态为
10 20 0
( , , , )
n
x x x
。
建立模型并设计算法实现目标状态为
12
( , , , )
n
d d d
并步数最少。
问题三
根据已有模型,设计一个实例,要求最少完成步数不少于 13 步。给出从初
始状态到目标状态的详细实现步骤。
5 / 44
二、符号说明
符号 符号意义
G
有向网络模型图
V
结点集合
E
边集合
G
与初始结点连通的有向网络模型图
V
与初始结点连通的结点集合
E
与初始结点连通的边集合
i
v
结点
ij
e
边
0
v
初始结点
0
x
初始向量
x
容量向量
d
目标向量
Base
进制基数
State
状态数组
Edge
邻接数组
0s
初始状态
E
的划分
max
{} 最大值函数
Cei ling
() 向上取整函数
剩余43页未读,继续阅读
资源评论
Hanxy_Robin
- 粉丝: 12
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功