題目五: 輸入兩個正整數 m 和 n,求最大公約數

A.輾轉相除法

1.核心思想

前提:被取余數%取余數=余數

a.第一次,拿大數%小數=余數

b.從第二次起,每次取余數部分(小數)就當成新一輪取余運算的被取余數,余數就當成新一輪取余運算的取余數

c.當被取余數%取余數=0時,此時找到最大公約數,其最大公約數=取余數,否則執行下一輪取余運算

2.核心代碼

if(m>n){
     //被除數變為除數,除數變為余數
     temp03=temp01%temp02;
     result=temp02;
     //當temp03=0時,代表temp02是最大公約數
     temp01=temp02;
     temp02=temp03;
}else{
     temp03=temp02%temp01;
     result=temp01;
     temp02=temp01;
     temp01=temp03;
}
//其中tempo1=m,temp02=n,temp03用于存放余數,result用來接收所產生的最大公約數

3.常見問題點分析

3.1 布爾類型變量flag與布爾類型變量flag01的作用分別是什么?

解答:flag的作用: 判斷是否輸入合法,若輸入合法就進入求公約數算法階段,此時flag=false,保證程序在求完公約數之后能順利結束.若非法則提示重新輸入,程序不會結束

flag01的作用:判斷最大公約數是否求解完畢,若求解完畢,求輸出公約數,并使flag01=false,退出當前求最大公約數這個循環,否則,則進入繼續求公約數的取余階段

3.2 為啥要判斷正整數m與正整數n的大小關系?

解答:輾轉相除法要求的是大數%小數,要保證每次大數在被取余數部分。

? 正整數m,正整數n之間的大小關系沒有要求,

3 運行截圖

3.1 第一次輸入m<=0且第二次時輸入時m>0且m<n

3.2 第一次輸入n<=0且第二次時輸入時n>0且m>=n

3.3 第一次輸入時,m>0且m<n;

3.4 第一次輸入時,n>0且m>=n;

4.源代碼

import java.util.Scanner;
public class Gcd{
    public static void main(String[] args) {
        //GCD中的G代表greatest c代表common d代表divisor(因子)
        System.out.println("題目五:輸入正整數m和n,求最大公約數----輾轉相除法");
        Scanner scanner=new Scanner(System.in);
        System.out.println("請輸入正整數m:");
        int m=scanner.nextInt();
        System.out.println("請輸入正整數n:");
        int n=scanner.nextInt();
        boolean flag=true;
        //flag用于判斷用戶輸入值是否正確,
        // 若不正確,就要求你重新輸入,否則flag=false,進入公約數判斷
        while(flag){
           if(m>0&&n>0){
              flag=false;
              boolean flag01=true;
              int temp01=m,temp02=n;
              int result=0;
              //result是用來接受最大公約數的
              while(flag01){
                  int temp03=0;
                  if(m>n){
                      //被除數變為除數,除數變為余數
                      temp03=temp01%temp02;
                      result=temp02;
                      //當temp03=0時,代表temp02是最大公約數
                      temp01=temp02;
                      temp02=temp03;
                  }else{
                      temp03=temp02%temp01;
                      result=temp01;
                      temp02=temp01;
                      temp01=temp03;
                  }
                  //flag01判定是否產生最大公約數,若產生,則退出循環
                  if(temp03==0){
                      flag01=false;
                      System.out.println("最大公約數為:"+result);
                  }
              }

           }else{
               System.out.println("輸入有誤,請檢查輸入的m值和n值");
               System.out.println("請再次輸入正整數m:");
               m=scanner.nextInt();
               System.out.println("請再次輸入正整數m:");
               n=scanner.nextInt();
           }
        }
    }
}

B.輾轉相減法

1.核心思想

前提:被減數-減數=差

a.第一次,拿大數-小數=差

b.從第二次起,每次拿減數與差進行大小的比較,使較大值為被減數,較小值為差

c.當差為0時,此時找到最大公約數,其最大公約數=被減數,否則執行下一輪減法運算

2.核心代碼

if(temp01>temp02){
  temp03 = temp01 - temp02;
  if (temp03 > temp02) {
      temp01 = temp03;
  }else if (temp03 < temp02) {
      temp01 = temp02;
      temp02 = temp03;
//    result = temp01;
  }else {
      result=temp03;
      //當減數與差相等,意味著此時就是最大公約數
      flag01 = false;
      System.out.println("最大公約數為:" + result);
   }
}else{
      temp03 = temp02 - temp01;
      if (temp03 > temp01) {
         temp02 = temp03;
      }else if (temp03 < temp01) {
         temp02 = temp01;
         temp01 = temp03;
      }else {
         result=temp03;
         //當減數與差相等,意味著此時就是最大公約數
         flag01 = false;
         System.out.println("最大公約數為:" + result);
        }
}

3.常見問題點分析

3.1 布爾類型變量flag與布爾類型變量flag01的作用分別是什么?

解答:flag的作用: 判斷是否輸入合法,若輸入合法就進入求公約數算法階段,此時flag=false,保證程序在求完公約數之后能順利結束.若非法則提示重新輸入,程序不會結束

flag01的作用:判斷最大公約數是否求解完畢,若求解完畢,求輸出公約數,并使flag01=false,退出當前求最大公約數這個循環,否則,則進入繼續求公約數的取余階段

3.2 為啥當差值與減數相等時,此時最大公約數為差值?

解答:輾轉相除法的核心是當被減數-減數=0時,可以推導出以下結論

? 最大公約數=差值=減數

因此當差值和減數相等時,最大公約數為差值

3 運行截圖

3.1 第一次輸入m<=0且第二次時輸入時m>0且m<n

3.2 第一次輸入n<=0且第二次時輸入時n>0且m>=n

3.3 第一次輸入時,m>0且m<n;

3.4 第一次輸入時,n>0且m>=n;

4.源代碼

import java.util.Scanner;

public class Gcd01 {
    public static void main(String[] args) {
        //GCD中的G代表greatest c代表common d代表divisor(因子)
        System.out.println("題目五:輸入正整數m和n,求最大公約數----輾轉相減法");
        Scanner scanner = new Scanner(System.in);
        System.out.println("請輸入正整數m:");
        int m = scanner.nextInt();
        System.out.println("請輸入正整數n:");
        int n = scanner.nextInt();
        boolean flag = true;
        //flag用于判斷用戶輸入值是否正確,
        // 若不正確,就要求你重新輸入,否則flag=false,進入公約數判斷
        while (flag) {
            if (m > 0 && n > 0) {
                flag = false;
                boolean flag01 = true;
                int temp01 = m, temp02 = n;
                int result = 0;
                //result是用來接受最大公約數的
                while (flag01) {
                    int temp03 = 0;
                    if(temp01>temp02){
                        temp03 = temp01 - temp02;
                        if (temp03 > temp02) {
                            temp01 = temp03;
//                        result = temp02;
                        }else if (temp03 < temp02) {
                            temp01 = temp02;
                            temp02 = temp03;
//                        result = temp01;

                        }else {
                            result=temp03;
                            //當減數與差相等,意味著此時就是最大公約數
                            flag01 = false;
                            System.out.println("最大公約數為:" + result);
                        }
                    }else{
                        temp03 = temp02 - temp01;
                        if (temp03 > temp01) {
                            temp02 = temp03;
                        }else if (temp03 < temp01) {
                            temp02 = temp01;
                            temp01 = temp03;
                        }else {
                            result=temp03;
                            //當減數與差相等,意味著此時就是最大公約數
                            flag01 = false;
                            System.out.println("最大公約數為:" + result);
                        }
                    }

                }
            }else{
                System.out.println("輸入有誤,請檢查輸入的m值和n值");
                System.out.println("請再次輸入正整數m:");
                m = scanner.nextInt();
                System.out.println("請再次輸入正整數m:");
                n = scanner.nextInt();
            }
        }
    }
}