水桶分水问题详解(C++实现)

2021年11月24日 阅读数:4
这篇文章主要向大家介绍水桶分水问题详解(C++实现),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

发呆——尽可能用最简单的话语让读者理解问题思路,让读者不在发呆
Talk is cheap, show me the code .
你知道的越多,你不知道的越多。ios

若有什么建议或者不足欢迎大佬评论区或者私信指出c++

​两水桶分水​数组

​三水桶分水​ide

​N水桶分水​atom

两水桶分水

若是你有无穷多的水,一个3 公升的提捅,一个5 公升的提捅,两只提捅形状上下都不均 匀,如何才能准确称出4 公升的水?spa

按照原始逻辑,两个水桶不断地分水,倒水

大桶向小桶倒满水,而后小桶满了,把小桶的水倒了,大桶的水倒向小桶
小桶满了之后,继续小桶的水倒了,大桶的倒向小桶
或者大桶倒小桶的时候,大桶没水了,把大桶接满水,
继续这种循环

 小桶水量为i    大桶水量为j    
j->i 大桶向小桶倒水,小桶满了
i=0 小桶倒空
j->i 大桶继续向小桶倒水,小桶满了继续
若是出现大桶为空,就把大桶接满水,继续这种循环

简单来讲两桶分水的规律就是:3d

​大桶没水了,就把大桶接满水​code

​大桶有水,就往小桶倒水​blog

​小桶满了,就把小桶倒了,从新让大桶向小桶倒水​排序

若是还不能理解咱们画一个矩阵描述

这里咱们以3L和5L的桶,求得目标为4L的水量为例子

横向是大桶的水量

竖向是小桶的水量

刚开始两个桶都没有水,按照规律咱们向大桶填满水水桶分水问题详解(C++实现)_c++

大桶向小桶填水

水桶分水问题详解(C++实现)_c++_02

小桶填满了,把小桶倒空水桶分水问题详解(C++实现)_线性代数_03

小桶倒空了,大桶继续向小桶倒

水桶分水问题详解(C++实现)_水桶分水_04

大桶没水了,小桶未满,把大桶水接满水桶分水问题详解(C++实现)_i++_05

大桶有水了,继续向小桶倒水水桶分水问题详解(C++实现)_线性代数_06

把小桶填满了,把小桶倒空

水桶分水问题详解(C++实现)_i++_07

此时咱们获得了目标值,大桶里为4L

能获得的判断就是小桶里没水,大桶里有目标水量

起始点就是0,0

若是咱们在这个过程当中能走到重复的位置,尚未找到目标值,证实不能凑出目标水量

也就是说,若是过程当中还能走到0,0点,咱们之间退出就行,有重复路径了,不能凑出目标水量

#include <iostream>

using namespace std;

void printStates(int x, int y){ //输入一下装水的过程
cout << "小水桶容量为:" << x << "," << "大水桶容量为:" << y << "\n";
}

bool twoBucket(int x, int y, int target){ //x是小桶的容量,y是大桶的容量,target是要求的目标水量
int i = 0, j = 0; //i是小桶里的水,j是大桶里的水
while (true) {
if (i == 0 || j == y) { //当小桶没水或者大桶满水->大桶向小桶倒水
while (i != x && j > 0) { //倒水的时候必定要保证大桶里有水
i++;j--;
printStates(i, j);
}
}
if (i == x) { //小桶水满了,就把小桶的水倒空了
while (i != 0) {
i--;
printStates(i, j);
}
if (i == 0 && j == target) { //若是此时大桶的水符合目标水量,直接跳出
return true;
}
if (i == 0 && j == 0) { //若是重复到两桶都没水了,证实没有办法获得目标值
return false;
}
}
if (j == 0) { //若是大桶没水了,就把大桶加满水
while (j != y){
j++;
printStates(i, j);
}
}
}
}

int main(){
cout << "请输入两个水桶的容量,以及想得到的目标水量";
int x,y,target;
cin >> x >> y >> target; //输入两个水桶的容量
int temp = x < y ? x : y; //把小容量的给x,大容量的给y
y = x < y ? y : x;
x = temp;
cout << (twoBucket(x, y, target) ? "能够凑成" : "没法凑成");
return 0;
}

水桶分水问题详解(C++实现)_线性代数_08

直接的输出结果,把输出语句放到当前倒水while循环的外面

符合上述规律

水桶分水问题详解(C++实现)_i++_09

三水桶分水

题目要求:有一个容积为8升的水桶里装满了水,另外还有一个容积为3升的空桶和一个容积为5升的空桶,

如何利用这两个空桶等分8升水?附加条件是三个水桶都没有体积刻度,也不能使用其它辅助容器。

这个问题其实和上面的也差很少,但这里有一个特色就是只有8L水

该图就是三个桶,容量分别为8L,5L,3L 其中8L的水是满的

水桶分水问题详解(C++实现)_线性代数_10

水桶分水问题详解(C++实现)_水桶分水_11

根据图来看,大桶向中桶倒水,而后中桶向小桶倒水

上面两桶分水的规律就是:

​大桶没水了,就把大桶接满水​

​大桶有水,就往小桶倒水​

​小桶满了,就把小桶倒了,从新让大桶向小桶倒水​

其实这里也是大概的想法,

​小桶不满,就把中桶的水倒向小桶​

​中桶没水了,就把大桶的水向里面倒​

​小桶满了,就把小桶的倒向大桶(这里是只有8L水,并非无限水)​

这里咱们用个bool数组来判断是否是走过当前点

有的时候三个桶会陷入循环圈,不能再用上面两桶的判断是否走过起始点了

#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;
}

水桶分水问题详解(C++实现)_i++_12

N水桶分水

三桶水的思路

​小桶不满,就把中桶的水倒向小桶​

​中桶没水了,就把大桶的水向里面倒​

​小桶满了,就把小桶的倒向大桶(这里是只有8L水,并非无限水)​

N桶水就是根据三桶水的规律

设当前为n个桶1 2 3 4 ……n(按容量排序,小的在前)

​1不满,就把2的向1倒​

​若是2没水,就把3向2倒……以此类推​

​若是1满了,就把1的水向n倒(要保证n有足够位置盛放1的水)​

​结束条件仍是,若是当前各个水桶的水量,在之前出现过证实进入了循环,没法得到目标值​

#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;
}

水桶分水问题详解(C++实现)_水桶分水_13