October 7, 2006

谈谈数组元素左旋问题(下)

上篇中 ,我给出了一些解决数组元素左移问题的不符合要求或很慢的解法。在下篇中,我将讲解3个很有“来头”(至少出现在《编程珠玑》里了:))的O(n)级算法。
第一个算法思想上和我曾经想到的一个直接插入元素的算法基本相同,也是通过递归地逐个放置数组元素来左旋数组的。只不过我使用的方法是逐个临时测试是否可以按照公式放置,而这个算法经过周密计算,直接给出了符合各种情况的通用下标计算方法:
对于任意的元素下标 i,它的新下标 i` = ((k - m) + i ) % k。
代码如下:

//先求最大公约数,其实有很多方法,这个叫“辗转相除法”
int facter (int i, int j) {
while (i != j) {
if (i > j) {
i -=j;
} else {
j -= i;
}
}
return i;
}
//元素互换函数,无聊。。。
void swap (int *n1, int *n2) {
int tmp;
tmp = *n1;
*n1 = *n2;
*n2 = *tmp;
}
void turn_left (int *a, int m, int k) {
int i, tmp, f;
k = k % m;
if (k == 0) {
return;
}
f = facter(m, k);
if (f == 1) {
i = 0;
do {
i = (i+k)%m;
swap(a, a+1);
} while (i != 0);
} else {
for (i = 0; i < tmp =" i;" tmp =" (tmp+k)%m;" href="http://lichray.blogspot.com/2006/09/blog-post_25.html">那篇文章中用图示详细分析了数组元素的位移过程。如果你想找到一点新的灵感,可以把一些代表元素的卡片(凯库勒?!)用线穿起来反复地排,看看开始时和结束时,数组产生了哪些变化:
似乎看不出什么端倪。。。但如果把每种颜色的线都反序一下,
呵,很漂亮啊。再分析一下——原来,要让数组元素左旋m位,只需先将数组全部反序,然后将下标0~m-1和m~k-1的两部分分别反序就行了!最快的算法居然就这么简单!
用Python表示一下(这个代码是可运行的):

def turn_left (a, m):
a.reverse()
a[:m].reverse()
a[m:].reverse()
return

C代码就不用写了吧,用上面那个swap()函数+循环将数组反序而已啊。
最后一个方法,说真的,我没看懂。。。据说利用了数论知识,也很快,原理和本文第一个其实区别不大,只是计算新下标的算法更先进了:

/*照抄编程珠玑,伪代码(汗~),懒得翻译。n是数组长度,r是左旋位数,gcd()函数计算最大公约数,for后面的式子表示i的取值范围。*/
for i = [0, gcd(r, n))
t = x[i]
j = i
loop
k = j + r
if k >= i
k -= n
if k == i
break
x[j] = x[k]
j = k
x[j] = t

还得好好学数学啊!理解这个会有时!
真希望所有的程序员(代码书写er就算了)人手一本《编程珠玑》(Programming Pearls),书中自有黄金物,早日摆脱索然无趣的代码!

2 comments:

Anonymous said...

phentermine 37.5 mg phentermine tiredness - phentermine results of weight loss

Anonymous said...

online phentermine phentermine online to buy - is the phentermine online the real stuff