(C语言)求最大公约数的四个方法 |
您所在的位置:网站首页 › c语言中求最大公约数 › (C语言)求最大公约数的四个方法 |
目录 一、穷 举 法 二、辗 转 相 除 法 三、更 相 减 损 术 四、Stein算法(结合辗转相除法和更相减损法的优势以及移位运算) 一、穷 举 法 即是最暴力无脑的方法:直接暴力枚举,直到出现一个能同时整除两数的值。但是不推荐,即浪费CPU.又浪费时间。 //穷举法 int divi_0(int x, int y) { if (x < y) { int tmp = y; y = x; x = tmp; } for (int i = y; i >= 1; i-- ) { if (x%i == 0 && y%i == 0) { return i; } } }二、辗 转 相 除 法 欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理: 定理:divi(a, b) = divi(a, a%b) 证明:对于 divi(a, b) ` 假设 d 是 a、b 的公约数,r = a%b, a = kb + r, r = a - kb, 即d 也是 r 的公约数; 对于divi(a, a%b) 假设另一 d 是 a, a%b 的公约数,r = a%b, a = kb + r, b = (a - r)k 即d也是 b 的公约数; 由此可证得最大公约数也是相同的。 //辗转相除法 int divi_1(int a, int b) { int divi = 0; while (a%b) { divi = a % b; a = b; b = divi; } divi = b; return divi; } 三、更 相 减 损 术(尼考曼彻斯法;辗转相减)更相减损法:更相减损术, 出自于中国古代的《九章算术》,也是一种求最大公约数的算法。 ①先判断两个数的大小,如果两数相等,则这个数本身就 是就是它的最大公约数。 ②如果不相等,则用大数减去小数,然后用这个较小数与它们相减的结果相比较,如果相等,则这个差就是它们的最大公约数,而如果不相等,则继续执行②操作。 原理:divi(a, b) = divi(b, a - b); 证明:假设 d 是a、b的公约数,r = a - b, 则d 是 r 的公约数,同理可证 最后两个数相等时一定是原来两个数的最大公约数。 //更相减损术 int divi_2(int a, int b) { if (a == b) { return a; } else if (a > b) { return divi_2(a - b, b); } else { return divi_2(b - a, a); } } 四、Stein算法(结合辗转相除法和更相减损法的优势以及移位运算) 众所周知,移位运算的性能非常快。对于给定的正整数a和b,不难得到如下的结论。其中gcb(a,b)的意思是求a,b的最大公约数的函数 当a和b均为偶数,gcb(a,b) = 2gcb(a/2, b/2) = 2 * gcb(a>>1, b>>1)当a为偶数,b为奇数,gcb(a,b) = gcb(a/2, b) = gcb(a>>1, b)当a为奇数,b为偶数,gcb(a,b) = gcb(a, b/2) = gcb(a, b>>1)当a和b均为奇数,利用更相减损术运算一次,gcb(a,b) = gcb(b, a-b), 此时a-b的结果必然是偶数,又可以继续进行移位运算。 证明:通过辗转相除法和更相减损术的证明易证。 //两者结合后的Stein算法 int Stein(int x, int y) { if (x < y) { int tmp = x; x = y; y = tmp; } if ( x%y == 0) { return y; } if (x % 2 == 0 && y % 2 == 0) { return 2*Stein(x >> 1, y >> 1); } else if (x%2 == 0 && y%2 != 0) { return Stein(x >> 1, y); } else if (x % 2 != 0 && y % 2 == 0) { return Stein(x, y >> 1); } else if (x % 2 != 0 && y % 2 != 0) { return Stein(x, (x - y) >> 1); } }
|
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |