Demo entry 6785147

ew

   

Submitted by anonymous on Mar 13, 2019 at 12:34
Language: C. Code size: 3.5 kB.

/***

     @Author:Innocence
	 @OS:Win10
	 @IDE:dev c++
	 @Edition:1.0 2019/3/10
			  2.0 2019/3/12
			  3.0 2019/3/13 
	 @Description:1.利用辗转相除法、穷举法、更相减损术、Stein算法求出两个数的最大公约数和(或)最小公倍数
				  2.输入测试数据组数,每组随机生成两个数,计算最大公约数和(或)最小公倍数
				  3.获取每种算法运行时间,计算每种算法平均运行时间

***/
#include <stdio.h>   //输入输出类头文件
#include <time.h>    //随机种子头文件
#include <stdlib.h>
#include <math.h>
#include <windows.h>

//辗转相除法函数嵌套求两数的最大公约数
int divisor_1 (int a,int b)    
{
	int temp;    //定义整型变量
 	if(a<b) {    //通过比较求出两个数中的最大值和最小值
    	temp=a;
    	a=b;
    	b=temp;
    }    //设置中间变量进行两数交换
   	while(b!=0) {    //通过循环求两数的余数,直到余数为0
    	temp=a%b;
    	a=b;    //变量数值交换
    	b=temp;
    }
  	return a;    //返回最大公约数到调用函数处
}
//辗转相除法函数嵌套求两数的最小公倍数
int multiple_1 (int a,int b)    
{
 	int divisor (int a,int b);    //自定义函数返回值类型
    int temp;
  	temp=divisor_1(a,b);    //再次调用自定义函数,求出最大公约数
  	return  (a*b/temp);    //返回最小公倍数到主调函数处进行输出
}
//辗转相除法函数递归调用
int gcd_1 (int a,int b)
{  
	if(a%b==0)
       return b;   
	else  
       return gcd_1(b,a%b);
 }

//穷举法求两数的最大公约数
 int divisor_2 (int a,int b)    
{
    int  temp;    //定义义整型变量
    temp=(a>b)?b:a;    //采种条件运算表达式求出两个数中的最小值
    while(temp>0){     
    	if (a%temp==0&&b%temp==0)    //只要找到一个数能同时被a,b所整除,则中止循环
          	break;    
       	temp--;    //如不满足if条件则变量自减,直到能被a,b所整除
    }
  	return  temp;    //返回满足条件的数到主调函数处
}
//穷举法求两数的最小公倍数
int multiple_2 (int a,int b)
{
  	int p,q,temp;
  	p=(a>b)?a:b;    //求两个数中的最大值
  	q=(a>b)?b:a;    //求两个数中的最小值
	temp=p;    //最大值赋给p为变量自增作准备
 	while(1){    //利用循环语句来求满足条件的数值
 	 	if(p%q==0)
      		break;    //只要找到变量的和数能被a或b所整除,则中止循环
    	p+=temp;    //如果条件不满足则变量自身相加
  	}
  	return  p;
}

//更相减损术求最大公约数
int gcd_3(int m,int n)
{
	int i=0,temp,x;
	while(m%2==0 && n%2==0)  //判断m和n能被多少个2整除
	{
		m/=2;
		n/=2;
		i+=1;
	}
	if(m<n){    //m保存大的值
		temp=m;
		m=n;
		n=temp;
	}
	while(x){
		x=m-n;
		m=(n>x)?n:x;
		n=(n<x)?n:x;
		if(n==(m-n))
			break;
	}
	if(i==0)
		return n;
	else 
		return ((int)pow(2,i)*n);
}

//Stein算法非递归调用求最大公约数
int Stein(unsigned int x,unsigned int y)
{
	int factor = 0;
	int temp;
	if ( x < y ){
	temp = x;
	x = y;
	y = temp;
    }
    if ( 0 == y )
		return 0;
	while ( x != y ){
		if ( x & 0x1 ){    //x为奇数 
			if ( y & 0x1 ){    //x和y都为奇数 
				y = ( x - y ) >> 1;
                x -= y;
            }
            else{    //x为奇数y为偶数 
                y >>= 1;
            }
        }
        else{    //x为偶数 
			if ( y & 0x1 ){    //x为偶数y为奇数 
				x >>= 1;
                if ( x < y ){
					temp = x;
                    x = y;
                    y = temp;
                }
            }
            else{    //x和y都为偶数 
                x >>= 1;
                y >>= 1;
                ++factor;
            }
        }
    }
	return ( x << factor );
}
//Stein算法递归调用求最大公约数
int gcd_4(int u,int v)
{
    if (u == 0) return v;
    if (v == 0) return u;
    //找2的因素 
    if (~u & 1)    // u是偶数 
    {
        if (v & 1)    //v是奇数 
            return gcd_4(u >> 1, v);
        else    //u和v都是偶数 
            return gcd_4(u >> 1, v >> 1) << 1;
    }
     if (~v & 1)    //u是奇数,v是偶数 
        return gcd_4(u, v >> 1);
     // 减少较大的参数
    if (u > v)
        return gcd_4((u - v) >> 1, v);
     return gcd_4((v - u) >> 1, u);
}
int max(int a,int b)
{
	if (a>b)
		return a;
	else 
	    return b;
}
int min(int a,int b)
{
	if (a>b)
		return b;
	else 
	    return a;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).