C语言实现大整数的辗转相除法

冷不防 2022-03-31 14:52 288阅读 0赞

## **辗转相除法，** ##

**原理，**

先用小的一个数除大的一个数，得第一个余数；  
再用第一个余数除小的一个数，得第二个余数；  
又用第二个余数除第一个余数，得第三个余数；  
这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。  
  
**例如求1515和600的最大公约数，**

第一次：用600除1515，商2余315；  
第二次：用315除600，商1余285；  
第三次：用285除315，商1余30；  
第四次：用30除285，商9余15；  
第五次：用15除30，商2余0。  
因此1515和600的最大公约数是15。

**C语言实现小数的辗转相除法度娘上一搜都找得到，这里介绍一个大整数的辗转相除法，**

#include<stdio.h>
    #include<iostream>
    #include<string.h>
    #include<stdlib.h>
    using namespace std;
    #define Max 1000
    
    /*
    compare功能：
    用于判断len1、len2两个大整数的长度，看哪个比较长
    
    先length()判断两个大整数的长度
    然后进行比较
    len1< len2：返回false
    len1==len2：看谁的数更大，len1的大返回true
    len1> len2：直接返回true
    */
    bool compare(string m,string n)
    {
        int len1 = m.length();
        int len2 = n.length();
        if( len1 < len2 )
            return false;
        if( len1 == len2 )
        {
            for(int i=len1-1; i>=0; i--)
            {
                if( m[i] > n[i] )
                    return true;
                else if( m[i] < n[i] )
                    return false;
            }
        }
        return true;
    }
    
    /*
    大数减法---结果不包括小数点
    用长度为len1的大整数p1 减去 长度为len2的大整数p2
    结果存在p1中，返回值代表结果的长度
    不够减：返回-1
    正好够：返回0
    */
    int SubStract(int *p1, int len1, int *p2, int len2)
    {
        int i;
        if( len1 < len2 )
            return -1;
        if( len1 == len2 )
        {
            // 判断p1 > p2
            for( i=len1-1; i>=0; i-- )
            {
                if(p1[i] > p2[i])   // 若大，则满足条件，可做减法
                    break;
                else if(p1[i] < p2[i]) // 否则返回-1
                    return -1;
            }
        }
    
        for( i=0; i<=len1-1; i++ )  // 从低位开始做减法
        {
            p1[i] -= p2[i];         // 相减
            if(p1[i] < 0)           // 若是否需要借位
            {
                // 借位
                p1[i] += 10;
                p1[i+1]--;
            }
        }
    
        for( i=len1-1; i>=0; i-- )  // 查找结果的最高位
        {
            if( p1[i] )             //最高位第一个不为0
                return (i+1);       //得到位数并返回
        }
    
        return 0;                   //两数相等的时候返回0
    }
    
    /*
    大数除法---结果不包括小数点
    a 被除数
    b 除数
    sum  商，存放计算的结果，即a/b=sum
    返回数组sum的有效长度，即商的位数
    */
    int division(char a[],char b[],char sum[])
    {
        int i, j;
        int len1, len2;     // 大数位数
        int number;         // 两大数相差位数
        int n;              // Subtract函数返回值
        int c[Max] = {0};   // 被除数
        int d[Max] = {0};   // 除数
    
        len1=strlen(a); // 获得大数的位数
        len2=strlen(b);
    
        // 将数字字符转换成整型数，且翻转保存在整型数组中
        for( j=0, i=len1-1; i>=0; j++, i-- )  // 转换数a
            c[j] = a[i] - 48;
        for( j=0, i=len2-1; i>=0; j++, i-- )  // 转换数b
            d[j] = b[i] - 48;
    
        number = len1 - len2;    // 相差位数
        for( i=len1-1; i>=0; i-- )    // 将除数扩大，使得除数和被除数位数相等
        {                             // 若450 3 ， 会把3变成003，上面已反转
            if( i >= number )
                d[i] = d[i-number];
            else
                d[i] = 0;   // 低位置0
        }
    
        len2 = len1;
        for( i=0; i<=number; i++ )    // 重复调用，同时记录减成功的次数，即为商
        {
            while((n = SubStract(c, len1, d+i, len2-i)) >= 0)
            {
                len1 = n;        // 结果长度
            }
        }
    
        int x=0;
    
        for( i=len1-1; i>=0; i-- )
        {
            sum[x++] = c[i] + 48;
        }
        return len1;
    }
    
    int main()
    {
        int len;
        char a[Max] = {0};   // 第一个大数
        char b[Max] = {0};   // 第二个大数
        char sum[Max] = {0};    // 计算结果
        char summ[Max] = {0};
    
        cout<<"请输入两个正整数：\n";
        cin>>a>>b;
    
        if(!compare(a,b))
        {
            char num[Max];
            strcpy(num,a);
            strcpy(a,b);
            strcpy(b,num);
        }
        len = division(a,b,sum);
    
        if(len>0)
        {
            while(len>0)
            {
                len = division(b,sum,summ);
                strcpy(b,sum);
                strcpy(sum,summ);
                memset(summ,0,sizeof(summ));
            }
            cout<<"最大公约数为："<<b<<endl;
        }
        else if(len=0)
        {
            cout<<"最大公约数为："<<b<<endl;
        }
        else
            cout<<"1"<<endl;
        return 0;
    }

![20190103195222272.png][]

![20190103195509167.png][]

[20190103195222272.png]: /images/20220331/ab743aa1af80490aa909c52585526abf.png
[20190103195509167.png]: /images/20220331/d05df3b3effb4a2c9caac85a58424352.png