计数的基本方法 ---枚举树（ 2.28）“树形图” 是数学中应用最为广泛的图形之一，在数学计数问题中，每当我们面对一些非常规的题目一筹莫展时、无从下手时， 枚举法往往可以发挥巨大的威力。枚举法又叫穷举法，顾名思义，就是把所有符合题目条件的对象一一列举出来，然后根据要求从中挑选出合理的。但是怎样在枚举的过程中既不重不漏地枚举出所有符合条件的对象呢？“树形图” 就可以使我们的枚举过程不仅形像直观，而且有条理又不易重复或遗漏，使人一目了然一．树形图在组合计算中的应用例1. 用一台天平和重1 克、3 克、9 克的砝码各一个 （不再用其它物体当砝码），当砝码只能放在同一盘内时，可称出不同的重量有多少种？例2. 甲乙两人进行乒乓球比赛，规定谁先胜三场谁胜。第一场甲胜。问到决出最后的胜负为止，共有几种不同的情形？其中甲胜的情形有几种？例3.某人游览A ,B,C 三个风景区，计划旅游5 天。由 A 区开始游览，一天换一个风景区，最后又回到A 区，试问有多少种游览路线？例4. 小马虎给4 位同学写信，由于粗心，他在把信装入信封时给弄错了，结果四位同学都没有收到小马虎给自己写的信，而是收到了他写给别的同学的信，请问一共有多少种可能情形？（PS.本题是组合数学中著名的“错装信封问题”把n 个已写好相应地址的信封任意打乱。问，所有信纸全都装错了信封的情况有多少种？例5. 下图中有 6 个点， 9 条线段，一只蚂蚁从A 点出发，沿着某几条线段爬到F 点，行进中，同一个点或同一条线段只能经过一次，这只蚂蚁最多有多少种不同的爬行路线？例6.对自然数作如下操作：如果是奇数就减去1，如果是偶数就除以2，如此操作直到结果变为1 为止。那么经过6 次操作后使结果变成1 的数有几个？二．枚举树在决策问题中的应用枚举树不仅可以帮助我们去计数，还可以帮我们在众多的决策中选择出一组最优的策略。例7. 四皇后问题是将4 个棋子放在4X4 的格子里，使得不会有两个棋子在同一行、同一列或对角线上。 （用象棋术语来讲，该问题是如何将4 个皇后放在4X4 的棋盘中，并且使得没有皇后能攻击对方）例8. 设有 13 个银币，标号为1、2、 3、⋯⋯13。其中有一块银币有假，假的一块重量与正常的不一样 （可能重了或轻了） ，真的银币重量完全一样。另给一块标准银币，标号为 0，试问如何用一座天平称3 次将假的一块找出来，并判断它是轻了还是重了？例9. 现有无刻度的3 个容器各一个，容器分别为10、7、4 升。 10 升的容器装满了酒。试求一种办法从中倒出2 升的酒来。（只能用现有的工具）
VIP
