使用Python解决一个编程竞赛

Question

我发现了这个问题，我认为解决这个问题会很有趣，但却不能真正想出一个正确的解决方案-

在一个房间里，有一个怪物N个正面，一个人(只有一个正面)。人类有两支激光枪。的第一枪，A在B开了第二枪，B摧毁了C2枪头开火时可能毁坏怪物和人类都是人头，但枪优先考虑怪物头高于人]。

同样，如果在射击之后怪物有一个正的非零值剩下多少头，怪物就会长出更多的头。怪物当枪A被使用时，长出G1头当B枪使用时，它会长出G2头。

问题是输入N, C1, C2, G1和G2，然后找出会是什么最短的组合人类必须使用的枪支选择(A或B)为了杀死怪物(怪物死了)当没有。头= 0)。[注:这个问题来自一个已经结束的编程比赛]

我试着用递归来解决这个问题，但发现自己对如何得到解决方案一无所知。所以，如果你能给一些如何解决这个问题的提示，那就太好了。

Answer 1

首先:Dijkstra's不是最优解:)

考虑到这句话:"枪可以同时摧毁怪物和人类的头"
我认为，如果你可以射击10个头，而怪物只有5个头，你不能杀死它，因为那样你也会死。对吗?

在任何情况下，任何解的形式都是:
ABABAABBABBB……(A和B的字符串)

在最后一击中杀死C1或C2头。每击中一次，你就击杀C1 - G1或C2 - G2头。

如果最后一击来自A，你必须用造成(C1-G1)或(C2-G2)伤害的射击摧毁N-A个头部。
如果最后一击来自B，你必须用造成(C1-G1)或(C2-G2)伤害的射击摧毁N-B个头部。

任何K都可以表示为:

X*i + Y*j = K

当然，X和Y必须是素数，等等。K个头可以被i次伤害X和j次伤害y摧毁

可以用扩展的最大公约数算法求出i和j的值。

解X = (C1-G1), Y = (C2-G2)和K =(一)
同时解出X = (C1-G1)， Y = (C2-G2)， K = (N-B)
最小的答案就是正确的答案:)

就是这样

Answer 2

啊，我看到你已经找到了一个解决方案在c++已经使用Dijkstra的算法:http://hashsamrat.blogspot.com/2010/10/surviving-monster-programming-problem.html

然而，你似乎在考虑"递归"和其他方法。

解决方案与实现是分开的。因此，你真正想做的是使用相同的算法(Dijkstra的，它只是宽度优先搜索，所以你首先访问最短路径)，但在python而不是c++中。

您可以逐行复制c++，使用python习惯用法使代码更清晰、更优雅。但你还是会用同样的算法。(或者，你可以谷歌一下人们在python中实现Dijkstra's的数百种方法。或者你也可以自己写;您所需要的只是一个优先级队列(参见wikipedia)，如果时间不是问题，您可以以列表字典的形式编写一个性能较差的优先级队列。

想想看，如果你说的"最短的选择集"只是指"最少的枪声"，那么你根本不需要Dijkstra;它只是宽度优先搜索(这相当于Dijkstra的所有边的权值为1)。

特别地，生成新节点的逻辑如下:

def howManyHeadsLeft(currentHeads, damage, regen):
    newHeads = heads - damage
    if {this results in blowing off our own head} and newHeads>0: #modify depending on assumptions
        # we killed ourselves without taking monster down with us
        return {} # the empty set of possible search nodes
    else:
        newHeads += regen
        # we could just say return {newHeads} here,
        # but that would be terribly slow to keep on searching the same
        # state over and over again, so we use a cache to avoid doing that
        # this is called dynamic programming
        if {we have never seen newHeads before}:
            return {newHeads}
        else
            return {}
def newSearchNodes(currentHeads):
    return howManyHeadsLeft(currentHeads, atypeDamage, atypeRegen) | howManyHeadsLeft(currentHeads, btypeDamage, btypeRegen)

搜索的"目标"条件是有足够的伤害杀死九头蛇而不杀死你自己(根据假设适当修改):

heads==1+atypeDamage or heads==1+btypeDamage

当然也有可能没有解决方案存在(两种类型的枪的回复>伤害)，在这种情况下，这个算法可能会永远运行，但可能会被修改为终止。