座標平面上,當螞蟻在 (a, b) 時,他可隨機移動到點 (a-1, b)、(a, b-1)、或 (a-1, b-1) 之中的一點,且移動到上述任一點的機率均為 1/3,接下來每次移動都與前次移動無關。現在有一隻螞蟻從 (x, y) 開始移動,直到他第一次遇到任意座標軸即停止移動,請問此螞蟻最後一次停止的點不是在原點 (0, 0) 機率為何?
範例測資
範例輸入 | 範例輸出 |
---|---|
EOF 輸入,每筆測資輸入兩正整數 x 和 y (x, y <= 10) | 答案以最簡分數表示,輸出「分子/分母」 |
3 3 2 2 1 1 | 70/81 22/27 2/3 |
解題思路
因為使用分數較難運算,所以可以將原點的機率 (也就是100%或1) 乘以 3 的 a + b 次方。可以使用二維陣列來存每個點的移動機率,使用 雙For迴圈 將每個點都走過一遍。答案的分子就是原本的點 = (0, 0) 的機率,分母就是原來的點的機率。最後將分數約分到最簡分數再輸出即可。
範例程式碼-ZeroJudge M283: 螞蟻的擴散
#include <iostream>
#include <math.h>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int x, y;
while (cin >> x >> y)
{
long long int arr[20][20] = {0};
long long int og = pow(3, x+y);
arr[y][x] = og;
for (int yy = y; yy>0; yy--)
{
for (int xx = x; xx>0; xx--)
{
long long int tmp = arr[yy][xx] / 3;
arr[yy-1][xx] += tmp;
arr[yy][xx-1] += tmp;
arr[yy-1][xx-1] += tmp;
}
}
long long int up = og - arr[0][0];
long long int down = og;
bool stop = false;
while (!stop)
{
stop = true;
for (long long int i = 2; i<=sqrt(up)+1; i++)
{
if (up % i == 0 && down % i == 0)
{
up /= i;
down /= i;
stop = false;
}
}
}
cout << up << "/" << down << "\n";
}
}
//ZeroJudge M283
//Dr. SeanXD