课后作业

第三十六课

本次上传使用 cpp 文件上传，如无过程，上传 cpp 中使用注释阐明思路也可以，或者涉及哪些知识点，也可以写出来

// 你的作业解答

/*下面是根据欧几里得算法编写的函数，它所计算的是 a 和 b 的( )
int euclid(int a,int b){
    if(b==0)
    return a;
    else
    return euclid(b,a %b);
}
A.最大公共素因子
B.最小公共素因子
C.最大公约数
D.最小公倍数
根据欧几里得算法编写的函数计算的是两个数 
a 和 b 的最大公约数。因此，正确答案是：
C. 最大公约数

10000以内，与10000互质的正整数有( )个
A.2000
B.4000
C.6000
D.8000
10000以内与10000互质的正整数有4000个。
正确答案是：
B. 4000
/**
要计算从1到2018中包含数字8的数，我们可以逐个检查每个数字，或者使用更系统的方法来统计。

1.从1到2018的范围：我们需要检查每个数字是否包含数字8。
2. 分段统计：
   - 从1到999
   - 从1000到1999
   - 从2000到2018

1. 从1到999
我们可以通过遍历1到999的每个数字，检查其是否包含数字8。

2. 从1000到1999
在这个范围内，所有数字的千位都是1，因此只需检查后面的三位数字（000到999）是否包含8。

3. 从2000到2018
在这个范围内，只有2000到2018的数字需要检查。

统计结果
从1到999：包含8的数字有：8, 18, 28, 38, 48, 58, 68, 78, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 98，总共有80个。
从1000到1999：后面三位数字中包含8的数字有：108, 118, 128, 138, 148, 158, 168, 178, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 198，总共有**280个**。
从2000到2018：只有2008包含8。

总计
将所有范围的结果相加：
- 从1到999：80个
- 从1000到1999：280个
- 从2000到2018：1个

总共包含数字8的数为：
80 + 280 + 1 = 361

因此，从1到2018这2018个数中，共有361个包含数字8的数。
**/
/**
1. 7个不同的球放到6个不同的盒子中，要求每个盒子至少放一个球的数量

为了计算7个不同的球分配到6个不同的盒子中，每个盒子至少放一个球，可以使用包含排除法。

1. 总的分配方式：首先，计算不限制条件下的分配方式。7个球可以放到6个盒子中，总方式为 \(6^7\)。
2. 至少有一个盒子为空：然后使用包含排除法，计算至少一个盒子为空的情况。使用包含排除法公式：
   N = \sum_{k=0}^{6} (-1)^k \binom{6}{k} (6-k)^7
   具体步骤为：
   (N = 6^7 - \binom{6}{1} 5^7 + \binom{6}{2} 4^7 - \binom{6}{3} 3^7 + \binom{6}{4} 2^7 - \binom{6}{5} 1^7\)

计算结果为：
(N = 279936 - 6 \times 78125 + 15 \times 16384 - 20 \times 2187 + 15 \times 128 - 6 \times 1\)
(= 279936 - 468750 + 245760 - 43740 + 1920 - 6\)
(= 279936 - 468750 + 245760 - 43740 + 1920 - 6 = 20736\)

所以，7个不同的球放到6个不同的盒子中，保证每个盒子至少放一个球的放法数量为20736种。

---

2. 某人射击8枪，命中4枪，恰好有三枪连续命中，有多少种不同的情况？

为了求解这个问题，我们可以将连续的三枪看作一个整体。这样我们可以将这个整体视为一个单独的命中事件，剩下的枪也要命中。

1. 考虑三个连续命中组成的整体：“命中命中命中”可以用一个单元表示，比如C，我们可以表示为C、H（未命中）。
2. 情景组合：将这个整体(C)和另外1枪命中的情况(H)总共需要放到8个位置中，这样我们有：

   - 总体为C、H、H、H、H（记为1个C和4个H）。

3. 排列方式：我们需要计算C与其余4个H的排列方式：
frac{5!}{1! \cdot 4!} = 5
4. 处理剩余的命中：其中C的具体排列有4种(可以命中第一次、第二次、第三次)；
5. 计算命中的组合：因此需要计算从4个命中中选择出3个位置的组合(剩下的枪未命中)：
\binom{5}{1} = 5
所以这部分总数量为 \(4 \cdot 5 = 20\)
因此，某人射击8枪，命中4枪，恰好有三枪连续命中的情况共有320种。
---
3. 有7个一模一样的苹果，放到3个一样的盘子中，一共有多少种放法？

在这种问题中可以使用星和条的方法（Stars and Bars）。

求解公式为：
设 (x_1, x_2, x_3) 分别是盘子1、2、3中苹果的数量。
需要解方程 (x_1 + x_2 + x_3 = 7)，且 (x_1, x_2, x_3 \g)。

根据星和条的定理，我们有：
binom{n+k-1}{k-1} = \binom{7+3-1}{3-1} = \binom{9}{2} = 36
因此，有7个一模一样的苹果放到3个一样的盘子中的放法总共有36种。

1. 下面是根据欧几里得算法编写的函数，它所计算的是 a 和 b 的( )

int euclid(int a,int b){
    if(b==0)
    return a;
    else
    return euclid(b,a %b);
}

• A.最大公共素因子
• B.最小公共素因子
• C.最大公约数
• D.最小公倍数

• ✅
• 历史解析:
  • 正确答案：C.最大公约数
  • 根据欧几里得算法编写的函数计算的是两个数 a 和 b 的最大公约数。因此，正确答案是：C.最大公约数

2. 10000以内，与10000互质的正整数有( )个

• A.2000
• B.4000
• C.6000
• D.8000

• ✅
• 历史解析:
  • 正确答案：B.4000
  • 互质的意思，与10000没有公约数，也即不能被10000的质因子整除
  • 10000分解质因子：10000 =2*2*2*2*5*5*5*5
  • 10000的质因子为2, 5，所以10000以内与10000互质的正整数不能包含2, 5这两个质因子
  • 由于10000以内的正整数中，有5000个偶数（能被2整除），2000个能被5整除的数，1000个能被10整除的数((2*5)=10这部分是重复计算的)
  • 所以10000以内与10000互质的正整数有10000 - 5000 - 2000 + 1000 = 4000个

3. 从1到2018这2018个数中，共有____个包含数字8的数

• ❌
• 历史解析:
  • 正确答案：544
  • 从1到2018这2018个数中，共有544个包含数字8的数
  • 我们使用分段统计的方法来计算：
  • 1. 从1到9：包含8的数字有1个
  • 2. 从10到99：1*8+10=18 包含8的数字有18个
  • 3. 从100到999：(1+18)*8+100=252 包含8的数字有252个
  • 4. 从1000到1999：1+18+252=271 包含8的数字有271个
  • 5. 从2000到2018： 包含8的数字有2个
  • 所以，从1到2018这2018个数中，共有1+18+252+271+2=544个包含数字8的数

公式解释

1. 从10到99：1*8 + 10 = 18

   • 这里的1*8表示 个位上的8：

     • 在10到99之间，个位上有可能是8的数字有：18, 28, 38,..., 98，每个十位上有且只有1个包含8的数，因此有1 * 8 = 8个数。

   • + 10表示 十位上的8：

     • 在10到99之间，十位上是8的数为：80, 81, 82,..., 89，共有10个数。

   所以，这个公式的含义是：个位上有8的数字有8个，十位上有8的数字有10个，因此总共有18个包含数字8的数字。

2. 从100到999：(1 + 18) * 8 + 100 = 252

   • 1 + 18表示前一段统计的结果，即从1到99的总数，这个部分用来计算在三位数中的重复情况。

   • * 8表示 个位和十位的组合情况：

     • 在100到999之间，个位和十位上都可能是8，这类组合的个数与前面的位数相关，所以乘以8。

   • + 100表示 百位上是8的情况：

     • 在100到999之间，百位上是8的数为：800到899，共有100个。

   这个公式的含义是：通过考虑个位、十位和百位上的可能性，总结得出共有252个包含数字8的三位数。

3. 从1000到1999：1 + 18 + 252 = 271

   • 1表示从1到9的统计结果（包含8的个数）。
   • + 18表示从10到99的统计结果。
   • + 252表示从100到999的统计结果。

   这个公式总结了之前的计算结果，并表明从1000到1999与前面统计的三位数情况一致，所以总共有271个包含8的数。

4. 7个不同的球放到6个不同的盒子中，要求每个盒子至少放一个球，一共有多少种方法?

• ❌
• 历史解析:
  • 这道题涉及将7个不同的球放入6个不同的盒子中，要求每个盒子至少放一个球。由于盒子的数量少于球的数量，因此至少有一个盒子需要放入2个球，而其余盒子每个放1个球。
  • 我们可以按以下步骤解题：
  • 1. 选出放2个球的盒子
  • 为了保证每个盒子至少有一个球，必须有一个盒子放入2个球。我们从7个不同的球中挑选出2个球，这2个球将被放入同一个盒子
  • 选出2个球的方式是从7个球中选2个，计算方式为组合：

    $C(7, 2) = \frac{7 \times 6}{2} = 21$

    即有21种不同的方式选择2个球放入一个盒子。
  • 2. 剩余球放入剩余盒子
  • 将2个球放入一个盒子后，剩下的5个球需要放入剩余的5个盒子中，每个盒子放1个球。这是一个排列问题，因为球和盒子都是不同的。
  • 我们也可以看作2个球为一个整体，这个整体和5个球一共有6个球，放入6个盒子中，每个盒子至少放1个球。这是一个排列问题。
  • 把6个球分别放入6个不同盒子的排列数为：

    $P(6, 6) = 6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$

    即有720种排列方式。
  • 3. 总方法数
  • 根据乘法原理，第一步和第二步的选择是相互独立的，因此总的放置方法数为：

    $C(7, 2) \times P(6, 6) = 21 \times 720 = 15120$

  • 因此，将7个不同的球放入6个不同的盒子中，要求每个盒子至少放1个球的放置方法总数是15120种

5. 某人射击8枪，命中4枪，恰好有三枪连续命中，有多少种不同的情况?

• ❌
• 历史解析:
  • 因为连续命中的三枪与单独命中的一枪不能相邻，因而这是一个插空问题。另外没有命中的之间没有区别，不必计数。即在四发空枪之间形成的5个空中选出2个的排列，即P(5,2)
  • 这道题是一个典型的插空问题,我们可以通过以下步骤详细分析：
  • 问题分析：
    1. 连续命中的三枪：这三枪视为一个整体（即一个“块”），可以认为这是一个单独的“命中块”。
    2. 单独命中的一枪：这一枪必须与这三枪连续命中的块分开，不能相邻。
    3. 空枪之间的空隙：剩下的4枪未命中，考虑到这4枪间有5个可以插入的空位（包括开头和结尾的位置）。
  • 因此，问题转化为在5个空位中选出2个位置，一个位置放置连续命中的三枪，另一个位置放置单独命中的一枪。由于命中与未命中的位置可以确定，没有命中的枪没有区别，直接选择即可。
  • 即，总的方法数为：P(5, 2) = 20，也可以分步计算：
  • 详细步骤：
    1. 确定命中块的位置：
       • 将4发未命中的枪摆放好之后，有5个空位可以插入三枪连续命中的块。因此，可以从这5个空位中选择一个位置放置三枪连续命中的块。
       • 选择的方法数为：

       $P(5, 1) = 5$

    2. 确定单独命中的一枪的位置：
       • 三枪连续命中的块占用一个位置后，剩下4个空位可以插入单独命中的一枪。
       • 因此，在剩余的4个空位中选择一个位置放置单独命中的一枪。
       • 选择的方法数为：

       $P(4, 1) = 4$

    3. 总排列方式：
       • 最终排列方式为连续命中的三枪与单独命中的一枪的排列乘积：

       $5 \times 4 = 20$

6. 有7个一模一样的苹果，放到3个一样的盘子中，一共有多少种放法？

• ❌
• 历史解析:
  • 这道题可以用插空法来解决，要求将 7 个相同的苹果分配到 3 个相同的盘子中，问一共有多少种分法。下面是详细解题步骤：
  • 1. 问题分析
  • 首先，这是一道组合问题，由于苹果和盘子都是相同的，分法只与苹果分配的数量有关，而与苹果或盘子本身无关。因此我们考虑将 7 个苹果划分成 3 组，每组表示某一个盘子里的苹果数量。
  • 2. 插空法思路
  • 插空法是解决这类问题的常见方法之一。基本思想是将 7 个苹果排成一行，然后在苹果之间的“空隙”中插入分隔符，分隔符将这些苹果划分成若干部分。具体步骤如下：
    • 1. 插入分隔符 我们有 7 个苹果，要分成 3组。苹果排成一排后，在 7个苹果之间有 6 个空隙，我们需要插入 2 个分隔符将苹果分隔成 3 组。
    • 2. 分类讨论 我们要分类讨论如何插入分隔符的不同情况来进行排列。
         第一类：有 2 个盘子为空
         如果有 2 个盘子是空的，则剩下 1 个盘子必须放 7 个苹果。这种情况下的放法只有 1 种。 第二类：有 1 个盘子为空
         当有 1 个盘子为空时，意味着剩下 2 个盘子要分配 7 个苹果。我们需要在 7 个苹果之间插入 1 个分隔符，这样分隔符两边的苹果数分别代表两个盘子的苹果数量。此时有以下可能：
      • 两边分别放 1 和 6 个苹果（共 2 种情况）。
      • 两边分别放 2 和 5 个苹果（共 2 种情况）。
      • 两边分别放 3 和 4 个苹果（共 1 种情况）。 这种情况下共有 $2 + 2 + 1 = 5$ 种分法。 第三类：每个盘子都有苹果 如果 3 个盘子里都必须有苹果，那么每个盘子至少有 1 个苹果。我们可以先给每个盘子分配 1 个苹果，剩下的 $7 - 3 = 4$ 个苹果就可以随意分配到 3 个盘子中。这相当于我们要在 4 个苹果之间插入 2 个分隔符。此时有以下可能：
      • 三个盘子分别放 1、1、2 个苹果（共 1 种情况）。
      • 三个盘子分别放 1、2、1 个苹果（共 2 种情况）。
      • 三个盘子分别放 2、1、1 个苹果（共 1 种情况）。 这种情况下共有 $1 + 2 + 1 = 4$ 种分法。
  • 3. 将三种情况加总，得到总的分法数量：
    • 2 个盘子为空：1 种
    • 1 个盘子为空：5 种
    • 没有空盘：4 种
  • 因此，总共有 $1 + 5 + 4 = 8$ 种分法