【C++】给定两个没有刻度的容器,对于任意给定的容积,求出如何只用两个瓶装出L升的水典型例子思路结束语

103 阅读 0 评论 68 点赞

我是靠谱客的博主专一大侠，最近开发中收集的这篇文章主要介绍【C++】给定两个没有刻度的容器,对于任意给定的容积,求出如何只用两个瓶装出L升的水典型例子思路结束语，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

典型例子

两个水桶分别可以装3L水和5L水，没有刻度，请问怎么装出4L的水。
解答
设A为小桶，B为大桶。
则过程中的每个状态可以如下表示：
方法一：
A B
0 5
3 2
0 2
2 0
2 5
3 4
此时B中装了4L水，共计6步

方法二：
A B
3 0
0 3
3 3
1 5
1 0
0 1
3 1
0 4
此时B中装了4L水，共计8步。

现然方法一比方法二可以更快得到结果。这两者的区别其实就在于：
方法一是刚开始的时候，大桶装满，倒到小桶里面，方法二是小桶装满倒入大桶里面。也就是一个正逆序的问题。

思路

通过上面的例子，我们可以了解到这看似是两个方案。但是却只是一个正序和一个逆序罢了。
那么我们可以求出一个通解吗？
下面我们再来看上面那个例子。
按照固定的思路：
1.假设A桶小，B桶大，且小桶可装m升水，大桶可装M升水。
2.我们一般情况下，肯定是把水装到大桶里面去。例如4L的水，肯定不能装到3L的桶里面去，必须装入5L的桶里面去。因此我们可以考虑，先把小桶装满，往大桶里面倒。
开始倒：
最初A和B中装的水都是0L，这是两个空桶。

0 0
A B
3 0 //A先装满（A=A+3）
0 3 //A中的水倒入B中（B=B+A，B小于5，则A=0；B大于等于5，则A=B-5）
3 3 //A装满（A=A+3）
1 5 //此时重复第二行
1 0 //将B中的水倒出（将B置零）
0 1 //A倒入B中（A和B互换）
3 1 //重复第二行
0 4
3 4 //此时B中已经有4L的水了。这上面便是方法二。此时不要停止，继续倒水
2 5
2 0 //重复第二行
0 2
3 2
0 5 //从最开始A=3.B=0，到了现在变成了A=0，B=5；完成了一个轮回。

我们如果把下面的这个粗体数字逆序来看看，发现这正是方法一。
这里的3就是小桶容积m，5就是大桶容积M。
这是偶然的吗？
我们继续验证一下。

例子2：有一个2L的桶和6L的桶，如何装出4L的水？
此时m=2；M=6；
按照我们之前的思路：
A B
2 0 //A=A+m
0 2 //B=B+A，B小于M，则A=0；B大于等于M，则A=B-M
2 2
0 4 //此时已经得出4L的水了。不要停止，继续倒水。
2 4
0 6//结束。

通过上面两个例子，我们发现了其算法的思路：
本质上都是在不断重复第二行的算法。
通过上面的例子，我们可以清晰的看到，正序和逆序的算法步骤的数量是不相等的，而我们肯定是想要次数最少的步骤，于是可以把上下两部分的步骤次数进行一次对比，然后输出次数最少的一种。
注意：这里并不是说明，逆序就是最短的，这里跟用要求称出的的水的体积有关。
注意2：如果我们经过了一个轮回，但是在大桶的轨迹中并没有找到需要的刻度，则可以认为该刻度不可达，则认为是无解的。

代码实现：

#include"iostream"
#include"algorithm"
#include"vector"
using namespace std;
void output(vector<int> a,vector<int> b,int L)//输出函数，用来输出结果
{
vector<int>::iterator ita, itb ,it;
for (it = b.begin(); it < b.end(); it++)//在大桶的轨迹b中搜寻指定的刻度
{
if (*it == L)
break;
}
if(it==b.end())//如果搜寻到b的末尾还没有找到对应刻度，则说明无解
{
cout << "No Solution" << endl;
return;
}
cout << "A" << "t" << "B" << endl;
if (b.end() - it - 1 > it - b.begin() + 1)//判断是后半部分长还是前半部分更长。
{
ita = a.begin();
itb = b.begin();
while (itb <= it)
{
cout << *ita << "t" << *itb << endl;
ita++; itb++;
}
}
else
{
for (it = b.end()-1; it > b.begin(); it--)
{
if (*it == L)
break;
}
ita = a.end()-1;
itb = b.end()-1;
while (itb >= it)
{
cout << *ita << "t" << *itb << endl;
ita--; itb--;
}
}
cout << "B中装了" << L << "升水" << endl;
}
void Bucket_problem()
{
int A, B, L;
vector<int> A1, B1;//用两个向量保存两条数据，到时候容易比较长短和输出
int flag = 0;
cout << "请输入两个容器的体积（正整数）：" << endl;
cin >> A >> B;
cout << "请输入想要装出的水的体积（正整数）：" << endl;
cin >> L;
cout << "此时A为小桶，B为大桶" << endl;
int M = max(A, B);
int m = min(A, B);
if (L > M)
{
cout << "No Solution" << endl;
return ;
}
if (L == m)
{
cout << "A" << "t" << "B" << endl;
cout << m << "t" << "0" << endl;
cout << "此时A中装了" << m << "升水" << endl;
return ;
}
if (L == M)
{
cout << "A" << "t" << "B" << endl;
cout << "0" << "t" << M << endl;
cout << "此时B中装了" << M << "升水" << endl;
return ;
}
int a = 0, b = 0;
a = m;
while (true)//制造一个循环
{
if (b == M)
{
b = 0;
if (a == 0 && b == 0) break;//退出条件
A1.push_back(a); B1.push_back(b);
swap(a, b);
A1.push_back(a); B1.push_back(b);
a = m;
continue;
}
A1.push_back(a); B1.push_back(b);
//
cout << A << "t" << B;
b = b + a;
if (b >= M)
{
a = b - M;
b = M;
A1.push_back(a); B1.push_back(b);
}
else
{
a = 0;
A1.push_back(a); B1.push_back(b);
a = m;
}
}
output(A1, B1, L);
}
int main()
{
Bucket_problem();
system("pause");
return 0;
}