C程序解决传教士与野人过河问题

"传教士与野人过河问题是一个经典的逻辑谜题，通常涉及到三个传教士和三个野人，以及一条只能承载一至两人（包括传教士和野人）的小船。目标是通过一系列合理的渡河操作，使得所有人都能安全到达对岸，且在任何时候都不能出现野人多于传教士的情况，因为那样的话，传教士可能会受到伤害。这个问题通常采用递归算法来解决，这里给出的C程序正是基于这一思路进行设计的。 在程序中，定义了一个名为`INFO`的结构体，它包含了关键的状态信息： 1. `nSavage`: 表示岸边野人的数量，初始值为3，目标为0，意味着所有野人都已过河。 2. `nBoanerges`: 表示岸边传教士的数量，初始值为3，目标为0，表示所有传教士都已过河。 3. `nSide`: 标记小船所在的位置，-1表示在左岸，1表示在右岸。 4. `nMoveSavage` 和 `nMoveBoanerges`: 分别记录本次渡河时野人和传教士的数量，用于递归过程中追踪状态变化。 5. `pPrevious` 和 `pNext`: 指针，用于连接不同状态的节点，形成状态链，便于回溯和查找解。 `GetNextMove`函数是程序的核心部分，它负责生成所有可能的下一次移动情况。这里通过一个`STORE`结构体数组`listStore`来存储每一步可能的状态，然后根据当前的移动情况（由`nMoveSavage`和`nMoveBoanerges`决定）从数组中找出合适的下一次移动。函数首先会根据小船所在的一侧（左岸或右岸）填充`listStore`，然后根据已移动的人数`iStart`来查找合法的下一步。 这个程序的执行流程大致如下： 1. 初始化传教士和野人的状态，并设置小船位置。 2. 调用`GetNextMove`函数，生成所有可能的下一次移动。 3. 对每个可能的移动，检查是否满足安全条件（即在任何情况下野人不能超过传教士），并继续递归调用`GetNextMove`，直到所有人员都到达对岸或者没有可行的移动方案为止。 4. 如果找到了满足条件的移动序列，记录并输出解决方案；如果没有找到，则返回失败。 这个C程序通过递归搜索所有可能的渡河序列，最终找到并输出一个有效的解决方案。虽然题目中给出的代码并不完整，但可以看出其基本思路和关键结构，对于理解传教士与野人过河问题的解决方法具有一定的参考价值。"