---
# System prepended metadata

title: 水桶問題(twobucket)
tags: [算法, Golang]

---

###### tags: `Golang` `算法`

# 水桶問題(twobucket)

## 兩個水桶倒出指定水量

### 邊際

1. 水桶大小為0
2. 目標合， 沒有辦法被兩水桶公因數整除

### 算法

1. 兩桶水都不滿足目標情況下 若滿足結束 不滿足
2. 檢查初始水桶裝滿 檢查條件1 不滿足 執行步驟3
3. 檢查另一個水桶是否滿足目標 不滿足 執行步驟4
4. 檢查另一個水桶是否裝滿 不滿足 執行步驟5
5. 把水倒到另一個桶子 回到步驟1


```go=
package twobucket

import "errors"

type Tbucket struct{
    size , amount int
}

func min(a, b int) int {
    if a > b {
        return b
    }
	return a
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func Solve(sizeBucketOne, sizeBucketTwo, goalAmount int, startBucket string) (goalBucket string, numSteps, otherBucketLevel int, e error) {
	if sizeBucketOne == 0 || sizeBucketTwo == 0 || goalAmount == 0 || goalAmount > sizeBucketOne && goalAmount > sizeBucketTwo {
		return "", 0, 0, errors.New("invalid bucket size or goal amount")
	}
	if goalAmount%gcd(sizeBucketOne, sizeBucketTwo) != 0 {
		return "", 0, 0, errors.New("no solution")
	}

    var start, other int
    switch startBucket {
        case "one":
    		other = 1
        case "two":
    		start = 1
        default:
    		return "", 0, 0, errors.New("invalid start bucket name")
    }

    buckets := [2]Tbucket{
        Tbucket{size:sizeBucketOne},
        Tbucket{size:sizeBucketTwo},
    }

    for buckets[0].amount != goalAmount && buckets[1].amount != goalAmount {
    	numSteps++
        switch {
            case buckets[start].amount == 0 :
        		buckets[start].amount = buckets[start].size
            case buckets[other].size == goalAmount:
				buckets[other].amount = goalAmount
            case buckets[other].amount == buckets[other].size:
            	buckets[other].amount = 0
            default:
        		pour := min(buckets[other].size-buckets[other].amount, buckets[start].amount)
				buckets[start].amount -= pour
				buckets[other].amount += pour
        }
    }

    if buckets[0].amount == goalAmount {
    	goalBucket = "one"
        otherBucketLevel = buckets[1].amount
        
    } else {
    	goalBucket = "two"
        otherBucketLevel = buckets[0].amount
    }

    return
}

```

## 兩個水桶是否能平分水

如果你有無窮多的水，兩個水桶分別為3,5公升，試問能否分出4,4公升的水

#### 解法

```
按照原始邏輯，兩個水桶不斷地分水，倒水

大桶向小桶倒滿水，然後小桶滿了，把小桶的水倒了，大桶的水倒向小桶
小桶滿了以後，繼續小桶的水倒了，大桶的倒向小桶
或者大桶倒小桶的時候，大桶沒水了，把大桶接滿水，
繼續這種循環
      
小桶水量為i    大桶水量為j    
j->i   大桶向小桶倒水，小桶滿了
i=0 小桶倒空
j->i 大桶繼續向小桶倒水，小桶滿了繼續
如果出現大桶為空，就把大桶接滿水，繼續這種循環


若起點是0，0
如果我們在這個過程中能走到重複的位置，還沒有找到目标值，證明不能湊出目標水量
也就是說，如果過程中還能走到0，0點，我們之間退出就行，有重複路徑了，不能湊出目標水量
```

```cpp=
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void printStates(int x, int y, int z){ //輸入一下裝水的過程
cout << "小水桶容量為：" << x << "," << "中水桶容量為：" << y << "," << "大水桶容量為：" << z << "\n";
}

bool twoBucket(int x, int y, int z, int targeta, int targetb){   //x是小桶的容量，y是中桶的容量，z是大桶的容量

bool isbool[x + 1][y + 1][z + 1];   //建立數組記錄是否走過目前位置
for (int i = 0; i <= x; i++) {      //isbool[i][j][k]代表小水桶為i，中為j，大為k是否以前出現過，
for (int j = 0; j <= y; j++) {  // 如果出現過以前的步驟說明不能獲得目标值
for (int k = 0; k <= z; k++) {  //先初始化數組，每個位置都沒走過
isbool[i][j][k] = false;
            }
        }
    }
int i = 0, j = 0, k = z;    //從起始位置開始走
while (true) {
if (isbool[i][j][k]) {  //如果走過，直接傳回false
return false;
        }
isbool[i][j][k] = true; //沒走過就标記目前位置
//如果三個桶中有兩個能獲得目标值了，證明完成分水任務，傳回true
if (i == targeta && j == targetb || j == targeta && k == targetb || i == targeta && k == targetb) {
return true;
        }
else if (i == x) {   //小桶水滿了，向大桶倒水
while (i > 0) {
i--;
k++;
            }
printStates(i, j, k);
        }
else if (i == 0 && j == 0) {     //小桶大桶都空着，大桶向中桶倒水
while (j < y && k > 0) {
j++;
k--;
            }
printStates(i, j, k);
        }
else if (i < x && j != 0) {     //小桶沒滿，中桶不空，中桶向小桶倒水
while (i < x && j > 0) {
i++;
j--;
            }
printStates(i, j, k);
        }
else if (i != 0 && j == 0) {     //小桶不空，中桶空着，大桶向中桶倒水
while (k > 0 && j < y ) {
k--;
j++;
            }
printStates(i, j, k);
        }
    }
}

int main(){
cout << "請輸入三個水桶的容量,以及想要分成的兩個水量，預設大水桶是裝滿水的\n";
int x,y,z, targeta, targetb;
cin >> x >> y >> z >> targeta >> targetb;    //輸入三個水桶的容量，以及想要分成的兩個水量
int num[3] = {x, y, z};  //把小容量的給x，中容量的給y，大容量的給z
sort(num,num + 3);  //從num[0]到num[3]之前的進行排序（num[3]不參與排序）
cout << (twoBucket(num[0], num[1], num[2], targeta, targetb) ? "可以平分" : "無法平分");
return 0;
}
```

### 無限水桶

```
三桶水的思路

​小桶不滿，就把中桶的水倒向小桶​

​中桶沒水了，就把大桶的水向裡面倒​

​小桶滿了，就把小桶的倒向大桶（這裡是隻有8L水，并不是無限水）​

N桶水就是根據三桶水的規律

設目前為n個桶1 2 3 4 ……n（按容量排序，小的在前）

​1不滿，就把2的向1倒​

​如果2沒水，就把3向2倒……以此類推​

​如果1滿了，就把1的水向n倒（要保證n有足夠位置盛放1的水）​

​結束條件還是，如果目前各個水桶的水量，在以前出現過證明進入了循環，無法獲得目标值​
```

```cpp=
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct {    //建立水桶結構體，每個水桶有他的容量和初始水量
int capacity;
int start;
} bucket;

bool CompareCapacity (const bucket &a, const bucket &b) {   //根據每個水桶的容量排序
return a.capacity < b.capacity;
}

bool CompareStart (const bucket &a, const bucket &b) {      //根據每個水桶目前的水量進行排序
return a.start < b.start;
}

bool isTrue(vector<bucket> buckets, vector<int> target) {   //檢測水桶中的水量是否到達目标分水量
sort(buckets.begin(), buckets.end(), CompareStart);     //把目前的水桶按照目前的水量從小到大排序
for (int i = 0; i < buckets.size(); i++) {              //判斷是否和目标分水量相等
if (buckets[i].start != target[i]) {                //有一個不相等就傳回false
return false;
        }
    }
return true;    //都相等就傳回true
}
bool isRepeat(vector<bucket> buckets, vector<int> &repeat) { //判斷是否為重複的内容，
int ri = 0, lenb = buckets.size();
while (ri < repeat.size()) {    //如果目前水桶的水量以前發生過，證明目前變成了死循環，無法獲得目标值
bool bo = true;             //水桶的數量是固定的，每次記錄水量的時候數組中n個為相同一次水量的統計
for (int i = 0; i < lenb; i++,ri++) {   //例子repeat=[1,2,3,   2,1,3,   0,1,5,   1,0,5]  水桶水量為3時
//每三個都是一次水量的統計
if (buckets[i].start != repeat[ri]) {   //循環一遍目前桶是否比對1，2，3，不比對就用這些桶繼續比對2，1，3，一直往下循環
bo = false;                         //如果有一個水量與統計中不比對，證明目前水量沒有出現過，記錄bo=false
            }
        }
if (bo) {   //如果bo為true，證明目前各個水桶水量以前出現過，水量進入了循環，無法獲得目标值
return true;
        }
    }
cout << "每個水桶的容量為";
for (int i = 0; i < lenb; i++) {    //如果沒出現過，就把這次的水量加進來，輸出一下目前的水量
repeat.push_back(buckets[i].start);
cout << buckets[i].start << " ";
    }
cout << "\n";
return false;
}


bool fallBucket(vector<bucket> buckets, vector<int> target, vector<int> repeat) {
sort(buckets.begin(), buckets.end(), CompareCapacity);  //把水桶按照水桶容量從小到大排序
sort(target.begin(), target.end()); //把想要的目标值進行從小到大排序
int index = 0;
while (true) {
//小桶滿了，大桶可以放就放到大桶
//小桶的水量等于小桶的容量，并且把小桶的水量倒向大桶，大桶的水不會溢出
if (buckets[0].start == buckets[0].capacity && buckets[0].start + buckets[buckets.size() - 1].start <= buckets[buckets.size() - 1].capacity) {
//小桶倒向大桶的過程中要確定小桶有水
while (buckets[0].start > 0) {
buckets[0].start--;
buckets[buckets.size() - 1].start++;
            }
//每次倒完水（每次更改完值），都要判斷是否達到目标值和判斷是否為重複的
if (isRepeat(buckets,repeat)) {   //判斷是否是重複的，如果以前出現過，證明水量進入循環，無法得到目标分水量
return false;
             }
if (isTrue(buckets, target)) { //判斷是否達到目标值
return true;
             }
         }  //目前小桶的沒有滿，就把下一個桶的水往目前這個桶倒（倒的時候要確定下一個桶有水）
else if (buckets[index].start < buckets[index].capacity && buckets[index+1].start != 0) {
//倒水的時候保證目前水桶未滿，并且下個水桶有水
while (buckets[index].start < buckets[index].capacity && buckets[index + 1].start > 0) {
buckets[index + 1].start--;
buckets[index].start++;
             }
//每次倒完水（每次更改完值），都要判斷是否達到目标值和判斷是否為重複的
if (isRepeat(buckets, repeat)) {   //判斷是否是重複的，如果以前出現過，證明水量進入循環，無法得到目标分水量
return false;
             }
if (isTrue(buckets, target)) { //判斷是否達到目标值
return true;
             }
         } else {   //下個桶沒水了，也就是進不去上面的if
index++;   //下個桶沒水了，去下下個桶向下個桶倒水，把目前桶指向下一個桶，循環即可
if (index + 1 == buckets.size()) { //如果循環到最後一個桶，就從第一個桶開始
index = 0;
             }
         }
    }
}

int main(){     //main方法隻是輸入輸出,定義變量
cout << "請輸入水桶的數量n\n";
int n;
cin >> n;
vector<bucket> buckets; //結構體類型的vector，記錄每個桶的初始水量和總容量
vector<int> target;     //記錄n個桶的目标值
vector<int> repeat;     //用來記錄目前幾個桶的水量，以前是否分成過，如果分成過說明進入了循環
bucket tempb;
int temp;
int a, b, c;
cout << "請輸入n個桶的容量\n";
for (int i = 0; i < n; i++) {
cin>>a;
tempb.capacity = a;
buckets.push_back(tempb);
    }
cout << "請輸入n個桶的初始容量\n";
for (int i = 0; i < n; i++) {
cin>>b;
buckets[i].start = b;
    }
cout << "請輸入n個桶的目标容量,可以亂序\n";
for (int i = 0; i < n; i++) {
cin>>c;
temp = c;
target.push_back(temp);
    }

cout << (fallBucket(buckets, target, repeat)?"可以湊成目标水量":"不能湊成目标水量");    //調用方法判斷是不是能生成
return 0;
}
      

```