算法：10元可以喝几瓶啤酒？

时间：2015-12-08 22:16:30 阅读：710 评论：0 收藏：0 [点我收藏+]

题目：
啤酒2块钱1瓶，
4个瓶盖换1瓶
2个空瓶换1瓶

问：10块钱可以喝几瓶？

什么语言实现并不重要，先要想好算法。然后在实现啊

=======================================================

gai + ping + jiu = 2, 4 * gai = 2, 2 * ping = 2, gai = 1/2, ping = 1, jiu = 1/2, 10 / jiu = 10 / (1/2) = 20

价值计算：
gai + ping + jiu = 2, 4 * gai = 2, 2 * ping = 2,
gai = 1/2, ping = 1, jiu = 1/2,

理想解：
10 / jiu = 10 / (1/2) = 20

瓶和盖不通用解：
10 = 5 * jiu + 5 * gai + 5 * ping
5 * gai + 5 * ping = 3 * jiu + 1 * gai + 1 * ping + 3 * gai + 3 * ping
4 * gai + 4 * ping = 3 * jiu + 3 * gai + 3 * ping
3 * gai + 3 * ping = 1 * jiu + 3 * gai + 1 * ping + 1 * gai + 1 * ping
4 * gai + 2 * ping = 2 * jiu + 2 * gai + 2 * ping
2 * gai + 2 * ping = 1 * jiu + 2 * gai + 1 * gai + 1 * ping
3 * gai + 1 * ping = 0 * jiu + 3 * gai + 1 * ping

3 + 3 + 1 + 2 + 1 = 10 * jiu, 3 * gai + 1 * ping

瓶和盖通用解：
10 = 5 * jiu + 5 * gai + 5 * ping
5 * gai + 5 * ping = 3 * jiu + 1 * gai + 1 * ping + 3 * gai + 3 * ping
4 * gai + 4 * ping = 3 * jiu + 3 * gai + 3 * ping
3 * gai + 3 * ping = 1 * jiu + 3 * gai + 1 * ping + 1 * gai + 1 * ping
4 * gai + 2 * ping = 2 * jiu + 2 * gai + 2 * ping
2 * gai + 2 * ping = 1 * jiu + 2 * gai + 1 * gai + 1 * ping
3 * gai + 1 * ping = 1 * jiu + 1 * gai + + 1 * gai + 1 * ping
2 * gai + 1 * ping = 1 * jiu + 1 * gai + 1 * ping

3 + 3 + 1 + 2 + 1 + 1 + 1 = 12 jiu, 1 * gai + 1 * ping
----------------------------------------------------------------------------------

价值计算：
gai + ping + jiu = 2, 4 * gai = 2, 2 * ping = 2,
gai = 1/2, ping = 1, jiu = 1/2,

超级理想解：
10 / jiu = 10 / (1/2) = 20

瓶和盖通用解：瓶和盖不通用情况的，符合实际的（最后买一瓶，最后剩1瓶1盖）理想解
10 = 5 * jiu + 5 * gai + 5 * ping
5 * gai + 5 * ping = 3 * jiu + 1 * gai + 1 * ping + 3 * gai + 3 * ping
4 * gai + 4 * ping = 3 * jiu + 3 * gai + 3 * ping
3 * gai + 3 * ping = 1 * jiu + 3 * gai + 1 * ping + 1 * gai + 1 * ping
4 * gai + 2 * ping = 2 * jiu + 2 * gai + 2 * ping
2 * gai + 2 * ping = 1 * jiu + 2 * gai + 1 * gai + 1 * ping
3 * gai + 1 * ping = 1 * jiu + 1 * gai + + 1 * gai + 1 * ping
2 * gai + 1 * ping = 1 * jiu + 1 * gai + 1 * ping

3 + 3 + 1 + 2 + 1 + 1 + 1 = 12 jiu, 1 * gai + 1 * ping

3 + 3 + 1 + 2 + 1 = 10 * jiu, 3 * gai + 1 * ping

现在问题来了，如何在瓶和盖不通用的情况下达到理想解

----------------------------------------------------------------------------------

价值计算：
gai + ping + jiu = 2,
4 * gai = 2, 2 * ping = 2,
gai = 1/2, ping = 1,
jiu = 2 - 1/2 - 1 = 1/2,

超级理想解：
10 / jiu = 10 / (1/2) = 20

瓶和盖通用解：瓶和盖不通用情况的，符合实际的（最后买一瓶，最后剩1瓶1盖）理想解
10 = 5 * jiu + 5 * gai + 5 * ping
5 * gai + 5 * ping = 3 * jiu + 1 * gai + 1 * ping + 3 * gai + 3 * ping = 4 * gai + 4 * ping
4 * gai + 4 * ping = 3 * jiu + 3 * gai + 3 * ping
3 * gai + 3 * ping = 2 * jiu + 1 * gai + 2 * gai + 2 * ping = 3 * gai + 2 * ping
3 * gai + 2 * ping = 1 * jiu + 3 * gai + 1 * gai + 1 * ping = 4 * gai + 1 * ping
4 * gai + 1 * ping = 1 * jiu + 1 * ping + 1 * gai + 1 * ping = 1 * gai + 2 * ping
1 * gai + 2 * ping = 1 * jiu + 1 * gai + 1 * gai + 1 * ping = 2 * gai + 1 * ping
2 * gai + 1 * ping = 1 * jiu + 1 * gai + 1 * ping

5 + 3 + 3 + 2 + 1 + 1 + 1 + 1 = 17 * jiu, 1 * gai + 1 * ping
验证：17 * 1/2 + 1 * 1/2 + 1 * 1 = 10 == 10

5 + 3 + 3 + 1 + 2 + 1 = 15 * jiu, 3 * gai + 1 * ping
验证：15 * 1/2 + 3 * 1/2 + 1 * 1 = 10 == 10

现在问题来了，如何在瓶和盖不通用的情况下达到理想解

=================================================================================

下面是一个网友用汇编做的题：

assume cs:cao,ds:data

data segment

kp dw 2 ;瓶
gai dw 4 ;盖
qian db 10 ; 钱
ping dw 0 ;总瓶数
data ends
cao segment
s:mov ax,data
mov ds,ax
mov dx,0 ; DX为盖子累加数
mov di,0 ;di为瓶累加数
mov cl,qian ;钱数
s0:sub cl,2 ;每次一瓶就是2元
inc ping ;总瓶数加1

mov si,ping ;SI为间接变量
sub si,di ;总瓶数-瓶子累加等于真值

cmp si,kp ;真值对比是否大于2
ja ok ;大于跳
kk:mov si,ping ; SI为间接变量
sub si,dx ;总盖子-累加盖子等于真值

cmp si,gai ;真值对比是否大于4
jcxz jiesu ;钱是否为0
jb s0 ;盖子是否小于，否不满足加瓶数条件
inc ping ;满足条件
add dx,4 ;累加盖子加4
jmp s0 ;循环
jiesu:mov ax,4c00h ;退出
int 21h
ok:inc ping ;总瓶子累加
add di,2 ;瓶子记录
jmp kk