一、實驗目的

1 掌握蠻力法的設計思想(利用計算機去窮舉所有的可能解,再從中依次找出可行解)
2 掌握蠻力法的具體實現和時間復雜度分析
3 理解蠻力法的常見特性
實驗要求：先用偽代碼描述利用蠻力法解決的算法解決方案，再用程序實現，計算時間復雜度，記錄最終測試數據和測試結果

二、實驗內容

（1）簡短明確地寫出實驗的內容

• （簡單）實驗內容1：計算一個整數數組中所有元素的差值。如a[0]-a[1]-…-a[n-1]。具體地，實驗通過實現一個 substraction 方法來計算數組中元素的逐步相減，最后輸出計算結果。

• （中等）實驗內容2：來計算兩個整數的最大公約數（GCD），并將這兩個整數化簡為最簡分數。程序包括輸入驗證，確保用戶輸入有效整數，并使用歐幾里得算法提高計算效率。最后，輸出化簡后的結果。

三、問題分析

(1) 分析要解決的問題，給出你的思路，可以借助圖表等輔助表達。

• 實驗內容一
  思路分析：
  輸入：我們有一個整數數組 a，長度為 n，即 a = [a[0], a[1], a[2], …, a[n-1]]
  計算過程：
  從數組的第一個元素 a[0] 開始，逐個從數組中每個元素中減去后續的元素。
  可以通過一個簡單的迭代來實現，從 a[0] 開始，接著依次減去 a[1], a[2], …, a[n-1]。
  輸出：輸出最終的計算結果。

• 實驗內容二
  1.最大公約數計算：如何高效地計算兩個整數的最大公約數。
  利用循環和取余操作，可以高效地計算最大公約數。這種方法相較于簡單遍歷更高效。
  2.分數化簡：如何利用最大公約數將兩個整數化簡為最簡分數。
  通過將兩個整數分別除以它們的最大公約數，得到最簡形式的分數。
  3.用戶輸入處理：如何確保用戶輸入的是有效的整數，并處理可能的錯誤輸入。
  使用 Scanner 讀取用戶輸入，確保輸入為整數。如果輸入無效，提示用戶重新輸入。

（2）其它（你認為需要在此說明的）

邊界條件: 程序需考慮特殊情況，例如輸入為零或負數的情況。可以設置條件使得輸入必須為正整數。

四、問題解決

(1)根據對問題的分析，寫出解決辦法。

• 實驗內容一
  我們可以通過一個循環來遍歷數組，初始值為第一個元素，然后不斷地從當前值中減去下一個元素。具體步驟如下：
  初始化 result 為數組的第一個元素 a[0]。
  從數組的第二個元素開始，依次減去每個元素，直到最后一個元素。
  輸出最終的 result。

• 實驗內容二
  1.用戶輸入：提示用戶輸入兩個整數，并對輸入進行有效性檢查。
  2.計算最大公約數（GCD）：使用歐幾里得算法來高效計算最大公約數。
  3.化簡分數：用最大公約數化簡輸入的兩個整數，輸出最簡分數形式。
  4.錯誤處理和提示：如果用戶輸入無效（如非整數、負數等），給予明確提示并要求重新輸入。

(2)描述你在進行實現時，主要的函數或操作內部的主要算法；分析這個算法的時間復雜度，并說明你設計的巧妙之處，如有創新，將其清晰的表述。

實驗內容一

1.主要函數：

2.時間復雜度：
遍歷數組：我們需要遍歷整個數組 a 一次，計算每個元素的差值。具體來說，遍歷從數組的第一個元素到最后一個元素，執行減法操作。
每次操作的時間：每一次從 result 中減去一個元素，所需的時間是常數時間 O(1)，因為減法操作是常數時間操作。
總時間復雜度：因為遍歷數組需要執行 n-1 次減法，其中 n 是數組的長度，因此總的時間復雜度是 O(n)，其中 n 為數組的長度。

3.運行結果

實驗內容二

主要函數：

1.選擇最小值：首先使用三元運算符確定 m 和 n 中的較小值，賦值給 min。
2.循環查找：從 min 開始向下逐一檢查每一個整數 i，判斷 i 是否同時為 m 和 n 的因子（即 m % i == 0 且 n % i == 0）。
3.返回結果：一旦找到這樣的 i，就立即返回它作為最大公約數。如果循環結束仍未找到，則返回1（表示 m 和 n 互質）。
4.
在最壞情況下，當 m 和 n 是互質的（如 8 和 9），函數會遍歷到 min 的值，即 O(min(m, n)) 次。
因此，時間復雜度為 O(min(m, n))。

(3)運行結果截圖以及其它（你認為需要在此說明的）

五、實驗結果總結

回答以下問題：

(1)通過實驗敘述你對蠻力法的理解及其優缺點

蠻力法是一種直接且簡單的解決問題的方法，通常通過枚舉所有可能的選項來尋找解決方案。在計算最大公約數時，蠻力法會逐一檢查直至找到最大的共同因子。
優點：
簡單易懂：實現代碼較為簡單，適合初學者理解。
可靠性：在小范圍內能夠保證找到正確答案。
缺點：
效率低：對于大數或復雜問題，時間復雜度較高，導致運行時間長。
資源消耗：可能需要較多的存儲和計算資源，尤其在數據量大時。

(2)請列出對你實驗中算法的改進之處。

1.使用歐幾里得算法：改用歐幾里得算法計算 GCD，可以將時間復雜度降低到 O(log(min(m, n)))，提高效率。
2.提前終止：在循環中，可以引入條件，例如如果 i 的平方大于 m 或 n，則可以提前結束查找。
3.緩存計算結果：對于頻繁計算相同數對的情況，可以緩存已計算的 GCD 值，避免重復計算。

(3)列出你在本次實驗中遇到的各種問題

1.輸入驗證：在實驗過程中，遇到了如何處理無效輸入（如負數或零）的問題。
2.邏輯錯誤：在初始實現中可能出現邊界條件處理不當的情況，比如輸入相同數字時未能正確返回該數字作為 GCD。