[转]Futurama中的数学问题 —— 要引入几个新躯体才够？

yylxxch

这个貌似可以建模成线性代数中的序列，然后将打乱的重新排列，根据需要调换的最少次数决定需要添加多少个额外开销。
具体的一时说不清了==

yylxxch

发现一开始把问题复杂化了，原来所谓的两者换完就不能再交换是这么个意思==
那么提供一种方法：假设身体为ABCDE，对应灵魂不妨设为bcdea，且五人间已经不可互换。
引入X，先与E交换得到灵魂a，记为X（a），然后与A交换得到灵魂b，记为X（b），以此类推：当现状态为X（n）时，与N交换。则必然可以一直交换到最后一个，此例为与D交换得到X（e）。X与E交换过，故再引入Y，令X与Y交换得到Y（e），Y与E交换即可。

yylxxch

b.p.bravo 发表于 2010-11-16 17:47
题设是“给定 n 个人以及他们之前使用“心灵对换机”的记录”，没有说大脑混乱是链表升（降）序的。如果 ...

这个无所谓啊，随便找一个开始对换，得到A的灵魂下一轮就和A的身体对换，一直持续下去，必然可以只剩最后一个，再加入第二个机器即可，如上例：
X与A换，得到X（b）、A（x）
X与B换，得到X（d）、B（b）
X与D换，得到X（e）、D（d）
X与E换，得到X（c）、E（e）
Y与C换，得到Y（a）、C（Y）
X与C换，得到X（y）、C（c）
Y与A换，得到Y（x）、A（a）
最后XY呼唤全部完成~