LLD 案例：自动售货机

自动售货机常和 ATM 放在一起考，二者都要处理“状态”和“找零”。区别在于售货机自己保管钱：顾客投进来的硬币放在哪里，取消时退什么，卖出去之后怎么找零，这些都要在设计里说清楚。

需求澄清

功能需求

1. 机器有若干货道（A1、A2……），每个货道一种商品、一个价格、若干库存。
2. 接受几种面额的硬币，实时显示已投金额；不认识的硬币直接退回。
3. 选择商品：钱够、有货、而且找得开零钱，才出货并找零。
4. 顾客随时可以取消，拿回自己投进去的硬币。
5. 运维可以补货、取钱、把机器设为停用。

非功能需求

• 不能收了钱不给货，也不能出了货却找不开零钱。
• 金额全部用整数（分）表示。

核心类

classDiagram
  accTitle: 自动售货机类图：状态、货道与找零
  class VendingMachine {
    -State state
    -Map slots
    -Map cash
    -List escrow
    +insert(int coin)
    +select(String code)
    +cancel() List
  }
  class State {
    <<enumeration>>
    IDLE
    HAS_MONEY
    OUT_OF_SERVICE
  }
  class Slot {
    -String product
    -int price
    -int count
  }
  class ChangeMaker {
    +makeChange(int amount, Map pool) List
  }
  VendingMachine --> State
  VendingMachine "1" *-- "many" Slot
  VendingMachine ..> ChangeMaker : uses

两笔钱要分开放：暂存区和钱箱

顾客投的硬币先进暂存区（escrow），机器自己的钱放在钱箱（cash）。分开放有两个好处：

• 取消时原样退回。退给顾客的就是他投进去的那几枚，不用临时计算怎么凑钱，也不会因为钱箱缺零钱而退不出。
• 成交是一步完成的。只有在确认能出货、能找零之后，才把暂存区并入钱箱、扣库存、吐找零。中途任何检查失败，状态都没变过，不需要回滚。

用到的设计模式

• 门面：投币口、按键和显示屏只和 VendingMachine 打交道，货道、钱箱和找零算法都藏在它后面。
• 用枚举实现的状态机：State 决定哪些操作合法：没投币不能选货，停用时不收硬币。这还不是状态模式。只有三个状态、每个检查一行，一个状态写一个类反而多出不少代码；后面“什么时候换成状态类”一节会讲什么时候该换。
• 暂存区是提交和回滚的边界：暂存区相当于一个事务。成交前顾客的钱一直单独放着；成交时先在副本上算好，再一次性提交；取消或检查失败时，把暂存区原样退回就是回滚。

核心代码

这里没有用 ATM 那一章的“一个状态一个类”，而是枚举加判断。状态只有三个，每个操作的合法性也只是一行检查，拆成状态类反而更啰嗦：

from dataclasses import dataclass
from enum import Enum, auto


class State(Enum):
    IDLE = auto()
    HAS_MONEY = auto()
    OUT_OF_SERVICE = auto()


@dataclass
class Slot:
    product: str
    price: int  # cents
    count: int


class VendingMachine:
    ACCEPTED = (200, 100, 50, 20, 10)  # cents

    def __init__(self, slots: dict[str, Slot], cash: dict[int, int]):
        self.slots = slots
        self.cash = cash                # coins the machine owns
        self.escrow: list[int] = []     # coins of the current customer
        self.state = State.IDLE

    def insert(self, coin: int) -> None:
        if self.state is State.OUT_OF_SERVICE or coin not in self.ACCEPTED:
            raise ValueError("coin rejected")       # it drops back into the tray
        self.escrow.append(coin)
        self.state = State.HAS_MONEY

    def cancel(self) -> list[int]:
        coins, self.escrow = self.escrow, []
        self.state = State.IDLE
        return coins                                # the very coins inserted

    def select(self, code: str) -> tuple[str, list[int]]:
        if self.state is not State.HAS_MONEY:
            raise RuntimeError("insert money first")
        slot = self.slots.get(code)
        if slot is None or slot.count == 0:
            raise RuntimeError("sold out")
        paid = sum(self.escrow)
        if paid < slot.price:
            raise RuntimeError(f"insert {slot.price - paid} more")
        pool = dict(self.cash)
        for coin in self.escrow:                    # inserted coins can go back out as change
            pool[coin] = pool.get(coin, 0) + 1
        change = make_change(paid - slot.price, pool)
        if change is None:
            raise RuntimeError("exact change only")  # escrow untouched: cancel still refunds
        for coin in change:                          # commit: nothing below can fail halfway
            pool[coin] -= 1
        self.cash, self.escrow = pool, []
        slot.count -= 1
        self.state = State.IDLE
        return slot.product, change

关键在 select 的顺序：先在副本上算找零，确认找得开，再一次性提交。找零时可以用顾客刚投的硬币，比如商品 1.5 元，顾客投了一枚 2 元，钱箱里正好有 0.5 元就够了。

找零算法

找零是“有限张数的硬币凑整”。每种面额张数有限，贪心可能失败（和 ATM 出钞是同一个问题），这里用一个小型动态规划，按一枚一枚的硬币做 0/1 选择，求张数最少的组合：

def make_change(amount: int, pool: dict[int, int]) -> list[int] | None:
    """Fewest coins adding up to amount, each coin in the pool used at most once."""
    best: dict[int, list[int]] = {0: []}
    for coin, n in pool.items():
        for _ in range(min(n, amount // coin)):
            for total, coins in list(best.items()):   # snapshot: this coin once per pass
                t = total + coin
                if t <= amount and (t not in best or len(best[t]) > len(coins) + 1):
                    best[t] = coins + [coin]
    return best.get(amount)

状态数不超过 amount 种可能的总额，找零金额一般只有几块钱，这个开销可以忽略。如果找不开，select 拒绝这笔交易，机器显示“请投零钱”，顾客可以继续投币或者取消。

什么时候换成状态类

枚举加判断的上限在于：状态一多，或者同一个操作在不同状态下的行为差别很大，判断就会散落到每个方法里。出现下面这些情况时，可以改成状态模式：

• 加入刷卡支付，多了“等待授权”“授权成功待出货”等状态；
• 出货失败需要重试或退款，多了“出货中”这个中间态；
• 维护模式下的按键有完全不同的含义（比如输入补货数量）。

扩展讨论

• 刷卡或扫码支付：抽出 PaymentMethod 策略。刷卡应先预授权，出货传感器确认商品掉落后再扣款；出货失败就撤销预授权。
• 出货失败：货道卡住时，传感器没检测到商品掉落，应退款并把该货道标记为故障。
• 一次买多件：暂存区的钱跨多次选择累计，最后统一找零。
• 远程监控：库存或零钱低于阈值时上报，运维按需补货。