算法訓練-最小公倍數-Java(遞歸實作)

問題描述

編寫一函數lcm，求兩個正整數的最小公倍數。

樣例輸入

一個滿足題目要求的輸入範例。

例：

3 5

樣例輸出

與上面的樣例輸入對應的輸出。

例：

資料規模和約定 　　輸入資料中每一個數的範圍。 　　例：兩個數都小于65536。

代碼示範

import java.util.Scanner;

/**
 * 編寫一函數lcm，求兩個正整數的最小公倍數
 * 
 * @author Clearlight
 *
 */
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    sc.close();
    
    System.out.println(a*b/f(a,b)); // 最小公倍數 = 兩數相乘 / 最大公約數
  }
  
  /**
   * 使用遞歸進行求解
   * 
   * @param a 輸入的數
   * @param b 輸入的數
   * @return  傳回兩個數的最大公約數
   */
  public static int f(int a, int b) {
    
    if(a%b == 0) {
      return b;
    }
    return f(b,a%b);
  }
}      

代碼分析

遞歸的思想應用 : 輾轉相除法
  找重複:a/b=c...a%b
        b/(a%b)=d...b%(a%b)
     ...
       第一項為:f函數的第二項的值
       第二項為:f函數的第一項對第二項的模
  找變化:變化的值應該作為參數(a和b一直在變化)
  找邊界:出口(當a%b=0時,傳回b即為最大公約數