华为OD机试 - 羊、狼、农夫过河 - 逻辑分析（Python/JS/C/C++ 2025 A卷 100分）

最新推荐文章于 2025-05-08 08:06:01 发布

哪吒

最新推荐文章于 2025-05-08 08:06:01 发布

阅读量873

点赞数 20

分类专栏：搬砖工逆袭Java架构师文章标签：华为od python javascript 2025A卷华为OD机试

本文为博主原创文章，未经博主允许不得转载。

本文链接：https://blog.csdn.net/guorui_java/article/details/145181474

版权

搬砖工逆袭Java架构师专栏收录该内容

335 篇文章

订阅专栏

在这里插入图片描述

华为OD机试 2025A卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

羊、狼、农夫都在岸边，当羊的数量小于狼的数量时，狼会攻击羊，农夫则会损失羊。农夫有一艘容量固定的船，能够承载固定数量的动物。

要求求出不损失羊情况下将全部羊和狼运到对岸需要的最小次数。只计算农夫去对岸的次数，回程时农夫不会运送羊和狼。

备注：农夫在或农夫离开后羊的数量大于狼的数量时狼不会攻击羊。

二、输入描述

第一行输入为M，N，X，分别代表羊的数量，狼的数量，小船的容量。

三、输出描述

输出不损失羊情况下将全部羊和狼运到对岸需要的最小次数（若无法满足条件则输出0）。

四、测试用例

1、输入

10 8 4

2、输出

3、说明

第一次运2只羊，1只狼，本岸8只羊，7只狼，，对岸2只羊，1只狼；
第二次运2只羊，2只狼，本岸6只羊，5只狼，，对岸4只羊，3只狼；
第三次运2只羊，2只狼，本岸4只羊，3只狼，，对岸6只羊，5只狼；
第四次运2只羊，2只狼，本岸2只羊，1只狼，，对岸8只羊，7只狼；
第五次运2只羊，1只狼，本岸0只羊，0只狼，，对岸10只羊，8只狼；

五、解题思路

羊的数量大于狼的数量，狼才不会吃羊。

只有羊 - 狼大于 2时，才能保证两岸的羊同时大于狼。

当船的容量是偶数，又要保证两岸的羊同时大于狼。

比如小船的容量是4，考虑最快运输问题

第一次运输尽可能先运3只羊+1只狼（保证船的满载、保证对岸的羊大于狼，此时还必须保证本岸剩余的羊大于狼）；
如果本岸剩余的羊不大于狼，则运输半船羊，半船-1只狼，首次少运一只，属于特例；
第二次，对半运输即可；
当狼不足半船时，将狼全部运完，其它的运羊；
当没有狼时，只运羊。

当船的容量是奇数，又要保证两岸的羊同时大于狼。

为了尽量保持对岸的羊等于狼（不被吃掉），尽量保证满载，单数运X/2+1只羊和X/2只狼，双数运X/2只羊和X/2+1只狼。

第一次运输，因为小船的容量是奇数，又要保证两岸的羊同时大于狼（比如小船的容量是5，考虑最快运输问题，尽可能的满载，因此运3只羊，2只狼即可）；
如果本岸羊比狼多出两只及以上，则可以先运X/2+1只羊、X/2只狼；
如果本岸羊只比狼多一只，则不能奇偶运输了，运输相同只羊和狼；
当狼不足半船时，将狼全部运完，其它的运羊；
当没有狼时，只运羊。

六、Python算法源码

# 导入相关库
from collections import Counter

# 模拟运输过程的主函数
def main():
    # 读取输入
    input_data = input()
    input_values = list(map(int, input_data.split(" ")))

    # 获取船的容量
    ship_capacity = input_values[2]

    # 模拟转移记录
    shift_log = simulate_shift(input_values[0], input_values[1])
    print("初始转移记录：", shift_log)

    # 计算有效运输次数
    transport_count = perform_transport(shift_log, ship_capacity)
    print("总共有效运输次数：", transport_count)

# 模拟转移过程
def simulate_shift(initial_ghost_count, initial_wolf_count):
    shift_log = []
    while initial_ghost_count + initial_wolf_count > 0:
        if initial_ghost_count - initial_wolf_count > 1:
            animal = "羊"
        elif initial_wolf_count > 0:
            animal = "狼"
        else:
            animal = "羊"
        shift_log.append(animal)

        # 更新羊和狼的数量
        if animal == "狼":
            initial_wolf_count -= 1
        else:
            initial_ghost_count -= 1
    
    return shift_log

# 执行运输的逻辑
def perform_transport(shift_log, ship_capacity):
    animal_count = {"羊": 0, "狼": 0}

    transport_count = 0
    left_index = 0
    right_index = ship_capacity

    while left_index < len(shift_log):
        once_count = min(right_index - left_index, len(shift_log) - left_index)
        counts = Counter(shift_log[left_index:left_index + once_count])
        ghost_count = counts.get("羊", 0)
        wolf_count = counts.get("狼", 0)

        if animal_count["羊"] + ghost_count > animal_count["狼"] + wolf_count:
            transport_count += 1
            animal_count["羊"] += ghost_count
            animal_count["狼"] += wolf_count
            left_index += once_count
            right_index += ship_capacity
            print(f"第{transport_count}次有效运输，运输的羊和狼数量：{ghost_count}:{wolf_count}")
        else:
            right_index -= 1
            if right_index == left_index:
                print("无有效运输")
                transport_count = 0
    
    return transport_count

# 启动主函数
if __name__ == "__main__":
    main()

七、JavaScript算法源码

// 模拟运输过程的主函数
function main() {
    // 读取输入
    const input = prompt();
    const inputValues = input.split(" ").map(Number);

    // 获取船的容量
    const shipCapacity = inputValues[2];

    // 模拟转移记录
    const shiftLog = simulateShift(inputValues[0], inputValues[1]);
    console.log("初始转移记录：", shiftLog);

    // 计算有效运输次数
    const transportCount = performTransport(shiftLog, shipCapacity);
    console.log("总共有效运输次数：", transportCount);
}

// 模拟转移过程
function simulateShift(initialGhostCount, initialWolfCount) {
    let shiftLog = [];
    while (initialGhostCount + initialWolfCount > 0) {
        let animal;
        if (initialGhostCount - initialWolfCount > 1) {
            animal = "羊";
        } else if (initialWolfCount > 0) {
            animal = "狼";
        } else {
            animal = "羊";
        }
        shiftLog.push(animal);

        // 更新羊和狼的数量
        if (animal === "狼") {
            initialWolfCount--;
        } else {
            initialGhostCount--;
        }
    }
    return shiftLog;
}

// 执行运输的逻辑
function performTransport(shiftLog, shipCapacity) {
    const animalCount = { "羊": 0, "狼": 0 };
    let transportCount = 0;
    let leftIndex = 0;
    let rightIndex = shipCapacity;

    while (leftIndex < shiftLog.length) {
        const onceCount = Math.min(rightIndex - leftIndex, shiftLog.length - leftIndex);
        const counts = shiftLog.slice(leftIndex, leftIndex + onceCount).reduce((acc, animal) => {
            acc[animal] = (acc[animal] || 0) + 1;
            return acc;
        }, {});
        const ghostCount = counts["羊"] || 0;
        const wolfCount = counts["狼"] || 0;

        if (animalCount["羊"] + ghostCount > animalCount["狼"] + wolfCount) {
            transportCount++;
            animalCount["羊"] += ghostCount;
            animalCount["狼"] += wolfCount;
            leftIndex += onceCount;
            rightIndex += shipCapacity;
            console.log(`第${transportCount}次有效运输，运输的羊和狼数量：${ghostCount}:${wolfCount}`);
        } else {
            rightIndex--;
            if (rightIndex === leftIndex) {
                console.log("无有效运输");
                transportCount = 0;
            }
        }
    }

    return transportCount;
}

// 启动主函数
main();

八、C算法源码

#include <stdio.h>
#include <string.h>

void simulateShift(int initialGhostCount, int initialWolfCount) {
    while (initialGhostCount + initialWolfCount > 0) {
        if (initialGhostCount - initialWolfCount > 1) {
            printf("羊 ");
        } else if (initialWolfCount > 0) {
            printf("狼 ");
        } else {
            printf("羊 ");
        }

        if (initialWolfCount > 0) {
            initialWolfCount--;
        } else {
            initialGhostCount--;
        }
    }
}

int performTransport(char shiftLog[], int shipCapacity) {
    int transportCount = 0;
    int leftIndex = 0;
    int rightIndex = shipCapacity;

    while (leftIndex < strlen(shiftLog)) {
        int onceCount = (rightIndex - leftIndex < strlen(shiftLog) - leftIndex) ? (rightIndex - leftIndex) : (strlen(shiftLog) - leftIndex);
        int ghostCount = 0;
        int wolfCount = 0;

        for (int i = leftIndex; i < leftIndex + onceCount; i++) {
            if (shiftLog[i] == '羊') ghostCount++;
            if (shiftLog[i] == '狼') wolfCount++;
        }

        if (ghostCount > wolfCount) {
            transportCount++;
            leftIndex += onceCount;
            rightIndex += shipCapacity;
            printf("第%d次有效运输，运输的羊和狼数量：%d:%d\n", transportCount, ghostCount, wolfCount);
        } else {
            rightIndex--;
            if (rightIndex == leftIndex) {
                printf("无有效运输\n");
                transportCount = 0;
            }
        }
    }

    return transportCount;
}

int main() {
    int shipCapacity;
    scanf("%d %d %d", &shipCapacity);
    char shiftLog[100];

    simulateShift(10, 8);
    int transportCount = performTransport(shiftLog, shipCapacity);
    printf("总共有效运输次数：%d\n", transportCount);

    return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

// 模拟转移过程
vector<string> simulateShift(int initialGhostCount, int initialWolfCount) {
    vector<string> shiftLog;
    while (initialGhostCount + initialWolfCount > 0) {
        string animal;
        if (initialGhostCount - initialWolfCount > 1) {
            animal = "羊";
        } else if (initialWolfCount > 0) {
            animal = "狼";
        } else {
            animal = "羊";
        }
        shiftLog.push_back(animal);

        // 更新羊和狼的数量
        if (animal == "狼") {
            initialWolfCount--;
        } else {
            initialGhostCount--;
        }
    }
    return shiftLog;
}

// 执行运输的逻辑
int performTransport(const vector<string>& shiftLog, int shipCapacity) {
    unordered_map<string, int> animalCount = {{"羊", 0}, {"狼", 0}};
    int transportCount = 0;
    int leftIndex = 0;
    int rightIndex = shipCapacity;

    while (leftIndex < shiftLog.size()) {
        int onceCount = min(rightIndex - leftIndex, (int)shiftLog.size() - leftIndex);
        unordered_map<string, int> counts;

        for (int i = leftIndex; i < leftIndex + onceCount; i++) {
            counts[shiftLog[i]]++;
        }

        int ghostCount = counts["羊"];
        int wolfCount = counts["狼"];

        if (animalCount["羊"] + ghostCount > animalCount["狼"] + wolfCount) {
            transportCount++;
            animalCount["羊"] += ghostCount;
            animalCount["狼"] += wolfCount;
            leftIndex += onceCount;
            rightIndex += shipCapacity;
            cout << "第" << transportCount << "次有效运输，运输的羊和狼数量：" << ghostCount << ":" << wolfCount << endl;
        } else {
            rightIndex--;
            if (rightIndex == leftIndex) {
                cout << "无有效运输" << endl;
                transportCount = 0;
            }
        }
    }

    return transportCount;
}

int main() {
    int shipCapacity;
    cin >> shipCapacity;
    vector<string> shiftLog = simulateShift(10, 8);
    int transportCount = performTransport(shiftLog, shipCapacity);
    cout << "总共有效运输次数：" << transportCount << endl;
    return 0;
}