递归定理——输出自身源代码的程序

递归定理的一个重要推论,便是对于任意一个程序(图灵机),其都可以在内部获得自身的表述。用程序设计的语言:任意一个程序,都能够在程序内部的某个部分获得自身的源代码。

递归定理的定理内容:咕着

阅读更多

魔塔问题属于NPC的证明

magic-tower

通过证明:0-1背包问题可归约到标准魔塔问题,得出判定问题——标准魔塔问题是NPC的

标准魔塔问题的定义

通俗的讲,标准魔塔问题是魔塔的简化,只考虑生命、攻击、防御、红蓝宝石,数值无上限;不考虑钥匙、金币、商店、道具等。

阅读更多