回 帖 发 新 帖 刷新版面

主题:摸彩票了,中了就加分!!!

现今,社会上流行着各种各样的福利彩票,彩票已经融入到了人人的日常生活中。彩票之所以能吸引那么多的人们,玩法多是一大原因。其中有一类是从前N个自然数中选出M个(不计顺序)不同的号码,如果这M个号码与摇奖时摇出的M个中奖号码完全相符,那么就中了头奖。如现在已经有的:30选7,35选7,36选7,37选7……
随着时间的推移,越来越多的人不满足于原来的玩法。为了追求更大的刺激,可供选择的号码和每注的号码个数越来越大,88选8,518选18,8888选68等应运而生。但是,由此也衍生出了许多的麻烦。由于数字越来越大,福彩中心的工作人员们已经无法用一般的计数器精确地计算出每一种彩票中头奖的概率。现在请你帮助他们,编一个程序:对于每一种玩法,能够快速准确地计算出中头奖概率的倒数。
输入输出:输入文件名为lottery.in。它包含两行:第一行是正整数N(M<=N<1040);
第二行是正整数M(0<M<=1000)
输出文件名为lottery.out。它仅包含一个数,表示在“N选M”的玩法中,中头奖的概率的倒数。输出文件中不应有多余的空格。
样例:lottery.in
5
2
lottery.out
10
样例说明“
本例为5选2的玩法,就是1-5这5个号码中任选2个(不计选后次序,1,2和2,1视为相同的)进行投注,如果你所选的2个号码与开奖时开出的2个号码完全相同,开出的头奖可能是下列10种中的任何一种:
(1,2)(1,3)(1,4)(1,5)
(2,3)(2,4)(2,5)
  (3,4)(3,5)
    (4,5)
所以,中头奖的概率是1/10.
我在这儿编了一个程序var
n,m,l,i,j:integer;
k:real;
c:real;
begin
readln(n,m);
k:=1;
l:=1;
for i:=n downto n-(m-1) do
k:=k*i;
for j:=m downto 1 do
l:=l*j;
c:=k/l;
write(c);
end.
不过个个测试数据都超时了,所以我要请教一个优化的程序,各位
大吓只要有的,便有每帖30分的优惠。!!!
[img]http://sports.sohu.com/upload/wallpapers/shaq_yao1024x768.jpg[/img]

回复列表 (共4个回复)

沙发

用高精度计算组合数,在计算时分别存储分子和分母,然后逐一约去分母(肯定能全部约去),再用1逐个除分子剩下的数,就能得出答案了

板凳

3 楼

当然快了,我老师教的方法,绝对优化……

4 楼

一定要顶住啊!!!!

我来回复

您尚未登录,请登录后再回复。点此登录或注册