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;
}
.
分享到:
- 2009-10-24 10:56
- 浏览 2180
- 评论(8)
- 论坛回复 / 浏览 (8 / 8138)
- 查看更多
相关推荐
阿里巴巴上机笔试题,想进阿里的同学可以看看
整理了一下阿里巴巴往届笔试面试题,希望对大家有帮助: 来源:阿里巴巴笔试面试圈>> 1、史上最全Java面试266题:算法+缓存+TCP+JVM+搜索+分布式+数据库 2、2018阿里软件工程师笔试题 3、2018秋招阿里巴巴java...
2014年3月31日全国统一在线笔试试题,完整的。
2014年阿里巴巴笔试题,题目非常经典,下载后仔细看看,对你一定会有帮助的!
阿里巴巴校园招聘笔试面试题淘宝校园招聘笔试试题27个文档资料合集: 2012阿里巴巴校园招聘阿里云C++笔试试题.doc 2013年阿里巴巴校园招聘笔试试题研发工程师.doc 2014年3月阿里巴巴实习招聘笔试题及部分答案.docx ...
2013杭州地区阿里巴巴笔试题
阿里巴巴校园招聘 产品岗笔试题_互联网 产品经理求职 校招 面试笔试题.pdf
阿里巴巴技术类笔试题2_3卷(测试工程师_公共题)
2009阿里巴巴笔试题.rar 2009阿里巴巴笔试题.rar
阿里巴巴笔试真题,想加入阿里巴巴的同学们加油了,对其他公司也有参考价值,不好容易才找到的。
阿里巴巴笔试题大全,包含近年笔试面试题,对程序员求职非常有用,物超所值
阿里巴巴的互联网笔试题和面试题。欢迎下载
文档是2014年阿里巴巴实习生笔试题。各个岗位的基础题是一样的,只是附加题不一样
阿里巴巴公司DBA笔试题 含答案,代表了国内DBA笔试题的经典,其实同志们,DBA笔试就那么些题,哈哈
阿里巴巴校招前端笔试题 校招前端笔试题.pages
2014阿里巴巴笔试题。答案在最后,个别不会,请见谅,有错请指正。
2009年 阿里巴巴笔试题,共分A卷、B卷、C卷三个部分,A卷为java部分。B卷是C++部分,C卷是公共题