一只大桶里盛着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]