釘子和小球，形成了一個按照等差數列來排序的金字塔結構
總時間限制:1000ms 記憶體限制:65536kB
同學們，我們不妨回憶一下，我們在哪裡見到過這個圖形呢？？？(#^.^#)
好吧，就是以前老師上機率的時候呀。
描述有一個三角形木闆,豎直立放，上面釘着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
本題是典型的動态規劃問題。每一個小球面臨每一個“下落”都有3種不同的選擇：
1。來自(i-1,j-1)，來自左上方的“釘子”那麼目前又有一個球經過i行j列
2。來自 (i-1,j)，來自右上方“釘子”，那麼目前又有一個球經過i行j列
3。來自(i-2,j-1)沒有釘子的話，經過這個位置的小球不是來自“左上”“右上”格子因為“左上”和“右上”的釘子可能直接掉下去
也就是說，我們隻需要用if判斷每種情況然後用
遞歸算出3種不同的情況對應的機率然後加起來就可以了。可是問題來了：機率？怎麼表示？？我的想法是，一個球一共有2^n種下落的情況，我們把2^n作為分母，把某個位置（i行j列）可能經過的次數作為分子，就可以得出機率。
資料結構long long int a[60][60];//a[i][j]——有多少個球會經過第i行第j列的位置
int b[60][60];//整型數組b——記錄目前對應位置有沒有釘子
代碼及其算法說明#include<iostream>
#include<algorithm>
using namespace std;
long long int a[60][60];//a[i][j]——有多少個球會經過第i行第j列的位置
int b[60][60];//整型數組b——記錄目前對應位置有沒有釘子
int n;//n為等差數列的最後一行釘子數
int m;//可能落入的格子編号
int main(){
long long int ans=0; //ans表示可能的落入的分母值
char c;//c如果是*——釘子；c如果是。——沒東西
cin>>n>>m;
for(int i = 0;i < n;i++)
{//i記錄目前周遊的行數
for(int j = 0;j <= i;j++)
{//j記錄目前周遊的列數
cin>>c;
if(c=='.')
b[i][j]=1;//如果沒有釘子的話，就記錄目前的整形數組對應位置為1
else
b[i][j]=-1;//如果有釘子的話，就記錄目前的整形數組對應位置為-1
}
}
a[0][0]=1;
for( int i=1;i<=n;i++){
for( int j=0;j<=i;j++){
/*每一個位置(i,j)的球可能來自三個地方(如果存在)：(i-1,j-1),(i-1,j),(i-2,j-1),
遞歸算出三個地方的機率再加起來就行了。*/
if(j >= 0 && b[i-1][j-1] == -1) a[i][j]+= a[i-1][j-1];
//如果來自(i-1,j-1)
//那麼目前又有一個球經過i行j列
if(j != i && b[i-1][j] == -1) a[i][j]+= a[i-1][j];
//如果來自 (i-1,j)，
//那麼目前又有一個球經過i行j列
if(i >= 2 && j >= 1 && b[i-2][j-1] == 1) a[i][j] += a[i-2][j-1] * 4;
//如果來自(i-2,j-1)沒有釘子的話，經過這個位置的小球可能來自“左上”“右上”格子
//因為“左上”和“右上”的釘子可能直接掉下去
if(i==n) ans = ans + a[i][j];//分母為2^n個球
}
}
while(a [n][m] % 2 == 0&& a[n][m] != 0){
a[n][m] /=2;//如果可以約分就約分
ans /=2;
}
if(a[n][m]==0)
ans=1;//輸出為0/1的情況
cout<<a[n][m]<<"/"<<ans<<endl;
return 0;
}
1。我們十分循規蹈矩地運用了遞歸，十分循規蹈矩地運用了約分。
2。我在送出的過程中失敗了3次，一次4分，兩次8分，後來隻好借鑒網上的方法思路，才知道因為大數乘法産生的數太大了于是乎溢出了，要用long long int 才可以存儲。于是我把a數組和ans 都變為long long int 型
3。至于有沒有可以更進一步的地方，我覺得還是有的，比如這個算法必須單獨考慮0/1的情況，有沒有一個更好的算法可以不單獨考慮這一個情況呢？
最後：還是要說——算法改變世界！