[心得] 有多少种换饮料的方法

楼主: jurian0101 (Hysterisis)   2014-05-30 01:59:37
Math版的问题
饮料一瓶2元,4个瓶身能换1瓶,2个瓶盖也能换1瓶。今有20元,最多可以喝几瓶。
把题目改造成等价的东西,拥有的 (盖,身) 数量是一个状态
起始是(10,10),换盖子移动(-1,1),换瓶身移动(1,-3),不可以停留在X/Y轴上
稍作探讨可以发现最佳结果必然是最后停在(1,3)
瓶身值0.5元,瓶盖值1元,饮料本身值0.5元,因此可以喝到 (20-1-1.5)/0.5 = 35瓶
这时候就想,假设一天换一次,总共有几种独特的兑换(走格子点)的方法?
果断打开MMA
Clear[a]; a[_, _] = 0; (*除了有定义之外,默认值为零*)
(*a是个虚拟的阵列,实际上是tag 于 head "a"之下的百余个储存的定义。MMA像是
个巨大的表达式/规则比对引擎*)
a[10,10] = 1; a[11,7] = 1; a[12,4] = 1; a[13,1] = 1;
a[9,11] = 1; a[8,12] = 1; a[7,13] = 1; a[6,14] = 1; a[5,15] = 1;
a[4,16] = 1; a[3,17] = 1; a[2,18] = 1; a[1,19] = 1;
(*高中排组的捷径问题那技巧*)
out[x_, y_] := x < 1 || x > 13 || y < 1 || y > 19;
While[a[1, 3] == 0,
Do[
Do[
If[And[
a[x + 1, y - 1] != 0 || out[x + 1, y - 1],
a[x - 1, y + 3] != 0 || out[x - 1, y + 3]],
a[x, y] = a[x + 1, y - 1] + a[x - 1, y + 3]
], {y, 1, 20 - x}];
, {x, 1, 13}];
];
a[1, 3]
Transpose@(Reverse /@ Table[a[x, y], {x, 1, 13}, {y, 1, 19}]) //
MatrixForm
(*把电脑表格顺序改成我们惯看的x-y轴排列,就是行倒置,然后转置*)
结果: 186360 种,跟一个表格debug用
作者: LPH66 (-6.2598534e+18f)   2014-05-30 08:15:00
是说把迭代顺序倒过来的话就不用 While 了(这有一个名词叫动态规划, Dynamic Programming)
楼主: jurian0101 (Hysterisis)   2014-05-30 13:01:00
睡前五分钟的急急忙忙,就没去想效率问题了。
作者: ToMoveJizz ( )   2014-05-31 01:32:00
m(__)m

Links booklink

Contact Us: admin [ a t ] ucptt.com