在这段代码中，我正在使用catlan数字来计算唯一的Binary Search Trees的数目。直到输入值的答案仍然是正确n=13的n>=14答案原来由一个要少一些。例如。对于n=14我的答案是2674439，而实际的答案是2674440.这里是代码。
#include "stdafx.h"
#include "iostream"
using namespace std;
class Solution {
public:
double arr[20000] = {};
double fact(int n) {
if (n == 1 || n == 0)
return 1;
if (arr[n] != 0)
return arr[n];
return arr[n] = ceil(n*fact(n - 1));
}
int numTrees(int n) {
int res = fact(2 * n) / ((fact(n + 1))*fact(n));
return res;
}
};
int main()
{
Solution s;
cout << s.numTrees(14)<<endl;
return 0;
}
问题是此功能：
int numTrees(int n) {
int res = fact(2 * n) / ((fact(n + 1))*fact(n));
return res;
}
基本上，通过将double值转换为int会损失一些精度，因此无法获得正确的值。如果将其更改为两倍，问题将消失。
更正的功能：
double numTrees(int n)
{
double res = fact(2 * n) / ((fact(n + 1))*fact(n));
return res;
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句