阿里巴巴一道笔试题
问题描述: 12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种?
这个笔试题，很YD，因为把某个递归关系隐藏得很深。<�这是我看到的提示信息�>
这个提示信息很关键，至少知道往什么方向上思考了，避开很多弯路。
分析：
12个人，分成两排，每排都是从矮到高排列，而且第二排的人比站在他前面的人高，如果用一个r[2][6]的数组表示一个排列，那么r[0][0]最矮（小），r[1][5]最高（大）。
三个数组
把这12个人的身高存储在数组h[12]中，最终排列结果存储在r[2][6]中，我们每一次排列都从第一列r[][0]开始，然后依次分配下一列。
每次从数组h[]中选两个数放置在数组r[][]中，为了标记数组h[]中已经使用的元素，定义一个辅助数组used[12]用以标记h[]对应位置有没有被使用。
isPlace()函数
假定数组r[2][6]的分配顺序为从上到下，从左到右，即首先是r[0][0], r[1][0]，最后是r[0][5], r[1][5]。
每次我们判断在一个位置r[i]j能否放置hk中的一个数时，要保证如下条件
used[k] = 0
h[k] > r[i][j-1] 如果i>0
r[i][j] > r[i-1][j] 如果i=1
嵌套for循环
数组r[2][6]的每一个位置可以有12个选择（普遍情况，不要去考虑isPlace()失败的发问，r[0][0]只能放最小的，r[1][5]只能放最大的）
我们一次放置一列的两个数，使得从第0列到第col列满足条件。
Read full article from 12个高矮不同的人
No comments:
Post a Comment