精华内容
下载资源
问答
  • 更相减损法

    千次阅读 2018-12-19 23:37:01
    更相减损法

    定义:

    更相减损法原本是为了约分而设计的:可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。

    1:任意给定两个正整数;判断它们是否都是偶数。

    若是,则用2约简;若不是则执行第二步。

    2:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。

    继续这个操作,直到所得的减数和差相等为止。

     

    第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数,相当于不要第一步。

    换成公式的写法:

    如果A > B,则 gcd(A,B) = gcd(B,A-B)

    如果A < B,则 gcd(A,B) = gcd(A,B-A)

     

    证明:

    不妨设A>B,设A和B的最大公约数为X,所以 A=aX,B=bx,其中a和b都为正整数,切a>b。

    C = A-B,则有C=aX−bX=(a−b)X

     

    因为a和b均为正整数,所以C也能被X整除,即A、B、C最大公约数均为X

    所以gcd(A,B) = gcd(B,A-B)

     

    代码实现:

     

    int GCD(int a, int b) {

        while (a != b) {

            if (a > b)

                a = a - b;

            else

                b = b - a;

        }

        return a;

    }

    展开全文
  • 分享给大家供大家参考,具体如下:先从网上摘录一段算法的描述如下:更相减损法:也叫 更相减损术,是出自《 九章算术》的一种求最大公约数的算法,它原本是为 约分而设计的,但它适用于任何需要求最大公约数的场合...

    本文实例讲述了Python基于更相减损术实现求解最大公约数的方法。分享给大家供大家参考,具体如下:

    先从网上摘录一段算法的描述如下:

    更相减损法:也叫 更相减损术,是出自《 九章算术》的一种求最大公约数的算法,它原本是为 约分而设计的,但它适用于任何需要求最大公约数的场合。

    《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”

    翻译成现代语言如下:

    第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。

    第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。

    看完上面的描述,我的第一反应是这个描述是不是有问题?从普适性来说的话,应该是有问题的。举例来说,如果我求解4和4的最大公约数,可半者半之之后,结果肯定错了!后面的算法也不能够进行!

    不管怎么说,先实现一下上面的算法描述:

    # -*- coding:utf-8 -*-

    #! python2

    def MaxCommDivisor(m,n):

    # even process

    while m % 2 == 0 and n % 2 == 0:

    m = m / 2

    n = n / 2

    # exchange order when needed

    if m < n:

    m,n = n,m

    # calculate the max comm divisor

    while m - n != n:

    diff = m - n

    if diff > n:

    m = diff

    else:

    m = n

    n = diff

    return n

    print(MaxCommDivisor(55,120))

    print(MaxCommDivisor(55,77))

    print(MaxCommDivisor(32,64))

    print(MaxCommDivisor(16,128))

    运行结果:

    2cb813e4a8c6e054afa6b0317501fc13.png

    不用说,上面程序执行错误百出。那么该如何更正呢?

    首先,除的2最终都应该再算回去!这样,程序修改如下:

    def MaxCommDivisor(m,n):

    com_factor = 1

    if m == n:

    return n

    else:

    # process for even number

    while m % 2 == 0 and n % 2 == 0:

    m = int(m / 2)

    n = int(n / 2)

    com_factor *= 2

    if m < n:

    m,n = n,m

    diff = m - n

    while n != diff:

    m = diff

    if m < n:

    m,n = n,m

    diff = m - n

    return n * com_factor

    print(MaxCommDivisor(55,120))

    print(MaxCommDivisor(55,77))

    print(MaxCommDivisor(32,64))

    print(MaxCommDivisor(16,128))

    通过修改,上面程序执行结果如下

    984c7e8dbad5d5d60e5e034f6633545d.png

    虽说这段程序写出来看着有点怪怪的,但是总体的算法还是实现了。与辗转相除等算法相比,这个在循环的层级上有一定的概率会减小。特别是最后的两组测试数字对儿,这种情况下的效果要好一些。但是,总体上的算法的效率,现在我还不能够给个准确的衡量。

    PS:这里再为大家推荐几款计算工具供大家进一步参考借鉴:

    希望本文所述对大家Python程序设计有所帮助。

    展开全文
  • 更相减损法 C语言

    2020-04-11 21:36:32
    # **更相减损法 C语言** #include<stdio.h> #include<math.h> int gcd(int m,int n) { int i=0,temp,x; while(m%2==0&&n%2==0) //判断m和n能被多少个2整除 { m/=2; n/=2; i+=1; } ...

    # **更相减损法 C语言**

    #include<stdio.h>
    #include<math.h>
    int gcd(int m,int n)
    {
    	int i=0,temp,x;
    	
    	while(m%2==0&&n%2==0)  //判断m和n能被多少个2整除
    	{
    		m/=2;
    		n/=2;
    		i+=1;
    	}
    	if(m<n)     //m保存大的值
    	{
    		temp=m;
    		m=n;
    		n=temp;
    	}
    	while(x)
    	{
    		x=m-n;
    		m=(n>x)?n:x;
    		n=(n<x)?n:x;
    		if(n==(m-n))
    			break;
    	}
    	if(i==0)
    		return n;
    	else 
    		return (int )pow(2,i)*n;
    
    }
    int max(int m,int n)//m和n存在被对方整除情况时的最大公约数
    {int temp;
       if(m<n)
    
    	   {
    		temp=m;
    		m=n;
    		n=temp;
    	}
       else if(m==n) return n;
       else if(m>n) return n;
    
       return n;
    }
    int min(int m,int n)//m和n存在被对方整除情况时的最小公倍数
    {int temp;
    if(m<n)
     {
    		temp=m;
    		m=n;
    		n=temp;
    }
    else if(m>n||m==n) return m;
    
    return m;
    }
    int main()
    {
     int m,n,t1,t2;
     printf("请输入两个整数:");//提示输入两个整数
     scanf("%d%d",&m,&n); 
     if(m%n!=0&&n%m!=0)//m和n不能被对方整除时
     {
    	 t1=gcd(m,n);//最大公约数
    printf(" 最大公约数:%d\n",t1);//最大公约数
    printf(" 最小公倍数:%d\n",m*n/t1);//最小公倍数
     }
     else//m和n存在被对方整除的情况
     {
    t1=max(m,n);
    t2=min(m,n);
    printf(" 最大公约数:%d\n",t1);//最大公约数
    printf(" 最小公倍数:%d\n",t2);//最小公倍数
     }
    
     return 0;
    }
    

    欢迎使用Markdown编辑器

    你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。

    新的改变

    我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能,我们增加了如下几点新功能,帮助你用它写博客:

    1. 全新的界面设计 ,将会带来全新的写作体验;
    2. 在创作中心设置你喜爱的代码高亮样式,Markdown 将代码片显示选择的高亮样式 进行展示;
    3. 增加了 图片拖拽 功能,你可以将本地的图片直接拖拽到编辑区域直接展示;
    4. 全新的 KaTeX数学公式 语法;
    5. 增加了支持甘特图的mermaid语法1 功能;
    6. 增加了 多屏幕编辑 Markdown文章功能;
    7. 增加了 焦点写作模式、预览模式、简洁写作模式、左右区域同步滚轮设置 等功能,功能按钮位于编辑区域与预览区域中间;
    8. 增加了 检查列表 功能。

    功能快捷键

    撤销:Ctrl/Command + Z
    重做:Ctrl/Command + Y
    加粗:Ctrl/Command + B
    斜体:Ctrl/Command + I
    标题:Ctrl/Command + Shift + H
    无序列表:Ctrl/Command + Shift + U
    有序列表:Ctrl/Command + Shift + O
    检查列表:Ctrl/Command + Shift + C
    插入代`在这里插入代码片码:Ctrl/Command + Shift + K
    插入链接:Ctrl/Command + Shift + L
    插入图片:Ctrl/Command + Shift + G
    查找:Ctrl/Command + F
    替换:Ctrl/Command + G

    合理的创建标题,有助于目录的生成

    直接输入1次#,并按下space后,将生成1级标题。
    输入2次#,并按下space后,将生成2级标题。
    以此类推,我们支持6级标题。有助于使用TOC语法后生成一个完美的目录。

    如何改变文本的样式

    强调文本 强调文本

    加粗文本 加粗文本

    标记文本

    删除文本

    引用文本

    H2O is是液体。

    210 运算结果是 1024.

    插入链接与图片

    链接: link.

    图片: Alt

    带尺寸的图片: Alt

    居中的图片: Alt

    居中并且带尺寸的图片: Alt

    当然,我们为了让用户更加便捷,我们增加了图片拖拽功能。

    如何插入一段漂亮的代码片

    博客设置页面,选择一款你喜欢的代码片高亮样式,下面展示同样高亮的 代码片.

    // An highlighted block
    var foo = 'bar';
    

    生成一个适合你的列表

    • 项目
      • 项目
        • 项目
    1. 项目1
    2. 项目2
    3. 项目3
    • 计划任务
    • 完成任务

    创建一个表格

    一个简单的表格是这么创建的:

    项目 Value
    电脑 $1600
    手机 $12
    导管 $1

    设定内容居中、居左、居右

    使用:---------:居中
    使用:----------居左
    使用----------:居右

    第一列 第二列 第三列
    第一列文本居中 第二列文本居右 第三列文本居左

    SmartyPants

    SmartyPants将ASCII标点字符转换为“智能”印刷标点HTML实体。例如:

    TYPE ASCII HTML
    Single backticks 'Isn't this fun?' ‘Isn’t this fun?’
    Quotes "Isn't this fun?" “Isn’t this fun?”
    Dashes -- is en-dash, --- is em-dash – is en-dash, — is em-dash

    创建一个自定义列表

    Markdown
    Text-to-HTML conversion tool
    Authors
    John
    Luke

    如何创建一个注脚

    一个具有注脚的文本。2

    注释也是必不可少的

    Markdown将文本转换为 HTML

    KaTeX数学公式

    您可以使用渲染LaTeX数学表达式 KaTeX:

    Gamma公式展示 Γ(n)=(n1)!nN\Gamma(n) = (n-1)!\quad\forall n\in\mathbb N 是通过欧拉积分

    Γ(z)=0tz1etdt. \Gamma(z) = \int_0^\infty t^{z-1}e^{-t}dt\,.

    你可以找到更多关于的信息 LaTeX 数学表达式here.

    新的甘特图功能,丰富你的文章

    Mon 06Mon 13Mon 20已完成 进行中 计划一 计划二 现有任务Adding GANTT diagram functionality to mermaid
    • 关于 甘特图 语法,参考 这儿,

    UML 图表

    可以使用UML图表进行渲染。 Mermaid. 例如下面产生的一个序列图:

    张三李四王五你好!李四, 最近怎么样?你最近怎么样,王五?我很好,谢谢!我很好,谢谢!李四想了很长时间,文字太长了不适合放在一行.打量着王五...很好... 王五, 你怎么样?张三李四王五

    这将产生一个流程图。:

    链接
    长方形
    圆角长方形
    菱形
    • 关于 Mermaid 语法,参考 这儿,

    FLowchart流程图

    我们依旧会支持flowchart的流程图:

    Created with Raphaël 2.2.0开始我的操作确认?结束yesno
    • 关于 Flowchart流程图 语法,参考 这儿.

    导出与导入

    导出

    如果你想尝试使用此编辑器, 你可以在此篇文章任意编辑。当你完成了一篇文章的写作, 在上方工具栏找到 文章导出 ,生成一个.md文件或者.html文件进行本地保存。

    导入

    如果你想加载一篇你写过的.md文件,在上方工具栏可以选择导入功能进行对应扩展名的文件导入,
    继续你的创作。


    1. mermaid语法说明 ↩︎

    2. 注脚的解释 ↩︎

    展开全文
  • 2.辗转相减法(更相减损法) 3.穷举法 最小公倍数:两数的乘积除以最大公约数 方法: 1.判断大小,并使大数赋给a,小数赋给b; 2.辗转相除法:在两数相除余数不为0的情况下循环相除,直至余数为0并得出最大公约数 3....

    最大公约数:
    1.辗转相除法
    2.辗转相减法(更相减损法)
    3.穷举法

    最小公倍数:两数的乘积除以最大公约数

    方法:
    1.判断大小,并使大数赋给a,小数赋给b;
    2.辗转相除法:在两数相除余数不为0的情况下循环相除,直至余数为0并得出最大公约数
    3.辗转相减法(更相减损法):两数之差不与两数任一个相等时,循环进行,递归,直至有一个数与余数相等即为最大公约数;
    4.穷举法:for循环i从最小数依次减小,直至被两数同时相除余数为0,即为最大公约数;

    源代码:

    #include<iostream>
    using namespace std;
    void ygq(int *a,int *b)/*判断大小*/
    {
    	int c;
    	if(*a<*b)
    	{
    		c=*a;
    		*a=*b;
    		*b=c;
    	}
    }
    int ygq1(int a,int b)/*辗转相除法*/
    {
    	int c=1;
    	ygq(&a,&b);
    	while(c!=0)
    	{
    		c=a%b;
    		a=b;
    		b=c;
    	}
    	return a;
    }
    int ygq2(int a,int b)/*辗转相减法*//*更相减损法*/
    {
    	ygq(&a,&b);
    	while(a!=b)
    	{
    		a=a-b;
    		ygq(&a,&b);
    	}
    	return a;
    }
    int ygq3(int a,int b)/*穷举法*/
    {
    	ygq(&a,&b);
    	for(int i=b;i>=1;i--)
    	{
    		if(a%i==0&&b%i==0){
    			return i;
    			break;
    		}
    	}
    	return 1;
    }
    int main()
    {
    	int a,b;
    	printf("请输入两个整数:");
    	cin>>a>>b;
    	if(a>0&&b>0)
    		printf("辗转相除法\n最大公约数:%d\n最小公倍数:%d\n",ygq1(a,b),a*b/ygq1(a,b));
    	else
    		printf("Error!");
    	if(a>0&&b>0)
    		printf("更相减损法\n最大公约数:%d\n最小公倍数:%d\n",ygq2(a,b),a*b/ygq2(a,b));
    	else
    		printf("Error!");
    	if(a>0&&b>0)
    		printf("穷举法\n最大公约数:%d\n最小公倍数:%d\n",ygq3(a,b),a*b/ygq3(a,b));
    	else
    		printf("Error!");
    	return 0;
    }
    

    备注:
    有问题可以评论,看到后我会尽力及时回复的,谢谢!

    展开全文
  • 要求两个正整数的最大公约数有两种方法,辗转相除法和更相减损法。 注:gcd(a,b)代表a和b的最大公约数。 辗转相除法的定义:对于两个正整数a和b,其中a&gt;b,r为a除以b的余数,gcd(a,b) = gcd(b,r); 原理:...
  • 本次实验内容为使用以下几种算法1:辗转相除法函数嵌套调用2:辗转相除法函数递归调用3:穷举法(利用数学定义4:更相减损法5:Stein算法函数非递归调用6:Stein算法函数递归调用;求出随机生成的几十组数据(两个一组)...
  • 更相减损法和辗转相除法(GCD)求最小公倍数和最大公约数 标签(空格分隔): 算法 算法竞赛 这两种算法平时经常听到,听起来也很装逼,但是我老是忘了他们的原理,今天好好想想,写下来。 更相减损法 更相减...
  • 求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数,a,b的最小公倍数记为[a,b]。 1:辗转相除法: 欧几里德算法又称辗转相除法,是指用于...
  • 时间复杂度 o(n) ...辗转相除可以用来求若干个形如(p/q)^ri的数的最大公约数,其中: ——p/q不可以再表示为次幂的形式 ​——p、q、ri均为正整数 算法推导 求指数的最大公约数,即: f(p^x...
  • 更相减损法:gcd(a,b)=gcd(a/2,b/2)∗2gcd(a,b)=gcd(a/2,b/2)∗2gcd(a,b) = gcd(a/2, b/2)*2 当a,b均为偶数 gcd(a,b)=gcd(a/2,b)gcd(a,b)=gcd(a/2,b)gcd(a,b) = gcd(a/2,b) 当仅有a为偶数 gcd(a,b)=gcd(a,b/2)gcd...
  • 求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数,a,b的最小公倍数记为[a,b]。 质因数分解法: 把每个数分别分解...
  • 更相减损法 (又名辗转相减法)4. Stein算法 1. 辗转相除法(又名欧几里德算法) 欧几里得算法,也叫辗转相除,简称 gcd,用于计算两个整数的最大公约数 定义: gcd(a,b) 为整数 a 与 b 的最大公约数 引理:gcd(a,b)...
  • 辗转相除法、更相减损法、Stein算法

    万次阅读 多人点赞 2017-07-30 18:42:55
    最大公约数和最小公倍数求解,常用的方法是短除进行因式分解,然后最大公约数是所有公共因子的乘积,最小公倍数是所有因子的乘积。 本质上求最小公倍数就是求最大公倍数:x=m*a, y=m*b;m是最大公约数,那最小...
  • 相减损原理 假设有两个数161和63,我们要求这两个数的最大公因数,不妨假定这个最大公因数为m,我们可以将较大的数161看成63+98,63与98的和161可以被m整除,其中63也可以被m整除,自然98可以被m整除; 所以这个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 422
精华内容 168
关键字:

更相减损法