围成一圈随机交换位置

来源：百度知道 编辑：UC知道 时间：2024/05/18 09:25:58
M个人围成一圈，每分钟相邻的两个人可以交换位置（只能有一对交换）。求使n个人的顺序颠倒（即每个人左边相邻的人换到右边，右边相邻的人换到左边）所需的最少时间（分钟数）。 比如m=4,要2分钟，比如m=5,要4分钟，比如m=6,要6分钟，求一个计算公式或算法。

答案是：
奇为(n-1)*(n-1)/4;
偶为(n/2)*(n/2-1);
能否说明具体的缘由，清楚一点，谢谢高手们啊！

只提供奇数程序。最快的方法就是，按距离的长短选择从上面过还是从下面过。比如1234567.选择上路的有（17）1次间距0，（26）5次间距2，选择下路的有（35）3次间距1。
#include<stdio.h>
void main()
{
int n,t=0,i,j=0;
scanf("%d",&n);
if((n+1)%2==0)
{
j=2*((n+1)/4-1);
for(i=1;i<=(n+1)/4 && j>=0;i++)
{
t=2*j+1+t;
j=j-2;
}
printf("从上面移动的次数%d\n",t);
j=2*((n+1)/2-(n+1)/4-1)-1;
for(i=(n+1)/4+1;i<(n+1)/2 && j>=0;i++)
{
t=2*j+1+t;
j=j-2;
}
}
printf("%d\n",t);
}