• 再设计几个扩展欧几里德算法C语言描述

    几种设计思路
    服务器君一共花费 20.062 ms 进行了 3 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    设计扩展欧几里德算法的程序描述 这个小节里,我们谈到了扩展欧几里德算法的PHP描述。但是鉴于PHP并不是有很强的代表性,这里再用C语言再描述一遍。

    思路还是一样,具体可以看前面一小节。先是用递归的方法:

    #include <stdio.h>
    #include <math.h>
    int x,y;
    int Euclid_Extend(int a,int b);
    int main()
    {
        int a,b,gcd;
        while(1)
        {
            printf("请输入两个整数,以空白字符分隔:\n");
            scanf("%d%d",&a,&b);
            if(0==a&&0==b)
            {
                printf("输入的数据有误,请重新输入!\n\n");
                continue;
            }
            gcd=Euclid_Extend(abs(a),abs(b));
            printf("%d和%d的最大公约数是%d\n",a,b,gcd);
            printf("%d=(%d)*(%d)+(%d)*(%d)\n\n",gcd,x*(a < 0?-1:1),a,y*(b < 0?-1:1),b);
        }
        return 0;
    }
    
    int Euclid_Extend(int a,int b)
    {
        int m,n;
        if(0==b)
        {
            x=1;
            y=0;
            return a;
        }
        else
        {
            n=Euclid_Extend(b,a%b);
            m=x;
            x=y;
            y=m-a/b*y;
            return n;
        }
    }
    

    可以自己在IDE跑一下,增加认识。

    如果按照PHP描述的思路,扩展欧几里德算法函数可以设计成这样:

    int exgcd(int a,int b,int &x,int &y)
    {
        if(b==0)
        {
            x=1;
            y=0;
            return a;
        }
        int r=exgcd(b,a%b,x,y);
        int t=x;
        x=y;
        y=t-a/b*y;
        return r;
    }
    

    这里用 C语言的全局变量代替地址传参 了。

    前面是用了递归的方法。非递归的函数如下:

    int exgcd(int m,int n,int &x,int &y)
    {
        int x1,y1,x0,y0;
        x0=1; y0=0;
        x1=0; y1=1;
        x=0; y=1;
        int r=m%n;
        int q=(m-r)/n;
        while(r)
        {
            x=x0-q*x1; y=y0-q*y1;
            x0=x1; y0=y1;
            x1=x; y1=y;
            m=n; n=r; r=m%n;
            q=(m-r)/n;
        }
        return n;
    }
    

    或者设置一个栈来保存辗转相除过程中的a/b。代码如下:

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    typedef struct Node
    {
        int num;
        struct Node *next;
    }*Link,Node;
    Link top=NULL;	//栈顶
    int Extend_Euclid(int a,int b);
    int main()
    {
        int a,b,gcd,temp;
        int x,y;
        Link p;
        while(1)
        {
            printf("请输入两个整数,以空白字符分隔:\n");
            scanf("%d%d",&a,&b);
            if(0==a&&0==b)
            {
                printf("输入的数据有误,请重新输入!\n\n");
                continue;
            }
            gcd=Extend_Euclid(abs(a),abs(b));
            printf("%d和%d的最大公约数是%d\n",a,b,gcd);
            x=1;
            y=0;
            while(top!=NULL)
            {
                temp=x;
                x=y;
                y=temp-top->num*y;
                p=top;
                top=top->next; //a/b退栈
                free(p);
            }
            printf("%d=(%d)*(%d)+(%d)*(%d)\n\n",gcd,x*(a < 0?-1:1),a,y*(b < 0?-1:1),b);
        }
        return 0;
    }
    
    int Extend_Euclid(int a,int b)
    {
        int r;
        Link p;
        if(0==b)
        return a;
        do
        {
            p=(Link)malloc(sizeof(Node));
            p->num=a/b;
            p->next=top;
            top=p;				//a/b进栈
            r=a%b;
            a=b;
            b=r;
        }
        while(r!=0);
        return a;
    }
    

    虽然改造成了非递归,仍然需要较大空间来保存中间值,在辗转相除次数较大时空间复杂度较高。要想提高效率,就要从改造算法出发考虑。寻求一种不使用倒推的算法。代码如下:

    #include <stdio.h>
    int Extend_Euclid(int a,int b,int* x,int* y);//扩展欧几里德算法
    int main()
    {
        int a,b,x,y,GCD;
        while (1)
        {
            printf("请输入a、b,以空白字符分隔:\n");
            scanf("%d%d",&a,&b);
            GCD=Extend_Euclid(a,b,&x,&y);
            printf("两数最大公约数是%d,x=%d y=%d\n\n",GCD,x,y);
        }
        return 0;
    }
    
    int Extend_Euclid(int a,int b,int* x,int* y)//扩展欧几里德算法
    {
        if(0==b)
        {
            *x=1;
            *y=0;
            return a;
        }
        int r;
        int x_i_2=1,y_i_2=0,x_i_1=0,y_i_1=1,x_i,y_i;
        while(r=a%b)
        {
            x_i=x_i_2-a/b*x_i_1;
            y_i=y_i_2-a/b*y_i_1;
            x_i_2=x_i_1;
            y_i_2=y_i_1;
            x_i_1=x_i;
            y_i_1=y_i;
            a=b;
            b=r;
        }
        *x=x_i;
        *y=y_i;
        return b;
    }
    

    与使用栈相比,只增加了x_i_2,y_i_2,x_i_1,y_i_1,x_i,y_i这六个中间变量,节省了空间。可见算法的选择对于程序的效率是至关重要的。计算机性能的提高对于运算速度的影响只有很少一部分,设计高效的算法才是提高程序运行效率的关键一步。

更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [Python程序设计] Tornado表单处理 3 个条目
  2. [Python程序设计] 从PHP到Python 3 个条目
  3. [数据库技术] MySQL常用自带函数 3 个条目
  4. [搜索引擎优化] 与百度权重有关的信息 2 个条目
  5. [Python程序设计] Django后台管理系统 2 个条目
  6. [智力开发与知识管理] 整体性学习策略 9 个条目
  7. [计算机算法] 两数交换的各种算法细节 2 个条目
  8. [移动开发] Android加载器Loaders 5 个条目
  9. [PHP程序设计] PHP中的Hash算法 3 个条目
  10. [PHP程序设计] PHP里的引用 5 个条目
  11. [JavaScript程序设计] Web实时通信技术名词解析 5 个条目
  12. [Python程序设计] Python语言概述 6 个条目
窗口 -- [博客]