[-]
这不是一个笑话,有法国的计算机科学家证明了,给煎饼排序,并且能最优化的翻转它们,是一个非常困难的难题。

如果你有两个大小不一样的煎饼同时放在锅里,你就必须不停的翻转他们,来使得它们两面都被煎到,并且火候刚好。如图。这里的问题便是,需要翻多少次。

并且在煎饼 = n 个的时候,最优的翻转数又是多少呐?这便是法国科学团队Informatique de 提出的问题,虽然这问题拿给真正做煎饼的大厨来说可能并没有这么难,但是科学家将其定位称了NP-HARD(不存在有效算法的非确定性多项式)。

据Informatique de 说他们目前只能搞定 n<=19 的问题,再往上便NP-HARD 了。 实际上这个问题,除了煎饼之外还有更实际的用途,例如基因组排序等等。 @oioi:擦,真不知道在说什么。还请达人讲解。

[ 广告 ]
赞一个 (4)

PREV :
NEXT :