一只大桶里盛着12升汽油要求把它们分成两份每份6升可是旁边没有量器 只有一只能装9升和一只能装5升的空桶请你利用这3只桶倒来倒去把汽油平分开来。#include stdio.h #include stdbool.h #include string.h #define MAX_STEPS 20 const int Capcity[3] {12, 9, 5}; const char *Bucket_name[3] {12升桶, 9升桶, 5升桶}; bool visited[13][10][6]; typedef struct { int state[3]; // 三个桶的油量 char action[100]; // 操作描述 } Step; Step steps[MAX_STEPS]; int step_count 0; // 目标状态12升桶6, 9升桶6, 5升桶0 bool Is_target(int s[3]) { return (s[0] 6 s[1] 6 s[2] 0); } // 复制状态 void Copy_state(int dst[3], int src[3]) { int i; for(i0;i3;i) dst[i] src[i]; } // 执行倒油操作从桶A倒到桶B成功返回1 bool Pour_oil(int curr[3], int A, int B, int next[3]) { int space; int amount; // 源桶必须非空目标桶必须未满 if (curr[A] 0 || curr[B] Capcity[B]) { return 0; } Copy_state(next, curr); // 计算倒油量 space Capcity[B] - curr[B]; // 目标桶剩余空间 amount curr[A] space ? curr[A] : space; // 取较小值 next[A] - amount; next[B] amount; return 1; } // 深度优先搜索 迭代加深 bool dfs(int curr[3], int depth, int max_depth) { int i, j; int next[3]; int amount; // 找到目标 if (Is_target(curr)) { step_count depth; return 1; } // 超过深度限制 if (depth max_depth) return 0; // 标记已访问 visited[curr[0]][curr[1]][curr[2]] true; // 尝试6种倒油方式 (0-1, 0-2, 1-0, 1-2, 2-0, 2-1) for (i 0; i 3; i) { for ( j 0; j 3; j) { if (i j) continue; if (Pour_oil(curr, i, j, next)) { // 跳过已访问状态 if (visited[next[0]][next[1]][next[2]]) continue; // 记录当前步骤 Copy_state(steps[depth].state, next); amount curr[i] - next[i]; sprintf(steps[depth].action, 从%s倒%d升到%s, Bucket_name[i], amount, Bucket_name[j]); // 递归搜索 if(dfs(next, depth 1, max_depth)) return 1; } } } // 回溯取消访问标记 visited[curr[0]][curr[1]][curr[2]] 0; return 0; } // 打印解决方案 void Print_solution() { int i; printf(初始状态: 12升桶装12升, 9升桶装0升, 5升桶装0升\n\n); printf(目标状态: 12升桶装6升, 9升桶装6升,5升桶装0升\n\n); for ( i 0; i step_count; i) { printf(步骤 %d: %s\n, i 1, steps[i].action); printf( [12升%d, 9升%d, 5升%d]\n, steps[i].state[0], steps[i].state[1], steps[i].state[2]); } } int main() { int start[3] {12, 0, 0}; // 初始状态 int max_d; bool found 0; // 迭代加深找到步数最少的解 for (max_d 1; max_d MAX_STEPS !found; max_d) { memset(visited, 0, sizeof(visited)); if (dfs(start, 0, max_d)) { found 1; printf(找到最优解共 %d 步操作\n, step_count); } } if (found) Print_solution(); else printf(未找到解决方案\n); return 0; }找到最优解共 8 步操作初始状态: 12升桶装12升, 9升桶装0升, 5升桶装0升目标状态: 12升桶装6升, 9升桶装6升,5升桶装0升步骤 1: 从12升桶倒5升到5升桶12升7, 9升0, 5升5步骤 2: 从5升桶倒5升到9升桶12升7, 9升5, 5升0步骤 3: 从12升桶倒5升到5升桶12升2, 9升5, 5升5步骤 4: 从5升桶倒4升到9升桶12升2, 9升9, 5升1步骤 5: 从9升桶倒9升到12升桶12升11, 9升0, 5升1步骤 6: 从5升桶倒1升到9升桶12升11, 9升1, 5升0步骤 7: 从12升桶倒5升到5升桶12升6, 9升1, 5升5步骤 8: 从5升桶倒5升到9升桶12升6, 9升6, 5升0