平分汽油问题
一只大桶里盛着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(i=0;i<3;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