跳转至

省钱租船大冒险：用C++成为节省高手！

嘿，小朋友们！今天我们要成为一个节省高手，学习如何用C++编程语言帮助我们以最省钱的方式租船去冒险！想象一下，夏日的阳光，清凉的河水，和你的朋友们一起在河上划船，多么美好啊！但是，我们有一个问题需要解决：我们怎样才能用最少的钱租到足够的船呢？让我们一步步来探索吧！

第一步：认识我们的船

在我们的冒险中，我们有两种船可以选择：

  • 小船：可以载4个人，租一小时要24元。
  • 大船：可以载6个人，租一小时要30元。

现在，假设我们有32个朋友要一起去玩，我们该怎么选择船呢？

第二步：试试看，用枚举法

首先，我们来做一个简单的尝试，这叫做“枚举法”。就像你在玩积木时，尝试各种组合看哪个最好一样，我们也来试试所有的船的组合，找出最省钱的那个！

用C++来实现枚举法的代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;

int main() {
    cout << "用枚举法找最省钱的租船方案！" << endl;

    const int smallBoatCostPerHour = 24, smallBoatCapacity = 4;
    const int bigBoatCostPerHour = 30, bigBoatCapacity = 6;
    const int totalPeople = 32;
    int minTotalCost = INT_MAX;

    for (int smallBoats = 0; smallBoats * smallBoatCapacity <= totalPeople; smallBoats++) {
        for (int bigBoats = 0; bigBoats * bigBoatCapacity + smallBoats * smallBoatCapacity <= totalPeople; bigBoats++) {
            if (bigBoats * bigBoatCapacity + smallBoats * smallBoatCapacity >= totalPeople) {
                int totalCost = smallBoats * smallBoatCostPerHour + bigBoats * bigBoatCostPerHour;
                if (totalCost < minTotalCost) {
                    minTotalCost = totalCost;
                }
            }
        }
    }

    cout << "最省钱的租船方案需要的总费用是：" << minTotalCost << "元。" << endl;

    return 0;
}

第三步：更聪明一点，用动态规划

当你对枚举法感到轻车熟路后，我们来学习一个更聪明的方法，叫做“动态规划”。动态规划听起来很高大上，但其实就是一个“记住你已经解决过的问题，不再重复解决”的聪明办法。

用C++实现动态规划的代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

int main() {
    cout << "用动态规划找最省钱的租船方案！" << endl;

    const int smallBoatCostPerHour = 24;
    const int smallBoatCapacity = 4;
    const int bigBoatCostPerHour = 30;
    const int bigBoatCapacity = 6;
    const int totalPeople = 32;

    // 初始化动态规划数组，所有值设为最大整数
    vector<int> dp(totalPeople + 1, INT_MAX);
    dp[0] = 0; // 不需要船时的费用为0

    // 对每个人数进行动态规划
    for (int i = 1; i <= totalPeople; i++) {
        // 尝试使用一艘小船
        if (i - smallBoatCapacity >= 0 && dp[i - smallBoatCapacity] != INT_MAX) {
            dp[i] = min(dp[i], dp[i - smallBoatCapacity] + smallBoatCostPerHour);
        }
        // 尝试使用一艘大船
        if (i - bigBoatCapacity >= 0 && dp[i - bigBoatCapacity] != INT_MAX) {
            dp[i] = min(dp[i], dp[i - bigBoatCapacity] + bigBoatCostPerHour);
        }
    }

    cout << "最省钱的租船方案需要的总费用是：" << dp[totalPeople] << "元。" << endl;

    return 0;
}

第四步：尝试其他方法，变得更强

掌握了枚举法和动态规划后，你已经是一个小小的节省高手了！但是，每次学习新技能都能让我们变得更强。你可以尝试写出其他的方法，比如“贪心算法”，它会帮你在特定情况下快速找到不错的解决方案。

用C++实现贪心算法的代码

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;

int main() {
    cout << "使用贪心算法找最省钱的租船方案！" << endl;

    const int totalPeople = 32;
    const int smallBoatCostPerHour = 24, smallBoatCapacity = 4;
    const int bigBoatCostPerHour = 30, bigBoatCapacity = 6;

    // 计算仅使用大船时的可能性
    int bigBoatsNeeded = totalPeople / bigBoatCapacity;
    int remainingPeople = totalPeople % bigBoatCapacity;
    int smallBoatsNeeded = 0;

    // 如果剩余人数不能完全用一艘大船容纳，考虑用小船
    if (remainingPeople > 0) {
        // 检查是否仅添加一艘小船就足够
        if (remainingPeople <= smallBoatCapacity) {
            smallBoatsNeeded = 1;
            //检查是否有空座位 
            if ((remainingPeople + bigBoatCapacity) % smallBoatCapacity == 0){
                smallBoatsNeeded++;
                bigBoatsNeeded--;               
            }
        } else {
            // 否则，尝试添加更多大船以减少小船的需要
            smallBoatsNeeded = (remainingPeople + bigBoatCapacity - 1) / bigBoatCapacity;
        }
    }

    // 计算总成本
    int totalCost = bigBoatsNeeded * bigBoatCostPerHour + smallBoatsNeeded * smallBoatCostPerHour;

    cout << "贪心算法计算结果：总费用为" << totalCost << "元。" << endl;
    cout << "使用大船数量：" << bigBoatsNeeded << endl;
    cout << "使用小船数量：" << smallBoatsNeeded << endl;

    return 0;
}

最后一步：和朋友们分享

学会了这些技巧后，不要忘记和你的朋友们分享你的冒险故事和解决问题的方法。也许下次，你们可以一起用编程解决更多有趣的问题呢！

编写这篇文章的目的是让小学生通过一个具体的、与生活相关的问题，逐步学习编程思想和C++编程语言的基础知识。通过逐步增加问题解决方案的复杂度，不仅激发他们的兴趣，也帮助他们理解更高级的编程概念。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用