Math 版 (精华区)
发信人: ssos (存在与虚无·戒酒戒网), 信区: Math
标 题: 清华大学95-97组合数学考题(转载)
发信站: 哈工大紫丁香 (2001年11月24日19:05:30 星期六), 转信
【 以下文字转载自 Computer 讨论区 】
【 原文由 ssos 所发表 】
（95年考题）
发信人: tomcat (九条命), 信区: e_note
标 题: 95年组合数学题
发信站: Holy Land BBS (Mon Dec 29 11:44:21 1997) , 转信
清华大学博士生入学考试95年组合数学考试题
1.正整数1到N顺序构成一个圆环，1与N相邻。从这N各数中去k个互不相邻的数的方案
有多少？
2.用相同的火柴搭成一个正8面体，有多少方案？
3.上楼梯迈一步可以上一级，也可以上两级，上N级楼梯有多少种上法？所有的上法
中一共用多少步？
4.在一 制古 球比赛� ，某选手始� 未落后过，最后以22:20战胜对手，在比赛过程
中没有出现5:5及15:15，有多少可能的表示比赛过程的比分记录？
5.一个矩形分成7行127列的网格，每个格子着1种颜色，现有6种颜色，证明无论怎样
着色，其中必有一个由格子构成的矩形的4个角上的格子着同一种颜色。
6.用单纯形算法解下列线形规划问题：
min z=2*x1+x2+x3
/ x1+ x2-2*x3<=8
< 4*x1- x2+ x3>=2
\ 2*x1+3*x2- x3>=4
x1,x2,x3>=0
发信人: lxm (大家新年好!), 信区: e_note
标 题: Re: 95年组合数学题
发信站: Holy Land BBS (Tue Dec 30 15:23:19 1997) , 转信
【 在 tomcat (九条命) 的大作中提到: 】
: 我做了几个题，结果是：
: 1. C(n-k+1,k)-C(n-k-1,k-2)=n*C(n-k,k)/(n-k)；
正确，另解：C(n-k-1,k-1)+C(n-k,k)=n*C(n-k-1,k-1)/k;
（实际上是书上的习题）
: 2. 186；
: 3. 与96年试题类似；
a(n) = F(n+1) ;
b(n) = b(n-1) + b(n-2) + a(n) ;
: 4. 5779381584；
用格路解：
[C(40,20)-C(40,19)] - [C(10,5)-C(10,4)][C(30,15)-C(30,14)]
- [C(30,15)-C(30,14)][C(10,5)-C(10,4)]
+ [C(10,5)-C(10,4)][C(20,10)-C(20,9)][C(10,5)-C(10,4)]
具体结果我没算，不知上面的式子对不对。
: 5. 是书上的习题；
: 6. 还没有做。
x1 = 5/7 ; x2 = 6/7 ;
min(z) = 16/7 ;
（96年考题）
发信人: too (DiscWoman), 信区: e_note
标 题: 去年组合数学考题（A卷）！
发信站: Holy Land BBS (Fri Dec 19 12:51:39 1997) , 转信
组合数学试题（A卷）
1。按照字典序、递增进位制数、递减进位制数和邻位对换4种全排列的生成算法
给出与中介数01010101对应的1-9的全排列。
2。3个a1，3个a2，……，3个an的全排列中，相同的字符不都排在一起
（例如当n=3时，a2a2a1a3a2a1a3a3a1可以，a2a2a2a1a3a1a3a3a1不可以），
求这样的排列的个数。
3。3维欧氏空间中x,y,z都是整数的点（x,y,z）称为整点，
1）至少多少个整点中必有两个整点的重心也是整点？
2）至少多少个整点中必有4个整点的重心也是整点？
4。上n级楼梯一步可跨一级或两级，有多少种上法？所有的上法中一步跨一级的总
步数是多少？
5。用外形相同的红火柴和绿火柴搭一个正8面体，有多少方案？
6。用单纯型法解线性规划问题：
minz = 4X1 + 2X2 + 2X3,
X1+X2-2X3 <=4,
4X1-X2+X3 >=1,
2X1+3X2-3X3>=2,
X1,X2,X3>=0.
发信人: Ice (不戒网了~用功考试), 信区: e_note
标 题: Re: 去年组合数学考题（A卷）！
发信站: Holy Land BBS (Fri Dec 19 23:29:55 1997) , 转信
B卷与A卷差不多，只是小处有所改动。
如4题中就计算一步跨两级的总步数。5题中正8面体变成了正六面体（好象是这样的）
而第6题就是用单纯形法。B题中的参数与再以前的一届的参数完全一致。
发信人: ggp (龙王), 信区: e_note
标 题: 对一下组合, 可以吗?
发信站: Holy Land BBS (Sat Dec 27 11:39:56 1997) , 转信
组合(A),我做了一些. 有人做过吗? 我不知道对不对.
1. 看到题目时, 我发现我忘乐该怎么做乐,
我再想想, 呵呵.
2. n
----
\ (-1)^k*C(n , k) * (3n + 2k)! / (3!)^(n-k)
/
----
k = 0
但是我不会化简乐,有谁能帮助我.
3. 1) 2 ^ 3 + 1
2) 4 ^ 3 + 1
4. 1) A * ((1 + sqrt(5)) / 2) ^ (t - 1) +
B * ((1 - sqrt(5)) / 2) ^ (t - 1);
其中 A = sqrt(5) / 5 , B = - sqrt(5) / 5;
2) A * ((1 + sqrt(5) / 2) ^ t +
B * ((1 - sqrt(5) / 2) ^ t +
C * t * ((1 + sqrt(5) / 2) ^ t +
D * t * ((1 - sqrt(5) / 2) ^ t;
其中 A = 2 * sqrt(5) / 25
B = -2 * sqrt(5) / 25
C = 1 / 10 + sqrt(5) / 10
D = 1 / 10 - sqrt(5) / 10;
5. 1 / 24 * (4 ^ 12 + 8 * 4 ^ 4 + 6 * 4 * 3 + 3 * 4 ^ 6)
= 699664
6. 用大M法.
minz = 4x1 + 2x2 + 2x3 + 0x4 + 0x5 + 0x6 + 6x7 + 6x8
x1 + x2 - 2x3 + x4 = 4
4x1 - x2 + x3 - x5 + x7 = 1
2x1 + 3x2 - 3x3 - x6 + x8 = 2
结果我还没有做出来. 呵呵.
发信人: ggp (龙王), 信区: e_note
标 题: Re: 对一下组合, 可以吗?
发信站: Holy Land BBS (Sat Dec 27 16:39:06 1997) , 转信
【 在 paladin (瞎逛逛) 的大作中提到: 】
: 你很危险，有不及格的可能。
这下可惨了, 看过书后, 又做了一点.
1. 字典序: 132547698.
递增序: 214365879.
递减序: 132547698.
邻位对换: 864135792.
6. x1 = 5 / 14;
x2 = 3 / 7;
z = 16 / 7.
现在能及格了吗?
发信人: hello (远方), 信区: e_note
标 题: Re: 对一下组合, 可以吗?
发信站: Holy Land BBS (Sat Dec 27 20:28:19 1997) , 转信
第3题的第二问，偶结果是25。
按第1问的结果，9个点里面可取2个使其重心为整点，这样，有25
点时，就可先取2点，再在剩下的23点中取2点。。。最后可取9组。再从中取2组，就得到
重心为整点的4点。
其他1，2，5，6结果相同。第4题我没有算到最后。
发信人: lxm (大家新年好!), 信区: e_note
标 题: Re: 对一下组合, 可以吗?
发信站: Holy Land BBS (Tue Dec 30 09:06:51 1997) , 转信
【 在 home (静思) 的大作中提到: 】
: t+1?
其实指数是几并不重要，指数不同，算出来的系数也会不同的。
我算出来一个结果不知道对不对：
b(n) = A * ((1 + sqrt(5) / 2) ^ t +
B * ((1 - sqrt(5) / 2) ^ t +
C * t * ((1 + sqrt(5) / 2) ^ t +
D * t * ((1 - sqrt(5) / 2) ^ t;
其中 A = sqrt(5) / 30
B = - sqrt(5) / 30
C = ( 4 * sqrt(5) + 5 ) / 30
D = - ( 4 * sqrt(5) - 5 ) / 30.
: 我只知母函数是x/(1-x-x^2)^2 不敢算通项
~~~~~~~~~~~~~ 这个母函数好象有点怪，
我没算母函数，但求出了特征方程：
� (x^2-x-1)^2=0
（97年考题）
发信人: tomcat (九条命), 信区: e_note
标 题: 97年组合数学考试题
发信站: Holy Land BBS (Thu Jan 1 17:41:33 1998) , 转信
97年组合数学题（A）
1.按字典序、递增进位制法、递减进位制法和邻位对换法求634271985
的中介数和下一个排列。
2.1~N做全排列，不出现i、i+1情况，可出现i+1、i的情况，i=1、2..
.N-1，求排列的个数？
3.3维欧氏空间中x,y,z都是整数的点（x,y,z）称为整点，
1）至少多少个整点中必有两个整点的重心也是整点？
2）至少多少个整点中必有4个整点的重心也是整点？
4.用两种直角等腰三角形和一种正方形的砖（如下图）给宽度为1，长
度为n的路铺面，每种砖的用量不限，有多少方案？
附加题：求正方形出现多少次？
路：|------------------------------------|
| | 1
|------------------------------------|
n
砖： |\ /\ |--|
1 |__\ /____\ |--| 1
1 2 1
5.用相同的红火柴和绿火柴各三根搭成一个正四面体，可以有多少种方
案？
6.用单纯形法解线性归化问题？
min z=8*x1+4*x2+4*x3
/ x1+ x2-2*x3<=8
< 4*x1- x2+ x3>=2
\2*x1+3*x2-3*x3>=4
x1,x2,x3>=0
（答案找不到了，不过跟95，96的差不多，主要第四题列递归方程
不要想当然考虑，最好是列两个方程组成递归方程组，然后再解出
最终方程。）
--
--
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: 天外飞仙]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：5.273毫秒