论文部分内容阅读
“唉——”阿木老叔和古噜噜刚踏进某展览馆，就远远地听到一声叹息。原来，展览馆的一位工作人员最近很烦恼，馆长要他在两座建筑里挑一座，为一位画家举办作品展。
“不就是二选一吗？这有何不好抉择的。我们帮你！”古噜噜拍拍胸脯，自信地说道。
工作人员将两座建筑的室内平面图递给阿木老叔和古噜噜。
这两座建筑的室内都有14个展厅，每相邻的两个展厅之间都有门相通。作为展览活动用的建筑，一定要保证让参观者不重复地一次走遍所有展厅，这样既可以节约参观时间，也可以保证参观能有序进行。
“两座建筑的面积相同，地理位置也都很好，而且租借费用一样，到底选用哪一座更好呢？”工作人员问。
“既然这两座建筑内每相邻的两个展厅都有门相通，那么就应该都能用于举办作品展。”古噜噜拿着图纸仔细打量。
阿木老叔从口袋里取出一支笔，说道：“这可不好说，画一画就知道了！”
于是，工作人员试着用箭头画一画，很快就找到了A建筑的参观路线（不唯一）。然而，他怎么也画不出B建筑能够一次走完的参观路线。
“这到底是我的问题，还是这座建筑有不对劲的地方？”工作人员很惶恐。
“要是采用一次次试画的办法，不但要试好多次，而且还很难做到不重复不遗漏。这样无法证明一次走完的参观路线确实不存在。”阿木老叔也陷入了沉思。
“怎么办呢？”工作人员非常迷茫。
大家都盯着两幅平面图，安静地思考着……
“有了！我想到办法了！”古噜噜似乎从地砖上得到了启发，“或许我们可以用涂色的办法来解决这个问题。”
“涂色？”
“对，蓝白相间地涂抹各个展厅，或者用0、1分别表示蓝白两色。现在，从起始展厅到终止展厅就会有一个由0、1组成的14位数。可以看出，参观者在‘蓝展厅（0）’里的话，下一站一定是去‘白展厅（1）’。如果存在一条不重复一次走完的参观路线，那么这个14位数中，0和1一定是相间排列的。也就是说，要么0和1的数量相同，要么相差1。”古噜噜一边在平面图上涂色，一边解释。
“这个办法不错！士别三日当刮目相看啊！”阿木老叔夸奖道。
“那当然，数学书籍我可没少读！”古噜噜继续说道，“但是，将相同方法用在B建筑上时，我们会发现0和1的数量相差2，所以，一条不重复一次走完的路线肯定不存在。”
工作人员一声叹息：“唉，明明B建筑看上去更有艺术感……”
“为了方便参观，选择A建筑会更好！”阿木老叔说道。
问题解决了，阿木老叔和古噜噜继续他们的参观之旅。
“其实，不管是参观画展还是参观博物馆，我们一般都想找出能一次走遍所有展厅的路线。而有时候，我们更想知道从这个展厅到另一个展厅有多少种走法。毕竟我们对某些展厅可能不感兴趣，或者有时候某个展厅的人太多，挤不进去，我们得更换参观路线。”古噜噜有感而发。
“听你这么一说，我想起了某座展览馆。”阿木老叔掏出手机，“瞧，这是它的室内平面图，是不是很像蜂房？游人参观是从左往右走的——可以往右走，也可以往右上、右下走，但是不可以走回头路，因为人太多，挤不回去了……”
“嗯，確实很像蜂房！我来研究一下。”古噜噜拿过手机，比画了两三下后说，“如果从起点出发去3号展厅，可以罗列出5种不同的走法：起点→1→3，起点→0→2→3，起点→0→1→3，起点→1→2→3，起点→0→1→2→3。”
“用枚举法嘛，这个我也会。不过，如果我们要去8号展厅呢？一一罗列恐怕就不行了。有没有什么规律可循呢？”阿木老叔抛出了一个难题。
“这个，这个……容我思考一下。” 古噜噜开始思考。
一分钟过去了，十分钟过去了，半小时要过去了，终于——古噜噜把难题解答出来了！
“我们先来看看前几个展厅，试试先简单后复杂地破解这个问题。”古噜噜说道。
从起点到0号展厅只有1种走法：起点→0；
从起点到1号展厅有2种走法：起点→1，起点→0→1；
从起点到2号展厅有3种走法：起点→0→2，起点→1→2，起点→0→1→2。
不难看出，如果想要到4号展厅去，那么在进入4号展厅之前的最后一个落脚点，不是2号展厅就是3号展厅。因此，到4号展厅去的路径总数，就是去2号展厅的路径总数加上去3号展厅的路径总数。由此，我们推算出从起点到4号展厅的走法有3 5=8（种）。于是，得到如下的结果：
有没有觉得很神奇？从起点到8号展厅有55种走法！假如一一罗列的话，脑袋肯定都要涨破了吧，而现在我们只是做了几次口算加法。如果不相信的话，你可以动手画一画哟！
“不就是二选一吗？这有何不好抉择的。我们帮你！”古噜噜拍拍胸脯，自信地说道。
工作人员将两座建筑的室内平面图递给阿木老叔和古噜噜。
这两座建筑的室内都有14个展厅，每相邻的两个展厅之间都有门相通。作为展览活动用的建筑，一定要保证让参观者不重复地一次走遍所有展厅，这样既可以节约参观时间，也可以保证参观能有序进行。
“两座建筑的面积相同，地理位置也都很好，而且租借费用一样，到底选用哪一座更好呢？”工作人员问。
“既然这两座建筑内每相邻的两个展厅都有门相通，那么就应该都能用于举办作品展。”古噜噜拿着图纸仔细打量。
阿木老叔从口袋里取出一支笔，说道：“这可不好说，画一画就知道了！”
于是，工作人员试着用箭头画一画，很快就找到了A建筑的参观路线（不唯一）。然而，他怎么也画不出B建筑能够一次走完的参观路线。
“这到底是我的问题，还是这座建筑有不对劲的地方？”工作人员很惶恐。
“要是采用一次次试画的办法，不但要试好多次，而且还很难做到不重复不遗漏。这样无法证明一次走完的参观路线确实不存在。”阿木老叔也陷入了沉思。
“怎么办呢？”工作人员非常迷茫。
大家都盯着两幅平面图，安静地思考着……
“有了！我想到办法了！”古噜噜似乎从地砖上得到了启发，“或许我们可以用涂色的办法来解决这个问题。”
“涂色？”
“对，蓝白相间地涂抹各个展厅，或者用0、1分别表示蓝白两色。现在，从起始展厅到终止展厅就会有一个由0、1组成的14位数。可以看出，参观者在‘蓝展厅（0）’里的话，下一站一定是去‘白展厅（1）’。如果存在一条不重复一次走完的参观路线，那么这个14位数中，0和1一定是相间排列的。也就是说，要么0和1的数量相同，要么相差1。”古噜噜一边在平面图上涂色，一边解释。
“这个办法不错！士别三日当刮目相看啊！”阿木老叔夸奖道。
“那当然，数学书籍我可没少读！”古噜噜继续说道，“但是，将相同方法用在B建筑上时，我们会发现0和1的数量相差2，所以，一条不重复一次走完的路线肯定不存在。”
工作人员一声叹息：“唉，明明B建筑看上去更有艺术感……”
“为了方便参观，选择A建筑会更好！”阿木老叔说道。
问题解决了，阿木老叔和古噜噜继续他们的参观之旅。
“其实，不管是参观画展还是参观博物馆，我们一般都想找出能一次走遍所有展厅的路线。而有时候，我们更想知道从这个展厅到另一个展厅有多少种走法。毕竟我们对某些展厅可能不感兴趣，或者有时候某个展厅的人太多，挤不进去，我们得更换参观路线。”古噜噜有感而发。
“听你这么一说，我想起了某座展览馆。”阿木老叔掏出手机，“瞧，这是它的室内平面图，是不是很像蜂房？游人参观是从左往右走的——可以往右走，也可以往右上、右下走，但是不可以走回头路，因为人太多，挤不回去了……”
“嗯，確实很像蜂房！我来研究一下。”古噜噜拿过手机，比画了两三下后说，“如果从起点出发去3号展厅，可以罗列出5种不同的走法：起点→1→3，起点→0→2→3，起点→0→1→3，起点→1→2→3，起点→0→1→2→3。”
“用枚举法嘛，这个我也会。不过，如果我们要去8号展厅呢？一一罗列恐怕就不行了。有没有什么规律可循呢？”阿木老叔抛出了一个难题。
“这个，这个……容我思考一下。” 古噜噜开始思考。
一分钟过去了，十分钟过去了，半小时要过去了，终于——古噜噜把难题解答出来了！
“我们先来看看前几个展厅，试试先简单后复杂地破解这个问题。”古噜噜说道。
从起点到0号展厅只有1种走法：起点→0；
从起点到1号展厅有2种走法：起点→1，起点→0→1；
从起点到2号展厅有3种走法：起点→0→2，起点→1→2，起点→0→1→2。
不难看出，如果想要到4号展厅去，那么在进入4号展厅之前的最后一个落脚点，不是2号展厅就是3号展厅。因此，到4号展厅去的路径总数，就是去2号展厅的路径总数加上去3号展厅的路径总数。由此，我们推算出从起点到4号展厅的走法有3 5=8（种）。于是，得到如下的结果：
有没有觉得很神奇？从起点到8号展厅有55种走法！假如一一罗列的话，脑袋肯定都要涨破了吧，而现在我们只是做了几次口算加法。如果不相信的话，你可以动手画一画哟！