大气网站欣赏太原网络营销网站

目录

题目

问题设计分析

代码

运行结果

 

---

题目

  容器里有10升油，现在只有两个分别能装3升和7升油的瓶子，需要将10 升油等分成2 个5 升油。程序输出分油次数最少的详细操作过程。

问题设计分析

  容器里有10升油，另外还有两个瓶子，要使得最后两个5升油，也就是说最后要达到的状态是：容器里有5升油，另外两个瓶子里的油加起来也为5升。

我们能做的只有不断的进行倒油的操作。

这是一个典型的“量水问题”或“分油问题”，类似于经典的“水壶问题”。解决这类问题通常需要通过状态空间搜索，即从初始状态出发，通过一系列合法的操作，达到目标状态。为了找到最少操作次数，广度优先搜索（BFS）是一个合适的方法，因为BFS可以确保在找到解时，步数是最少的。

我们需要定义如何表示当前的状态。一个状态可以表示为三个数字：(大容器中的油量, 3升瓶中的油量, 7升瓶中的油量)。初始状态是 (10, 0, 0)。

Bfs的执行步骤为：

1.将大容器中的油倒入3升瓶，直到大容器为空或3升瓶满。

2.将大容器中的油倒入7升瓶，直到大容器为空或7升瓶满。

3.将3升瓶中的油倒入大容器，直到3升瓶为空或大容器满（但大容器初始有10升容量，可以认为它不会被倒满，因为总油量是10升）。

4.将3升瓶中的油倒入7升瓶，直到3升瓶为空或7升瓶满。

5.将7升瓶中的油倒入大容器，直到7升瓶为空或大容器满（同样，大容器不会被倒满）。

6.将7升瓶中的油倒入3升瓶，直到7升瓶为空或3升瓶满。

代码

#include <iostream>
#include <string>using namespace std;// 油量状态
struct State {int large;  // 大容器油量int small3; // 3升瓶油量int small7; // 7升瓶油量
};// 操作描述
struct Operation {State from;State to;string desc;
};const int MAX_STATES = 1000; // 假设最多1000种状态
State visited[MAX_STATES];   // 记录已访问的状态
int visitedCount = 0;        // 已访问状态的数量// 检查状态是否已访问
bool isVisited(const State& s) {for (int i = 0; i < visitedCount; ++i) {if (visited[i].large == s.large && visited[i].small3 == s.small3 && visited[i].small7 == s.small7) {return true;}}return false;
}// 记录新状态
void markVisited(const State& s) {visited[visitedCount++] = s;
}// BFS 求解最少步骤
void solveOilSplitting() {State initialState = {10, 0, 0};State queue[MAX_STATES]; // 手动实现的队列int front = 0, rear = 0;queue[rear++] = initialState;markVisited(initialState);Operation parent[MAX_STATES]; // 记录路径int parentIndex = 0;while (front < rear) {State current = queue[front++];// 检查是否达到目标if (current.large == 5) {// 回溯路径Operation path[MAX_STATES];int steps = 0;State s = current;while (s.large != 10 || s.small3 != 0 || s.small7 != 0) {for (int i = 0; i < parentIndex; ++i) {if (parent[i].to.large == s.large && parent[i].to.small3 == s.small3 && parent[i].to.small7 == s.small7) {path[steps++] = parent[i];s = parent[i].from;break;}}}// 打印路径cout << "最少操作步骤：" << endl;for (int i = steps - 1; i >= 0; --i) {cout << steps - i << ". " << path[i].desc << " ("<< path[i].from.large << "," << path[i].from.small3 << "," << path[i].from.small7 << ") -> ("<< path[i].to.large << "," << path[i].to.small3 << "," << path[i].to.small7 << ")" << endl;}return;}// 生成所有可能的下一步操作// 操作1: 大容器 -> 3升瓶if (current.large > 0 && current.small3 < 3) {int pour = min(current.large, 3 - current.small3);State next = {current.large - pour, current.small3 + pour, current.small7};if (!isVisited(next)) {queue[rear++] = next;markVisited(next);parent[parentIndex++] = {current, next, "将大容器的油倒入3升瓶"};}}// 操作2: 大容器 -> 7升瓶if (current.large > 0 && current.small7 < 7) {int pour = min(current.large, 7 - current.small7);State next = {current.large - pour, current.small3, current.small7 + pour};if (!isVisited(next)) {queue[rear++] = next;markVisited(next);parent[parentIndex++] = {current, next, "将大容器的油倒入7升瓶"};}}// 操作3: 3升瓶 -> 大容器if (current.small3 > 0) {State next = {current.large + current.small3, 0, current.small7};if (!isVisited(next)) {queue[rear++] = next;markVisited(next);parent[parentIndex++] = {current, next, "将3升瓶的油倒入大容器"};}}// 操作4: 3升瓶 -> 7升瓶if (current.small3 > 0 && current.small7 < 7) {int pour = min(current.small3, 7 - current.small7);State next = {current.large, current.small3 - pour, current.small7 + pour};if (!isVisited(next)) {queue[rear++] = next;markVisited(next);parent[parentIndex++] = {current, next, "将3升瓶的油倒入7升瓶"};}}// 操作5: 7升瓶 -> 大容器if (current.small7 > 0) {State next = {current.large + current.small7, current.small3, 0};if (!isVisited(next)) {queue[rear++] = next;markVisited(next);parent[parentIndex++] = {current, next, "将7升瓶的油倒入大容器"};}}// 操作6: 7升瓶 -> 3升瓶if (current.small7 > 0 && current.small3 < 3) {int pour = min(current.small7, 3 - current.small3);State next = {current.large, current.small3 + pour, current.small7 - pour};if (!isVisited(next)) {queue[rear++] = next;markVisited(next);parent[parentIndex++] = {current, next, "将7升瓶的油倒入3升瓶"};}}}cout << "无法分成两个5升。" << endl;
}int main() {solveOilSplitting();return 0;
}

运行结果