辗转相除法和穷举法的优缺点和特点
发布网友
发布时间：2022-05-19 09:34
共1个回答
热心网友
时间：2023-10-09 21:51
辗转相除法的优点：在于它能以有系统的方式求出两数的最大公约数，而无需分别对它们作因式分解。大数的素因数分解被认为是一个困难的问题，即使是现代的计算机也非常难于处理，所以许多加密系统的原理都是建基于此。
辗转相除法的缺点：运算繁琐、复杂、易错，从算法实现角度考虑，该方法 存在存储量大，运算时间长，运算速度慢等不足．
辗转相除法特点：惟一分解,即这些数系中的数能够被惟一地分解成不可约元素(素数在这些数系的对应物)。
辗转相除法原理：
设两数为a、b(b<a），用*(a,b）表示a，b的最大公约数，r=a mod b 为a除以b以后的余数，k为a除以b的商，即a÷b=k.......r。辗转相除法即是要证明*(a,b)=*(b,r）。
第一步：令c=*(a,b），则设a=mc，b=nc
第二步：根据前提可知r =a-kb=mc-knc=(m-kn)c
第三步：根据第二步结果可知c也是r的因数
第四步：可以断定m-kn与n互质【否则，可设m-kn=xd，n=yd，（d>1），则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数成为cd，而非c，与前面结论矛盾】
从而可知*(b,r)=c，继而*(a,b)=*(b,r）。
证毕。
二、穷举法的优缺点和特点
穷举法的优点：算法简单。
穷举法的缺点：运行时所花费的时间长。
穷举法的特点：掌握利用穷举法解决问题的基 本要求；学会编写程序实现穷举法。
例子：
用穷举法解题时，就是按照某种方式列举问题答案的过程。针对问题的数据类型而言，常用的列举方法一有如下三种：
（1）顺序列举 是指答案范围内的各种情况很容易与自然数对应甚至就是自然数，可以按自然数的变化顺序去列举。
（2）排列列举 有时答案的数据形式是一组数的排列，列举出所有答案所在范围内的排列，为排列列举。
（3）组合列举 当答案的数据形式为一些元素的组合时，往往需要用组合列举。组合是无序的。
例子如下：在公元五世纪我国数学家张丘建在其《算经》一书中提出了“百鸡问题 ”：
“鸡翁一值钱5，鸡母一值钱3，鸡雏三值钱1。百钱买百鸡，问鸡翁、母、雏各几何？”这个数学问题的数学方程可列出如下：
Cock+Hen+Chick=100
Cock*5+Hen*3+Chick/3=100
显然这是个不定方程，适用于穷举法求解。依次取Cock值域中的一个值，然后求其他两个数，满足条件就是解。
