比较求最大公因数和最大公倍数的几种算法在不同输入规模的情况下的运行时间
**辗转相除法：**假设有两个数a和b（其中没有0），先找出a和b中较大的并赋值给a，较小的赋值给b。然后把a作为被除数，b作为除数进行运算。如果余数不为0则将b赋值给a将余数赋值给b再次运算，如此反复直到b为0，此时a就是最大公因数。
代码如下：
我这里采用的是文件输入输出，因为这样比较好改出入数据的规模。输入的数据我采用的是的产生在[1,500]之间的随机数。
#include<iostream>
#include<cstdlib>
#include<time.h>
#include<fstream>
#include<random>
using namespace std;
ifstream in;
ofstream out,out_ans;
int main()
{
clock_t start,finish;
void swap(int& a, int& b);
int Fun_1(const int a1,const int b1);
int Fun_2(const int a1, const int b1);
out.open("num.txt");
out_ans.open("结果.txt");
if (out.is_open())
{
cout << "写入文件打开成功" << endl;
}
if (out_ans.is_open())
{
cout << "结果文件打开成功" << endl;
}
srand((unsigned)time(NULL));//重置随机函数的种子
int i = 1;
while (i <= 50000)
{
out << (rand()%(500)+1) << " " << (rand() % (500) + 1) << endl; //限定产生的数据范围在[1,500]之间
i++;
}
in.open("num.txt");
if (in.is_open())
{
cout << "读入文件打开成功" << endl;
}
start = clock(); //开始计时
while (!(in.eof()))
{
int num_1, num_2, ans_1,ans_2;
in >> num_1 >> num_2;
out << endl;
ans_1 = Fun_1(num_1, num_2);
ans_2 = Fun_2(num_1, num_2);
out_ans << "最大公因数是：" << ans_1 << endl;
out_ans << "最小公倍数是：" << ans_2 << endl;
}
in.close();
out.close();
out_ans.close();
finish = clock(); //结束计时
double duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout << "运行时间是：" << duration << endl;
system("pause");
return 0;
}
void swap(int& a, int& b) /*找出参数中较大的数和较小的数*/
{
int t = 0;
if (a < b)
{
t = a;
a = b;
b = t;
}
}
int Fun_1(const int a1,const int b1) /*根据辗转相除法求出最大公因数*/
{
int x, y;
int t = 0;
x = a1;
y = b1;
swap(x, y);
while (y != 0)
{
t = x % y;
x = y;
y = t;
}
return x;
}
int Fun_2(int a1,int b1) /*求最小公倍数*/
{
int product = 0;
product = a1 * b1;
return product / Fun_1(a1, b1); /*最小公倍数数等于两数之积除以最大公因数*/
}
不同规模数据的运行时间
**枚举法：**在[1,a][1,b]中找出一个既能被a整除也能被b整除的数c，则c就是最大公因数。
代码如下：
#include<iostream>
#include<cstdlib>
#include<time.h>
#include<fstream>
#include<random>
using namespace std;
ifstream in;
ofstream out, out_ans;
int main()
{
int Fun01(int a, int b);
int Fun02(int a, int b);
clock_t start, finish;
start = clock();
out.open("num.txt");
out_ans.open("结果.txt");
if (out.is_open())
{
cout << "写入文件打开成功" << endl;
}
if (out_ans.is_open())
{
cout << "结果文件打开成功" << endl;
}
in.open("num.txt");
if (in.is_open())
{
cout << "读入文件打开成功" << endl;
}
while (!(in.eof()))
{
int num_1, num_2, ans_1, ans_2;
in >> num_1 >> num_2;
out << endl;
ans_1 = Fun01(num_1, num_2);
ans_2 = Fun02(num_1, num_2);
out_ans << "最大公因数是：" << ans_1 << endl;
out_ans << "最小公倍数是：" << ans_2 << endl;
}
in.close();
out.close();
out_ans.close();
finish = clock();
double duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout << "运行时间是：" << duration << endl;
system("pause");
return 0;
}
int Fun01(int a, int b) //枚举法求最大公因数
{
if (a == 0 || b == 0)
{
cout << "输入有错误" << endl;
}
int min;
min = a > b ? b : a;
while (true)
{
if (a%min == 0 && b%min == 0)
break;
min--;
}
return min;
}
int Fun02(int a, int b) //如果若干个a能被b所整除，则找到最小公倍数
{
int m, n, t,max;
m = a;
n = b;
if (m < n)
{
t = m;
m = n;
n = t;
}
max = m;
while (true)
{
if (m%n == 0)
break;
m += max;
}
return m;
}
不同规模数据的运行时间
更相减损法：：第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
代码如下：
#include<iostream>
#include<cstdlib>
#include<time.h>
#include<fstream>
#include<random>
#include<cmath>
using namespace std;
ifstream in;
ofstream out, out_ans;
int main()
{
int Funcation(int a, int b);
int Fun(int a1, int b1);
clock_t start, finish;
out.open("num.txt");
out_ans.open("结果.txt");
if (out.is_open())
{
cout << "写入文件打开成功" << endl;
}
if (out_ans.is_open())
{
cout << "结果文件打开成功" << endl;
}
srand((unsigned)time(NULL));//重置随机函数的种子
int i = 1;
while (i <= 50000)
{
out << (rand() % (500) + 1) << " " << (rand() % (500) + 1) << endl; //限定产生的数据范围在[1,500]之间
i++;
}
in.open("num.txt");
if (in.is_open())
{
cout << "读入文件打开成功" << endl;
}
start = clock();
while (!(in.eof()))
{
int num_1, num_2, ans_1, ans_2;
in >> num_1 >> num_2;
out << endl;
ans_1 = Funcation(num_1, num_2);
ans_2 = Fun(num_1, num_2);
out_ans << "最大公因数是：" << ans_1 << endl;
out_ans << "最小公倍数是：" << ans_2 << endl;
}
in.close();
out.close();
out_ans.close();
finish = clock();
double duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout << "运行时间是：" << duration << endl;
system("pause");
return 0;
}
int Funcation(int a, int b)
{
void swap(int& a, int& b);
int count = 0, ans = 0;
if (a % 2 == 0 && b % 2 == 0)
{
a /= 2;
b /= 2;
count++;
}
swap(a, b);
while (true)
{
ans = a - b;
a = (b > ans) ? b : ans; //把结果和减数中较大的赋值给a
b = (ans < b) ? ans : b; //把结果和减数中较小的赋值给b
if (ans == (a - b)) //
break;
}
return ans*pow(2, count);
}
void swap(int& a, int& b) //比较大小并且交换
{
int t;
if (a < b)
{
t = a;
a = b;
b = t;
}
}
int Fun(int a1, int b1) /*求最小公倍数*/
{
int product = 0;
product = a1 * b1;
return product / Funcation(a1, b1); /*最小公倍数数等于两数之积除以最大公因数*/
}
不同规模数据的运行时间
Stein算法：： Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。来研究一下最大公约数的性质，发现有 gcd( kx,ky ) = kgcd( x,y ) 这么一个非常好的性质。试取 k=2，则有 gcd( 2x,2y ) = 2 * gcd( x,y )。很快联想到将两个偶数化小的方法。那么一奇一个偶以及两个奇数的情况如何化小呢？
先来看看一奇一偶的情况： 设有2x和y两个数，其中y为奇数。因为y的所有约数都是奇数，所以 a = gcd( 2x,y ) 是奇数。根据2x是个偶数不难联想到，a应该是x的约数。我们来证明一下：(2x)%a=0，设2x=na，因为a是奇数，2x是偶数，则必有n是偶数。又因为 x=(n/2)*a，所以 x%a=0，即a是x的约数。因为a也是y的约数，所以a是x和y的公约数，有 gcd( 2x,y ) <= gcd( x,y )。因为gcd( x,y )明显是2x和y的公约数，又有gcd( x,y ) <= gcd( 2x,y )，所以 gcd( 2x,y ) = gcd( x,y )。至此，我们得出了一奇一偶时化小的方法。
再来看看两个奇数的情况：设有两个奇数x和y，不妨设x>y，注意到x+y和x-y是两个偶数，则有 gcd( x+y,x-y ) = 2 * gcd( (x+y)/2,(x-y)/2 )，那么 gcd( x,y ) 与 gcd( x+y,x-y ) 以及 gcd( (x+y)/2,(x-y)/2 ) 之间是不是有某种联系呢？为了方便设 m=(x+y)/2 ，n=(x-y)/2 ，容易发现 m+n=x ，m-n=y 。设 a = gcd( m,n )，则 m%a=0,n%a=0 ，所以 (m+n)%a=0，(m-n)%a=0 ，即 x%a=0 ，y%a=0 ，所以a是x和y的公约数，有 gcd( m,n )<= gcd(x,y)。再设 b = gcd( x,y )肯定为奇数，则 x%b=0,y%b=0 ，所以 (x+y)%b=0 ，(x-y)%b=0 ，又因为x+y和x-y都是偶数，跟前面一奇一偶时证明a是x的约数的方法相同，有 ((x+y)/2)%b=0,((x-y)/2)%b=0 ，即 m%b=0 ，n%b=0 ，所以b是m和n的公约数，有 gcd( x,y ) <= gcd( m,n )。所以 gcd( x,y ) = gcd( m,n ) = gcd( (x+y)/2,(x-y)/2 )。
整理一下，对两个正整数 x>y ：
1.均为偶数 gcd( x,y ) =2gcd( x/2,y/2 )；
2.均为奇数 gcd( x,y ) = gcd( (x+y)/2,(x-y)/2 )；
2.x奇y偶 gcd( x,y ) = gcd( x,y/2 )；
3.x偶y奇 gcd( x,y ) = gcd( x/2,y ) 或 gcd( x,y )=gcd( y,x/2 )；
这个看起来可能有点烦，我们可以来个例子：gcd(98,63) -->gcd(63,49) -->gcd(56,7) -->gcd(28,7) --> gcd(14,7) -->gcd(7,7) -->gcd(7,0) -->if(b==0)最大公因数是a =7
代码如下：
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<fstream>
using namespace std;
ifstream in;
ofstream out, out_ans;
int main()
{
clock_t start, finish;
int Stein(int a, int b);
int Fun(int a1,int b1);
out.open("num.txt");
out_ans.open("结果.txt");
if (out.is_open())
{
cout << "写入文件打开成功" << endl;
}
if (out_ans.is_open())
{
cout << "结果文件打开成功" << endl;
}
srand((unsigned)time(NULL));//重置随机函数的种子
int i = 1;
while (i <= 50000)
{
out << (rand() % (500) + 1) << " " << (rand() % (500) + 1) << endl; //限定产生的数据范围在[1,500]之间
i++;
}
in.open("num.txt");
if (in.is_open())
{
cout << "读入文件打开成功" << endl;
}
start = clock(); //开始计时
while (!(in.eof()))
{
int num_1, num_2, ans_1, ans_2;
in >> num_1 >> num_2;
out << endl;
ans_1 = Stein(num_1, num_2);
ans_2 = Fun(num_1, num_2);
out_ans << "最大公因数是：" << ans_1 << endl;
out_ans << "最小公倍数是：" << ans_2 << endl;
}
in.close();
out.close();
out_ans.close();
finish = clock(); //结束计时
double duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout << "运行时间是：" << duration << endl;
system("pause");
return 0;
}
int Stein(int a,int b)
{
if (a<b)
{
int temp = a;
a = b;
b = temp;
}
if (b == 0)//当相减为零，即两数相等时，最大公因数是a
return a;
if (a % 2 == 0 && b % 2 == 0) //均为偶数时
return 2 * Stein(a / 2, b / 2);
if (a % 2== 0) //a为偶数，b为基数时
return Stein(a / 2, b);
if (b % 2 == 0) //a为奇数，b为偶数
return Stein(a, b / 2);
return Stein((a + b) / 2, (a - b) / 2); //均为奇数时
}
int Fun(int a1, int b1) /*求最小公倍数*/
{
int product = 0;
product = a1 * b1;
return product / Stein(a1, b1); /*最小公倍数数等于两数之积除以最大公因数*/
}
不同规模数据的运行时间
现在我们来综合分析一下：
从上图中可以看出在50组数据时除了枚举法，其他方法的时间几乎可以忽略，在500组数据的时候Stein算法要略优于其他三种算法，5000组数据的时候变成了更相减损法要更好一点，在50000组数据的时候差异就更加明显了，枚举法和Stein算法耗费的时间比其他两种算法的时间要长，总体来说辗转相除法和更相减损法更加的平均，没有哪一段有特别明显的变化。