c++ 查找后序BST排列数

lnlaulya  于 2023-11-19  发布在  其他
关注(0)|答案(2)|浏览(90)

我正在处理一个问题,它说:找到从1到n的BST排列(postorder 遍历)。例如,对于n = 3:我们有6!- 1 = 5个排列,因为(3 1 2)不是BST postorder。
我为此写了一个算法,例如n = 4:
x1c 0d1x的数据
总共有3!+2!+2!+3!= 16
我写了这段代码,使用这个算法来计算从1到n的排列数:

int calcPerm(int n)
{
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        sum += (fact(n-1-i) * fact(i));
    }
    return sum;
}

字符串
我知道一些n,1 <= n <= 20它给了我一个错误的答案,我不知道为什么它不工作。任何帮助将不胜感激。

dpiehjr4

dpiehjr41#

factory在32位整数的范围外增长得很快。但是退一步说,那个公式(算法)是不正确的。你写:
为此写了一个算法,例如n = 4:[...]总共有3!+2!+2!+3!= 16
但是16不是<$4的正确结果,应该是14。𝑛
以下是所有可能的后序的表格,以及它们是否可以成为BST:
| 后序|有效BST?|
| --|--|
| 1 2 3 4 |是的|
| 1 2 4 3 |是的|
| 1 3 2 4 |是的|
| 1 3 4 2 |没有|
| 1 4 2 3 |没有|
| 1 4 3 2 |没有|
| 2 1 3 4 |是的|
| 2 1 4 3 |是的|
| 2 3 1 4 |是的|
| 2 3 4 1 |是的|
| 2 4 1 3 |没有|
| 2 4 3 1 |是的|
| 3 1 2 4 |没有|
| 3 1 4 2 |是的|
| 3 2 1 4 |是的|
| 3 2 4 1 |是的|
| 3 4 1 2 |没有|
| 3 4 2 1 |是的|
| 4 1 2 3 |没有|
| 4 1 3 2 |是的|
| 4 2 1 3 |没有|
| 4 2 3 1 |没有|
| 4 3 1 2 |没有|
| 4 3 2 1 |是的|
因此,尽管你的算法在< 4时给出了正确的结果,但从4开始,它开始超过预期的结果。𝑛

Catalan数

可以描述BST的后序数实际上对应于一个具有10个节点的二叉树可以具有的 * shape * 的数量。一旦树的 shape 建立,只有一种方法可以用给定的数字标记节点,这样它就可以是BST。因此,这也唯一地对应于后序数。
二叉树的形状数由Catalan数给出。
我们可以使用增量公式来计算其中的前21个,对于x1= 20,结果是6,564,120,420。int没有足够的范围,所以应该使用long
代码:

#include <iostream>
#include <vector>

std::vector<long> getCatalans(const int n) {
    std::vector<long> results = {1};
    long c = 1;
    for (int i = 1; i <= n; ++i) {
        c = 2*(2*i - 1) * c / (i + 1);
        results.push_back(c);
    }
    return results;
}

int main() {
    std::vector<long> catalans = getCatalans(20);
    for (int n = 1; n <= 20; n++) {
        std::cout << n << ". " << catalans[n] << std::endl;
    }
}

字符串
输出量:

1. 1
2. 2
3. 5
4. 14
5. 42
6. 132
7. 429
8. 1430
9. 4862
10. 16796
11. 58786
12. 208012
13. 742900
14. 2674440
15. 9694845
16. 35357670
17. 129644790
18. 477638700
19. 1767263190
20. 6564120420

qzwqbdag

qzwqbdag2#

仅供参考,节点编号为1到n(包括1和n)的BST的数量由第n个Catalan数给出:


的数据
来源:https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1214/sections/section8/

#include <iostream>
#include <vector>

unsigned long long CatalanRecursive(unsigned int n) {
  if (n <= 1) return 1;
  unsigned long long res = 0;
  for (unsigned int i = 0; i < n; i++)
    res += CatalanRecursive(i) * CatalanRecursive(n - i - 1);
  return res;
}

unsigned long long CatalanDynamicProgramming(unsigned int n) {
  std::vector<unsigned long long> catalan(n + 1, 0);
  catalan[0] = catalan[1] = 1;
  for (unsigned int i = 2; i <= n; i++)
    for (unsigned int j = 0; j < i; j++)
      catalan[i] += catalan[j] * catalan[i - j - 1];
  return catalan[n];
}

int main() {
  unsigned int n = 3;
  std::cout << "CatalanRecursive(" << n << ") = " << CatalanRecursive(n) << '\n';
  std::cout << "CatalanDynamicProgramming(" << n << ") = " << CatalanDynamicProgramming(n) << '\n';
  n = 4;
  std::cout << "CatalanRecursive(" << n << ") = " << CatalanRecursive(n) << '\n';
  std::cout << "CatalanDynamicProgramming(" << n << ") = " << CatalanDynamicProgramming(n) << '\n';
  n = 5;
  std::cout << "CatalanRecursive(" << n << ") = " << CatalanRecursive(n) << '\n';
  std::cout << "CatalanDynamicProgramming(" << n << ") = " << CatalanDynamicProgramming(n) << '\n';
  return 0;
}

字符串

输出:

CatalanRecursive(3) = 5
CatalanDynamicProgramming(3) = 5
CatalanRecursive(4) = 14
CatalanDynamicProgramming(4) = 14
CatalanRecursive(5) = 42
CatalanDynamicProgramming(5) = 42

相关问题