題目敘述

釘子和小球 Time Limit: 1000MS Memory Limit: 10000K 題目描述 有一個三角形木板,豎直立放，上面釘著n(n + 1) / 2顆釘子，還有(n + 1)個格子(當n = 5時如圖1)。每顆釘子和周圍的釘子的距離都等于d，每個格子的寬度也都等于d，且除了最左端和最右端的格子外每個格子都正對著最下面一排釘子的間隙。 讓一個直徑略小于d的小球中心正對著最上面的釘子在板上自由滾落，小球每碰到一個釘子都可能落向左邊或右邊（概率各1/2），且球的中心還會正對著下一顆將要碰上的釘子。例如圖2就是小球一條可能的路徑。 我們知道小球落在第i個格子中的概率pi=，其中i為格子的編號，從左至右依次為0, 1, ..., n。現在的問題是計算拔掉某些釘子后，小球落在編號為m的格子中的概率pm。假定最下面一排釘子不會被拔掉。例如圖3是某些釘子被拔掉后小球一條可能的路徑。 輸入描述 第1行為整數n(2 ≤ n ≤ 50)和m(0 ≤ m ≤ n)。以下n行依次為木板上從上至下n行釘子的信息，每行中'*'表示釘子還在，'.'表示釘子被拔去，注意在這n行中空格符可能出現在任何位置。 輸出描述 僅一行，是一個既約分數(0寫成0/1)，為小球落在編號為m的格子中的概率pm。既約分數的定義：A/B是既約分數，當且僅當A, B為正整數且A和B沒有大于1的公因子。 樣例輸入 5 2** .* * ** . * * * * * * * 樣例輸出 7/16

這題真的做的人吐血.....本來DP已經寫的夠小心了，還要弄個高精才過的了...唉呀，不管了

只要注意細節，就可以通過.....

1.題目給出的是釘子的位置，但是我們要用到的空格，切每次球通過的路徑是釘子間的空隙，所以要相應的處理下。本人采用的是map[i,j]儲存的是（i,j）位置釘子的情況，f[i-1,j]儲存的是釘子(i,j)的通過的球的情況。

2.動態方程如下：

　f[i+1,j]:=f[i,j]+f[i+1,j];f[i+1,j+1]:=f[i,j]+f[i+1,j+1]; (if map[i,j]='*')

?? f[i+2,j+1]:=f[i,j]*4+f[i+2,j+1];(if map[i,j]='.')

3.記得加高精！

代碼如下：

?

??1?const?acc=10000;
??2?type
??3?????arra=record
??4????????????????da:array[0..30]of?longint;
??5????????????????l:longint;
??6?????end;
??7?var?i,j,n,m,q:longint;
??8?????map:array[0..50,0..50]of?char;
??9?????f:array[0..60,0..60]of?arra;
?10?????ch:char;
?11?????fm,t,z:arra;
?12?function?add(a,b:arra):arra;
?13?var
?14????c:arra;i:longint;
?15?begin
?16??????fillchar(c,sizeof(c),0);
?17??????if?a.l>b.l?then?c.l:=a.l?else?c.l:=b.l;
?18??????for?i:=1?to?c.l?do
?19??????????begin
?20???????????????c.da[i]:=c.da[i]+a.da[i]+b.da[i];
?21???????????????if?c.da[i]>=acc?then
?22??????????????????begin
?23???????????????????????inc(c.da[i+1]);
?24???????????????????????c.da[i]:=c.da[i]?mod?acc;
?25??????????????????end;
?26??????????end;
?27??????if?c.da[c.l+1]>0?then?inc(c.l);
?28??????add:=c;
?29?end;
?30?procedure?mult2(var?a:arra);
?31?var?i,k:longint;b:arra;
?32?begin
?33??????k:=0;
?34??????fillchar(b,sizeof(b),0);
?35??????b.l:=a.l;
?36??????for?i:=1?to?a.l?do
?37??????????begin
?38???????????????b.da[i]:=b.da[i]+a.da[i]*2;
?39???????????????if?b.da[i]>=acc?then
?40??????????????????begin
?41???????????????????????b.da[i]:=b.da[i]?mod?acc;
?42???????????????????????inc(b.da[i+1]);
?43??????????????????end;
?44??????????end;
?45??????if?b.da[b.l+1]<>0?then?inc(b.l);
?46??????a:=b;
?47?end;
?48?procedure?divid2(var?a:arra);
?49?var?i,k,t:longint;b:arra;
?50?begin
?51??????k:=0;
?52??????fillchar(b,sizeof(b),0);
?53??????b.l:=a.l;
?54??????for?i:=?a.l?downto?1?do
?55??????????begin
?56???????????????k:=k*acc+a.da[i];
?57???????????????if?k>=2?then
?58??????????????????begin
?59???????????????????????t:=k?shr?1;
?60???????????????????????b.da[i]:=t;
?61???????????????????????k:=k-(t?shl?1);
?62??????????????????end;
?63??????????end;
?64??????a:=b;
?65??????while?(a.da[a.l]=0)and(a.l>1)?do?dec(a.l);
?66?end;
?67?procedure?print(a:arra);
?68?var?i:longint;s:string;
?69?begin
?70??????write(a.da[a.l]);
?71??????for?i:=a.l-1?downto?1?do
?72??????????begin
?73???????????????str(a.da[i]+acc,s);
?74???????????????delete(s,1,1);
?75???????????????write(s);
?76??????????end;
?77?end;
?78?begin
?79??????
?80??????readln(n,m);
?81??????fillchar(f,sizeof(f),0);
?82??????f[0,1].da[1]:=1;f[0,1].l:=1;
?83??????for?i:=1?to?n?do
?84??????????begin
?85???????????????for?j:=1?to?i?do
?86???????????????????begin
?87????????????????????????read(ch);
?88????????????????????????while?(ch<>'*')and(ch<>'.')?do?read(ch);
?89????????????????????????map[i,j]:=ch;
?90???????????????????end;
?91???????????????readln;
?92??????????end;
?93??????for?i:=0?to?n-1?do
?94??????????begin
?95???????????????for?j:=1?to?i+1?do
?96???????????????????begin
?97????????????????????????if?map[i+1,j]='*'?then
?98???????????????????????????begin
?99????????????????????????????????f[i+1,j]:=add(f[i,j],f[i+1,j]);
100????????????????????????????????f[i+1,j+1]:=add(f[i,j],f[i+1,j+1]);
101???????????????????????????end
102????????????????????????else
103????????????????????????????begin
104?????????????????????????????????z:=add(f[i,j],f[i,j]);
105?????????????????????????????????z:=add(z,z);
106?????????????????????????????????f[i+2,j+1]:=add(z,f[i+2,j+1]);
107????????????????????????????end;
108???????????????????end;
109??????????end;
110?????t:=f[n,m+1];
111?????if?(t.l=1)and(t.da[1]=0)?then?writeln('0/1')
112?????else
113?????????begin
114??????????????q:=n;
115??????????????while?not(odd(t.da[1]))?and?not((t.l=0)and(t.da[1]=0))?do
116????????????????????begin
117?????????????????????????divid2(t);
118?????????????????????????dec(q);
119????????????????????end;
120??????????????fillchar(fm,sizeof(fm),0);
121??????????????fm.da[1]:=1;fm.l:=1;
122??????????????for?i:=1?to?q?do?mult2(fm);
123??????????????print(t);write('/');print(fm);writeln;
124?????????end;
125?end.

?

posted @ 2009-11-10 15:56 瀑布飛鷹 閱讀(...) 評論(...) 編輯 收藏 刷新評論刷新頁面返回頂部

公告

Copyright ?2019 瀑布飛鷹

轉載于:https://www.cnblogs.com/waterfalleagle/archive/2009/11/10/1599991.html

總結

以上是生活随笔為你收集整理的noi99钉子和小球 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。