第6章 数学和逻辑--2

10000 以内被 2 整除的数有 5000 个

10000 以内被 5 整除的数有 2000 个

两者存在重复计算的数，即被 10 整除的数，有 1000 个。

被 2 或 5 整除的数有：5000 +2000 – 1000 =6000

互质的数有：10000 - 6000 ＝ 4000 个

2、鸽巢原理/抽屉原理

桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有

一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。

抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元

素，假如有 n+1 个元素放到 n 个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉

原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。

抽屉原理的另一个表达：如果有 n 个集合和 kn+1 个元素，将元素放入集合中之后，至

少有 1 个集合中有 k+1 个元素。

运用抽屉原理的核心是分析清楚问题中，哪个是物件，哪个是抽屉。

例子：属相是有 12 个，那么任意 37 个人中，一个属相至少不少于多少个人。

答案：4 人。

分析：这时将属相看成 12 个抽屉，则一个抽屉中有 37/12，即 3 余 1，余数不考虑，而向

上考虑取整数，所以这里是 3+1=4 个人，但这里需要注意的是，前面的余数 1 和这里加上的

1 是不一样的。（思考 38 个人的情况）

【NOIP2019 普及组】12.一副纸牌除掉大小王有 52 张牌，四种花色，每种花色 13 张。假设

从这 52 张牌中随机抽取 13 张纸牌,则至少（ ）张牌的花色一致。

A.4 B.2 C.3 D.5

答案：A

解析：抽屉原理，最坏情况,13 张牌对应四种花色的牌数为 3、3、3、4。抽屉存储：黑桃黑

桃黑桃，抽屉 2：红桃红桃红桃，抽屉 3：梅花梅花梅花，抽屉 4：方片方片方片 这时再抽

一张，不管放在哪，都能满足要求。

6.3 逻辑

1.今天是星期日，那么 100 天以后是星期几？

解析：

本题是周期性问题求解，每周有 7 天；

那么 100 天除去完整的 7 天周期以外，剩余填数 = 100 % 7 = 2（14 个完整周期剩余

2 天）；

因此 100 天以后是星期几，相当于 2 天之后是星期几，答案是星期二。

2、今天是星期日，那么 10¹⁰⁰天以后是星期几？

解析：

我们并不急于求出 10¹⁰⁰,而是像 1,10,100,100,10000…这样,依次增加 0 的个数, 观察

其规律。

0 的个数

0 1 天以后的星期数 1÷7=0 余 1 -> 一

1 10 天以后的星期数 10÷7=1 余 3 -> 三

2 100 天以后的星期数 100÷7=14 余 2 -> 二

3 1000 天以后的星期数 1000÷7=142 余 6 -> 六

4 10000 天以后的星期数 10000÷7=1428 余 4 -> 四

5 100000 天以后的星期数 100000÷7=14285 余 5 -> 五

6 1000000 天以后的星期数 1000000÷7=142857 余 1 -> 一

7 10000000 天以后的星期数 10000000÷7=1428571 余 3 -> 三

8 100000000 天以后的星期数 100000000÷7=14285714 余 2 -> 二

9 1000000000 天以后的星期数 1000000000÷7=142857142 余 6 -> 六

10 10000000000 天以后的星期数 10000000000÷7=1428571428 余 4 -> 四

11 100000000000 天以后的星期数 100000000000÷7=14285714285 余 5-> 五

12 1000000000000 天以后的星期数 1000000000000÷7=142857142857 余 1->一

因此 10¹⁰⁰以后的星期数，可以将天数中的 0 的个数（10

¹⁰⁰有 100 个 0）除以 6，通过所

得余数来判断。

100 ÷ 6 = 16余4

因此，10

¹⁰⁰天以后是星期四。

3. 2017 年 10 月 1 日是星期日，1999 年 10 月 1 日是（ ）。

A. 星期三 B. 星期日 C. 星期五 D. 星期二

解析：

闰年：一年 366 天，非闰年：一年 365 天。

判断标准：四年一闰,百年不闰,四百年再闰（n%4==0&&n%100!=0 ||n % 400 == 0）

意思是：不是整百的年份只要被 4 整除的就是闰年,整百的年份必须得被 400 整除才是

闰年

1999 年~2016 年中的闰年有：2000、2004、2008、2012、2016，5 个闰年。

也就是说 1999 年 10 月 1 日~2017 年 10 月 1 日总天数 = 18 年，总天数 = 18 * 365 +

5 = 6575 天。6575/7 结果为 939 周余 2 天。

说明：1999 年 10 月 1 日为周五。

4.一个人站在坐标（0, 0）处，面朝 x 轴正方向。第一轮，他向前走 1 单位距离，然

后右转；第二轮，他向前走 2 单位距离，然后右转；第三轮，他向前走 3 单位距离，然后

右转……他一直这么走下去。请问第 2017 轮后，他的坐标是：（_________，_________）。

（请在答题纸上用逗号隔开两空答案）

1+2*3+(4*5+6)*7 转换为前缀表达式，结果是：  + + 1 * 2 3 * + * 4 5 6 7

2、后缀表达式

后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后；比如：

3 4 + 5 × 6 -

A、后缀表达式计算机求值

与前缀表达式类似，只是顺序是从左至右：

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个

数，用运算符对它们做相应的计算（次顶元素 和 top 栈顶元素），并将结果入栈；重复上

述过程直到表达式最右端，最后运算得出的值即为表达式的结果

例如后缀表达式“3 4 + 5 × 6 -”。

从左至右扫描，将 3 和 4 压入堆栈；

遇到+运算符，因此弹出 4 和 3（4 为栈顶元素，3 为次顶元素，注意与前缀表达式做比

较），计算出 3+4 的值，得 7，再将 7 入栈；

将 5入栈；

接下来是×运算符，因此弹出 5 和 7，计算出 7×5=35，将 35 入栈；

将 6入栈；

最后是-运算符，计算出 35-6 的值，即 29，由此得出最终结果。

B、将中缀表达式转换为后缀表达式

转换过程需要用到栈，具体过程如下，从左向右扫描表达式：

1）如果遇到操作数，我们就直接将其输出。

2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。

3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。

注意，左括号只弹出并不输出。

4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直

到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压

入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都

不会弹出" ( "。

5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。

例如，中缀表达式 1+((2+3)×4)-5 转换为后缀表达式的结果为： 123+4×+5-

中缀表达式a+b*c+(d*e+f)*g，其转换成后缀表达式则为 abc*+de*f+g*+

6.5 数学和逻辑课堂练习

【NOIP2019 普及组】7.把 8 个同样的球放在 5 个同样的袋子里,允许有的袋子空着不放,问

共有多少种不同的分法?（ ）提示:如果个球都放在一个袋子里,无论是哪个袋子,都只

算同一种分法。

A.22 B.24 C.18 D.20

答案：C

解析：数学计数问题，枚举法求解，8 个同样的球分 1 个袋子共 1 种方案，分 2 个袋子共 4

种方案，分 3 个袋子共 5 种方案，分 4 个袋子共 5 种方案，分 5 个袋子共 3 种方案，合计

18 种。

【NOIP2019 提高组】10.一次期末考试，某班有 15 人数学得满分，有 12 人语文得满分，并

且有 4 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（ ）

A.23 B.21 C.20 D.22

答案：A

解析：容斥原理，总满分人数=数学满分+语文满分-语文数学满分=15+12-4=23。

【NOIP2018 普及组】6. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照

CapsLock、字母键 A、字母键 S、字母键 D、字母键 F 的顺序循环按键，即 CapsLock、A、

S、D、F、CapsLock、a、s、d、f、……，屏幕上输出的第 81 个字符是字母（ ）。

A.A B. S C. D D. a

答案：A

解析：考察字符串相关知识。按键顺序为 ASDFasdfASDFasdf...，周期为 8，所以 81 % 8

= 1，答案是 A。

【NOIP2018 普及组】12.设含有 10 个元素的集合的全部子集数为 S，其中由 7 个元素组成

的子集数为 T，则 T / S 的值为（ ）。

A.5 / 32 B.15 / 128 C.1 / 8 D.21 / 128

答案：B

解析：

解法一：

T =   =   = 120

S =   +   +   + … +   = 1024

T / S = 120 / 1024 = 15 / 128

解法二：

考察排列与组合基础知识。10 个元素的集合的子集数有 2^10=1024 个，由 7 个元素组成

的子集数有 C(10，7)= C(10，3)= 120 种，故答案是 120 / 1024 = 15 / 128。

注意：

n 个元素的子集数：集合的子集可以含集合中的任意元素,甚至可以是空集,所以集合中的每

个元素都可以有选或不选的可能.每个元素都有两个选择.含有 n 种元素的集合中,子集是

2*2*……*2 即 2 的 n 次方个。

【NOIP2017 提高组】9.将 7 个名额分给 4 个不同的班级，允许有的班级没有名额，有( )

种不同的分配方案。

A.60 B.84 C.96 D.120

答案：D

解析：相当于 11 个名额给每个班，每个班不少于 1 个，有隔板法有=120 种