最少交换次数题目（奖励发放完毕）

shaowu459

经统计，静听溪流公式正确且最短，在静听溪流作出公式总结后（注意说明是最少次数的理由）发放技术分奖励，其余公式正确者每人发放50财富值，已发放完毕。

静听溪流

shaowu459

奖励已发放完毕。

shaowu459

除了替换的方法，还有一种利用判断“环”个数的方法解决这个问题，具体公式的一种写法参考我在16楼的公式。下面具体说明一下用环判断最少交换次数的原理。在具体介绍之前，先说明一个基础点：假如BA想交换成AB，BA这两个字母只最少需要交换一次；假如CAB想变成ABC，最少只需要交换两次，也就是n个位置不同的字母最少需要n-1次交换就可以将位置换到位。有了这个基础，下面来做具体说明：

如下图，源字符第一个字母是C，在结果字符串中是第三个；回到源字符串，第三个字符是A，A在第二个字符串中是第一个；再回到源字符串，第一个是C。如果继续按上述方法查找，会发现就循环起来了，循环中只有字母A和C，不会影响其他字母，我们可以把两个字符串中的A和C看做一个环（环之间不交叉），只需要在源字符串中将他们两个互相交换位置，这两个字母就会到正确的位置上了。因为有AC两个字母，所以只需要交换一次。





同理，如下的字符串中CAF三个字母组成了一个环，源字符串中的这3个字母交换两次，这三个字母位置就都会正确，并且交换过程中不影响其他的字母。




根据上面的方法，继续找环，B字母的位置正确，不需要交换，自成一个环，交换次数是环里字母的数字个数1减去1，等于0次，也就是不需要交换。剩余ED组成一个环，需要交换一次。所以，最少的交换次数=CAF的两次+B的0次+ED的一次=3次。


单看每个环，将字母归到正确位置的最少交换次数就是字母数量-1。每个环的字母互相独立，如果在各个环直接交换字母，会导致交换次数增多。因此，按上述分环计算的方法能得到将字母位置全部交换正确的最少交换次数。



简单总结一下：
1）从字符串第一个字母开始，按位置查找环，位置正确的字母独立成环，每个环之间不交叉；
2）每个环的最少交换次数是环的字母个数n-1；
3）有一个环，最少交换次数就是字母个数-1，因此整个字符串的最少交换次数就是：字符串长度-环的个数。