乐读窝

程序员的数学思维修炼

乐读窝 > 科普学习 > 程序员的数学思维修炼

4.2乘法原理

书籍名:《程序员的数学思维修炼》    作者:周颖



在实际应用中,要将所有情况都列出来,经常要用到乘法原理和加法原理。下面先来看看乘法原理的应用。



4.2.1 行程安排的问题


在日常生活中常常会遇到这样一些问题,就是在做一件事时,要分几步才能完成,而在完成每一步时,又有几种不同的方法。要知道完成这件事一共有多少种方法,就需要用乘法原理来解决。

例如:某公司销售部王经理从重庆到成都参加西南片区的销售会议,之后再到北京参加全国销售会议。其中,他从重庆到成都可以乘长途汽车、火车或飞机,从成都到北京可以乘火车或飞机。那么,王经理从重庆经成都到北京共有多少种不同的走法?

分析这个问题发现,王经理从重庆到北京要分两步走,第一步是从重庆到成都,可以有3种走法,即:

第二步是从成都到北京,有两种走法,即:

所以,王经理从重庆经成都到北京共有下面的6种走法:

在上面讨论问题的过程中,我把所有可能的办法一一列举出来,这种方法叫穷举法。穷举法对于讨论方法数不太多的问题是很有效的,但是如果每一步中的方法数很多时,需要重复列出很多项目,费时费力,还容易出错。例如,在上例中,如果从重庆到成都有10种(或20种走法),从成都到北京又有10种(或更多)的走法,要将每种走法列举出来,将是比较繁琐的事。



4.2.2 乘法原理适用条件


为了解决穷举法比较繁琐的这个问题,可以对上例的行程问题做一番总结,从中提出相应的规律,以方便解决类似问题。

上面的例子中,完成一件事要分两个步骤,由穷举法得到的结论可看出,用第1步所有的可能方法数乘以第2步所有的可能方法数,就是完成这件事的总方法数。

一般地,如果完成一件事需要n个步骤,其中,做第1步有M1种不同的方法,做第2步有M2种不同的方法,做第3步有M3种不同的方法……,做第n步有Mn种不同的方法,那么,完成这件事一共有N种方法,由各步的方法数相乘而得到。

这就是乘法原理。

哪些情况下适用乘法原理?

乘法原理的核心就是分步:每步都只完成其中的一部分,只有每一步都完成了这件事才算完成。分步计数时应注意步与步之间的连续性和独立性,以确保在计数时不遗漏不重复。

因此分步完成的任务可适用乘法原理,有些问题可能需要仔细分解一下才能化解为分步完成的结构。



4.2.3 棋盘上棋子的放法


再来看一个例子。如图4-5所示是一个4×4方格的棋盘,要在该棋盘中放4枚棋子,使每行每列只能出现一个棋子,问:共有多少种不同的放法(图4-5是其中一种放置棋子的方法)?

图4-5

由于4枚棋子要一个一个地放入棋盘的方格内,因此可看成是分4步解决这个问题。

(1)放置第1枚棋子。此时由于16个棋盘方格都没有棋子,因此,这枚棋子可放在任意一个方格中,有16种不同的放法,如图4-6所示。

图4-6

(2)放置第2枚棋子。由于棋盘中已经放置了1枚棋子,放第1枚棋子那一行和一列中的其他方格内也不能放第2枚棋子,因此还剩下9个方格可以放第2枚棋子,即第2枚棋子有9种放法,如图4-7所示。

图4-7

(3)放置第3枚棋子。这时需去掉第1、2枚棋子所在的行和列的方格,还剩下4个方格可以放置第3枚棋子,则第3枚棋子有4种放法,如图4-8所示。

图4-8

(4)放第4枚棋子。由于要去掉前3枚棋子所在行和列的方格,只剩下1个方格可以放第4枚棋子了,因此第4枚棋子只有1种放法,如图4-9所示。

图4-9

根据上面的分析,用乘法原理即可求出4枚棋子的放置方法数量,共有:

种不同的放法。



4.2.4 买彩票保证中奖的方法


接下来说一个轻松的话题,说说用乘法原理来计算彩票的问题。

目前我国有福利彩票和体育彩票两大类,为国家的福利和体育事业做出了贡献。民众购买彩票为相关事业做出贡献,也有可能中奖改善自己的生活。

作为购买彩票的民众来说,肯定是希望自己能中大奖,那么,该怎么买彩票才能确保中奖呢?

由于彩票中奖号码是由摇奖机随机生成的,没办法猜中,因此,要确保中奖,只有将所有彩票号码全部买完没有遗漏,才可确保中奖!

那么,所有彩票号码共有多少种可能?要花多少钱才能买完?这就需要我们用乘法原理将所有可能都计算出来。

例如,对于体育彩票中的“七星彩”,其游戏规则是:彩票号码长度为7位,每位数字为0~9中的一个。那么,七星彩的彩票号码有多少种可能?

如图4-10所示,绘制7个方框用来填写彩票号码。

图4-10

由于有7个号码,可以认为是分7个步骤来生成彩票号码。

(1)填第1位号码。可以有0~9这10个数字可用,共10种可能。

(2)填第2位号码。可以有0~9这10个数字可用,共10种可能。

(3)填第3位号码。可以有0~9这10个数字可用,共10种可能。

(4)填第4位号码。可以有0~9这10个数字可用,共10种可能。

(5)填第5位号码。可以有0~9这10个数字可用,共10种可能。

(6)填第6位号码。可以有0~9这10个数字可用,共10种可能。

(7)填第7位号码。可以有0~9这10个数字可用,共10种可能。

根据乘法原理,七星彩的号码总数共有:

对于七星彩来说,由于各位数字允许相同,因此计算起来很简单。全部七星彩号码有1000万个,将这1000万个号码全部买完可保证中特等奖。