阿里巴巴笔试题_身高排队问题

12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

假定这12个人各自有自己的编号，即1、2、3... 11、12. 并且编号1到编号12所代表的人身高是递增的。
解这道题基于观察发现的如下规律：
a、第一排第一个人必定是1.
b、第一排第二个位置的可选值是2、3，第一排第三个位置的可选值是3、4、5，...，第一排第6个人的可选值是6、7、8、9、10、11
c、第一排的数字确定后，第二排的顺序可以唯一确定。因为剩下的6个数字只能递增排列（显然只有一种结果），所以只需确定第一排的所有排列可能就行了。 如下是解题的最初实现方法。采用穷举法实现。

#include <iostream>
using namespace std;

#include <vector>
#include <set>

// 后来发现不需要记录路径中现有节点。因为数字本身存在偏序的问题，往上涨就行了
set<int> path;
vector<vector<int>> marks;

int getCount(int depth, int max)
{
	if(depth==marks.size()) {
		int flag=0;
		for(int i=0; i<marks[depth-1].size(); i++) {
			// path.find(marks[depth][i]) == path.end() &&
			if( marks[depth-1][i]>max) {
				flag ++;
			}
		}
		return flag;
	}
	int count = 0;
	for(int i=0;i<marks[depth-1].size();i++) {
		if( marks[depth-1][i]>max) {
			count += getCount(depth+1,marks[depth-1][i]);
		}
	}
	return count;
}


int main()
{
	int n;
	while(cin>>n) {
		

		marks.clear();
		for(int i=1; i<=n/2; i++) {
			vector<int> node;
			for(int j=0;j<i;j++) {
				node.push_back(i+j);
			}
			marks.push_back(node);
		}

		cout << getCount(1, 0) << endl;



	}
	return 0;
}

.

评论

8 楼 GC_Man 2009-11-10  

我不太懂算法，上来学习下。
大家看这样行不，先排好第一排。完全按从矮到高。然后只要从第二个开始遍历。随即抽6个人到第二排。统计下可能的次数就可以了吧。
各位大哥看我这样的算法可以不，纯粹提疑问加学习，欢迎指导

7 楼 BenArfa 2009-11-04  

gembler 写道

BenArfa 写道

(12,6)/7 = 132
如果对数学解释感兴趣的话我可以贴出来分析过程，写起来有几句话的

愿闻其详

阁下晚上好，这题大体思路是这样的
如果要满足题意，只要从12个人中挑选6个人放在第一排，那么所有的人的位置就都确定了，因为是要求按身高排序的。
这里我们的挑选方法以及限制条件是这样的：12个人先从矮到高排序，然后每个人被选到第一排或者第二排，如果要满足题意，当且仅当每挑选完一次之后，第二排中的人数不多于第一排中的人数。

而这个条件的排列就是(12,6)-(12,5)。

6 楼 gembler 2009-11-04  

BenArfa 写道

(12,6)/7 = 132
如果对数学解释感兴趣的话我可以贴出来分析过程，写起来有几句话的

愿闻其详

5 楼 BenArfa 2009-11-03  

(12,6)/7 = 132
如果对数学解释感兴趣的话我可以贴出来分析过程，写起来有几句话的

4 楼 20.Shadow 2009-10-28  

引用楼主思路的Erlang代码 (testCalc.erl) :

-module(testCalc). 
-export([test/0]).

test() ->
L1 = [[A1, A2, A3, A4, A5, A6] ||
A1 <- [1],
A2 <- [2, 3],
A3 <- [3, 4, 5],
A4 <- [4, 5, 6, 7],
A5 <- [5, 6, 7, 8, 9],
A6 <- [6, 7, 8, 9, 10, 11],
A2 > A1,
A3 > A2,
A4 > A3,
A5 > A4,
A6 > A5
],
print(L1),
io:format("Len = ~p", [length(L1)]).

print ([]) ->
null;
print([H | T]) ->
Arr = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
L2 = lists:filter(fun(E) -> R = lists:member(E, H), not R end, Arr),
io:format("L1 = ~p, L2 = ~p~n", [H, L2]),
print(T).

132个结果 - Right.

3 楼 fruitking 2009-10-27  

我也从新整理了一下
http://fruitking.iteye.com/blog/505037
java版本的
我采用的是栈操作来遍历
有详细分析解决过程

2 楼 chinpom 2009-10-27  

<p><strong>我是用状态生成树的方式来做的，先把12个人按从低到高一次编号，从（1 ; 2）出发，加入3和4的时候生成（1,3 ; 2,4）和（1,2 ; 3,4），然后加入5和6，分别从前面的两个状态出发，可以生成5种状态，就是说6个人时有5种排列。最好是画出状态生成树，就很容易写出代码了，核心代码有十几行,全部代码如下：</strong></p>
<pre name="code" class="java">import java.util.ArrayDeque;
import java.util.Deque;

public class TwoOrderQueue {

private int count = 0;
private int total = 0;
private Deque&lt;Integer&gt; place = new ArrayDeque&lt;Integer&gt;();

public TwoOrderQueue(int total) {
this.total = total;
}

private void firstOrder(int order, int level) {
place.add(order);
if (level &gt;= total / 2) {
count++;
for (Integer i : place)
System.out.print(i + " ");
System.out.println();
place.pollLast();
return;
}

for (int i = order + 1; i &lt; 2 * (level + 1); i++)
firstOrder(i, level + 1);
place.pollLast();
}

public void firstOrder() {
firstOrder(1, 1);
System.out.println("第一排一共有" + count + "种排列");
}

public static void main(String[] args) {
TwoOrderQueue q = new TwoOrderQueue(12);
q.firstOrder();
}
}</pre>
<p> <strong>当有12个人时，一共输出132种排列。</strong></p>
<p> </p>
<p>顺便向楼主打听一下，阿里的笔试情况怎么样？难不难？我想毕业后回浙江，就是不知道能不能进阿里。现在大四上个学期还有几门专业课，特别是数字信号处理很难，现在在上的考查课《人工智能导论》对解这类题目的帮助挺大的，<img src="/images/smiles/icon_mad.gif" alt=""> 就是来上课的同学越来越少了。</p>

1 楼 seraphim871211 2009-10-26  

嗯，不错，回溯就可以了