中科院研究生考试的算法题

(ducktemple joyfire)

　　已知一个长度为n的数组和一个整数k，并且只有一个用于交换的附加空间单元，用程序安排如何交换数组中的元素，尽量减少交换次数，得到和将原数组循环右移k次所得的相同的结果。输出交换以后的结果。

　　交换次数最多的就是一个一个循环右移；要减少次数，就是直接把元素放到右移k以后的位置(当然有可能到最右边还不够，又从左边数起)。每个元素只需要移动一次。但是如果你仔细思考实现方法，就会发现有一些问题需要解决。

　　经过讨论和优化，最终得到以下算法伪代码。也许还有更好的办法，希望交流

void main(){

　　//已知extern real array[n]和extern int k
　　//已知唯一一个用于交换的空间extern real ExchangeSpace

　　int divisor=GCD(n,k);
　　//函数GCD表示求最大公约数

　　int i,j;
　　int m=n/divisor-1;

　　for (i=1;i<=divisor;i++){
　　　　for (j=1;j<=m;j++){
　　　　　　myswap(i,j,k);
　　　　};
　　};
}//main()

void myswap(int i,int j,int k){

　　int next=(i+j*k)mod(n);
　　//求出循环右移k以后的位置，用mod就可以处理到最左边以后回到右边

　　ExchangeSpace=array[next];
　　array[next]=array[i];
　　array[i]=ExchangeSpace;
　　//交换
};

 

Index

中科院研究生考试的算法题(Mar. 26, 2003, by ducktemple joyfire)
  -->进一步说明(Apr. 1, 2003, by joyfire)
  -->智者常同渡一桥(Apr. 2, 2003, by lzl)