引入
1、容器里有10升油,现在只有两个分别能装3升和7升油的瓶子,需要将10 升油等分成2 个5 升油。程序输出分油次数最少的详细操作过程。
思考
这题主要是要求了输出分油次数最少的操作,网上很多算法都是寻找可行解,没有找出最优解。
仔细分析这题发现思路很简单:
开始总共只有两种倒法,十升向7升的到,十升向3升的到,然后不回倒,下一步倒向另一个,当7升的倒满了之后,再回倒入10升的杯子中,进入循环,直到有解为止。
最终状态一定是10升的杯子有5升,7升的杯子有5升。
状态 | 10升 | 3升 | 7升 |
---|---|---|---|
初始 | 10 | 0 | 0 |
状态1 | 7 | 3 | 0 |
状态2 | 7 | 0 | 3 |
状态3 | 4 | 3 | 3 |
状态4 | 4 | 0 | 6 |
状态5 | 1 | 3 | 6 |
状态6 | 1 | 2 | 7 |
状态7 | 8 | 2 | 0 |
状态8 | 8 | 0 | 2 |
状态9 | 5 | 3 | 2 |
状态10 | 5 | 0 | 5 |
代码
这里只是简单实现了一下,复杂一点可以将结果保存到数组中,然后根据需求再输出。
#include <iostream>
using namespace std;//开始总共只有两种倒法,十升向7升的到,十升向3升的到,然后不回倒,下一步倒向另一个,直到有解为止
int pull(int m, int n) {int decaliter = 10,//十升的容器中有十升油a = 0,b = 0,total = 1;//表示步骤数while (decaliter != 5) { if (a == 0) { //第一步向3/7L杯子倒油decaliter -= m; a += m; cout << total++ << ": 10 L容器向 " << m << " L容器倒入 " << m << " L油" << endl;} if (a > 0 && b < n) {//3/7L杯子有油时倒入7/3L杯子 if (b + a <= n) {//如果n为7升,b+a小于7升,将3升倒入7升杯子中b += a;cout << total++ << ": " << m << " L容器向 " << n << " L容器倒入 " << a << " L油" << endl;a -= a; } else { //不然就为m是7升,b+a大于7升,,将3升倒入3升杯子中a -= n - b; cout << total++ << ": " << m << " L容器向 " << n << " L容器倒入 " << n - b << " L油" << endl;b = n; } } if (b == n) { //当7升容器倒满后,将7升倒回10升容器中b -= n;decaliter += n;cout << total++ << ": " << n << " L容器向 10 L容器倒入 " << n << " L油" << endl;}//最后状态一定是十升容器有5升,7升容器有5升if (m >= n) { if (a == 5) break; } else { if (b == 5)break; } }cout << " 10L容器中有 " << decaliter << " L油, " << m << " L容器中有 " << a << " L油, " << n << " L容器中有 " << b << " L油" <<"\n"<< endl;return --total;
}
int main() { int min;cout << "第 1 种方案:" << endl;min = pull(3, 7);cout << "第 2 种方案:" << endl; if (min > pull(7, 3))cout << "第 2 种方案步骤最少。"; else cout << "第 1 种方案步骤最少。"; return 0;
}
注
拿到题目就找了一下CSDN,上面也有些博客写上了自己的思路,我直接将网址CP到下面了,以供大家参考。
https://blog.csdn.net/dufemt/article/details/80335300?spm=1001.2101.3001.6650.7&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EOPENSEARCH%7Edefault-7.no_search_link&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EOPENSEARCH%7Edefault-7.no_search_link
https://blog.csdn.net/RAYFUXK/article/details/84776307?ops_request_misc=&request_id=&biz_id=102&utm_term=1%E3%80%81%E5%AE%B9%E5%99%A8%E9%87%8C%E6%9C%8910%E5%8D%87%E6%B2%B9%EF%BC%8C%E7%8E%B0%E5%9C%A8%E5%8F%AA%E6%9C%89%E4%B8%A4%E4%B8%AA%E5%88%86%E5%88%AB%E8%83%BD%E8%A3%853%E5%8D%87%E5%92%8C7%E5%8D%87%E6%B2%B9%E7%9A%84%E7%93%B6%E5%AD%90&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduweb~default-4-84776307.nonecase&spm=1018.2226.3001.4187
https://blog.csdn.net/qq_44365861/article/details/109482281?ops_request_misc=&request_id=&biz_id=102&utm_term=1%E3%80%81%E5%AE%B9%E5%99%A8%E9%87%8C%E6%9C%8910%E5%8D%87%E6%B2%B9%EF%BC%8C%E7%8E%B0%E5%9C%A8%E5%8F%AA%E6%9C%89%E4%B8%A4%E4%B8%AA%E5%88%86%E5%88%AB%E8%83%BD%E8%A3%853%E5%8D%87%E5%92%8C7%E5%8D%87%E6%B2%B9%E7%9A%84%E7%93%B6%E5%AD%90&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduweb~default-0-109482281.pc_search_result_hbase_insert&spm=1018.2226.3001.4187