請問: 如何使用c寫出遞迴的最小公倍數程式,請各位高手指教指教~

#include 
#include 
 
using namespace std;
 
int gcd(int a,int b)  //最大公因數
{
     int temp;
     while(a%b!=0)
     {
         temp=a%b;
         a=b;
         b=temp;
     }
     return b;
}
 
int lcm(int a,int b)   //最小公倍數
{
    return a*b/gcd(a,b);
}
 
 
int main(int argc, char *argv[])
{
  int a,b,c;
  cout << "本程式將求三數之最大公因數與最小公倍數\n"; 
  cout << "請輸入三數:";
  cin >> a >> b >> c;
  cout << a << "," << b << "," << c << "之最大公因數為" << gcd(gcd(a,b),c) << "\n";
  cout << a << "," << b << "," << c << "之最小公倍數為" << lcm(lcm(a,b),c) << "\n";   
  system("PAUSE"); 
  return 0;
}
      

網海無涯，唯學是岸！

就題意應該是對最大公因數做遞迴... 這邊修改一下qoo1234大大的method int gcd(int a,int b) //最大公因數 { int temp; if(a%b != 0) { temp = gcd(b, a%b); } else { return a%b; } return temp; } 以上..有誤請多多指教

int gcd(int a,int b)  //最大公因數
{ 
  return (b ? gcd(b,a%b) : a);
}
 
int lcm(int a,int b)   //最小公倍數
{
  return a*b/gcd(a,b);
} 
 
int main()
{   
  cout << "lcm(4,5)最小公倍數為" << lcm(4,5) << "\n";   
  system("PAUSE"); 
  return 0;
}     

網海無涯，唯學是岸！

感謝樓上幾位高手相助,但我的意思是說真接寫出最小公倍數的遞迴, 而不是利用最大公因數的遞迴後再來求最小公倍數, 或著要求最小公倍數一定要透過最大公因數來求呢..感謝指教..

int lcm(int a, int b, int nlcm)
{
        if (nlcm%a == 0 && nlcm%b == 0)
        {
        }
        else
        {
                nlcm  ;
                nlcm = test(a, b, nlcm);
        }
        return nlcm;
}

lcm再呼叫的時候 nlcm不能為0... 很笨的方法各位大大請多多指教 發表人 -

上面的程式我在做稍微修改(真的是很笨的方法) < class="code"> int test(int a, int b, int n) { int temp = n*a; if (temp%b != 0) { n ; temp = test(a, b, n); } return temp; } 這是利用倍數n來去判斷是否為公倍數,比起上面用加法的好多了

landochu你好，為什麼各位前輩會算最大公因數再來求最小公倍數 這個應該是因為上數學課就是這樣教的吧，而這應該是最有效率的方式    如果你要看起來很單純得方式，你可以仿照pkdemon的方式再做修改 例如求A,B兩數的最小公倍數(前提當然是正整數)

int LCM(A,B)
{
    int X,Y,I;        if ( A > B )
    {
        for ( I = 1; I <= B; I   )
        {
            if (( B*I % A) == 0 )//於數為零，代表是倍數
                return B*I;
        }
    }
    else
    {
        for ( I = 1; I <= A; I   )
        {
            if (( A*I % B) == 0 )//於數為零，代表是倍數
                return A*I;
        }
    }
}    

第二種方式應該比較直觀，但數字很大的話，先求最大公因數應該會比較有效率

我不太懂為什麼要傳三個變數進去,n那個變數是幹嘛的.. int test(int a, int b, int n)

landochu 你好,    n是計算最小公倍數為a的多少倍(當然要改寫成b的也可以)< > 回答簡單了點,希望能夠明白< >

請問一下各位大大 為什麼while的條件是a%b!=0才跳出？ 為什麼不是a%b==0才跳出？ 我這邊不是很明白，哪位大大可以解釋給我聽？ 感激！