杜牧简介-山西政法管理干部学院

Algorithm Design Strategies

1. Row and Column Exchanges
Can one transform the left table into the right table by exchanging its rows and columns?

〖translate〗
行与列的变换
能否通过行与列的变换将左边的表格转换成右边的表格？
解：不行！
根据行列式的规律，可以将右边的数看成4×4的行列式
所以，不管行和列怎么去变换，那么它行的数 字与列的数字始终不会发生改变。例如：坐
标第一行的数字分别是1、2、3、4，那么无论怎么变，这 行数字中定存在1、2、3、4这四
个数字（数字的顺序可能发生改变）。那么可以发现右边的表格中第 二行和第三行中，就违
背了这个规律。可以将5和15的位置交换一下，就正确的.

2. Predicting a Finger Count
A little girl counts from 1 to 1000 using the fingers of her left hand as follows. She starts by calling
her thumb 1, the first finger 2, middle finger 3, ring finger 4, and little finger 5. Then she reverses
direction, calling the ring finger 6, middle finger 7, the first finger 8, and her thumb 9, after which
she calls her first finger 10, and so on. If she continues to count in this manner, on which finger
will she stop?
〖translate〗
猜想指头的数
一个小女孩用自己左手的手指从1到1 000依照下面的方法进行数数。她开始称大拇指为
1，食指为2，中指为3，无名指为4，小指为5, 。然后反向，称其无名指为6，中指为7，
食指为8，大拇指为9，依次这样数下去。如果她用这种方式 继续数下去，在哪个手指会停
下？
解：令a,b,c,d,e,f,g,分别代表正向大拇 指，正向食指，正向中指，正向无名指，正向小指，
反向无名指，反向中指，反向食指。1到8分别是a 到g，9到16又是a到g,那么a到g形
成循环，一个周期为8，那么从1到1000为125个周期 ，故在数到1000的时候恰好在食指

上。
『拓展』
如果是1到n 的话，同样如此，将n除以8，所得的余数，从a开始数起，按这样即可得
出那个手指了.

3. Mental Arithmetic
A 10 × 10 table is filled with repeating numbers on its diagonals as shown in the following figure.
Calculate the total sum of the table’s numbers in your head

〖translate〗
智力算法
一个10×10的表格在斜线上填满重复数，如以下方式。用你的大脑算出所有数之和。
解：这道题可以用很多方法做出来，不同的学历层次的人因知识面的不同做法也存
在不同。那么不用笔算 ，口算是否一下子算出来结果呢？答案是可以口算出来的.
将此个格
子旋转180度，与原来的 格子对应相加，每个小格子之和为20，共100个格子，故总和为2000，
再除以2，最后结果为1 000.

4. A Fake Among Eight Coins
There are eight identical-looking coins; one of these coins is counterfeit and is known to be
lighter than the genuine coins. What is the minimum number of weighings needed to identify the
fake coin with a two-pan balance scale without weights?
〖translate〗
九个硬币中的假币
这里有九个 模样无法分辨的硬币，其中一个是假冒的并知道它比真硬币要轻。在无读数
的双盘天秤上，最少需要多少 次称量才能辨别出假币？
解：将9个硬币分成3份，取两份放在天平两侧，即每盘中有三个硬币。 （第
一种情况） 如果天平是平的，那么假币在第三堆中；再将第三堆的三个硬币拿出两个放在
天平上，若是天平是平的， 那么另外一个就是假币，若天平不是平的，那么天平翘起的那
一边是假币，即轻的那个是假币。故只要两 次。
（第二种情况）如果天平不是平的，那么将翘起的那一侧的三个硬币放在天平再称，取出

两个硬币放在两侧，若是平的，那么第三个是假币；若天平不是平的，那么翘起的那一边
是假币，即轻的那个是假币。故也是两次。
结果最少是两次才能称出假币.

5. Page Numbering
Pages of a book are numbered sequentially starting with 1. If the total number of decimal digits
used is equal to 1578, how many pages are there in the book?
〖translate〗
一本书的页数是从1开始连续的。如果总共的页数的小数（数字）总共加起来为1578，那么这本书有多少页？
解：可以得到1--9总和为45，10-- 19总和为55，以此类推，90--99总和为135，即45，
55,65...135总和为90 0,故1578-900=678.100--109总和为55，110--119总和为65...170 --179总和
为125，其总和为720。有因为179,178,

6. Glove Selection
There are 20 gloves in a drawer: 5 pairs of black gloves, 3 pairs of brown, and 2 pairs of . You
select the gloves in the dark and can check them only after a selection has been made. What is
the smallest number of gloves you need to select to guarantee getting the following?
(a) At least one matching pair
(b) At least one matching pair of each color.
〖translate〗:
手套的选择
抽屉里有20双手套，其中5双是黑色的， 3双食棕色的，2双是灰色的。你在黑暗的地方
选择手套，并且只能在做出选择之后才能检查其颜色。那 么你最少需要选择几次手套才能
保证下面的要求？
• 至少有一双配对;
• 至少每种颜色有一双。
解：由于手套有左右手之分，故假设在最差的情况下，选了5个黑色的，3个棕 色的，2个
灰色的，这10个手套全部为做手套，故再只需选1个手套就有一双配对了，故总共需11< br>次；
至少每种颜色都要配对，那么最差的情况下，2双灰色的，3双棕色的，以及5个 左手套，
只要再选一个，就可以了。故总需要16次。

7. A stack of Fake Coins
There are 10 stacks of 10 identical-looking coins. All of the coins in one of these stacks are
counterfeit, and all the coins in the other stacks are genuine. Every genuine coin weighs 10 grams,
and every fake weighs 11 grams. You have an analytical scale that can determine the exact weight
of any number of coins. What is the minimum number of weighings needed to identify the stack
with the fake coins?
〖translate〗
这里有10堆硬币，每堆有10个难以辨别真假 的硬币。所有的硬币中只有一堆是假币，
其他的都是真的。每个真的硬币重10克，每个假币重11克。 你有一个带砝码的天平可以
准确的称量每个硬币。那么最少需要称几次才能辨别那一堆是假币？
解：将每堆分别编上号①②③④⑤⑥⑦⑧⑨⑩，再从这些堆里对应拿出1个，2个，3

个……10个硬币，然后进行称量。如果这55个硬币都是真的，那么总重为550克，那么实
际上有假币参与其中，故所称的实际总重比550克多几克就在那一堆了（如多了2克，就
在第二堆里， 以此类推）。

8. Three Jugs
Given an 8-pint jug full of water and two empty jugs of 5-and 3-pint capacity,
get exactly 4 pints of water in one of the jugs by completely filling up and∕
or emptying jugs into others.
〖translate〗
给出一个能装满8品特水的大罐子，以及两个容量分别为5品特、3 品特的空罐子，通过
完全填满或是罐子倒空到其他的罐子中的方式，在其中一个罐子中称出4品特的水。
解： 容量 编号 转变过程
8 ① 8 3 3 6 6 1 1 4
5 ② 0 →5 →2 →2 →0 →5 →4 → 4
3 ③ 0 0 3 0 2 2 3 0
由此可以看出，用7个步骤就可以完成。

placement
Give a list of n distinct integers and a sequence of n boxes with preset inequality signs
inserted between them, design an algorithm that places the numbers into the boxes to
satisfy those inequalities. For example ,the number 2,5,1,and 0 can be placed in the four
boxes as shown below:
0<5<1<2
〖translate〗
数字的放置
给出n个一系列的不等整数以及n个一序列的格子,且带有不等号。设计一个 算法，在格
子里排列这些数以便满足它们的不等关系。例如，数字2，5，1和0可以放置在这四个格< br>子里，如以下排列：
0＜5＞1＜2 。
解：给出一些列数 ，例如：8＞2＜6＜13＞1＜3＜7＞4＜10＞5……那么要从小到大排列，
则先看小于号之间的 数。
＞ ＜ ＜ ＞ ＜ ＜ ＞ ＜ ＞ ……
① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ……
将这一系 列的格子进行编号（格子没显示出来），可以找到从小到大1,2,3,4,5,6,7,8,10,13，那么从小于号的后边开始，＿＞1＜2＜＿＞3＜4＜＿＞5＜＿＞＿ …… 然后对大于号的前
边的数也按大小顺序排列，即从最右边开始，13＞1＜2＜10＞ 3 ＜4 ＜8＞ 5 ＜7 ＞6。
另外的一种方法是将最大的数和最小的数找出来 ，大于号前就填上最大的数，第①个
即填13，第②个为小于号前填上最小的数，即为1。除去1和13 ，又判断出最小值及最大
值，没遇到小于号就填最小数，遇到大于号就填最大的数（前提是将前面的已填 的数除去），
这样就填好了.


10．The other wolf- goat-cabbage puzzle
You have 4n counters of four types: n wolfs, n goats, n cabbages , and n hunters. the

object is to place the counters in a row such that no one is in danger；that is， hunter is
next to a wolf, no wolf is next to a goat, and no goat is next to a cabbage. In addition, no two
counters of the same kind may be next to each other either. How many ways are there to
solve the puzzle?
〖translate〗
你有四个种类对立物，总共有4n个：n头狼，n头羊，n个白菜以 及n个猎人。这些
物体按照顺序排列起来使没有谁可以受到危险。像这样，猎人挨着狼，不可羊挨着狼， 不
可羊挨着白菜。另外，同一种类型的不能挨在一起。怎样解决这个难题？
解：将猎人，狼， 羊，白菜进行编号，分别为①②③④，要使相邻的两者没有受到威胁，
可以先针对4个排列，即③①④② ；那么要是8个，则为③①③①④②④②；12个，则为
③①③①③①④②④②④②。。。。以此类推， 在4n个的情况下，可以这么排列：
。。。。③①③①③①③①③①④②④②④④②④②。。。。故可以解决这个问题。