基于java的用递归法十个人排队买一个五元的商品,五个人拿五元,五个人拿十元,可以给每个人都找零,假设售货员一开始没有零钱
时间: 2024-02-27 14:52:21 浏览: 58
这个问题可以使用递归实现,具体思路如下:
1. 定义一个递归函数,输入为当前队列中需要找零的人数、需要找的零钱数、已有的零钱数、队列中每个人持有的钱数。
2. 如果当前队列中需要找零的人数为0,则表示所有人都找零完成,返回true。
3. 如果需要找的零钱数为0,则表示当前队列中的人都已经找到了零钱,进入下一个递归,递归的输入参数为队列中需要找零的人数减1、需要找的零钱数为当前队列中下一个人持有的钱数与售货员手中的零钱数之差、已有的零钱数等于当前队列中下一个人持有的钱数。
4. 如果队列中第一个人持有的钱数小于等于售货员手中的零钱数,则尝试给他找零。找零的方法是,判断售货员手中是否有足够的零钱找给他,如果有,则进入下一个递归,递归的输入参数为队列中需要找零的人数减1、需要找的零钱数为当前队列中下一个人持有的钱数与售货员手中的零钱数之差、已有的零钱数等于当前队列中下一个人持有的钱数加上售货员手中的零钱数减去当前队列中第一个人持有的钱数。
5. 如果第一个人持有的钱数大于售货员手中的零钱数,则无法给他找零,返回false。
6. 如果以上所有条件都不满足,则表示无法完成找零,返回false。
下面是Java语言实现的代码片段:
```
public boolean makeChange(int num, int change, int cash, int[] queue) {
if (num == 0) {
return true;
}
if (change == 0) {
return makeChange(num - 1, queue[num - 1] - cash, queue[num - 1], queue);
}
if (queue[0] <= cash) {
if (makeChange(num, change - queue[0], cash - queue[0] + queue[num], queue)) {
return true;
}
}
if (cash >= 5 && makeChange(num, change - 5, cash - 5, queue)) {
return true;
}
if (cash >= 10 && change >= 10 && makeChange(num, change - 10, cash - 10, queue)) {
return true;
}
return false;
}
```
阅读全文