随笔-11  评论-1  文章-0  trackbacks-0
唉 昨天晚上看了两部电影,日志没更新。。。
昨天还在分治与递归,偶然间发现了一个求两个数最大公约数的算法。
欧几里德:
1int 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 阅读(205) 评论(0)  编辑 收藏 引用 所属分类: 算法初步

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理