我对这个作业问题很难过.我想我有正确的答案但不确定如何证明.我也不确定如何处理证据.这是问题所在:
Gekko教授一直梦想在北达科他州进行直排轮滑.他计划在美国2号公路上穿越该州,该公路从明尼苏达州东部边界的大福克斯(Grand Forks)经过蒙大拿州西部边境附近的威利斯顿(Williston).教授可以携带两升水,他可以在缺水前滑行数英里.(因为北达科他州相对平坦,教授不必担心上坡路段的饮用水比平坦或下坡路段更高)教授将在大福克斯开始用两升满水.他的官方北达科他州地图显示了美国2号沿线的所有地方,他可以在那里补充水量和这些地点之间的距离.
该教授的目标是尽量减少沿着他的路线穿越该州的停水次数.提供一种有效的方法,通过这种方法,他可以确定应该制作哪些止水器.证明您的策略产生最佳解决方案,并给出其运行时间.
我认为他应该选择他的站点,以便他在用完水之前走最远的距离.也就是说,在每一站,如果他继续前进,他将在下一站之前用完水.
我不知道该怎么办.我敢打赌,这已经做过,但我对CS的这个领域很新,可以使用一些指导.
你的算法是正确的。
尝试通过对经过的停靠点数量的归纳来证明以下内容。 经过每个水点后，没有其他策略可以减少停留次数，并且在停留次数相同的情况下，没有其他策略可以给你留下更多的水。
在 0 止损处，所有策略都是相等的，因此证明该陈述是微不足道的。
如果按照这个策略你不停下来喝酒，结果很容易证明。
如果您确实在停靠点喝酒，则根据该陈述在前一停靠点为真这一事实，您可以证明另一个策略上次进行了更多停靠（因此它们在停靠点上没有领先，并且不能在下一站上领先）水，因为你刚刚得到了水），否则其他策略也必须同样刚刚得到水（否则他们将在下一站之前耗尽水）。
这足以填写归纳证明。
如果您对正式证明所需的内容以及如何进行证明的概念感到困惑，请参阅我如何进行证明。我还在博客中介绍了我使用该讲义的经验。