用BFS方法求解平分汽油问题

一只大桶里盛着18升汽油，要求把它们分成两份，每份9升，可是旁边没有量器， 只有一只能装10升和一只能装7升的空桶，请你利用这3只桶倒来倒去，把汽油平分开来。

#include <stdio.h> #include <stdbool.h> #include <string.h> #define MAX_STATES 10000 // 容量数组 const int Capacity[3] = {18, 10, 7}; // 桶名指针数组 const char *Bucket_name[3] = {"18升桶", "10升桶", "7升桶"}; /* 结构体记录一次倒油操作：由哪个桶给哪个桶倒的油, ** * 倒了多少油, 三个桶的油量 */ typedef struct { int state[3]; int parent; int from; int to; int amount; } Node; // 定义结构体数组，依次记录所有的倒油操作 Node queue[MAX_STATES]; // 队首队尾标记 int head = 0, tail = 0; // 记录三个桶油量出现与否 bool visited[19][11][8]; // 到达目标状态 bool Is_target(int s[3]); // 一次倒油操作 bool Pour_oil(int curr[3], int A, int B, int next[3], int *amount); // 启动倒油操作，用BFS方法寻找最短步数 int bfs(int start[3]); // 输出平分的步骤 void Print_path(int target_index); int main() { int start[3] = {18, 0, 0}; // 初始三个桶的油量 int result; memset(visited, 0, sizeof(visited)); // 记录有无解决方案 result = bfs(start); if (result != -1) { printf("找到最优解!\n"); Print_path(result); } else { printf("未找到解决方案\n"); } return 0; } bool Is_target(int s[3]) { return (s[0] == 9 && s[1] == 9 && s[2] == 0); } bool Pour_oil(int curr[3], int A, int B, int next[3], int *amount) { int space; // 若倒出桶为空，或倒入桶已满，倒油操作失败 if (curr[A] == 0 || curr[B] == Capacity[B]) return false; // next数组赋初值 next[0] = curr[0]; next[1] = curr[1]; next[2] = curr[2]; // 倒入桶能导入的油量 space = Capacity[B] - curr[B]; // 确定实际的倒油量，curr[A]=倒出桶的油量 *amount = curr[A] < space ? curr[A] : space; // 执行倒油操作后，倒出桶和倒入桶的油量 next[A] -= *amount; next[B] += *amount; // 实现了一次倒油操作 return true; } int bfs(int start[3]) { int i, j; int next[3]; int amount; // 三个桶的初始状态放入队尾，-1是初始标志 queue[tail].state[0] = start[0]; queue[tail].state[1] = start[1]; queue[tail].state[2] = start[2]; queue[tail].parent = -1; queue[tail].from = -1; queue[tail].to = -1; queue[tail].amount = 0; tail++; // 新的位置索引 // 对三个桶的状态做标记 visited[start[0]][start[1]][start[2]] = true; // 若队列不空 while (head < tail) { // 从队首取出结构体 Node *current = &queue[head]; if (Is_target(current->state)) { return head; // 返回目标状态的索引值 } // 由当前三个桶的状态尝试各种允许的倒油操作 for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { if (i == j) continue; if (Pour_oil(current->state, i, j, next, &amount)) { if (!visited[next[0]][next[1]][next[2]]) { // 一次倒油操作入队尾 queue[tail].state[0] = next[0]; queue[tail].state[1] = next[1]; queue[tail].state[2] = next[2]; queue[tail].parent = head; queue[tail].from = i; queue[tail].to = j; queue[tail].amount = amount; tail++; // 对三个桶的状态做标记 visited[next[0]][next[1]][next[2]] = true; } } } } head++; // 新的队首索引 } return -1; // 没有找到解决方案 } void Print_path(int target_index) { int path[MAX_STATES]; int len = 0; int i; i = target_index; // path逆序存放求解步骤索引 while (i != -1) { path[len++] = i; i = queue[i].parent; } printf("共 %d 步操作：\n", len - 1); // 逆序输出求解步骤 for (i = len - 1; i >= 0; i--) { Node *node = &queue[path[i]]; if (node->from == -1) { printf("初始状态: [18升=%d, 10升=%d, 7升=%d]\n", node->state[0], node->state[1], node->state[2]); } else { printf("步骤 %d: 从%s倒%d升到%s\n", len - 1 - i, Bucket_name[node->from], node->amount, Bucket_name[node->to]); printf(" [18升=%d, 10升=%d, 7升=%d]\n", node->state[0], node->state[1], node->state[2]); } } }

找到最优解!
共 11 步操作：
初始状态: [18升=18, 10升=0, 7升=0]
步骤 1: 从18升桶倒10升到10升桶
[18升=8, 10升=10, 7升=0]
步骤 2: 从10升桶倒7升到7升桶
[18升=8, 10升=3, 7升=7]
步骤 3: 从7升桶倒7升到18升桶
[18升=15, 10升=3, 7升=0]
步骤 4: 从10升桶倒3升到7升桶
[18升=15, 10升=0, 7升=3]
步骤 5: 从18升桶倒10升到10升桶
[18升=5, 10升=10, 7升=3]
步骤 6: 从10升桶倒4升到7升桶
[18升=5, 10升=6, 7升=7]
步骤 7: 从7升桶倒7升到18升桶
[18升=12, 10升=6, 7升=0]
步骤 8: 从10升桶倒6升到7升桶
[18升=12, 10升=0, 7升=6]
步骤 9: 从18升桶倒10升到10升桶
[18升=2, 10升=10, 7升=6]
步骤 10: 从10升桶倒1升到7升桶
[18升=2, 10升=9, 7升=7]
步骤 11: 从7升桶倒7升到18升桶
[18升=9, 10升=9, 7升=0]