Chinaunix首页 | 论坛 | 认证专区 | 博客

Aimerの博客

http://nil.csail.mit.edu/6.824/2015/schedule.html

  • 博客访问: 289102
  • 博文数量: 105
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1565
  • 用 户 组: 普通用户
  • 注册时间: 2014-08-21 00:58
  • 认证徽章:
个人简介

锻炼精神,首先要锻炼肉体

文章分类

全部博文(105)

文章存档

2018年(1)

2016年(1)

2015年(102)

2014年(1)

我的朋友
微信关注

IT168企业级官微



微信号:IT168qiye



系统架构师大会



微信号:SACC2013

分类: IT职场



1. 七夕节n对恋人(n>=2)围成一圈举行篝火晚会。晚会的规则是:男女相同,且每对恋人处在相邻的位置上。请问有多少种不同的圈子?
     

2. 书架一排有5个格子。现在有20本书,编号从1到20。要求20本书要摆放在同一排里,并且从左到右编号依次递减;每个格子至少有一本书;并且编号7,8,9的书籍必须在同一个格子里面。问,一共有多少种可能的摆放方法?

3. 6×9的的方格中,起点的左下角,终点在右上角,从起点到终点,只能从下向上,从左向右走,问一共有多少种不同的走法。

4. 10个相同的糖果,分给三个人,每个人至少要得一个。有()种不同分法


5. 一个合法的表达式由()包围,()可以嵌套和连接,如(())()也是合法 表达式;现在有 6 对(),它们可以组成的合法表达式的个数为____

6. 参加支付宝夜谈分享的同学共有50人,现设有甲、乙、丙三个夜谈主题。有40人选择参加甲夜谈主题,36人选选择参加乙夜谈主题,30人选择参加丙夜谈主题,兼选甲乙夜谈主题的有28人,兼选甲丙夜谈主题的有26人,兼选乙丙两门夜谈主题的有24人,甲乙丙三个夜谈主题均选的有20人,问三个夜谈主题未选的有多少人?( )

7. 6支笔,其笔身和笔帽颜色相同:但6支笔颜色各不相同,求全部笔身都戴错笔帽的可能性有多少种?

8. 
在如下8*6的矩阵中,请计算从A移动到B一共有____种走法。要求每次只能向上或向右移动一格,并且不能经过P。
 

9. 将7723810的各位数字打乱排序,可组成的不同的7位自然数的个数是?

10. a)ABCDEFG七人站队,要求A必须在B的左边(可不相邻),共有  种排法?
       b)在a的条件下若AB必须相邻,有  种排法?

==============================================================================
答案及解析:
1. 解析:
n 对恋人围成一个圈,n 对恋人全排列的情况是 n! , 去除掉围成一个圈转动的情况围成一圈的所有情况是 (n-1)!
每对恋人对应的是 2 个人,男女,女男,一共 n 个位置,只要有一对男,女的位置发生变化就是一个新的圈子。
所以,n 个位置,每个位置都有 2 中不同的排列,所以一共 2^n 种,再加上围成一圈的所有情况,一共就是
2^n*(n-1)!

2. 解析:
这道题涉及到捆绑法+ 挡板法
捆绑法: 7,8,9 当做一个元素来看,因为顺序一定,所以不进行内部排序,
20 个元素编程 18 个元素,18 个元素形成了 17 个空挡 。而我们要将这 17 个元素分成 5 份,就需要 4 个挡板。

C(空挡个数,挡板个数) = C(17,4) = 2380

3. 解析:
这道题是经典的走格子问题
从起点到终点一共要走 (6+9) = 15 个格子,其中横坐标选 6 个 C(15,6) 便是所有不同的走法
C(15,6) = 5005

4. 解析:
这道题是最基本的挡板法
10个糖果形成 9 个空
分给 3 个人,需要 2 个板
因为这道题是每个人至少 1 颗糖,所以 C(空数目,板数目) = C(9,2) = 36

如果这道题变型的话,去掉”每个人至少要得一个“这个条件的话,对应的公式为 C(空挡数目-1+板数目-1,挡板数目-1)

5.解析:
这道题考察的是卡特兰数,对应的是 6 组,每组中的两个元素 '(', ')' 是需要有序列的,C(2n,n)/(n+1) = C(12,6)/(6+1)

6. 解析:
这道题考察的是组合数学中的容斥问题
未选主题的人数 = 总人数(全集) - (选择 甲, 乙 , 丙 主题的人数)

|甲 U 乙 U 丙| = |甲| + |乙| + |丙| - |甲n乙| - |乙 n 丙| - |甲 n 丙| + |甲 n 乙n 丙|= 
                     = 40+36+30 - 28 - 26 - 24 + 20 = 48 
带入上述式子

50 - 48 = 2 

7.解析:
这道题做错了,是典型的容斥定理中的错排问题
级数和的公式背下来就行,要不就是记住递归公式,到时候往里面代数就可以了

下面的 n 代表的是, 将 n 个编号元素放在 n 个编号位置上,元素编号与位置编号不对应的方法数 D(n)

D(n) = (n-1)[D(n-2) + D(n-1)] ; (n > 2) 
D(0) = 1 ; D(1) = 0  

n = 6 

D(6) = 265


8.解析:
这道题考察的同样是容斥定理中的'斥'

首先计算出 A--> B 的所有可能是 C(12,7)
然后计算出 A->P->B 的所有可能,这一过程满足的是乘法技术原理
使用 A-> P 的所有情况乘上 P->B 的所有情况,

C(6,2)*C(6,3) 


最后结果 = C(12,7) - C(6,2)*C(6,3) = 492

9. 解析:
这道题考察的是,全排列 - 不满足条件的

首先 7 个数字全排列 = 7!
而不满足条件的是首项数字为 0 的这种情况,因为如果首项为 0 那么,
它就是一个六位数了,

7!-6! 

除了上述处理,还需要知道在这些数据中存在重复的数字, 7 , 对于数字 7 来说 两个 7 之间存在一个先后的排序问题,
两个 7 A(2,2)= 2 , 这种重复性同样存在于 6! 这种情况中,

所以为了去掉两个 7 的排序问题,还需要除上两个 7 的排序问题
即, 

(7!-6!)/2! = 2160

10. 解析:
##这道题考察的是捆绑和排列去重
7!/2! , 即, 全排列除上AB 全排列 = 2520 , 我的乘法算错了

##这道题考察的是捆绑法将 AB 两个元素看做一个元素,一共6 个元素全排列,6! 
但是别忘了, AB 两个元素自己还有一个顺序全排列呢 2! 
但是别忘了,这道题是在第一问的条件下展开的,即 AB 顺序是一定的,所以 2! 是无需计算上的
  
所以这道题b)的答案为 6!


end
阅读(753) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册