喜迎
春节

最大公约数几种算法分析

程序设计方法学作业
技术
发布日期:   2019-03-09
文章字数:   4.4k
阅读时长:   22 分

程序设计方法学上机——（一）

 

  • 题目：

运行最大公约数的常用算法，进行程序的调试与测试，要求程序设计风良好，并添加异常处理模块（如非法输入）。

 

  1. 辗转相除法：

其算法过程为： 前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数

==>大数放a中、小数放b中；

==>求a/b的余数；

==>若temp=0则b为最大公约数；

==>如果temp!=0则把b的值给a、temp的值给a；

==>返回第二步；

(1)非递归

(2)递归

  1. 穷举法：

穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。

  1. 更相减损法：

==>任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

==>以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

  1. Stein算法

对两个正整数 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( x,x ) = x ，就用这个。

  1. 非递归
  2. 递归
  • 算法构造：
  1. 辗转相除流程图：

(1)非递归：

 

(2)递归：

 

 

 

  1. 穷举法流程图：

 

 

  1. 更相减损法流程图：

 

  1. Stein算法流程图：
  1. 非递归：

 

  1. 递归：

 

  • 算法实现：（源码）
  1. 辗转相除法：

(1)非递归：

  1. //辗转相除法
  2.  
  3. /*函数嵌套调用*/
  4.  
  5.  
  6.  
  7. #include<stdio.h>  /*输入输出类头文件*/
  8.  
  9. #include<stdlib.h>
  10.  
  11. #include<time.h>
  12.  
  13. #include<windows.h>
  14.  
  15.  
  16.  
  17. int GCD (int a,int b)    /*自定义函数求两数的最大公约数*/
  18.  
  19. {
  20.  
  21.   int  temp;          /*定义整型变量,用于交换变量时做临时变量*/
  22.  
  23.   if(a<b)             /*通过比较求出两个数中的最大值和最小值*/
  24.  
  25.     { temp=a;a=b;b=temp;} /*设置中间变量进行两数交换*/
  26.  
  27.    while(b!=0)           /*通过循环求两数的余数，直到余数为0*/
  28.  
  29.     {
  30.  
  31.       temp=a%b;
  32.  
  33.       a=b;              /*变量数值交换*/
  34.  
  35.       b=temp;
  36.  
  37.     }
  38.  
  39.   return (a);            /*返回最大公约数到调用函数处*/
  40.  
  41. }
  42.  
  43.  
  44.  
  45.  
  46.  
  47. int main()
  48.  
  49. {
  50.  
  51. /*计时函数所需定义语句*/
  52.  
  53. double dur;
  54.  
  55. LARGE_INTEGER time_start;
  56.  
  57. LARGE_INTEGER time_over;
  58.  
  59. double dqFreq;
  60.  
  61. LARGE_INTEGER f;
  62.  
  63. QueryPerformanceFrequency(&f);
  64.  
  65. dqFreq=(double)f.QuadPart;
  66.  
  67.  
  68.  
  69.  int gcd; /*公约数*/
  70.  
  71.  int i,a[100001],b[100001]; /*定义两个数组*/
  72.  
  73.  srand(1);                  /*随机函数*/
  74.  
  75.  for(i=0;i<20;i++)         /*循环来控制数据规模*/
  76.  
  77.  {
  78.  
  79.   a[i]=1+rand()%100;
  80.  
  81.   b[i]=1+rand()%100;
  82.  
  83.  }
  84.  
  85.  QueryPerformanceCounter(&time_start);
  86.  
  87. for(i=0;i<20;i++)
  88.  
  89. {
  90.  
  91.   gcd=GCD(a[i],b[i]);    /*自定义函数*/
  92.  
  93.   printf("随机数为%d,%d",a[i],b[i]);
  94.  
  95.   printf("这两个整数的最大公约数是 %d\n\n",gcd);  /*输出最大公约数*/
  96.  
  97.   QueryPerformanceCounter(&time_over);
  98.  
  99.   dur=(time_over.QuadPart-time_start.QuadPart)/dqFreq;
  100.  
  101. }
  102.  
  103. printf("所需时间%f seconds\n",dur);
  104.  
  105.  return 0;
  106.  
  107. }
  1. 递归：
  1. //辗转相除法
  2.  
  3. /*函数递归*/
  4.  
  5.  
  6.  
  7.  
  8.  
  9. #include<stdio.h>  /*输入输出类头文件*/
  10.  
  11. #include<stdlib.h>
  12.  
  13. #include<windows.h>
  14.  
  15.  
  16.  
  17. int GCD (int a,int b) /*自定义函数求两数的最大公约数*/
  18.  
  19. {  if(a%b==0) /*看b是否是最大公约*/
  20.  
  21.        return b;
  22.  
  23. else
  24.  
  25.        return GCD(b,a%b);
  26.  
  27. }
  28.  
  29.  
  30.  
  31. int main() /*主函数*/
  32.  
  33. {
  34.  
  35. /*计时函数所需定义语句*/
  36.  
  37. double dur;
  38.  
  39. LARGE_INTEGER time_start;
  40.  
  41. LARGE_INTEGER time_over;
  42.  
  43. double dqFreq;
  44.  
  45. LARGE_INTEGER f;
  46.  
  47. QueryPerformanceFrequency(&f);
  48.  
  49. dqFreq=(double)f.QuadPart;
  50.  
  51.  
  52.  
  53.  int gcd; /*变量用于存最大公约数*/
  54.  
  55.  int i,a[100001],b[100001]; /*定义两个数组*/
  56.  
  57.  
  58.  
  59.  srand(10);                     /*随机函数*/
  60.  
  61.  for(i=0;i<100000;i++)
  62.  
  63.  {
  64.  
  65.   a[i]=1+rand()%100;
  66.  
  67.   b[i]=1+rand()%100;
  68.  
  69.  }
  70.  
  71.  
  72.  
  73.  QueryPerformanceCounter(&time_start);
  74.  
  75. for(i=0;i<100000;i++)
  76.  
  77. {
  78.  
  79.  
  80.  
  81.   gcd=GCD(a[i],b[i]);           /*自定义主调函数*/
  82.  
  83.   printf("随机数为%d,%d",a[i],b[i]);
  84.  
  85.   printf("这两个整数的最大公约数是 %d\n\n",gcd);  /*输出最大公约数*/
  86.  
  87.  
  88.  
  89.   QueryPerformanceCounter(&time_over);
  90.  
  91.   dur=(time_over.QuadPart-time_start.QuadPart)/dqFreq;
  92.  
  93. }
  94.  
  95. printf("所需时间%f seconds\n",dur);
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  return 0;
  102.  
  103. }
  104.

 

 

  1. 穷举法：
  1. //穷举法
  2.  
  3. #include<stdio.h>  /*输入输出类头文件*/
  4.  
  5. #include<stdlib.h>
  6.  
  7. #include<time.h>
  8.  
  9. #include<windows.h>
  10.  
  11. #include<math.h>
  12.  
  13. int GCD (int a,int b) /*自定义函数求两数的最大公约数*/
  14.  
  15. {
  16.  
  17.     int  temp;          /*定义义整型变量*/
  18.  
  19.     temp=(a>b)?b:a;    /*采种条件运算表达式求出两个数中的最小值*/
  20.  
  21.     while(temp>0)
  22.  
  23.     {
  24.  
  25.        if (a%temp==0&&b%temp==0) /*只要找到一个数能同时被a,b所整除，则中止循环*/
  26.  
  27.           break;
  28.  
  29.        temp--;      /*如不满足if条件则变量自减，直到能被a,b所整除*/
  30.  
  31.     }
  32.  
  33.   return (temp); /*返回满足条件的数到主调函数处*/
  34.  
  35. }
  36.  
  37.  
  38.  
  39. int main()
  40.  
  41. {
  42.  
  43. /*计时函数所需定义语句*/
  44.  
  45. double dur;
  46.  
  47. LARGE_INTEGER time_start;
  48.  
  49. LARGE_INTEGER time_over;
  50.  
  51. double dqFreq;
  52.  
  53. LARGE_INTEGER f;
  54.  
  55. QueryPerformanceFrequency(&f);
  56.  
  57. dqFreq=(double)f.QuadPart;
  58.  
  59.  
  60.  
  61.  int gcd; /*变量用于存最大公约数*/
  62.  
  63.  int i,a[100001],b[100001];     /*定义两个数组*/
  64.  
  65.  
  66.  
  67.  srand(10);                     /*随机函数*/
  68.  
  69.  for(i=0;i<100000;i++) /*通过循环输入规模*/
  70.  
  71.  {
  72.  
  73.   a[i]=1+rand()%100;
  74.  
  75.   b[i]=1+rand()%100;
  76.  
  77.  }
  78.  
  79.  
  80.  
  81.  QueryPerformanceCounter(&time_start);
  82.  
  83. for(i=0;i<100000;i++)
  84.  
  85. {
  86.  
  87.  
  88.  
  89.   gcd=GCD(a[i],b[i]); /*自定义主调函数*/
  90.  
  91.   printf("随机数为%d,%d",a[i],b[i]);
  92.  
  93.   printf("这两个整数的最大公约数是 %d\n\n",gcd);  /*输出最大公约数*/
  94.  
  95.   QueryPerformanceCounter(&time_over);
  96.  
  97.   dur=(time_over.QuadPart-time_start.QuadPart)/dqFreq;
  98.  
  99. }
  100.  
  101. printf("所需时间%f seconds\n",dur);
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  return 0;
  108.  
  109. }

 

  1. 更相减损：
  1. //更相减损
  2.  
  3.  
  4.  
  5. #include<stdio.h>  /*输入输出类头文件*/
  6.  
  7. #include<stdlib.h>
  8.  
  9. #include<time.h>
  10.  
  11. #include<windows.h>
  12.  
  13. #include<math.h>
  14.  
  15. int GCD(int m,int n)
  16.  
  17. {
  18.  
  19. int i=0,temp,x;
  20.  
  21. while(m%2==0 && n%2==0)  //判断m和n能被多少个2整除
  22.  
  23. {
  24.  
  25. m/=2;
  26.  
  27. n/=2;
  28.  
  29. i+=1;
  30.  
  31. }
  32.  
  33. if(m<n)     //m保存大的值
  34.  
  35. {
  36.  
  37. temp=m;
  38.  
  39. m=n;
  40.  
  41. n=temp;
  42.  
  43. }
  44.  
  45. while(x)
  46.  
  47. {
  48.  
  49. x=m-n;
  50.  
  51. m=(n>x)?n:x;
  52.  
  53. n=(n<x)?n:x;
  54.  
  55. if(n==(m-n))
  56.  
  57. break;
  58.  
  59. }
  60.  
  61. if(i==0)
  62.  
  63. return n;
  64.  
  65. else
  66.  
  67. return (int )pow(2,i)*n;
  68.  
  69. }
  70.  
  71. int main()
  72.  
  73. {
  74.  
  75. //计时函数所需的定义语句
  76.  
  77. double dur;
  78.  
  79. LARGE_INTEGER time_start;
  80.  
  81. LARGE_INTEGER time_over;
  82.  
  83. double dqFreq;
  84.  
  85. LARGE_INTEGER f;
  86.  
  87. QueryPerformanceFrequency(&f);
  88.  
  89. dqFreq=(double)f.QuadPart;
  90.  
  91.  
  92.  
  93.  int gcd; //定义变量用于存放最大公约数
  94.  
  95.  int i,a[100001],b[100001];//定义两个数组
  96.  
  97.  
  98.  
  99.  srand(10);      //随机函数
  100.  
  101.  for(i=0;i<100000;i++) //通过循环控制规模
  102.  
  103.  {
  104.  
  105.   a[i]=1+rand()%100;
  106.  
  107.   b[i]=1+rand()%100;
  108.  
  109.  }
  110.  
  111.  QueryPerformanceCounter(&time_start);
  112.  
  113. for(i=0;i<100000;i++)
  114.  
  115. {
  116.  
  117.  
  118.  
  119.   gcd=GCD(a[i],b[i]); //自定义主调函数
  120.  
  121.   printf("随机数为%d,%d",a[i],b[i]);
  122.  
  123.   printf("这两个整数的最大公约数是 %d\n\n",gcd);  /*输出最大公约数*/
  124.  
  125.   QueryPerformanceCounter(&time_over);
  126.  
  127.   dur=(time_over.QuadPart-time_start.QuadPart)/dqFreq;
  128.  
  129. }
  130.  
  131. printf("所需时间%f seconds\n",dur);
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  return 0;
  138.  
  139. }

 

  1. Stein算法：
  1. 非递归：
  1.  //stein
  2.  
  3.  /*非递归*/
  4.  
  5. #include<stdio.h>  /*输入输出类头文件*/
  6.  
  7. #include<stdlib.h>
  8.  
  9. #include<time.h>
  10.  
  11. #include<windows.h>
  12.  
  13. #include<math.h>
  14.  
  15.  
  16.  
  17.  
  18.  
  19.  int SteinGCD( unsigned int x, unsigned int y )
  20.  
  21.   /* return the greatest common divisor of x and y */
  22.  
  23. {
  24.  
  25.         int factor = 0;
  26.  
  27.         int temp;
  28.  
  29.         if ( x < y )
  30.  
  31.         {
  32.  
  33.                 temp = x;
  34.  
  35.                 x = y;
  36.  
  37.                 y = temp;
  38.  
  39.         }
  40.  
  41.         if ( 0 == y )
  42.  
  43.         {
  44.  
  45.                 return 0;
  46.  
  47.         }
  48.  
  49.         while ( x != y )
  50.  
  51.         {
  52.  
  53.                 if ( x & 0x1 )
  54.  
  55.                 {/* when x is odd */
  56.  
  57.                         if ( y & 0x1 )
  58.  
  59.                         {/* when x and y are both odd */
  60.  
  61.                                 y = ( x - y ) >> 1;
  62.  
  63.                                 x -= y;
  64.  
  65.                         }
  66.  
  67.                         else
  68.  
  69.                         {/* when x is odd and y is even */
  70.  
  71.                                 y >>= 1;
  72.  
  73.                         }
  74.  
  75.                 }
  76.  
  77.                 else
  78.  
  79.                 {/* when x is even */
  80.  
  81.                         if ( y & 0x1 )
  82.  
  83.                         {/* when x is even and y is odd */
  84.  
  85.                                 x >>= 1;
  86.  
  87.                                 if ( x < y )
  88.  
  89.                                 {
  90.  
  91.                                         temp = x;
  92.  
  93.                                         x = y;
  94.  
  95.                                         y = temp;
  96.  
  97.                                 }
  98.  
  99.                         }
  100.  
  101.                         else
  102.  
  103.                         {/* when x and y are both even */
  104.  
  105.                                 x >>= 1;
  106.  
  107.                                 y >>= 1;
  108.  
  109.                                 ++factor;
  110.  
  111.                         }
  112.  
  113.                 }
  114.  
  115.         }
  116.  
  117.         return ( x << factor );
  118.  
  119. }
  120.  
  121.  
  122.  
  123. int main()
  124.  
  125. {
  126.  
  127. //计时函数所需要定义的语句
  128.  
  129. double dur;
  130.  
  131. LARGE_INTEGER time_start;
  132.  
  133. LARGE_INTEGER time_over;
  134.  
  135. double dqFreq;
  136.  
  137. LARGE_INTEGER f;
  138.  
  139. QueryPerformanceFrequency(&f);
  140.  
  141. dqFreq=(double)f.QuadPart;
  142.  
  143.  
  144.  
  145.  int gcd;//定义变量用于存放最大公约数
  146.  
  147.  int i,a[100001],b[100001];//定义两个数组
  148.  
  149.  
  150.  
  151.  srand(10);   //随机函数
  152.  
  153.  for(i=0;i<100000;i++)//通过循环控制规模
  154.  
  155.  {
  156.  
  157.   a[i]=1+rand()%100;
  158.  
  159.   b[i]=1+rand()%100;
  160.  
  161.  }
  162.  
  163.  
  164.  
  165.  QueryPerformanceCounter(&time_start);
  166.  
  167. for(i=0;i<100000;i++)
  168.  
  169. {
  170.  
  171.  
  172.  
  173.   gcd=SteinGCD(a[i],b[i]);
  174.  
  175.   printf("随机数为%d,%d",a[i],b[i]);
  176.  
  177.   printf("这两个整数的最大公约数是 %d\n\n",gcd);  /*输出最大公约数*/
  178.  
  179.   //printf("所需时间%f\n",(double)(end-start)/CLOCKS_PER_SEC);
  180.  
  181.   QueryPerformanceCounter(&time_over);
  182.  
  183.   dur=(time_over.QuadPart-time_start.QuadPart)/dqFreq;
  184.  
  185. }
  186.  
  187. printf("所需时间%f seconds\n",dur);
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  return 0;
  194.  
  195. }
  196.
  1. 递归：
  1. //stein
  2.  
  3. /*递归实现*/
  4.  
  5. #include<stdio.h>  /*输入输出类头文件*/
  6.  
  7. #include<stdlib.h>
  8.  
  9. #include<time.h>
  10.  
  11. #include<windows.h>
  12.  
  13. #include<math.h>
  14.  
  15. int SteinGCD(int u,int v)
  16.  
  17. {
  18.  
  19.     if (u == 0) return v;
  20.  
  21.     if (v == 0) return u;
  22.  
  23.     // look for factors of 2
  24.  
  25.     if (~u & 1) // u is even
  26.  
  27.     {
  28.  
  29.         if (v & 1) // v is odd
  30.  
  31.             return SteinGCD(u >> 1, v);
  32.  
  33.         else // both u and v are even
  34.  
  35.             return SteinGCD(u >> 1, v >> 1) << 1;
  36.  
  37.     }
  38.  
  39.      if (~v & 1) // u is odd, v is even
  40.  
  41.         return SteinGCD(u, v >> 1);
  42.  
  43.      // reduce larger argument
  44.  
  45.     if (u > v)
  46.  
  47.         return SteinGCD((u - v) >> 1, v);
  48.  
  49.      return SteinGCD((v - u) >> 1, u);
  50.  
  51. }
  52.  
  53. int main()
  54.  
  55. {
  56.  
  57. //计时函数所需要定义的语句
  58.  
  59. double dur;
  60.  
  61. LARGE_INTEGER time_start;
  62.  
  63. LARGE_INTEGER time_over;
  64.  
  65. double dqFreq;
  66.  
  67. LARGE_INTEGER f;
  68.  
  69. QueryPerformanceFrequency(&f);
  70.  
  71. dqFreq=(double)f.QuadPart;
  72.  
  73.  
  74.  
  75.  int gcd;//定义变量用于存放最大公约数
  76.  
  77.  int i,a[100001],b[100001];//定义两个数组
  78.  
  79.  
  80.  
  81.  srand(10);   //随机函数
  82.  
  83.  for(i=0;i<100000;i++)//通过循环控制规模
  84.  
  85.  {
  86.  
  87.   a[i]=1+rand()%100;
  88.  
  89.   b[i]=1+rand()%100;
  90.  
  91.  }
  92.  
  93.  
  94.  
  95.  QueryPerformanceCounter(&time_start);
  96.  
  97. for(i=0;i<100000;i++)
  98.  
  99. {
  100.  
  101.  
  102.  
  103.   gcd=SteinGCD(a[i],b[i]);
  104.  
  105.   printf("随机数为%d,%d",a[i],b[i]);
  106.  
  107.   printf("这两个整数的最大公约数是 %d\n\n",gcd);  /*输出最大公约数*/
  108.  
  109.   //printf("所需时间%f\n",(double)(end-start)/CLOCKS_PER_SEC);
  110.  
  111.   QueryPerformanceCounter(&time_over);
  112.  
  113.   dur=(time_over.QuadPart-time_start.QuadPart)/dqFreq;
  114.  
  115. }
  116.  
  117. printf("所需时间%f seconds\n",dur);
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  return 0;
  124.  
  125. }

 

  • 调试、测试：
  1. 调试：
  1. 随机数调试：（以3组数据为例）

 

===>观察a[i],b[i]当i在变化是每次的不同随机数，此时为未开始，二者为0;

 

===>i=0时，a[i]=72,b[i]=100

 

 

===>i=1时，a[i]=73,b[i]=95

 

===>i=2,a[i]=98,b[i]=97

 

 

 

  1. 测试:

 

--Stein递归--

 

 

 

--Stein非递归--

 

 

--更相减损--

 

--穷举法--

 

 

--辗转相除递归--

 

 

--辗转相除非递归--

  • 分析：

 

 

--测试时间的表格结果--

  1. 6种算法比较：规模相同，数据范围相同：

在100组数据和1000组数据：辗转相除非递归算法效率比较高；

在10000组数据：stein算法效率较高

 

 

  1. 同一种算法比较，数据范围不同时，运行时间的变化幅度：

对于6种方法，当规模相同，随着随机数的范围不同，运行时间都有所增加，其中辗转相除非递归增加最为明显，

 

  • 总结：

本程序运用六种代码来测试效率，采取了平均值来避免偶然性误差。

 

本实验为了测试求最大公约数的算法效率，在实验过程中，遇到了一些问题。

  1. 刚开始手动输入两位两位数据，发现效率低且不能进行大规模数据测试
  2. 计时函数在用的时候是在网上看了一些程序采用到本程序上

不足：

  1. 测试数据没有实现数据为0时求公约数
  2. 每次运行时间差异较大，没有找到原因所在
  3. 感觉数据测试不是很准确，数据规模范围没有达到比较好的地步

 

如果有什么错误请各位大神指出来，完成之后记得撒花撒花~~

文章作者: 周周
文章链接: https://zznomuxu.github.io/posts/zuoye3.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 周周 !
程序设计方法学作业
赏
评 论
  目录