exam1_summary

9/10 本週考試重點總結 (題目分析與Java實作)

Problem A: GCD (最大公因數)

• 目標： 計算兩個正整數 $x$ 和 $y$ 的最大公因數。
• 輸入：
  • 第一行是測試案例數量 $T$。
  • 接下來 $T$ 行，每行包含兩個整數 $x$ 和 $y$ ($1 \le x, y \le 1,000,000$)。
• 輸出： 每個測試案例的最大公因數。
• 核心考點：
  • 必須自己實現 GCD 演算法，不能使用內建函式庫。
  • 歐幾里得演算法 (Euclidean algorithm) 是最推薦的方法，無論是使用遞迴或迭代版本都可以。

import java.util.Scanner;

public class Problem_A_Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 讀取有幾組測試資料

        while (T-- > 0) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            System.out.println(gcd(x, y));
        }
        scanner.close();
    }

    // 歐幾里得演算法的迭代（迴圈）實現
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

---

Problem B: Score (分數計算)

• 目標： 根據公式 Score = S * (N - 2 * K) / N 計算多選題得分。
• 輸入： 多筆資料，每行包含三個整數 $S$ (總分)、$N$ (選項數)、$K$ (答錯數)。
• 輸出： 計算出的分數（浮點數）。若分數低於 0，則輸出 0.0。
• 核心考點：
  • 數學運算： 需注意整數與浮點數的型別轉換，以避免精度損失。
  • 條件判斷： 必須處理分數小於 0 的情況，可以使用 if 條件式或 Math.max(0, calculated_score) 來實現。

import java.util.Scanner;

public class Problem_B {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        while (sc.hasNext()) {
            int S = sc.nextInt();
            int N = sc.nextInt();
            int K = sc.nextInt();
            
            long numerator = (long)S * (N - 2 * K);
            
            double score = (double)numerator / N;
            
            if (score < 0) {
                score = 0.0;
            }
            
            System.out.println(score);
        }
        
        sc.close();
    }
}

---

Problem C: Shopping (購物餘額)

• 目標： 根據初始存款和一系列交易，即時計算並輸出每次交易後的餘額。
• 輸入：
  • 第一行是初始存款 $N$。
  • 接下來有多行交易金額 $M$ ($M > 0$ 為收入，$M < 0$ 為支出)。
• 輸出： 每發生一筆交易，就輸出一行更新後的餘額。
• 核心考點：
  • 迴圈與狀態更新： 使用迴圈持續讀取輸入，並在一個變數中不斷更新餘額。
  • 輸入處理： 程式必須能處理到沒有更多輸入為止 (End-of-File)。

import java.util.Scanner;
public class Problem_C {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        long N = sc.nextLong();
        
        while (sc.hasNext()) {
            long M = sc.nextLong();
            N += M;
            System.out.println(N);
        }
        
        sc.close();
    }
}

---

Problem D: Taipei 101 Vertical Marathon (爬樓梯問題)

• 目標： 計算爬 $n$ 階樓梯的方法總數，每次只能爬 1 階或 2 階。
• 輸入：
  • 第一行是測試案例數量 $T$。
  • 接下來 $T$ 行，每行一個整數 $n$ ($1 \le n \le 25$)。
• 輸出： 爬到第 $n$ 階的方法數。
• 核心考點：
  • 遞迴/動態規劃： 這是典型的斐波那契數列 (Fibonacci sequence) 應用題。
  • 遞迴關係式： ways(n) = ways(n-1) + ways(n-2)。
  • 基本情況： ways(1) = 1，ways(2) = 2。由於 $n$ 的範圍很小，可以使用遞迴、迭代或備忘錄法來解。

import java.util.Scanner;

public class Problem_D_Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 建立 DP 陣列，預先計算好結果，空間換取時間
        int[] dp = new int[26];
        dp[1] = 1; // Base Case: 爬 1 階有 1 種方法
        dp[2] = 2; // Base Case: 爬 2 階有 2 種方法 (1+1, 2)

        // 從 3 開始，用迴圈計算到 25
        for (int i = 3; i <= 25; i++) {
            dp[i] = dp[i-1] + dp[i-2]; // DP 狀態轉移方程式
        }
        
        int T = scanner.nextInt();
        while (T-- > 0) {
            int n = scanner.nextInt();
            System.out.println(dp[n]); // 直接查表輸出，效率極高
        }
        scanner.close();
    }
}

---

Problem E: Formula solution (一元二次方程式解的個數)

• 目標： 判斷一元二次方程式 $ax^2 + bx + c = 0$ 有多少個實數解。
• 判別式： $\Delta = b^2 - 4ac$。
• 輸入： 多筆資料，每行包含三個整數 $a, b, c$ ($0 \le a, b, c \le 1000$)。
• 輸出： 根據 $\Delta$ 的值輸出實數解的個數（2, 1, 或 0）。
• 核心考點：
  • 數學知識： 運用判別式 $\Delta$ 的正、零、負來判斷解的個數。
  • 條件分支： 使用 if-elif-else 結構來處理三種情況並給出對應輸出。

import java.util.Scanner;
public class Problem_E{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int a,b,c,x;
        while (sc.hasNext()) {
            a=sc.nextInt();
            b=sc.nextInt();
            c=sc.nextInt();
            x = b * b - 4 * a * c;
            if (x > 0) {
                System.out.println("2");
            } else if (x == 0) {
                System.out.println("1");
            } else {
                System.out.println("0");
            }
        }
        sc.close();
    }
}

---

Problem F: Zapping (電視選台)

• 目標： 在 0-99 的循環頻道中，從頻道 $a$ 切換到 $b$ 所需的最少按鍵次數（只能按「上」或「下」）。
• 輸入： 多筆資料，每行包含兩個整數 $a$ 和 $b$，並以 -1 -1 作為輸入結束的標記。
• 輸出： 從 $a$ 到 $b$ 的最少按鍵次數。
• 核心考點：
  • 循環距離計算：
    • 向上走的步數：(b - a + 100) % 100
    • 向下走的步數：(a - b + 100) % 100
  • 比較： 取上述兩種走法步數的最小值。
  • 輸入終止： 迴圈需在讀到 -1 -1 時結束。

import java.util.Scanner;

public class Problem_F_Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (true) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            if (a == -1 && b == -1) break; // 結束條件

            // 計算順時針（向上）的距離
            int forward = (b - a + 100) % 100;
            // 計算逆時針（向下）的距離
            int backward = (a - b + 100) % 100;

            // 輸出兩者中的較小值
            System.out.println(Math.min(forward, backward));
        }
        scanner.close();
    }
}

---

Problem G: Digital Sum (各位數之和)

• 目標： 計算一個正整數 $N$ 的所有位數加總。
• 輸入：
  • 第一行是測試案例數量 $T$。
  • 接下來 $T$ 行，每行一個整數 $N$ ($0 \le N \le 100,000$)。
• 輸出： $N$ 的各位數之和。
• 核心考點：
  • 數字拆解：
    • 方法一 (數學)： 使用迴圈，透過 % 10 取出個位數，再用 / 10 去掉個位數，直到數字變為 0。
    • 方法二 (字串)： 將數字轉為字串，遍歷字串中的每個字元，將其轉回數字後相加。

import java.util.Scanner;

public class Problem_G_Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();

        while (T-- > 0) {
            int n = scanner.nextInt();
            int sum = 0;

            // 處理 n=0 的邊界情況
            if (n == 0) {
                System.out.println(0);
                continue;
            }

            // 使用 while 迴圈是處理此問題最標準的作法
            while (n > 0) {
                sum += n % 10; // 取得個位數並加入總和
                n /= 10;       // 移除個位數
            }
            System.out.println(sum);
        }
        scanner.close();
    }
}