Water and Jug Problem

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

• Fill any of the jugs completely with water.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous “Die Hard” example)

Input: x = 3, y = 5, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

提示	解題應用
Math	規律觀查

Default:

func canMeasureWater(x int, y int, z int) bool {

}

解答思路:

這題也許以前在數學課時曾經碰過，與其說是寫程式考數學的成分佔大多數，也因此留下了一堆負評，總而言之結論就是要用兩個不同大小的容器x,y來確認是否能量出特定體積的液體z，可以整理成以下兩點:

1. ax + by = z (a,b分別表示倒入的次數，若為負數則表示為倒出的次數)
2. GCD(x, y) = c ; z % c == 0 其中如果a,b皆為整數，那麼z就會是x,y最大公因數的倍數

剩下就是驗證x,y,z帶入之後是否能符合上述條件就能確認是否能量出特定體積的液體。

程式碼解說:

一開始先檢查兩個容器的總體積是否比要求的目標體積大，如果不是就不符合題目所給予的條件回傳false，而如果任一個容器的體積或是兩個容器的總體積剛好與目標體積相等則回傳true，最後如果上述條件都不符合，就只要檢查z是不是x,y最大公因數的倍數(相除餘數為0)，便能得知是否量得出特定體積的液體

func canMeasureWater(x int, y int, z int) bool {
	if x+y < z {
		return false
	} else if x == z || y == z || x+y == z {
		return true
	}
	return z%gcd(x, y) == 0
}

如果要用程式來實作求最大公因數，首先要先知道輾轉相除法的做法，基本上就是不斷的在兩數之間取餘數並做取代，直到其中一方歸0而另一方剩餘的值就會是最大公因數

func gcd(x int, y int) int {
	var tmp int
	for y != 0 {
		tmp = y
		y = x % y
		x = tmp
	}
	return x
}

完整程式碼:

func canMeasureWater(x int, y int, z int) bool {
	if x+y < z {
		return false
	} else if x == z || y == z || x+y == z {
		return true
	}
	return z%gcd(x, y) == 0
}
func gcd(x int, y int) int {
	var tmp int
	for y != 0 {
		tmp = y
		y = x % y
		x = tmp
	}
	return x
}

總結:

要用兩個不同大小的容器x,y來確認是否能量出特定體積的液體z，可以整理成以下兩點:

1. ax + by = z (a,b分別表示倒入的次數，若為負數則表示為倒出的次數)
2. GCD(x, y) = c ; z % c == 0 其中如果a,b皆為整數，那麼z就會是x,y最大公因數的倍數

剩下就是驗證x,y,z帶入之後是否能符合上述條件就能確認是否能量出特定體積的液體。