BJFU_计算机算法设计与实践_实验1

╰+哭是因爲堅強的太久メ 2023-02-23 05:27 1阅读 0赞

## 实验1 ##

### 问题描述 ###

求两个自然数 m 和 n 的最大公约数。设m和n是两个自然数，m和n的最大公约数记为gcd(m,n)，是能够同时被m和n整除的最大整数。测试数据从txt中读取。

##### 算法1：整数检测 #####

算法描述
    1.t = min{
        m, n}。
    2.m除以t，若余数为0，则执行步骤3，否则执行第4 步。
    3.n除以t，若余数为0，则返回t值，否则执行第4 步。
    4. t = t - 1，转第2 步。

#include<iostream> 
    #include<time.h> 
    #include<stdio.h> 
    #include<dos.h> 
    #include<iomanip> 
    using namespace std;
    int Continuous_int(int m,int n)
    {
        
    	int t;
    	if(m<n)
    	{
        
    		t=m;
    	}
    	else
    	{
        
    		t=n;
    	}
    	while(t>0)
    	{
        
    		if(m%t==0&&n%t==0) 
    		{
        
    			return t;
    		}
    		else
    		{
        
    			t--;
    		}
    	}
    }
    //clock计数法
    int main()
    {
        
    	int m,n;
    	double t1,t2;
    	FILE *fp=fopen("in.txt","r");
    	if(!fp)
    	{
        
    		cout<<"can't open file"<<endl; return -1;
    	}
    	cout<<"算法1：连续整数法"<<endl;
    	t1=clock();
    	while(!feof(fp))
    	{
        
    		fscanf(fp,"%d",&m);
    		fscanf(fp,"%d",&n);
    		cout<<left<<setw(11)<<m<<"与	"<<left<<setw(11)<<n<<"最大公约数: "<<Continuous_int(m,n)<<endl;
    	}
    	t2=clock();
    	fclose(fp);
    	cout<<"耗时（计数法）:"<<(t2-t1)/CLK_TCK<<"秒"<<endl;
    	return 0;
    }
    //time计时法
    int main()
    {
        
    	int m,n;
    	time_t start,end;
    	FILE *fp=fopen("in.txt","r"); 
    	if(!fp)
    	{
        
    		cout<<"can't open file"<<endl; 
    		return -1;
    	}
    	cout<<"算法1：连续整数法"<<endl;
    	start=time(NULL);
    	while(!feof(fp))
    	{
        
    		fscanf(fp,"%d",&m);
    		fscanf(fp,"%d",&n);
    		cout<<left<<setw(11)<<m<<"与 "<<left<<setw(11)<<n<<"最大公约数: "<<Continuous_int(m,n)<<endl;
    	}
    	end=time(NULL); 
    	fclose(fp);
    	printf("The time was:%f秒\n",difftime(end,start));
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 1]

##### 算法 2：欧几里得算法 #####

算法描述
    1.r = m % n;
    2.循环直到r = 0
    	2.1m = n;
    	2.2n = r ;
    	2.3r = m % n;
    3.输出n;

#include<iostream> 
    #include<time.h> 
    #include<stdio.h> 
    #include<dos.h> 
    #include<iomanip> 
    using namespace std; 
    int Euclid(int m,int n)
    {
        
    	if(m<n)	//交换使得 m>n
    	{
        
    		int t;
    		t=m;
    		m=n;
    		n=t;
    	}
    	int r=m%n;
    	while(r!=0)
    	{
        
    		m=n; n=r; r=m%n;
    	}
    	return n;
    }
    //clock 计数法
    int main()
    {
        
    	int m,n;
    	double t1,t2;
    	FILE *fp=fopen("in.txt","r");
    	if(!fp)
    	{
        
    		cout<<"can't open file"<<endl; return -1;
    	}
    	cout<<"算法 2：欧几里得算法"<<endl;
    	t1=clock(); 
    	while(!feof(fp))
    	{
        
    		fscanf(fp,"%d",&m);
    		fscanf(fp,"%d",&n);
    		cout<<left<<setw(11)<<m<<"  与	"<<left<<setw(11)<<n<<" 最 大 公 约 数 : "<<Euclid(m,n)<<endl;
    	}
    	t2=clock();
    	fclose(fp);
    	cout<<"耗时（计数法）:"<<(t2-t1)/CLK_TCK<<"秒"<<endl;
    	return 0;
    }
    //time 计时法
    int main()
    {
        
    	int m,n;
    	time_t start,end;
    	FILE *fp=fopen("in.txt","r");
    	if(!fp)
    	{
        
    		cout<<"can't open file"<<endl;	
    		return -1;
    	}
    	cout<<"算法 2：欧几里得算法"<<endl;
    	start=time(NULL); 
    	while(!feof(fp))
    	{
        
    		fscanf(fp,"%d",&m);
    		fscanf(fp,"%d",&n);
    		cout<<left<<setw(11)<<m<<" 与 "<<left<<setw(11)<<n<<" 最 大 公 约 数 : "<<Euclid(m,n)<<endl;
    	}
    	end=time(NULL);
    	fclose(fp);
    	printf("The time was:%f 秒\n",difftime(end,start));
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 3]

##### 算法 3：分解质因数法 #####

1：对 m 分解质因数
    	1.1：i=2，num1=0。
    	1.2：若 m 不小于 i，转第 1.3 步；否则，结束分解。
    	1.3：若 m 能整除 i，转第 1.4 步；否则，i++，转第 1.2 步。
    	1.4：m=m/i, i 存入数组 a，num1++，转第 1.2 步。
    2：同理对 n 分解质因数
    3：对 m，n 提取公因数
    3.1：i=0 j=0 gcd=1
    	3.2：若 a[i]等于 b[j]，则 gcd=gcd*a[j]，i++，j++；否则，转第 3.3 步。
    	3.3：若 a[i]小于 b[j]，转 3.4 步；否则，转 3.5 步。
    	3.4：i++，若 i 小于数组 a 中的质因数总数 num1，转第 3.2 步；否则算法结束。
    	：j++，若 j 小于数组 b 中的质因数总数 num2，转第 3.2 步；否则算法结束。

#include<iostream> #include<time.h> #include<stdio.h> #include<dos.h> #include<iomanip> using namespace std;
    void Divide(int m,int a[],int &num)	//分解质因数法
    {
        
    	num=0; int i=2;
    	while(i<=m)
    	{
        
    		while(m>0&&m%i==0)
    		{
        
    			a[num]=i;
    			m=m/i;
    			num++;
    		} 
    		i++;
    		}
    	}
    int Same(int a[],int n1,int b[],int n2)	//相同质因子之积
    {
        
    	int i=0,j=0;
    	int gcd=1;
    	while(i<n1&&j<n2)
    	{
        
    		if(a[i]==b[j])
    		{
        
    			gcd*=a[i];	//找到一个公因子
    			i++;
    			j++;
    		}
    		else if(a[i]<b[j]) 
    		{
        
    			i++;
    		}
    		else
    		{
        
    			j++;
    		}
    	}
    	return gcd;
    }
    //clock 计数法
    int main()
    {
        
    	int m,n;	//m,n 为待处理整数
    	int a[100],b[100];//存放质因数的数组
    	int num1,num2;//存放质因数的个数
    	double t1,t2;
    	FILE *fp=fopen("in.txt","r"); 
    	if(!fp)
    	{
        
    		cout<<"can't open file"<<endl;
    		return -1;
    	}
    	cout<<"算法 3：分解质因数"<<endl;
    	t1=clock(); 
    	while(!feof(fp))
    	{
        
    		fscanf(fp,"%d",&m);
    		fscanf(fp,"%d",&n);
    		Divide(m,a,num1);	//分解质因数
    		Divide(n,b,num2);		//分解质因数cout<<left<<setw(11)<<m<<"与	"<<left<<setw(11)<<n<<"最大公约数:
    		"<<Same(a,num1,b,num2)<<endl;
    	}
    	t2=clock(); 
    	fclose(fp);
    	cout<<"耗时（计数法）:"<<(t2-t1)/CLK_TCK<<"秒"<<endl;
    	return 0;
    }
    //time 计时法
    int main()
    {
        
    	int m,n;	//m,n 为待处理整数
    	int a[100],b[100];	//存放质因数的数组
    	int num1,num2;	//存放质因数的个数
    	time_t start,end;
    	FILE *fp=fopen("in.txt","r"); 
    	if(!fp)
    	{
        
    		cout<<"can't open file"<<endl;
    		return -1;
    	}
    	cout<<"算法 3：分解质因数"<<endl;
    	start=time(NULL);
    	while(!feof(fp))
    	{
        
    		fscanf(fp,"%d",&m);
    		fscanf(fp,"%d",&n); 
    		Divide(m,a,num1);	//分解质因数Divide(n,b,num2);	//分解质因数
    		cout<<left<<setw(11)<<m<<"与 "<<left<<setw(11)<<n<<"最大公约数:
    		"<<Same(a,num1,b,num2)<<endl;
    	}
    	end=time(NULL);
    	fclose(fp);
    	printf("The time was:%f 秒\n",difftime(end,start));
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 5]

##### 算法 4：短除法 #####

算法描述
    1.i=2，gcd=1。
    2.若m小于n，则交换m和n的值。
    3.若i不大于n，则转步骤4；否则，输出gcd。
    4.若m和n同时整除i，则m=m/i，n=n/i，gcd=gcd*i；否则，i++，转步骤3。

#include<iostream>
    #include<time.h>
    #include<stdio.h> 
    #include<dos.h> 
    #include<iomanip> 
    using namespace std;
    int Gcd(int m,int n)	//分解质因数法
    {
        
    	if(m<n)	//保证 m 大 n 小
    	{
        
    		int t;
    		t=m;
    		m=n;
    		n=t;
    	}
    	int gcd=1,i=2;
    	while(i<=n)	//n 是较小数
    	{
        
    		while(m%i==0&&n%i==0)
    		{
        
    			gcd=gcd*i;	//i 是公因子
    			m=m/i;
    			n=n/i;
    		}
    		i++;	//寻找下一个公因子
    	}
    	return gcd;
    }
    //clock 计数法
    int main()
    {
        
    	int m,n;
    	double t1,t2;
    	FILE *fp=fopen("in.txt","r"); 
    	if(!fp)
    	{
        
    		cout<<"can't open file"<<endl;
    		return -1;
    	}
    	cout<<"算法 4：短除法"<<endl;
    	t1=clock(); 
    	while(!feof(fp))
    	{
        
    		fscanf(fp,"%d",&m);
    		fscanf(fp,"%d",&n);
    		cout<<left<<setw(11)<<m<<"  与	"<<left<<setw(11)<<n<<" 最 大 公 约 数 : "<<Gcd(m,n)<<endl;
    	}
    	t2=clock();
    	fclose(fp);
    	cout<<"耗时（计数法）:"<<(t2-t1)/CLK_TCK<<"秒"<<endl;
    	return 0;
    }
    //time 计时法
    int main()
    {
        
    	int m,n;
    	time_t start,end;
    	FILE *fp=fopen("in.txt","r");
    	if(!fp)
    	{
        
    		cout<<"can't open file"<<endl; return -1;
    	}
    	cout<<"算法 4：短除法"<<endl;
    	start=time(NULL);
    	while(!feof(fp))
    	{
        
    		fscanf(fp,"%d",&m);
    		fscanf(fp,"%d",&n);
    		cout<<left<<setw(11)<<m<<" 与 "<<left<<setw(11)<<n<<" 最 大 公 约 数 : "<<Gcd(m,n)<<endl;
    	}
    	end=time(NULL);
    	fclose(fp);
    	printf("The time was:%f 秒\n",difftime(end,start));
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 7]

##### 总结 #####

算法一“连续整数探测”是蛮力法，当 min(m,n)较小时，也是比较好的方法。算法二“欧几里得”，古老悠久，代码简洁，当 m 和 n 相差巨大时，算法中的模运算可将大数迅速转化为小数。而算法三“分解质因数”和算法四“短除法”， 本质都是求质因数，但短除法不必求出所有质因数后再提取公共质因数，而是直接求公共质因数，因此效率比分解质因数更高。  
求解最大公因数很简单，却有多种算法供解决，并且大多算法还可改进，这让我意识到一个好算法是反复努力和重新修正的结果。通过实验一，我理清了算法设计的一般过程，即：明确待处理问题，分析问题，算则算法设计技术，设计并描述算法，手工运算算法，分析算法的效率，满意后再根据算法编写代码。同时也加深了对算法五大特性的理解。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200705201826401.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200705201904668.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200705202308198.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200705202422698.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200705203159620.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200705204206776.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200705211343879.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200705211719728.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw==,size_16,color_FFFFFF,t_70