荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: huhaiming (一生只爱她), 信区: Program
标  题: 说一下昨天zoj的题目
发信站: 荔园晨风BBS站 (Sun Jun  8 19:27:07 2003), 站内信件

http://acm.zju.edu.cn/contests/list_problem.php?cid=48

我只会做3题,之后会贴出程序。

1004, 是一道关于排列组合的概率题目,推出公式即可。

1007, 最容易的题目,是求每列灯要变成 亮-灭 交替出现序列最少要动的次数
       做法是,假定第一盏灯是亮或者灭的情况下需要动的次数,最小的为答案。
       而在每次中,必定要动而且只动一下,在第一盏灯灭或亮的情况下。
       所以写起来非常顺手,二十几行搞掂了。

1008, 简单的编译题目,统计c++代码的注释数目,并且将注释内容的小写字母
       换成大写字母。 本来我做得十分繁琐的,因为上学期学了编译原理,
       尝试用自动机去做,可惜要考虑的东西非常多,后来重写,按照笨笨的
       思路,搞掂了。写出来也算十分简单了,不是费太多的时间,整个思路写
       下来也就是差不多50行的代码。有兴趣看代码就不用我解释都看得懂的了。

详细说一下1004的思路,n个里面只有m个是相同的,先取出这m个的可能是C(n,m)
对于每种只有m个的可能,剩余的n-m个求错位排列即可。
错位排列的递推式子是: Dn = (n-1)*(Dn-1 + Dn-2)
而所有的可能性就是n!
所以,所求的概率就是 C(n,m) * Dn-m / n!
而C(n,m)=n!/( m! * (n-m)! ) ,待入上式即得 Dn-m/m!/(n-m)!
即程序中所写。
关于错位排列方面的内容,自己看组合数学方面的书,都有说的。
可以推出公式后,稍微注意一下100的阶乘要用double表示。写出来
的程序又是只有14行左右的。

--

菩提本无树,明镜亦非台

本来无一物,何处惹尘埃

※ 修改:·huhaiming 於 Jun  8 21:09:20 修改本文·[FROM: 192.168.0.200]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.200]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店