算法案例-辗转相除法与更相减损术.ppt

该【算法案例-辗转相除法与更相减损术 】是由【54156456】上传分享，文档一共【27】页，该文档可以免费在线阅读，需要了解更多关于【算法案例-辗转相除法与更相减损术 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。算法案例-辗转相除法与更相减损术辗转相除法更相减损术两种算法的比较算法案例分析总结与展望辗转相除法01定义辗转相除法,也称为欧几里得算法,是一种用于求两个整数的最大公约数(GCD)的经典算法。该算法基于一个简单的事实:对于任意两个整数a和b(b不为0),存在整数q和r,使得a=bq+r,且0≤r<b。选择两个非负整数a和b,并设置a为要计算最大公约数的两个数中的较大数,b为较小数。,则最大公约数为a,返回a作为结果;否则,执行下一步。,使得a=bq+r,其中0≤r<b。,将b更新为r。。在加密学中,辗转相除法用于实现模幂运算,是RSA等公钥密码算法中的关键步骤。在计算机科学中,辗转相除法常用于实现模逆运算、解线性同余方程等。在计算机图形学中,辗转相除法用于实现***除法和纹理映射。应用场景更相减损术02更相减损术是一种古老的求最大公约数的方法,最早出现在中国古代的《九章算术》中。它通过不断减去两个数的较大值和较小值,直到无法再减,得到的结果即为所求的最大公约数。,例如a和b(a>b)。,得到差值c。,重复步骤2,直到无法再减。,得到的b即为所求的最大公约数。03在数学中,更相减损术可以用于证明一些与最大公约数相关的定理和性质。01更相减损术在数学、计算机科学等领域都有应用。02在计算机科学中,更相减损术可以用于实现整数的最大公约数计算,是辗转相除法的另一种形式。应用场景