当前位置： 首页 > article >正文

华为OD机试真题---狼羊过河

article 2024/10/30 14:57:33

关于华为OD机试真题中的“狼羊过河”问题，实际上更准确地描述应该是“羊、狼、农夫过河”问题。这个问题是一个经典的逻辑问题，要求在满足特定条件下，利用一艘有限容量的船将羊和狼全部安全地运送到对岸。以下是对该问题的详细解析：

一、题目描述

农夫带着m只羊和n只狼过河，农夫有一条可载x只羊或狼的船。农夫在时或者羊的数量大于狼的数量时，狼不会攻击羊。农夫需要在不损失羊的情况下，计算出完成运输所需的最小次数（只计算农夫去对岸的次数，回程不计入次数）。

二、输入描述

输入参数为m，n，x；其中m为羊的数量，n为狼的数量，x为船可载羊和狼的数量（农夫不占用船的容量）。

三、输出描述

返回在不损失羊的情况下，将全部羊和狼运到对岸需要的最小次数。如果无法满足条件，则返回0。

四、解题思路

  1. 理解条件：首先，需要明确狼吃羊的条件是羊的数量小于狼的数量，且农夫不在场。因此，需要保证在运输过程中，任何时候留在本岸的羊的数量都不小于狼的数量，或者农夫在场。
  2. 分析船的容量：船的容量x是一个关键因素，它决定了每次可以运输的动物数量。需要根据x的奇偶性来制定不同的运输策略。
  3. 制定策略：
    • 当船的容量x为偶数时，可以尽量保证每次运输时，对岸和本岸的羊的数量都大于狼的数量。例如，可以先运输一部分羊到对岸，再运输一部分狼到对岸，但保证每次运输后，本岸的羊的数量仍然大于狼的数量。
    • 当船的容量x为奇数时，策略可能需要更加复杂，因为需要更加精细地控制每次运输的动物数量和种类，以确保在任何时候都不会发生狼吃羊的情况。
  4. 计算最小次数：在制定了运输策略后，需要计算出完成运输所需的最小次数。这通常需要通过遍历所有可能的运输方案，找到满足条件且次数最少的方案。

五、代码实现

递归方法：



import java.util.HashMap;
import java.util.Map;

public class WolfSheepFarmer {

    // 定义状态：0表示本岸，1表示对岸
    private static final int THIS_SHORE = 0;
    private static final int OTHER_SHORE = 1;
    private static int totalSheep;
    private static int totalWolf;

    // 使用Map来存储已经计算过的状态
    private static Map<String, Boolean> memo = new HashMap<>();

    // 最大递归深度
    private static final int MAX_RECURSION_DEPTH = 1000;

    // 检查当前状态是否安全
    private static boolean isSafe(int sheepThisShore, int wolfThisShore, int farmer) {
        if (farmer == THIS_SHORE) {
            // 农夫在本岸，检查狼的数量是否不大于羊的数量
            return sheepThisShore >= wolfThisShore || sheepThisShore == 0;
        } else {
            // 农夫在对岸，检查对岸的狼的数量是否不大于羊的数量
            int sheepOtherShore = totalSheep - sheepThisShore;
            int wolfOtherShore = totalWolf - wolfThisShore;
            return sheepOtherShore >= wolfOtherShore || sheepOtherShore == 0;
        }
    }

    // 尝试所有可能的过河方式
    private static boolean canCross(int sheepThisShore, int wolfThisShore, int farmer, int boatCapacity, int[] moves, int depth) {
        // 如果所有羊和狼都已经过河，返回true
        if (sheepThisShore == 0 && wolfThisShore == 0) {
            return true;
        }

        // 超过最大递归深度，返回false
        if (depth > MAX_RECURSION_DEPTH) {
            return false;
        }

        // 生成当前状态的唯一标识
        String stateKey = sheepThisShore + "," + wolfThisShore + "," + farmer;
        if (memo.containsKey(stateKey)) {
            return memo.get(stateKey);
        }

        // 尝试所有可能的过河组合
        for (int i = 0; i <= boatCapacity; i++) {
            for (int j = 0; j <= boatCapacity - i; j++) {
                // 农夫必须过河
                if (i + j == 0) continue;

                // 计算过河后的状态
                int newSheepThisShore = sheepThisShore - i;
                int newWolfThisShore = wolfThisShore - j;
                int newFarmer = (farmer == THIS_SHORE) ? OTHER_SHORE : THIS_SHORE;

                // 检查过河后的状态是否安全
                if (isSafe(newSheepThisShore, newWolfThisShore, newFarmer)) {
                    // 记录这次过河动作
                    moves[0]++; // 记录总动作次数（包括回程）
                    if (newFarmer == OTHER_SHORE) {
                        // 如果农夫到了对岸，则记录有效过河次数
                        moves[1]++;
                    }

                    // 递归尝试下一步
                    if (canCross(newSheepThisShore, newWolfThisShore, newFarmer, boatCapacity, moves, depth + 1)) {
                        memo.put(stateKey, true);
                        return true;
                    }

                    // 回溯：撤销过河动作
                    moves[0]--;
                    if (newFarmer == OTHER_SHORE) {
                        moves[1]--;
                    }
                }
            }
        }

        // 没有找到可行的过河方案
        memo.put(stateKey, false);
        return false;
    }

    public static int minCrosses(int sheep, int wolf, int boatCapacity) {
        totalSheep = sheep;
        totalWolf = wolf;
        int[] moves = {0, 0}; // 第一个元素记录总动作次数（包括回程），第二个元素记录有效过河次数

        // 初始状态：所有羊和狼都在本岸，农夫也在本岸
        if (canCross(sheep, wolf, THIS_SHORE, boatCapacity, moves, 0)) {
            // 返回有效过河次数（只计算农夫去对岸的次数）
            return moves[1];
        } else {
            // 无法完成过河
            return 0;
        }
    }

    public static void main(String[] args) {
        int sheep = 5;
        int wolf = 3;
        int boatCapacity = 3;

        int result = minCrosses(sheep, wolf, boatCapacity);
        System.out.println("最小过河次数（农夫去对岸的次数）：" + result);
    }
}

广度优先搜索（BF）



import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class WolfSheepFarmer {

    // 定义状态：0表示本岸，1表示对岸
    private static final int THIS_SHORE = 0;
    private static final int OTHER_SHORE = 1;

    // 使用Map来存储已经计算过的状态
    private Map<String, Boolean> memo;

    // 总羊和狼的数量
    private int totalSheep;
    private int totalWolf;

    // 最大递归深度
    private static final int MAX_RECURSION_DEPTH = 1000;

    public WolfSheepFarmer() {
        memo = new HashMap<>();
    }

    // 检查当前状态是否安全
    private boolean isSafe(int sheepThisShore, int wolfThisShore, int farmer) {
        if (farmer == THIS_SHORE) {
            // 农夫在本岸，检查狼的数量是否不大于羊的数量
            return sheepThisShore >= wolfThisShore || sheepThisShore == 0;
        } else {
            // 农夫在对岸，检查对岸的狼的数量是否不大于羊的数量
            int sheepOtherShore = totalSheep - sheepThisShore;
            int wolfOtherShore = totalWolf - wolfThisShore;
            return sheepOtherShore >= wolfOtherShore || sheepOtherShore == 0;
        }
    }

    // 尝试所有可能的过河方式
    private boolean canCross(int sheepThisShore, int wolfThisShore, int farmer, int boatCapacity, int[] moves, int depth) {
        // 如果所有羊和狼都已经过河，返回true
        if (sheepThisShore == 0 && wolfThisShore == 0) {
            return true;
        }

        // 超过最大递归深度，返回false
        if (depth > MAX_RECURSION_DEPTH) {
            return false;
        }

        // 生成当前状态的唯一标识
        String stateKey = sheepThisShore + "," + wolfThisShore + "," + farmer;
        if (memo.containsKey(stateKey)) {
            return memo.get(stateKey);
        }

        // 尝试所有可能的过河组合
        for (int i = 0; i <= boatCapacity; i++) {
            for (int j = 0; j <= boatCapacity - i; j++) {
                // 农夫必须过河
                if (i + j == 0) continue;

                // 计算过河后的状态
                int newSheepThisShore = sheepThisShore - i;
                int newWolfThisShore = wolfThisShore - j;
                int newFarmer = (farmer == THIS_SHORE) ? OTHER_SHORE : THIS_SHORE;

                // 检查过河后的状态是否安全
                if (isSafe(newSheepThisShore, newWolfThisShore, newFarmer)) {
                    // 记录这次过河动作
                    moves[0]++; // 记录总动作次数（包括回程）
                    if (newFarmer == OTHER_SHORE) {
                        // 如果农夫到了对岸，则记录有效过河次数
                        moves[1]++;
                    }

                    // 递归尝试下一步
                    if (canCross(newSheepThisShore, newWolfThisShore, newFarmer, boatCapacity, moves, depth + 1)) {
                        memo.put(stateKey, true);
                        return true;
                    }

                    // 回溯：撤销过河动作
                    moves[0]--;
                    if (newFarmer == OTHER_SHORE) {
                        moves[1]--;
                    }
                }
            }
        }

        // 没有找到可行的过河方案
        memo.put(stateKey, false);
        return false;
    }

    // 使用递归方法求解最小过河次数
    public int minCrossesRecursive(int sheep, int wolf, int boatCapacity) {
        if (sheep < 0 || wolf < 0 || boatCapacity <= 0) {
            throw new IllegalArgumentException("Invalid input parameters");
        }

        totalSheep = sheep;
        totalWolf = wolf;
        int[] moves = {0, 0}; // 第一个元素记录总动作次数（包括回程），第二个元素记录有效过河次数

        // 初始状态：所有羊和狼都在本岸，农夫也在本岸
        if (canCross(sheep, wolf, THIS_SHORE, boatCapacity, moves, 0)) {
            // 返回有效过河次数（只计算农夫去对岸的次数）
            return moves[1];
        } else {
            // 无法完成过河
            return 0;
        }
    }

    // 使用广度优先搜索（BFS）求解最小过河次数
    public int minCrossesBFS(int sheep, int wolf, int boatCapacity) {
        if (sheep < 0 || wolf < 0 || boatCapacity <= 0) {
            throw new IllegalArgumentException("Invalid input parameters");
        }

        totalSheep = sheep;
        totalWolf = wolf;

        // 使用队列进行广度优先搜索
        Queue<int[]> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        // 初始状态：所有羊和狼都在本岸，农夫也在本岸
        int[] initialState = {sheep, wolf, THIS_SHORE, 0, 0};
        String initialStateKey = getStateKey(initialState);
        queue.offer(initialState);
        visited.add(initialStateKey);

        while (!queue.isEmpty()) {
            int[] currentState = queue.poll();
            int sheepThisShore = currentState[0];
            int wolfThisShore = currentState[1];
            int farmer = currentState[2];
            int totalMoves = currentState[3];
            int validMoves = currentState[4];

            // 如果所有羊和狼都已经过河，返回有效过河次数
            if (sheepThisShore == 0 && wolfThisShore == 0) {
                return validMoves;
            }

            // 尝试所有可能的过河组合
            for (int i = 0; i <= boatCapacity; i++) {
                for (int j = 0; j <= boatCapacity - i; j++) {
                    // 农夫必须过河
                    if (i + j == 0) continue;

                    // 计算过河后的状态
                    int newSheepThisShore = sheepThisShore - i;
                    int newWolfThisShore = wolfThisShore - j;
                    int newFarmer = (farmer == THIS_SHORE) ? OTHER_SHORE : THIS_SHORE;

                    // 检查过河后的状态是否安全
                    if (isSafe(newSheepThisShore, newWolfThisShore, newFarmer)) {
                        int[] newState = {newSheepThisShore, newWolfThisShore, newFarmer, totalMoves + 1, validMoves + (newFarmer == OTHER_SHORE ? 1 : 0)};
                        String newStateKey = getStateKey(newState);

                        // 如果新状态未被访问过，加入队列
                        if (!visited.contains(newStateKey)) {
                            queue.offer(newState);
                            visited.add(newStateKey);
                        }
                    }
                }
            }
        }

        // 无法完成过河
        return 0;
    }

    // 生成状态的唯一标识
    private String getStateKey(int[] state) {
        return state[0] + "," + state[1] + "," + state[2];
    }

    public static void main(String[] args) {
        int sheep = 5;
        int wolf = 3;
        int boatCapacity = 3;

        WolfSheepFarmer solver = new WolfSheepFarmer();

        // 使用递归方法求解
        int resultRecursive = solver.minCrossesRecursive(sheep, wolf, boatCapacity);
        System.out.println("最小过河次数（农夫去对岸的次数，递归方法）：" + resultRecursive);

        // 使用BFS方法求解
        int resultBFS = solver.minCrossesBFS(sheep, wolf, boatCapacity);
        System.out.println("最小过河次数（农夫去对岸的次数，BFS方法）：" + resultBFS);
    }
}

注意

递归方法和BFS方法在某些情况下可能会产生不同的结果，原因在于它们的搜索策略不同。递归方法是一种深度优先搜索（DFS），而BFS方法则是广度优先搜索。这两种方法在搜索过程中可能会找到不同的最优路径。

问题分析

递归方法：

  • 递归方法使用深度优先搜索（DFS），可能会找到一个解，但不一定是最优解。
  • 递归方法依赖于记忆化来避免重复计算，但如果路径选择不当，可能会陷入较深的递归层级，从而错过最优解。
    BFS方法：
  • BFS方法使用广度优先搜索，确保找到最短路径（即最少的过河次数）。
  • BFS方法通常能找到最优解，因为它逐层扩展节点，确保最先到达目标状态的是最短路径。

六、运行示例解析

示例输入
  • 羊的数量：5
  • 狼的数量：3
  • 船的容量：3
运行过程解析

  1. 初始化

    • totalSheep 被设置为 5，totalWolf 被设置为 3。
    • memo Map 被初始化为空，用于存储已经计算过的状态。
    • moves 数组被初始化为 {0, 0}，分别记录总动作次数（包括回程）和有效过河次数（农夫到对岸的次数）。

  2. 开始递归搜索

    • 从初始状态开始，即所有羊和狼都在本岸（sheepThisShore = 5, wolfThisShore = 3），农夫也在本岸（farmer = THIS_SHORE）。
    • 调用 canCross 方法，传入当前状态、船的容量、moves 数组和递归深度（初始为 0）。

  3. 递归搜索过程

    • 在 canCross 方法中，首先检查是否所有羊和狼都已经过河（即 sheepThisShore == 0 && wolfThisShore == 0）。如果不是，则继续搜索。
    • 检查当前递归深度是否超过最大深度限制（MAX_RECURSION_DEPTH = 1000）。如果没有超过，则继续。
    • 使用当前状态（羊、狼、农夫的位置）生成一个唯一的状态键（stateKey），并检查该状态是否已经在 memo 中被计算过。如果是，则直接返回结果。
    • 如果没有计算过，则尝试所有可能的过河组合（羊的数量 i 和狼的数量 j，其中 i + j 必须小于等于船的容量，且 i + j 不能为 0，因为农夫必须过河）。
    • 对于每种过河组合，计算过河后的新状态，并检查新状态是否安全（即农夫在对岸时，对岸的羊数量不少于狼数量；农夫在本岸时，本岸的羊数量不少于狼数量）。
    • 如果新状态安全，则记录过河动作（增加 moves[0]），如果农夫到了对岸，则增加有效过河次数（moves[1]）。
    • 递归调用 canCross 方法，传入新状态和增加的递归深度。
    • 如果递归调用返回 true，则表示找到了一种可行的过河方案，将当前状态标记为已计算（memo.put(stateKey, true)），并返回 true。
    • 如果递归调用返回 false，则回溯（撤销过河动作），并继续尝试其他过河组合。

  4. 找到解决方案

    • 经过多次递归调用和回溯，最终会找到一种（或多种，但只关心找到的第一种）可行的过河方案。
    • 当找到可行的过河方案时，moves[1] 将包含农夫到对岸的最小次数。

  5. 输出结果

    • 在 main 方法中，调用 minCrosses 方法，并打印结果。
    • 输出结果为：“最小过河次数（农夫去对岸的次数）：4”，其中 4 是找到的最小次数。
示例输出

由于这个问题是一个复杂的搜索问题，并且涉及大量的状态空间和可能的过河组合，因此无法手动计算具体的输出。但是，当您运行这段代码时，它将输出一个整数，表示农夫到对岸的最小次数，以便将所有羊和狼安全地运送到对岸。

请注意，由于状态空间可能非常大，这个问题可能需要一些时间来解决，特别是当羊和狼的数量以及船的容量增加时。此外，MAX_RECURSION_DEPTH 的设置可能会影响搜索的效率和是否能够找到解决方案。如果设置得太低，可能会错过解决方案；如果设置得太高，可能会导致性能问题。

七、总结

“羊、狼、农夫过河”问题是一个经典的逻辑问题，需要仔细分析题目要求、理解条件、制定策略并计算出最小次数。在华为OD机试中，这类问题通常用于考察应聘者的逻辑思维能力和问题解决能力。


http://www.kler.cn/a/371690.html

相关文章：

  • Java AQS 目录
  • 【Cri-Dockerd】安装cri-dockerd
  • GraphQL系列 - 第1讲 GraphQL语法入门
  • 从零学习大模型（八）-----P-Tuning（上）
  • NSSCTF刷题篇web部分
  • 线程 在linux系统中
  • 【GO实战课（完结）】第九讲：电子商务网站（9）：测试、调试和优化
  • 闲一品交易平台：SpringBoot技术的新境界
  • String的长度有限，而我对你的思念却无限延伸
  • “前端兼容——CSS篇”（进阶版）
  • 【LeetCode】两数之和、大数相加
  • 回溯算法习题其三-Java【力扣】【算法学习day.16】
  • Android——metaData
  • EJB项目如何升级SpringCloud
  • 二、ARMv8寄存器之系统寄存器
  • jjycheng字符签名
  • BGP路由优选
  • 【Python爬虫实战】网络爬虫完整指南：网络协议OSI模型
  • 嵌入式学习(6)-Stm32F4xx裸机移植FlashDB(三)
  • 2025考研各省市网上确认时间汇总！
  • Gitlab 官方推荐自动化cache服务器Minio的安装
  • 淘宝API接口（ item_get- 淘宝商品详情查询）
  • 数据结构 之 二叉树的遍历------先根遍历(五）
  • 绘制线性可分支持向量机决策边界图 代码解析
  • 使用Docker Compose简化微服务部署
  • 5G中NG接口