给定n个互异的关键字组成的序列k=<k1,k2,...,kn>，且关键字有序（k1<k2<...<kn），从这些关键字中构造一棵二叉查找树。对每个关键字ki，每次搜索到的概率为pi。还有n+1个“虚拟键”d0,d1,...,dn，他们代表不在k的值。d0代表所有小于k1的值，dn代表所有大于kn的值，对于i = 1,2,...,n-1,虚拟键di代表位于ki和ki+1之间的值。对于每个di，每次搜索di的概率为qi。要求建立一棵最优二叉查找树，使所有的搜索操作访问的结点总数最少，并输出平均搜索每个结点的访问结点数的值。 输入描述 第一行n个实数p1,p2...pn， 表示k1,k2,...kn搜索到的概率。 第二行n+1个实数d0,d1,...dn, 表示 n+1个虚拟键搜索到的概率。 输出描述 一个实数，表示平均搜索每个结点的访问结点数的值。 输入样例 0.15 0.1 0.05 0.1 0.2 0.05 0.1 0.05 0.05 0.05 0.1 输出样例 一个实数，保留两位小数结果值。

解题思路： 最优二叉查找树问题可用动态规划求解。设e[i][j]表示构造关键字ki到kj的最优二叉查找树的最小代价，w[i][j]表示构造关键字ki到kj的查找树中关键字的概率之和。则有以下递推关系式： e[i][i] = qi+di，当j=i时，构造只有一个结点的查找树，代价就是该结点的概率。 e[i][j] = min{e[i][r-1]+e[r+1][j]+w[i][j]}，当j>i时，假设k(r)是关键字ki,...,kj中的根，那么只需找到使得代价最小的根。 根据以上递推关系式，可以用动态规划求解e[i][j]，并得到最优二叉查找树的最小代价和平均搜索每个结点的访问结点数。 具体实现： 1. 读取输入的关键字概率和虚拟键概率。 2. 初始化二维数组e和w，将主对角线e[i][i]和w[i][i]的值设置为关键字概率和虚拟键概率。 3. 使用两个for循环计算e[i][j]和w[i][j]，外层循环控制i和j的范围，内层循环计算e[i][j]和w[i][j]的值。 4. 输出最优二叉查找树的平均搜索每个结点的访问结点数，即e[1][n]的值。 代码实现如下： #include <iostream> #include <vector> #include <iomanip> using namespace std; double optimalBinarySearchTree(vector<double>& p, vector<double>& q) { int n = p.size(); vector<vector<double>> e(n + 2, vector<double>(n + 1, 0)); // 存储最优二叉查找树的代价 vector<vector<double>> w(n + 2, vector<double>(n + 1, 0)); // 存储概率之和 for (int i = 1; i <= n + 1; i++) { e[i][i - 1] = q[i - 1]; w[i][i - 1] = q[i - 1]; } for (int l = 1; l <= n; l++) { for (int i = 1; i <= n - l + 1; i++) { int j = i + l - 1; e[i][j] = INT_MAX; w[i][j] = w[i][j - 1] + p[j] + q[j]; for (int r = i; r <= j; r++) { double t = e[i][r - 1] + e[r + 1][j] + w[i][j]; if (t < e[i][j]) { e[i][j] = t; } } } } return e[1][n]; } int main() { vector<double> p = {0.15, 0.1, 0.05, 0.1, 0.2}; vector<double> q = {0.05, 0.1, 0.05, 0.05, 0.05, 0.1}; double result = optimalBinarySearchTree(p, q); cout << fixed << setprecision(2) << result << endl; return 0; } [2024-06-09 14:30:32 | AI写代码神器 | 1311点数解答]