- 若 n >= 2*m,則 n = n - 2*m,並回到步驟 1。
- 若 m >= 2*n,則 m = m - 2*n,並回到步驟 1。
- 若 n 或 m 其中一個為 0,或是上述二個條件均失敗時,結束。
舉例來說:n = 12, m = 5。
- 因為 n >= 2*m,所以 n = 12 - 2*5 = 2。此時 n = 2, m = 5。
- 因為 m >= 2*n,所以 m = 5 - 2*2 = 1。此時 n = 2, m = 1。
- 因為 n >= 2*m,所以 n = 2 - 2*1 = 0。此時 n = 0, m = 1。
- 因為 n 為 0,結束。
另一個例子是 n = 31, m = 12。
- 因為 n >= 2*m,所以 n = 31 - 2*12 = 7。此時 n = 7, m = 12。
- 因為 n < 2*m 且 m < 2*n,所以直接結束。
[解法] 其實有點像是輾轉相除法找最大公因數,不過小改一點點,唯一的小麻煩就是像第二個例子那樣,雖然還沒找到最大公因數,但是因為已經觸發條件了所以就終止計算了。但也不能傻傻地用暴力法硬算,因為 n 跟 m 的值很大,所以如果兩者差距很大還直接一步一步慢慢算會很慢,所以要稍稍修改一下輾轉相除法的概念。
其實如果有透徹了解輾轉相除法的話,只要改成這樣就好:
- 若 n >= 2*m,則 n = n mod 2*m
- 若 m >= 2*n,則 m =m mod 2*n
實作如下:
沒有留言:
張貼留言