小荷才露尖尖角,早有蜻蜓立上头
——小池
这个问题是这样描述的:
山西煤老板有 3000 吨煤,要运到 1000km 公里外的地方卖。他选择使用火车来运煤,每辆火车行驶一公里将消耗一吨煤,且火车载货上限为 1000 吨。
山西煤老板是个懂代码的家伙,你觉得它最多能拉多少煤过去?
且不论懂代码的人为什么要选择这么蛋疼的方式拉煤。。算了,直接把它抽象成数学问题。
山西煤老板的煤总量为 amount, 总里程为 totalTrail,火车载重为 load
这类问题存在隐藏条件:
1、假设每辆车都能装满货物,那么 amount 一定是 load 的整数倍。(因为这样可以最大化送达货物)
2、载物工具一定是每走一步消耗一个物品。(因为系数为 1 最简单,但是其实这个系数是灵活的,而且并不麻烦。)
这道题举的例子比较简单,心算也是无压力的,主要讲讲思路。
3000t 煤先用 3 辆车拉满,行至 1000/3(km) 处,三辆车一共损失了负载 1000t 煤,停车,把剩下的 2000t 煤装到 2 辆车里拉,再往前行驶 1000/2(km), 又损失了 1000t 煤。最后 1 车拉走这 1000t 煤。
∴amount = 1000-1000(1-1/2-1/3)=833.3t 煤
代码用递归来实现,解出两个出口:
1、递归... 最后一趟车了,拉完,结束
2、递归... 最后几辆车了,拉完,结束
- 1 package cn.train;
- 2 3 public class Train {
- 4 public static void main(String[] args) {
- 5 int huoWu = 3000;
- 6 int load = 1000;
- 7 double totaltrail = 1000;
- 8 huoWu = calculate(huoWu, load, 0.0, totaltrail);
- 9 System.out.println("剩余货物为" + huoWu);
- 10
- }
- 11 public static int calculate(int huoWu, int load, double trail, double totaltrail) {
- 12 int quantity = huoWu / load; //计算车数
- 13 //不到最后一车就拉完了
- 14
- if (totaltrail - trail < load / quantity) {
- 15 huoWu -= quantity * (totaltrail - trail);
- 16
- return huoWu;
- 17
- }
- 18 //最后一车了
- 19
- if (huoWu == load) {
- 20 huoWu -= (int)(totaltrail - trail);
- 21
- return huoWu;
- 22
- }
- 23 trail += load / quantity; //开始走了
- 24 huoWu -= load;
- 25
- return calculate(huoWu, load, trail, totaltrail);
- 26
- }
- 27
- }
来源: http://www.cnblogs.com/tomasman/p/6853185.html