// 第 1 周 – 算法示例：最大公约数（欧几里得算法）
// 运行：go run ./w01/gcd
package main

import "fmt"

// 伪代码：
//
//	Function GCD(a, b)
//	  While b ≠ 0
//	    m ← a mod b ; a ← b ; b ← m
//	  End while
//	  Return a
//	End function
func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b // 并行赋值：不需要辅助变量
	}
	return a
}

// 同样的算法，打印每一步。
func gcdTrace(a, b int) int {
	fmt.Printf("%6s %6s %6s\n", "a", "b", "a mod b")
	for b != 0 {
		fmt.Printf("%6d %6d %6d\n", a, b, a%b)
		a, b = b, a%b
	}
	return a
}

func main() {
	fmt.Println("GCD(48, 18) =", gcd(48, 18))
	fmt.Println()
	r := gcdTrace(1071, 462)
	fmt.Println("GCD(1071, 462) =", r)
}