给定一个正整数n，计算出一组{0,1,2,...,n}的排列，使得这个排列的任何子序列都不能形成等差数列，比如 n=4时，(2, 0, 1, 4, 3)符合要求，但是n=6时，(0, 5, 4, 3, 1, 2)不符合要求，因为（5,4,3)(5,3,1)都是等差数列。

这个题目可以有一个nlgn的算法，首先我们注意到{偶数，奇数，奇数}，{偶数，偶数，奇数}是不可能形成等差数列的，那么给定一个n，然后将序列分成2部分：
{偶数列} {奇数列}
可以看出任何子序列，如果既有元素属于偶数列，又有元素属于奇数列，是不可能构成等差数列的。下面我们只要保证偶数列和奇数列各自的子序列不会形成等差数列。这很容易，我们只需要将偶数列的每个数除以2，这是又形成了一个{0,1,2,[n/2]}的序列，可以用前面的方法把这个也分成奇数偶数列。同理，对奇数列只需要减1除以2，也可以用前面的方法排列，如此递归下去，就可以形成满足要求的排列。

• Re:转载 (0) ecjtuQX 2008-07-31 14:37:10
• 这个算法是对的么？疑惑... (21) harry 2009-01-04 15:40:21