山东省专业群建设网站,哪家公司可以做网站,下载宝硬盘做网站,应用制作app软件目录 题目
问题设计分析
代码
运行结果 题目 容器里有10升油#xff0c;现在只有两个分别能装3升和7升油的瓶子#xff0c;需要将10 升油等分成2 个5 升油。程序输出分油次数最少的详细操作过程。 问题设计分析 容器里有10升油#xff0c;另外还有两个瓶子#xff0c;要…目录 题目
问题设计分析
代码
运行结果 题目 容器里有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 stringusing 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;
}
运行结果
