唉 昨天晚上看了两部电影，日志没更新。。。
昨天还在分治与递归，偶然间发现了一个求两个数最大公约数的算法。
欧几里德：
1
int GongYueShu(int m,int n)
2
{
3
4return ((n==0) ? m:GongYueShu(n,m%n));
5//辗转相除，欧几里得
6
}
只要一行，呵呵。
还有就是适合大数的二分法，stein算法：
1int gcd(int a,int b) //对于大数，stein算法
2{
3
if(a<b){//arrange so that a>b
4 int temp = a;
5 a = b;
6 b=temp;
7
}
8 if(b==0)//the base case
9 return a;
10 if(a%2==0 && b%2 ==0)//a and b are even
11 return 2*gcd(a/2,b/2);
12 if ( a%2 == 0)// only a is even
13 return gcd(a/2,b);
14 if ( b%2==0 )// only b is even
15 return gcd(a,b/2);
16 return gcd((a+b)/2,(a-b)/2);// a and b are odd
17}
也很巧妙，呵呵。
对了，对于昨天的三路划分快速排序，终于看懂了。
1void QuickSort(int *a, int left,int right)
2{
3 int i,j,k,p,q;
4 int pivot = a[right];
5 if(right<=left)return;
6 i=left-1;j=right;p=left-1;q=right;
7 while(1){
8 while(a[++i]<pivot)
9 if(i==j)break;
10 while(pivot<a[--j])
11 if(j==left)break;
12 if(i>=j)break;
13 myswap(a,i,j);
14 if(a[i]==pivot)
15 {
16 p++;myswap(a,p,i);
17 }
18 if(a[j]==pivot)
19 {
20 q--;myswap(a,q,j);
21 }
22 }
23 if(pivot>a[right])
24 {
25 myswap(a,i,right);
26 k=right-1;
27 }
28 else k=right;
29 //j--;i++; //加上就出错
30 while(k>=q&&i<=right)
31 {
32
33 myswap(a,k,i);k--;i++;
34 } //把左边等于pivot的元素移到中间
35 for(k=left;k<=p;k++,j--) //把右边等于pivot的元素移到中间
36 myswap(a,k,j);
37 QuickSort(a,left,j);
38 QuickSort(a,i,right);
39}
posted on 2010-07-20 12:57
douhui 阅读(206)
评论(0) 编辑 收藏 引用 所属分类:
算法初步