c - 2つの数値のLCM

Question

LCMプログラムの結果が間違っています。

最初に数値のgcdを見つけてから、積をgcdで割ります。

int gcd(int x, int y)
{
  while(y != 0)
  {
    int save = y;
    y = x % y;
    x = save;
  }
  return y;
}

int lcm(int x, int y)
{
  int prod = x * y;
  int Gcd = gcd(x,y);
  int lcm = prod / Gcd;

  return lcm;
}

どんな助けでも大歓迎です。

score 6 · Accepted Answer

関数gcdは常にを返し0ます。変化する

return y;

に

return x;

ユークリッドの互除法を理解する：

RULE 1: gcd(x,0) = x
RULE 2: gcd(x,y) = gcd(y,x % y)

検討x = 12し、y = 18

  gcd (12, 18)
  = gcd (18, 12)  Using rule 2
  = gcd (12,6)    Using rule 2
  = gcd (6, 0)    Using rule 1
  = 6

あなたが見ることができるように、いつyゼロxになるかはそうなるgcdので、あなたは戻る必要がありxますy。

また、lcmを計算するときは、最初に数値を乗算しているため、オーバーフローが発生する可能性があります。代わりに、次のことができます。

lcm = x * (y / gcd(x,y))

しかし、lcm収まらない場合はint、それを作成する必要がありますlong long

score 4 · Accepted Answer

問題1） int gcd = gcd(x,y);

gcdはすでに関数として定義されています。同じ名前の変数を定義することはできません。

問題2）inに変更すると、毎回0が返されreturn yます。return xgcd()

問題3）とが大きいx * y場合、オーバーフローする可能性があります。xy

score 0 · Accepted Answer

gcd関数ではyではなくxを返す必要があります。

また、製品x * yが常に？に収まると確信していますintか？そのためにもを使用することをお勧めしますlong long。

score 0 · Accepted Answer

#include <iostream>

using namespace std; 

long long gcd(long long int a, long long int b){
    if(b==0)
        return a;
    return gcd(b,a%b);
}

long long lcm(long long a,long long b){
    if(a>b)
        return (a/gcd(a,b))*b;
    else
        return (b/gcd(a,b))*a;
} 

int main(){
    long long int a ,b ;
    cin>>a>>b;
    cout<<lcm(a,b)<<endl;
    return 0;
}

score 0 · Accepted Answer

このCプログラムは、LCMを見つけるための異なるアプローチです。

 #include<stdio.h>
    int main()
    {
        int a,b,lcm=1,i=2;
        printf("Enter two numbers to find LCM\n" );
        scanf("%d %d",&a ,&b);
        while(i <= a*b)
        {
            if(a%i==0 & b%i==0)
            {
                lcm=lcm*i;
                a=a/i;
                b=b/i;
                i=i-1;
            }
            if( a%i==0 & b%i!=0)
            {
                lcm=lcm*i;
                a=a/i;
                i=i-1;
            }
            if( b%i==0 & a%i!=0)
            {
                lcm=lcm*i;
                b=b/i;
                i=i-1;
            }
            i++;
        }
        printf("The LCM of numbers is %d\n", lcm);
    }

c - 2つの数値のLCM

5 に答える 5

Related

Reference