###### 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;
}
```
Sign in with Wallet
Connect another wallet