C语言 扩展欧几里得算法代码

给定两个正整数m和n,我们计算它们的最大公因子d和两个整数a和b,使得a*m+b*n=d

算法流程
　　E1.置a'=b=1;a=b'=0;c=m,d=n;

　　E2.计算d和r,使得c=q*d+r;

　　E3.若r==0;则退出,当前已有a*m+b*n=d;

　　E4;c=d;d=r;t=a';a'=a;a=t-q*a;t=b';b'=b;b=t-q*b;返回E2.

证明

　　对于已有的m和n,假设m>n;如果刨除变量a,b,a',b';算法与欧几里得算法完全一样,为计算最大公约数的算法.

　　最终要求的为a*m+b*n=d=GCD(m,n);如果改式子成立由欧几里得算法可推出a'*n+b'*(m%n)=GCD(n,m%n);

　　因为GCD(m,n)=GCD(n,m%n);

　　所以a*m+b*n=a'*n+b'*(m%n)

　　　　　　　　=a'*n+b'*(m-(m/n)*n)

　　　　　　　　=a'*n+b'*m-b'*(m/n)*n

　　　　　　　　=b'*m+(a'-b'*(m/n))*n

　　所以a=b';b=a'-b'*(m/n);

　　可以推出根据a‘、b'可以计算a、b。

代码实现


代码如下:

void EGCD(int m,int n)
{
    int a,a1,b,b1,c,d,q,r,t;
    a1=b=1,a=b1=0,c=m,d=n;
    while(1)
    {
        q=c/d,r=c%d;
        if(r==0)
        {
            printf("(%d)*%d+(%d)*%d=%d\n",a,m,b,n,d);
            return;
        }
        c=d,d=r,t=a1,a1=a,a=t-q*a,t=b1,b1=b,b=t-q*b;
    }
}

赞 (0)

相关推荐

  • C语言实现的排列组合问题的通用算法、解决方法

    尽管排列组合是生活中经常遇到的问题,可在程序设计时,不深入思考或者经验不足都让人无从下手.由于排列组合问题总是先取组合再排列,并且单纯的排列问题相对简单,所以本文仅对组合问题的实现进行详细讨论.以在n个数中选取m(0<m<=n)个数为例,问题可分解为: 1. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止. 2. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m. 很明显,上述方法是一个递归的过程,也

  • 马尔可夫链算法（markov算法）的awk、C++、C语言实现代码

    1. 问题描述 马尔可夫链算法用于生成一段随机的英文,其思想非常简单.首先读入数据,然后将读入的数据分成前缀和后缀两部分,通过前缀来随机获取后缀,籍此产生一段可读的随机英文. 为了说明方便,假设我们有如下一段话:   复制代码 代码如下: Show your flowcharts and conceal your tables and I will be mystified. Show your tables and your flowcharts will be obvious. 假设前缀的长

  • c语言实现冒泡排序、希尔排序等多种算法示例

    实现以下排序 插入排序O(n^2) 冒泡排序 O(n^2) 选择排序 O(n^2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 希尔排序 O(n^1.25) 1.插入排序 O(n^2) 一般来说,插入排序都采用in-place在数组上实现.具体算法描述如下:⒈ 从第一个元素开始,该元素可以认为已经被排序⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置⒋ 重复步骤3,直到找到已排序的元素

  • c语言 汉诺塔算法代码

    复制代码 代码如下: #include<stdio.h> void move(char a,char b) {     printf("%c->%c\n",a,b); } void han(int n,char a,char b,char c) {     if(n>0)     {         han(n-1,a,c,b);         move(a,b);         han(n-1,c,b,a);     } } int main() {   

  • C语言实现魔方阵算法(幻方阵 奇魔方 单偶魔方实现)

    C语言实现魔方阵算法(幻方阵 奇魔方 单偶魔方实现)

    例如三阶魔方阵为: 魔方阵有什么的规律呢? 魔方阵分为奇幻方和偶幻方.而偶幻方又分为是4的倍数(如4,8,12--)和不是4的倍数(如6,10,14--)两种.下面分别进行介绍. 2 奇魔方的算法 2.1 奇魔方的规律与算法 奇魔方(阶数n = 2 * m + 1,m =1,2,3--)规律如下: 数字1位于方阵中的第一行中间一列:数字a(1 < a  ≤ n2)所在行数比a-1行数少1,若a-1的行数为1,则a的行数为n:数字a(1 < a  ≤ n2)所在列数比a-1列数大1,若a-1的列

  • C语言解决螺旋矩阵算法问题的代码示例

    C语言解决螺旋矩阵算法问题的代码示例

    赶集网校招就采用了螺旋输出矩阵作为程序题,要求将矩阵螺旋输出如: 图中6*6矩阵线条所示为输出顺序,如果输出正确的话应该输出1~36有序数字.  我想的是这么做的: #include <stdio.h> //#define LEN 1 //#define LEN 2 //#define LEN 3 #define LEN 4 void printClock(int a[][LEN]){//输出函数 int t; int i = 0, m = 0; int j = LEN, n = LEN; w

  • C语言快速幂取模算法小结

    C语言快速幂取模算法小结

    本文实例汇总了C语言实现的快速幂取模算法,是比较常见的算法.分享给大家供大家参考之用.具体如下: 首先,所谓的快速幂,实际上是快速幂取模的缩写,简单的说,就是快速的求一个幂式的模(余).在程序设计过程中,经常要去求一些大数对于某个数的余数,为了得到更快.计算范围更大的算法,产生了快速幂取模算法.我们先从简单的例子入手:求abmodc 算法1.直接设计这个算法: int ans = 1; for(int i = 1;i<=b;i++) { ans = ans * a; } ans = ans %

  • C语言实现字符串匹配KMP算法

    C语言实现字符串匹配KMP算法

    字符串匹配是计算机的基本任务之一. 举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"? 下面的的KMP算法的解释步骤 1. 首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较.因为B与A不匹配,所以搜索词后移一位. 2. 因为B与A不匹配,搜索词再往后移. 3. 就这样,直到字符

  • 对C语言中递归算法的深入解析

    对C语言中递归算法的深入解析

    许多教科书都把计算机阶乘和菲波那契数列用来说明递归,非常不幸我们可爱的著名的老潭老师的<C语言程序设计>一书中就是从阶乘的计算开始的函数递归.导致读过这本经书的同学们,看到阶乘计算第一个想法就是递归.但是在阶乘的计算里,递归并没有提供任何优越之处.在菲波那契数列中,它的效率更是低的非常恐怖. 这里有一个简单的程序,可用于说明递归.程序的目的是把一个整数从二进制形式转换为可打印的字符形式.例如:给出一个值4267,我们需要依次产生字符'4','2','6',和'7'.就如在printf函数中使用

  • C语言位图算法详解

    C语言位图算法详解

    本文详细讲述了位图算法的定义与C语言实现方法,分享给大家供大家参考之用.具体如下: 位图法定义: 位图法就是bitmap的缩写,所谓bitmap,是用每一位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况.通常是用来判断某个数据存不存在的. 例如,要判断一千万个人的状态,每个人只有两种状态:男人,女人,可以用0,1表示.那么就可以开一个int数组,一个int有32个位,就可以表示32个人.操作的时候可以使用位操作.   数据结构: unsigned int bit[N]; 在这个数组

随机推荐