课后作业

第二十七课

小明在某一天中依次有七个空闲时间段，他想要选出至少两个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息，则小明一共有多少种选择时间段的方案？

• ❌

• 历史解析

  • 组合数使用公式 C(n, m) = n! / (m! * (n - m)!) 计算，其中 n! 表示 n 的阶乘，很明显你的计算方式是错误的
  • 就此题而言，使用组合数求解不应是C(4,2)，而应该是C(5,2) + C(3,3)，即从 5 个时间段中选 2 个时间段，再从 3 个时间段中选 3 个时间段
  • 我们有7个空闲时间段，选择 k 个时间段来练习唱歌，并且每2个练习时间段之间必须至少有2个空闲时间段
  • 为了满足每两个练习时间段之间至少有两个空闲时间段的要求，我们可以转换为一个组合问题来求解
  • 为了使问题简化，我们把每个练习时间段及其后的两个空闲时间段看作一个“单位块”
  • 例如，选择1个练习时间段，那么这个时间段会占用1个位置，且在它之后有2个空闲时间段，这样每个“单位块”实际上占用了3个时间段
  • 选了k个练习时间段，这些时间段占用了3k个时间段
  • 但是，我们需要注意最后一个练习时间段后面不需要2个空闲时间段，所以实际上总消耗的时间段数为3k-2（即最右边的2个空闲时间段不计入）
  • 那么，剩余时间段数便为7-(3k-2)=7-3k+2=9-3k
  • 例如，如果我们选择了2个练习时间段，这2个练习时间段之间必须有2个空闲时间段，因此实际消耗的时间段数为3*2-2=4，剩余时间段数为9-3*2=3，因此我们是排列2 + 3个时间段,即5个时间段中选2个时间段排列组合，即C(5,2)
  • 如果我们选择了3个练习时间段，这3个练习时间段之间必须有2个空闲时间段，因此实际消耗的时间段数为3*3-2=7，剩余时间段数为9-3*3=0，因此我们是排列3 + 0个时间段,即3个时间段中选3个时间段排列组合，即C(3,3)
  • 对于我们的练习来说，一共只存在两种情况，即选择了2个练习时间段和选择了3个练习时间段，所以总的方案数为C(5,2) + C(3,3)

• 参考答案

#include <iostream>
using namespace std;

// 计算阶乘
int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}

// 计算组合数C(n, k)
int combination(int n, int k) {
    if (k > n) {
        return 0;
    }
    return factorial(n) / (factorial(k) * factorial(n - k));
}

// 计算组合总数
int total(int n, int k){
    return n-(3*k-2)+k;
}

int main() {
    int n = 7;
    int ways= 0;
    int k1 = 2;
    int k2 = 3;
    
    ways += combination(total(n,k1), k1);
    ways += combination(total(n,k2), k2);

    cout << "选择时段的总方法数为: " << ways << endl;
    return 0;
}