锐客网

  1. 首页 > it技术 > >

编程珠玑-第二章旋转算法篇

编程珠玑第二章比较精髓，开篇三个题目 1：给定一个包含32位整数的顺序文件，它至多包含40亿个这样的整数，并且整数的次序是随机的，请查找一下此文件中不存在的32位整数（至少必有一个遗漏，为什么？）。在有足够的主存的情况下，你会如何解决这个问题？如果可以使用若干外部临时文件但主存却只有上百个字节，你会如何解决这个问题？ 2：请将一个具有n个元素的一维向量向左旋转i个位置。例如，假设n=8,i=3,那么向量abcdefgh旋转之后的向量defghabc。，你有很精彩的方法么？ 3：给定一个英语单词词典，请找出所有的变位词集。例如，因为"pots","stop","tops"相互之间都是由另外一个单词的各个字母改变序列而构成的，因此这些词相互之间就是变位词。 下面我们来解决我个人的难题2。 1）杂耍算法。 这个算法很巧妙运用了i和n的最大公约数，那么原理是什么了？我最后在网上找到经典的论证方法。原文在此 点击打开链接 。如下： 这个算法在执行gcd（i,n）次后就停止了，为什么？ 先来了解一点数论知识（以下内容摘自《初等数论》，潘承洞著）：
1 同余：
设m不等于0, 若m|a-b,即 a-b=km, 则称m为模，a同余于b模m，以及b是a对模m的剩余。记作
。
2 同余类
对给定的模m，有且恰有m个不同的模m的同余类，他们是
0 mod m，1 mod m，…，（m-1）mod m。
3 完全剩余系
一组数y1,y2,…，ys称为是模m的完全剩余系，如果对任意的a有且仅有一个yj是a对模m的剩余，即a同余于yj模m。
由此可见0,1,2，…，m-1是一个完全剩余系。因此，如果m个数是两两不同余的，那么这m个数便是完全剩余系。
基于以上知识，我们可以证明这样一个事实，即如果i和n互质的话，那么序列：
0i mod n2i mod n3i mod n….(n-1)*i mod n
就包括了集合{0,1,2 … n-1}的所有元素。（下一个元素(n)*i mod n 又是0）
为什么？
【编程珠玑-第二章旋转算法篇】证明：
由于0,1,2，…，n-1本身是一个完全剩余系，即它们两两互不同余。设此序列为Xi（0<=i<=n-1），可得下式：

Xi≠Xj (mod n),
由于i与n是互质的，所以
Xi*i ≠i*Xj (mod n),这里由于不能打出不同余字符因此用不等于替代,因此i*Xi是m个互不同余数，那么可断定它们是完全剩余系。有了上面的结论，那么如果i和n互质，下面的赋值过程便能完成所有值的赋值（设数组为X[0..n-1],长度为n）：
t = X[0]
X[0] = X[i mod n]
X[i mod n] = X[2i mod n]
…….
X[(n-2)*i mod n] = X[(n-1)*i mod n]
X[ (n-1)*i mod n] = t。
因为以上操作已经把包括{0,1,…,n-1}所有元素放到了最终位置上，每次完成一个元素的放置。根据以上我们得到了一个中间结论，如果i和n互质，我们就可以一次完成。那么如果i和n不是互质的呢？ 自然的想法是利用我们已经得到的结论，让i和n互质，即让i’ = i/(gcd(i,n))，n’ = n/(gcd(i,n))。这样便构造了一对互质的数, i’和n’。这意味着把整个数组的每g=gcd(i,n)个元素组成块，如下所示：

这样，根据已得结论，我们可以一次获得最终答案，因为i’和n’互质，由于我们的单位是块元素，所以，必须要g次来完成块的移动，每次相当于把g中的一个元素移到最终位置上。所以总共需要g次移动，算法终止。□ 整个证明过程最巧妙的地方在于对i和n进行处理的时候，以及处理之后转换成块元素的这个地方，感觉很巧妙，这样的证明绝对秒杀什么陪集数目的说法，回味无穷。
下面是我的实现：

#include int gcd(int i, int n){ while(i != n){ if(i > n) i -= n; else n -= i; } return i; }template void turnleft(T a[],int i,int n) { int count = gcd(i,n); for(int var =0; var

2：转置算法。
这种算法比较直观，容易理解。应用的话，代码正确率也高些。
ab开始，转制a得到a'b，在转制b得到a'b'，然后转制整个a'b'得到（a'b')'实际上就是ba,产生了下面的代码
reverse(0,i-1); //cbadefgh reverse(i,n-1); //cbahgfed reverse(0,n-1); //defghabc 拓展问题：向量旋转函数将向量改为abc转换为cba？如何实现。（这个问题建模了如何交换非邻接内存块的问题） 思路如下： （a'b'c')' = cba 直观上比较，杂技算法对每个元素仅存取一次，而求逆要两次，那么杂技算法算法的速度要两倍于求逆。实际上当n比较大而旋转距离变长的时候， 由于杂技算法的高速缓存性能比较差，而求逆大部分操作为顺序读取，由于缓存局部性的影响，杂技算法的实际表现并不如求逆算法 。 3:内存块交换，递归的思想。算法描述很简单，就是实现比较难一点，看了好久才看懂。
#include template void Swap(T a[],int l,int r,int interval) { for(int i=0; i void swap_block(T a[],int interval,int n) { if((interval==0)||(interval==n)) return ; int i; int p = i = interval; int j= n-interval; while(i!=j) { if(i>j) { Swap(a,p-i,p,j); i-= j; } else { Swap(a,p-i,p+j-i,i); j-=i; } //printf("%s\n",a); } Swap(a,p-i,p,i); // printf("%s\n",a); } int main() { char a[] = "abcdefgh"; swap_block(a,3,8); printf("%s\n",a); return 0; }



感想：总觉得在算法面前，智商不够用，大牛们究竟是什么样的脑袋，虽然觉得算法这东西很大程度上就是熟能生巧的过程，但是如何思考，如何在不看帮助的情况下，自己做出一些有意义的见解，想法。看来有必要什么时候的去看看波西亚的《如何解题》这本书，提高提高。不过，其实现在慢慢的抓住细节，弄懂没一点知识，多少有了点感觉。加油！

    推荐阅读


    上一篇：OpenGL|LearnGL - 11.1 - 实现简单的Gouraud光照模型

    下一篇：51Nod|【概率DP】51Nod 1398 等公交