QQ扫一扫联系
积木游戏：设有n 个小木块排成一排，如下图：
游戏开始时，每个小木块向下的一面涂有红、黄、蓝三种颜色之中的一种（约定：0表示红色，1表示黄色，2表示兰色）。要求通过翻看与交换方式对小木块重新排列（翻看的规则为每个小木快只能看一次），最终成为下面的形状：
即相同颜色的木块排列在一起，设计一个翻看与交换的方案，使得用最少的交换次数实现上面的要求。
[算法描述] 翻看小木块时，可以从两端进行。
例如，设中间状态如下：
此时，可以从两个方向看，即从A或B处开始：
（1）若看A则有三种可能性：
为红色，则不用交换
为兰色，交换一次，即A与B交换
为黄色，交换两次，即C与B交换一次，然后A与C再交换一次
此时，平均交换次数为1。
（2）若看B，也有三种可能性：
为兰色，则不用交换
为红色，交换一次，即B与A交换。
为黄色，交换一次，即B与C交换。
此时，平均交换次数为2/3。
由此可见，从B处翻看直到游戏结束，次数最少符合题目要求。
[程 序]
