Evo. G Tech Team Forum
Welcome to Evo. G Tech Team Forum. We have moved to a new website : www.evogtechteam.com

Thanks you.

by Evo. G Tech Team Management.

用C++找出HCF和LCF

View previous topic View next topic Go down

用C++找出HCF和LCF

Post by too wei on August 30th 2015, 23:36

最大公约数Highest Common Factor(HCF)
最小公倍数Lowest Common Factor(LCF)


这里介绍了2种找出HCF的方法
只要找到了HCF,使用以下算法就可找出LCF

LCF=两整数的乘积 / HCF


1. 辗转相除法

有两整数a和b:
① a%b得余数c
② 若c=0,则b即为两数的最大公约数
③ 若c≠0,则a=b,b=c,再回去执行①

例如求27和15的最大公约数过程为
27÷15 余12
15÷12余3
12÷3余0
因此,3即为最大公约数

Code:
int func(int max,int min)   //if max = 30,min = 20
{
   int temp = 0;
   if(max < min)
   //make sure max is really max
   {
      temp = max;
      max=min;
      min=temp;
   }

   do
   {
      temp = max % min;   //reuse temp variable   //30%20   = 10   //20%10 = 0
      max = min;   //max = 20   //max = 10
      min = temp;  //min = 10   //min = 0
   }while(min != 0);

   return max;   //10
}



Code:
//递归版本
int cal_HCF(int max,int min)
{
   int temp = 0;
   if(max < min)   //make sure max is really max
   {
      temp = max ;
      max = min;
      min = temp;
   }

   temp = max % min;   //reuse temp
   max = min;
   min = temp;

   if(min != 0)
      cal_HCF(max,min);
   else
      return max;

}


2.相减法

有两整数a和b
① 若a>b,则a=a-b
② 若a小于b,则b=b-a
③ 若a=b,则a(或b)即为两数的最大公约数
④ 若a≠b,则再回去执行①

例如求27和15的最大公约数过程为:
27-15=12
( 15>12 ) 15-12=3
( 12>3 )12-3=9
( 9>3 ) 9-3=6
( 6>3 )6-3=3
( 3==3 ) //answer!

Code:
void main ( )     //相减法求最大公约数
{
   int m, n, a, b, c;
   cout<<"Input two integer numbers:"<<endl;
   cin>>a;
   cin>>b;
   m=a;
   n=b;
   // a, b不相等,大数减小数,直到相等为止

   while ( a!=b)
   {
      if (a>b)        a=a-b;         
      else  b=b-a;
   }
   cout<<"The largest common divisor:"<<a<<endl;
   cout<<"The least common multiple:"<<m*n/a<<endl;
}

too wei
Sponsor
Sponsor

Posts : 31
Points : 17731
Reputation : 0
Join date : 2015-04-21
Age : 19
Location : Johor

View user profile

Back to top Go down

View previous topic View next topic Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum