精华内容
下载资源
问答
  • C语言求最大公约数

    2021-05-08 17:00:44
    C语言求最大公约数main函数1、辗转相除法2、枚举法3. 更相减损法(辗转相减法)4. stein算法 main函数 /* main方法: 用x、y来接收所输入两个数,调整两者大小,保证y > x; #include <stdio.h> int ...

    main函数

    /*
    	main方法:
    		用x、y来接收所输入两个数,调整两者大小,保证y > x; 
    
    #include <stdio.h>
    
    int main()
    {
    
    	int x, y;
    	printf ("请分别输入两个整数:");
    	scanf ("%d %d", &x, &y);
    	//保证y > x
    	if (x > y)
    	{
    		int temp;
    		temp = x;
    		x = y;
    		y = temp;
    	}
    	// 辗转相除法
    	metheo1(x,y);
    	// 枚举法
    	metheo2(x,y);
    	// 更相减损法(辗转相减法)
    	metheo3(x, y);
    	// stein算法(效率高)
    	metheo4(x, y);
    
    	return 0;
    }
    

    1、辗转相除法

    /*
    		辗转相除法:
    			原理:
    				令 y > x 保证y大于x;
    				a = y / x;	①
    				b = y % x;	②
    				由① ②可得:
    							y = ax + b;
    							所以(x,y)的公约数也就是(b,x)的公约数;
    				令f(x,y)表示x,y的公约数
    				则 f(x,y)= f(b,x);
    	*/
    
    void metheo1(int x, int y)
    {
    	int a, b;
    	do
    	{
    		a = y / x;
    		b = y % x;
    		if (b == 0)
    		{
    			printf("辗转相除法所得最大公约数是:%d\n",x);
    		}
    		else
    		{
    			y = x;
    			x = b;
    		}
    	} while (b);
    }
    

    2、枚举法

       /*
       	枚举法:
       		原理:
       			选取数a,a的取值从两者中较小的数开始选取
       			若不满足(y % a == 0 && x % a == 0)
       			则递减直至第一个满足条件的数出现即为最大公约数
       			printf("枚举法所得最大公约数是:%d\n", a);
       */
    
    void metheo2(int x, int y)
    {
    	int a = x;
    	for (a = x; a >= 1; a--)
    	{
    		if (y % a == 0 && x % a == 0)
    		{
    			printf("枚举法所得最大公约数是:%d\n", a);
    			break;
    		}
    	}
    }
    

    3. 更相减损法(辗转相减法)

    	/*
    		更相减损法(辗转相减法)
    			原理:(同余)
    				y = ap , x = bp
    				y 以及 x 都为奇数
    				其中p为最大公约数,a、b为相应倍数
    				则 y - x = (a - b)p,当a = b = 1时及y = x时,y = x = p即为最大公约数
    	*/
    
    void metheo3(int x, int y)
    {
    	int cnt = 0;
    	do
    	{
    		if (x % 2 == 0 && y % 2 == 0)
    		{
    			x = x / 2;
    			y = y / 2;
    			cnt++;
    		}
    		else
    		{
    			while (y != x)
    			{
    				int a = x;
    				x = y - x;
    				if (a < x)
    				{
    					int temp = x;
    					x = a;
    					a = temp;
    				}
    				y = a;
    			}
    			if (cnt == 0)
    			{
    				printf("用更相减损法所得的最大公约数为:%d\n",x);
    				cnt = 0;
    			}
    			else
    			{
    				printf("用更相减损法所得的最大公约数为:%d\n",2*cnt*x);
    			}
    			break;
    		}
    	} while (cnt);
    }
    
    

    4. stein算法

    该方法运行效率较高,后续笔者会单独写一篇文章介绍stein算法;
    
    展开全文
  • C语言求最大公约数GCD的算法C语言求最大公约数GCD的算法完整源码(定义,实现,main函数测试) C语言求最大公约数GCD的算法完整源码(定义,实现,main函数测试) #include <iostream> int gcd1( int a, int b...

    C语言求最大公约数GCD的算法完整源码(定义,实现,main函数测试)

    #include <iostream>
    
    
    int gcd1( int a, int b ) {
        while( b > 0 ) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
    
    int gcd2( int a, int b ) {
        if ( b == 0 ) return a;
        if ( a == 0 ) return b;
        return gcd2(b, a % b);
    }
    
    int gcd3( int a, int b ) {
        if ( a == 0 ) return b;
        if ( b == 0 ) return a;
        while ( a != b ) {
            if ( a > b ) {
                a = a-b;
            } else {
                b = b-a;
            }
        }
        return a;
    }
    
    int gcd4 ( int a, int b ) {
        if ( a == 0 ) return b;
        if ( b == 0 ) return a;
        if ( a == b ) return a;
        if ( a > b ) return gcd4(b, a-b);
        else  return gcd4(a, b-a);
    }
    
    int main()
    {
        int a, b;
        std::cout << "Enter number 1 : ";
        std::cin >> a;
        std::cout << "Enter number 2 : ";
        std::cin >> b;
        std::cout << "GCD of " << a << " and "
                  << b << " is " << gcd1(a,b) << std::endl;
        std::cout << "GCD of " << a << " and "
                  << b << " is " << gcd2(a,b) << std::endl;
        std::cout << "GCD of " << a << " and "
                  << b << " is " << gcd3(a,b) << std::endl;
        std::cout << "GCD of " << a << " and "
                  << b << " is " << gcd4(a,b) << std::endl;
        return 0;
    }
    
    
    展开全文
  • 1. ```#include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; int fun(int a,int b) { int i,t,n,f; f=a*b; if(a&lt;b) {t=a; a=b; b=t; } while(b!=0) ...//记住最后的最大公...
    
     1.
    
    ```#include<stdio.h>
    #include<stdlib.h>
    int fun(int a,int b)
    { int i,t,n,f;
    f=a*b;
    if(a<b)
    {t=a;
    a=b;
    b=t;
    }
    while(b!=0)
    {n=a%b;
    a=b;
    b=n;
    }
    i=f/a;
    printf("%5d%7d",a,i);//记住最后的最大公约数输出的是除数a;
    return(a);
    }
    int main()
    {int a,b;
    scanf("%d%d",&a,&b);
    int fun(int,int);
    fun(a,b);
    system("pause");
    return 0;
    }
    
    
    展开全文
  • 最大公约数法 首先了解它的一般法(欧几里得算法):假设存在两个数A和B,假如A%B的结果不为0,那么A和B的最大公约数是B与A%B的...最大公约数的代码:(基于C++实现的函数) int gcd(int a,int b) { in...

    最大公约数的求法

    首先了解它的一般求法(欧几里得算法):假设存在两个数A和B,假如A%B的结果不为0,那么A和B的最大公约数是B与A%B的最大公约数,一直往下计算,直到后者为0,此时的最大公约数为A’(注意不是A而是A’)。就比如上边的例子,当A%B==0的时候,最大公约数就是B了,这个A’就代表B。

    最大公约数的代码:(基于C++实现的函数)

    int gcd(int a,int b)
    {
    	int g;
    	if(b==0)g=a;
    	else g=gcd(b,a%b);
    	return g;
    }
    

    最小公倍数与最大公约数的关系:

    假设存在两个数A和B,那他们的最大公倍数就是A和B的积除以的A和B最大公约数即A*B/gcd(A,B)

    有了上边求最大公约数的基础,那么我们就可以很轻松的求出两个数的最小公倍数了!不多说,上代码(基于C++语言实现的函数):

    int mingbs(int a,int b)
    {
    	return a*b/gcd(a,b);//gcd函数在上边
    }
    

    最大公约数的性质的拓展:

    其实求最大公约数是一件很简单的事情,但是它背后的数学性质也很重要;我在这里浅谈一下我曾经应用到的它的性质。

    性质1:假如两个数的最大公约数是1,那么这两个数互质。
    性质2:假如两个数互质(性质1),那么这两个数组成的最大的不可能的数是他们的积减去他们的和;反之则没有能够组成的最大不可能数,即不可能组成的数是无穷。

    由于我没接触到它的别的性质,等我接触到后再补充。
    上述两条性质再蓝桥杯的题目《包子凑数问题》中应用比较经典,因为它与动态规划联系起来运用了,有兴趣的读者可以去尝试解决,这样可以提高自己的编程应用能力。《包子凑数问题》请等待我有时间后,再与读者朋友们分享一下我的解题方法。

    展开全文
  • 最大公约数:Greatest Common Divisor,简写为gcd,依靠的是gcd(a,b)=gcd(b,a mod b);证明如下: 设两个数a>b,则a可表示为:a=kb+r; 则a mod b=r; r=a-kb; 设d为a,b的公约数,则a%d=b%d=0 ; r%d=a%d-kb%d=0;则d也...
  • 最大公约数欧几里得Euclid算法最大公约数欧几里得Euclid算法完整源码(定义,实现,main函数测试) 最大公约数欧几里得Euclid算法完整源码(定义,实现,main函数测试) #include <stdio.h> // Euclid's ...
  • C语言求最大素公约数 题目描述: Haue的ACM比赛又开赛了,小z兴致勃勃的来参赛,小z本来想拿一个奖回去的,可一上来就被一个题目给弄晕了,“这是哈呀”,小z说道,“啥是素数,啥是最大公约数,啥又是最大素公约数...
  • 自定义函数求最大公约数和最小公倍数 解题思路: 1.利用辗转相除法求出最大公约数,而得出两个数的最大公约数,把两数相乘再除以最大公约数就能求出最小公倍数。 2.约数:若整数 d 既是整数 m 的约数,也是整数 n 的...
  • C语言最大公约数和最小公倍数

    千次阅读 2018-04-13 17:40:39
    求最大公倍数(GCD)与最小公约数(LCM),构造两函数gcd与lcm先求出两数的最大公约数,再用两数和最大公...如果不知道这种求最大公约数的方法的话,很容易会想到这种方法:  取两数中的较小数,从1开始到这个最小数 做...
  • 算法提高 求最大公约数 时间限制:1.0s 内存限制:512.0MB 编写一函数gcd,求两个正整数的最大公约数。 样例输入: 5 15样例输出:5 样例输入: 7 2样例输出:1作者注释:常用两种方法:递归法,相减法...
  • 四种方法分别为:辗转相除...穷举法(也叫枚举法)穷举法两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数 。 ①定义1:对两个正整...
  • 最大公约数:令两个数为a和b(不论顺序)。若b不为0,更新a和b的值:把a/b的余数赋值给b,把b原来的值赋给a。...int gcd(int a, int b)//求最大公约数函数 { int tem = 0; while (tem = a % b) { a =
  • 请计算2个数的最大公约数和最小公倍数;(最大公约数可以使用辗转相除法,最小公倍数=2个数的乘积/它们的最大公约数) Input: 输入数据有多组,每组2个正整数a,b(2<a , b<1000) Output: 在一行内输出a和b的...
  • c语言函数求最大公倍数和最小公约数 #include&amp;lt;stdio.h&amp;gt; #include&amp;lt;math.h&amp;gt; #include&amp;lt;string.h&amp;gt; #include using namespace std; int main...
  • Description:写两个函数,分别两个整数的最大公约数和最小公倍数,用主函数调用这两个函数,并输出结果。 Input:输入仅一行,输入两个整数。 Output:输出二行, 第一行:输出最大公约数 第二行:输出最小公倍数...
  • C语言递归求最大公约数

    万次阅读 2018-05-23 22:03:40
    但是之前用辗转相除法求最大公约数是不是不够方便?用递归实现代码简单;而且思路也简单:int f(int m,int n){ if(m%n == 0)return n; else return f(n,m%n); }这是关键代码,f是函数,在函数内又调用自身;...
  • C语言四种方法求最大公约数

    万次阅读 多人点赞 2019-03-09 13:26:03
    1.辗转相除法(欧几里德法) C语言中用于计算两个正整数a,b的最大公约数,采用函数嵌套调用形式进行两个数的最大公约数。其算法过程为: 前提:设两数为a,b设其中a做被除数,b做除数,temp为余数 Steps:大数放a中...
  • 分别两个整数的最大公约数和最小公倍数,用主函数调用这两个函数,并输出结果。 #include<stdio.h> int yue(int m,int n) { int r; if(m<n) { int t=n; n=m; m=t; } while(n) { r=m%n; m=n; ...
  • 编写一函数gcd,两个正整数的最大公约数。 样例输入: 5 15 样例输出: 5 样例输入: 7 2 样例输出: 1 #include <stdio.h> int main(void) { int s1,s2; scanf("%d%d",&s1,&s2); int ys; while( ...
  • C语言练习7--使用函数求最大公约数

    千次阅读 2019-11-03 18:17:33
    使用函数求最大公约数 本题要求实现一个计算两个数的最大公约数的简单函数 函数接口定义: int gcd( int x, int y ); 其中 x 和 y 是两个正整数,函数 gcd 应返回这两个数的最大公约数。 裁判测试程序样例...
  • 1、编写递归函数求两个正整数a和b的最大公约数(GCD,Greatest Common Divisor),使用Euclid算法: 如果a除以b能整除,则最大公约数是b。 否则,最大公约数等于b和a%b的最大公约数@[TOC](这里写自定义目录标题) #...
  • /*写两个函数,分别取两个整数的最大公约数和最小公倍数,用主函数调用这两个函数,并输出结果。两个整数由键盘输入。*/ #include <stdio.h> #include <math.h> long CommomDivisor(int x,int y); ...

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 256
精华内容 102
关键字:

c语言求最大公约数函数

c语言 订阅