Home > Old Blog Posts > 猴子爬楼梯

猴子爬楼梯


昨天学校数学竞赛时遇到一道很有趣的题,迫于时间,当时只能用凑的方法写上一个答案。后来终于在某节无聊的课上把它解决了。

问题描述:一只猴子在一架共有n级的梯子上爬上爬下,它每次或者上升16级,或者下降9级,如果它能从地面爬到最顶上一级,然后回到地面,那么n的最小值是?

解答:我们把每次走的决策总结成下表:

0 16 32 48 64 80 96 112 128 144
7 23 39 55 71 87 103 119 135
14 30 46 62 78 94 110 126
5 21 37 53 69 85 101 117
12 28 44 60 76 92 108
3 19 35 51 67 83 99
10 26 42 58 74 90
1 17 33 49 65 81
8 24 40 56 72
15 31 47 63
6 22 38 54
13 29 45
4 20 36
11 27
2 18
9
0

左上角是猴子开始时的高度,若向上爬则向右移动一格,下降则向下移动一格,直到碰到0结束,在这样任一条路径中遇到的最大数值就是n的一个可能值,也就是说我们要寻找一条路径,使得这路径上最大的数值最小。

我们先来分析0的可能位置。显然,每一列数的个数是单调递增的,而0只可能出现在某一列的最后一个数,为了尽可能地使路径上的数最小,我们要让路径“尽量靠着边上”,据此不难得出下列算法:

从0出发,每次先加16,再重复减9直到不能减,遇到0结束。这一列数中最大的数就是n的取值。

这里我们给出整个数列:

0, 16, 7, 23, 14, 5, 21, 12, 3, 19, 10, 1, 17, 8, 24, 15, 6, 22, 13, 4, 20, 11, 2, 18, 9, 0

所以n的最小值是24。不难证明,该算法可推广到上下任意步的情形。

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: