PHP Catalan数のいくつかの応用
7684 ワード
1 <?php
2 # ，
3 # catalan
4 # n ， 2n
5 # ， 2i+1
6 # 0， 2i， 2i-1 ，
7 # ， ，
8 # ， ， f(2n) n
9 # f(2n) = f(0)f(2n-2) + f(2)f(2n-4) + ... + f(2n-2)f(0)
10 #f(i)f(2n-i-2) i ， 2n-i+2
11 # f(2) = 1, f(4) = 2 ...
12
13 #n n
14 function count_pop($n) {
15 # 0 ，
16 if ($n <= 1) return 1;
17 $sum = 0;
18 for ($i = 0; $i < $n; $i++) {
19 $sum += count_pop($i) * count_pop($n - 1 - $i);
20 }
21
22 return $sum;
23 }
24
25 echo count_pop(4);
26
27 #
28 # n
29 # 2 ()(),(())
30 # catalan
31 # a， 1， 2i+1，
32 # f(n) n ，
33 #f(n) = f(0)f(n-1) + f(1)f(n-2) + ... + f(n-1)f(0)
34 # f(i)f(n-1-i) i ， n-1-i
35 #
36
37 #
38 # 2n 。 5 。 n 5 ， n 10
39 # ， 10 ， 5
40 # 5 ，10 ，
41
42 # n ， ，
43 # 1 2
44 # / \ / \
45 # 2 3 1 3
46 # 1 2
47 # / \ /
48 # 2 3 1
49 # /
50 # 3
51
52 # catalan ， f(n) n
53 # f(n) = f(0)f(n-1) + f(1)f(n-2) + ... + f(n-1)f(0)
54 #f(i)f(n-1-i) i ， n-i-1
55 # ，
56 ?>