当前位置: 首页 > Python > 正文

递归法求最大公约数

一. 题目分析如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。根据约数的定义可知,某个数的所有约数一定不大于这个数本身,几个自

小编

一. 题目分析

如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。

根据约数的定义可知,某个数的所有约数一定不大于这个数本身,几个自然数的最大公约数也一定不大于其中任何一个数。所以当要求任意两个正整数的最大公约数,即是求出一个不大于其中两数中的任何一个,但又能同时整除两个整数的最大自然数。

二.算法构造(流程图)

1.辗转相除法


2.穷举法

3.更相减损法

4.stein算法


三.算法实现

#include <stdio.h>
#include <time.h>
#include <math.h>

int  gcd(int a,int b)//辗转相除法

 if(a%b==0)//若a能整除b则b为最大公约数
       return b;  
 else 
       return gcd(b,a%b);//否则进行递归
}

void gcd_input(int m,int n)
{
 
int t1;
t1=gcd(m,n);
printf("最大公约数是 %d\n",t1);//得出最大公约数
}


void multiple (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;   //如果条件不满足则变量自身相加
  }
 printf("最大公约数是 %d\n",a*b/p);//得出最大公约数a*b/p
}

void gcd2(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;//用i来储存2的个数
 }
 if(m<n)     //m保存大的值
 {
  temp=m;
  m=n;
  n=temp;
 }
 while(x)
 {
  x=m-n;//计算两个数的差
  m=(n>x)?n:x;//比较m和n,和差的打消
  n=(n<x)?n:x;
  if(n==(m-n))
   break;
 }
 if(i==0)
  printf("最大公约数是%d\n",n);
 else
  printf("最大公约数是%d\n",(int )pow(2,i)*n);


}

 int Stein( unsigned int x, unsigned int y )//Stein算法

  {
int factor = 0;// 当两数均为偶数时将其同时除以2至至少一数为奇数为止,
//记录除掉的所有公因数2的个数factor    
    int temp;
        if ( x < y )//让 x为两者中大的数
        {
                temp = x;
                x = y;
                y = temp;
        }
        if ( 0 == y )
        {
                return 0;
        }
        while ( x != y )
        {
                if ( x & 0x1 )//判断x是否为奇数
                {
                        if ( y & 0x1 )//再判断y是否为奇数
                        {                          
    y = ( x - y ) >> 1;//将两数之差除于2
                                x -= y;
                        }
                        else//当x为奇数,y为偶数是when x is odd and y is even
                        {
                                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;
                        }
                }
        }

  printf("最大公约数是%d\n",x << factor);
       
}


void main()

 clock_t start, finish;
 double duration;

 int i,j,x;
    int flag=1;
 int str[20]={345,12350,34363,3345,422,6755,536,57,375,57,37,975,775,4735,673,5633,563,339,596,84};
 
    while(flag)
 {
  
  printf("请选择您所使用的方法,按F键结束:\n");

  printf("1.辗转相除法\n");

  printf("2.穷举法\n");

  printf("3.更损相减法\n");

  printf("4.stein算法\n");

  scanf("%d",&x);

  if (x=='F')
   break;

 switch(x)

 {
  case 1:{
     printf("辗转相除法所得到的结果为:\n");

     start = clock();

     for( i=0;i<20;i++)
     {
      if(str[i]<0||str[i+1]<0||str[i] != (int)str[i]||str[i+1] != (int)str[i+1])
       printf("输入非法请重新输入!");//输入非法的判断

      gcd_input(str[i],str[i+1]);
     }
 
      finish = clock();

      duration = (double)(finish - start) / CLOCKS_PER_SEC;
  
      break;
     
      }
  case 2:{
     printf("穷举法所得到的结果为:\n");

     start = clock();

     for( i=0;i<20;i++)
     {
      if(str[i]<0||str[i+1]<0||str[i] != (int)str[i]||str[i+1] != (int)str[i+1])
       printf("输入非法请重新输入!");
    
      multiple(str[i],str[i+1]);
     }
  
      finish = clock();
 
      duration = (double)(finish - start) / CLOCKS_PER_SEC;
  
      break;
    
    }

  case 3:{
     printf("更损相减法所得到的结果为:\n");

     start = clock();

     for( i=0;i<20;i++)
     {
      if(str[i]<0||str[i+1]<0||str[i] != (int)str[i]||str[i+1] != (int)str[i+1])
       printf("输入非法请重新输入!");
  
      gcd2(str[i],str[i+1]);
     }
  
      finish = clock();

      duration = (double)(finish - start) / CLOCKS_PER_SEC;
  
      break;
     
      }

  case 4:{
     printf("stein法所得到的结果为:\n");
           
     start = clock();

     for( i=0;i<20;i++)
     {
     if(str[i]<0||str[i+1]<0||str[i] != (int)str[i]||str[i+1] != (int)str[i+1])
       printf("输入非法请重新输入!");
      Stein(str[i],str[i+1]);
     }
  
      finish = clock();

      duration = (double)(finish - start) / CLOCKS_PER_SEC;
  
      break;
     
      }
 
 }

 printf( "所花费时间为%f seconds\n\n", duration);

 }

}
四.调试、测试及运行结果
1.测试
1.1辗转相除法

#include <stdio.h>
#include <time.h>
#include <math.h>
int  gcd(int a,int b)//辗转相除法

 if(a%b==0)
       return b;  
 else 
       return gcd(b,a%b);
}

void gcd_input(int m,int n)
{
 
int t1;

t1=gcd(m,n);

printf("最大公约数%d\n",t1);/*最大公约数*/

}

void main()
{
 long k = 10000000;
 clock_t start, finish;
 double duration;
 int i,j,x;
    int flag=1;
 int str[20]={90,177,83,45,42,35,66,54,89,54,64,96,785,64,63,543,35,345,56,54};
 start = clock();
 for( i=0;i<20;i++)
  gcd_input(str[i],str[i+1]);
 finish = clock();
 duration = (double)(finish - start) / CLOCKS_PER_SEC;
 printf( "所花费时间为%f seconds\n\n", duration);
}


1.2穷举法

#include <stdio.h>
#include <time.h>
#include <math.h>

void multiple (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;   /*如果条件不满足则变量自身相加*/
  }
 printf("最大公约数是 %d\n",a*b/p);
}

void main()
{
  clock_t start, finish;
 double duration;
 int i,j,x;
    int flag=1;
 int str[20]={90,177,83,45,42,35,66,54,89,54,64,96,785,64,63,543,35,345,56,54};
 start = clock();
 for( i=0;i<20;i++)
  multiple(str[i],str[i+1]);
 finish = clock();
 duration = (double)(finish - start) / CLOCKS_PER_SEC;
 printf( "所花费时间为%f seconds\n\n", duration);
}

1.3更相减损法

#include <stdio.h>
#include <time.h>
#include <math.h>

void gcd2(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;
 printf("最大公约数是%d\n",n);
 else
 //return (int )pow(2,i)*n;
 printf("最大公约数是%d\n",(int )pow(2,i)*n);


}


void main()
{
  clock_t start, finish;
 double duration;
 int i,j,x;
    int flag=1;
 int str[20]={90,177,83,45,42,35,66,54,89,54,64,96,785,64,63,543,35,345,56,54};
 start = clock();
 for( i=0;i<20;i++)
 gcd2(str[i],str[i+1]);
 finish = clock();
 duration = (double)(finish - start) / CLOCKS_PER_SEC;
 printf( "所花费时间为%f seconds\n\n", duration);
}



1.4.Stein算法

#include <stdio.h>
#include <time.h>
#include <math.h>

 int Stein( unsigned int x, unsigned int y )//Stein算法

  {
int factor = 0;// 当两数均为偶数时将其同时除以2至至少一数为奇数为止,
//记录除掉的所有公因数2的个数factor    
    int temp;
        if ( x < y )//让 x为两者中大的数
        {
                temp = x;
                x = y;
                y = temp;
        }
        if ( 0 == y )
        {
                return 0;
        }
        while ( x != y )
        {
                if ( x & 0x1 )//判断x是否为奇数
                {
                        if ( y & 0x1 )//再判断y是否为奇数
                        {                          
    y = ( x - y ) >> 1;//将两数之差除于2
                                x -= y;
                        }
                        else//当x为奇数,y为偶数是when x is odd and y is even
                        {
                                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;
                        }
                }
        }

  printf("最大公约数是%d\n",x << factor);
       
}

void main()
{
 l clock_t start, finish;
 double duration;
 int i;
 int str[20]={90,177,83,45,42,35,66,54,89,54,64,96,785,64,63,543,35,345,56,54};
 start = clock();
 for( i=0;i<20;i++)
  Stein(str[i],str[i+1]);
 finish = clock();
 duration = (double)(finish - start) / CLOCKS_PER_SEC;
 printf( "所花费时间为%f seconds\n\n", duration);
}


2.运行结果
总共用了4组不同的数据来做测试,求其平均时间。
2.1辗转相除法


2.2 穷举法




平均时间为0.0495s

2.3更损相减法


2.4 Stein算法


平均时间为0.029s

五.总结
1.计算运行时间的方法

计算运行时间可以运用到clock()函数。clock函数定义如下: clock_t clock( void ); 这个函数返回从“开启这个程序进程”到“程序中调用clock()函数”时之间的CPU时钟计时单(clock tick)数。其中clock_t是用来保存时间的数据类型。

在time.h文件中,我们可以找到对它的定义:
#ifndef _CLOCK_T_DEFINED
typedef long clock_t;
#define _CLOCK_T_DEFINED
#endif

为了获取 CPU 所使用的秒数,仍需要除以 CLOCKS_PER_SEC。CLOCKS_PER_SEC 等于 1000000。在开头记录下时间start=clock(),再在末尾记录下时间end=clock(),两个时间相减即再除以CLOCKS_PER_SEC就为时间差。

2.运算符号的使用

2.1按位与(&)
a&x为对数a的二进制形式的取位操作,即去a二进制形式的第x位。在stein算法中a&1可以用于判断数a的奇偶性,即a末位为0即为偶数,末位为1的为奇数。

2.2按位左移(<<)
a<<=x等价于a*2^x,即为a乘以2的x次幂。原理是让a的二进制形式左移x位。这样与2的幂次方相乘使运算更快更方便。

2.3按位右移(>>)
a>>=x等价于a/(2^x),即使a除以2的x次幂。原理是让a的二进制形式右移x位。这样与2的幂次方相除使运算也更快。

Stein算法的优点之一就在于运用了移位运算操作,求最大公约数更加简洁和精确。
————————————————

 


上一篇: 全国青少年软件编程等级考试标准(Python1级-6级)
返回顶部