|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 算法理论与分析 』 (http://bbs.xml.org.cn/list.asp?boardid=60) ---- 如何证明这个算法的正确性！ (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=43226) |
|
-- 作者：lanyuandong -- 发布时间：2/11/2007 5:10:00 PM -- 如何证明这个算法的正确性！ 求两个数的最大公约数的算法 gys(int max,int min) { if(min>max) max<->min; //交换两个数 int r; while((r=max%min)!=0) { max=min; min=r; } return min; } 如何证明这个算法是正确的？ |
|
-- 作者：Logician -- 发布时间：2/11/2007 6:08:00 PM -- 利用gcd(a,b) = gcd(a%b,a)进行归纳证明即可
|
|
-- 作者：lanyuandong -- 发布时间：2/11/2007 10:09:00 PM -- 还是不明白呀 如何归纳呀？ |
|
-- 作者：Logician -- 发布时间：2/11/2007 10:51:00 PM -- 就是每一次循环得到的两个新数，他们的gcd和原来两个数的gcd相同 而到最后一步，当一个数a_n整除另一个数b_n时，自然有gcd(a_n,b_n)=a_n 那么这个a_n，也是原来那两个数的gcd。 现在只要再证明一下这个算法一定会终止就可以了 这是显然的，因为对每一个n>1每一次新的a_n至少比a_{n-1}小一个，所以在有限步内，一定能减到1。而减到1时（或此之前的某一步）一定有a_n|b_n，所以算法一定在有限步内终止。 |
|
-- 作者：lanyuandong -- 发布时间：2/13/2007 1:09:00 PM -- 谢谢，看来我还是太笨了，哈哈，等我认真看看能明白不…… |
|
-- 作者：shellkk -- 发布时间：3/19/2007 2:17:00 PM -- 很简单 a mod b的余数必定能被a和b的最大公约数整除 |
|
-- 作者：悟空 -- 发布时间：4/13/2007 1:46:00 PM -- a mod b的余数必定能被a和b的最大公约数整除 if max=a=k*n min= b=m*n n为最大公约数 a%b=l*n l *n为某次%后余数 所以最后那个min就是最大公约数 |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
39.063ms |