作者：玫瑰花开-内蒙_238 | 来源：互联网 | 2023-02-10 07:41
原题是中文的，直接上链接。本文尤其注意(1<<N)这种写法，现在的编译器默认把1视为32位int（Google到这篇文章），而这道题目的金字塔最大可以达到50层，毫无疑问1
原题是中文的，直接上链接。
本文尤其注意(1<
分析金字塔每一层，从第0层到第N层看作一个组合展开式，如从第0层到第5层：
1
1 2 1
1 3 3 1
1 4 6 4 6
1 5 10 10 5 1
1 6 15 20 15 6 1
dp[i][j]表示第i层第j个数的值。规律是：每一个数 = 头上那个数+头上那个数的左边那个数。而有没有钉子会影响它的算法，每一个数处一个钉子，当有钉子时这个数会分成两份分别贡献给下一层的左右两个数，没有钉子时候全部贡献给下下层的一个数，具体见程序。
每一个格子的概率为格子里的数num/(1<
另外，约分的求法用辗转相除法求得最大公约数，之后分子分母同时除以这个最大公约数即可。我的代码如下：
1: #include
2: #include
3: using namespace std;
4: const int LEVEL_SIZE = 51;
5:
6: unsigned long long euclid(unsigned long long a, unsigned long long b)
7: {
8: if (a
9: {
10: unsigned long long temp = a;
11: a = b;
12: b = temp;
13: }
14: while(b)
15: {
16: unsigned long long temp = a % b;
17: a = b;
18: b = temp;
19: }
20: return a;
21: }
22:
23: int main()
24: {
25: bool hasNail[LEVEL_SIZE][LEVEL_SIZE];
26: unsigned long long dp[LEVEL_SIZE][LEVEL_SIZE];
27: int level=0, m=0;
28: cin >> level >> m;
29: if (level<2 || level>50 || m<0 || m>level)
30: return -1;
31: memset(hasNail, false, sizeof(hasNail));
32: memset(dp, 0, sizeof(dp));
33:
34: dp[0][0] = 1;
35: char c;
36: cin >> c;
37: if (c=='*')
38: {
39: hasNail[0][0] = true;
40: dp[1][0] = dp[1][1] = 1;
41: }
42: for (int i=2; i<=level; i++)
43: {
44: for (int j=0; j
45: {
46: cin >> c;
47: if (c=='*') hasNail[i-1][j] = true;
48: }
49: if (hasNail[i-1][0])
50: dp[i][0] += dp[i-1][0];
51: for (int j=1; j<=i; j++)
52: {
53: if (hasNail[i-1][j-1]) dp[i][j] += dp[i-1][j-1];
54: if (hasNail[i-1][j]) dp[i][j] += dp[i-1][j];
55: if (!hasNail[i-2][j-1])
56: dp[i][j] += (dp[i-2][j-1]<<2);
57: }
58: }
59:
60: if (dp[level][m]==0)
61: cout <<"0/" <<((unsigned long long)1<
62: else
63: {
64: unsigned long long numerator = dp[level][m];
65: unsigned long long denominator=((unsigned long long)1<
66: unsigned long long temp = euclid(numerator, denominator);
67: cout <'/' <
68: }
69: return 0;
70: }
京公网安备 11010802041100号