Python实现：从互异关键字序列构造最优二叉查找树并求平均搜索结点数

```python import sys n_values = list(map(float, sys.stdin.readline().split())) d_values = list(map(float, sys.stdin.readline().split())) n = len(n_values) # Create a matrix to store the optimal costs cost_matrix = [[0] * (n + 1) for _ in range(n + 1)] # Create a matrix to store the probabilities prob_matrix = [[0] * (n + 1) for _ in range(n + 1)] # Calculate the cumulative probabilities for real keys cumulative_p = [0] * (n + 1) for i in range(1, n + 1): cumulative_p[i] = cumulative_p[i - 1] + n_values[i - 1] # Calculate the cumulative probabilities for dummy keys cumulative_q = [0] * (n + 1) for i in range(1, n + 1): cumulative_q[i] = cumulative_q[i - 1] + d_values[i - 1] # Dynamic programming approach to calculate the optimal cost matrix for l in range(1, n + 1): for i in range(0, n - l + 1): j = i + l prob_matrix[i][j] = cumulative_p[j] - cumulative_p[i] + cumulative_q[j] - cumulative_q[i] cost_matrix[i][j] = sys.maxsize for r in range(i, j): cost = cost_matrix[i][r] + cost_matrix[r + 1][j] + prob_matrix[i][j] if cost < cost_matrix[i][j]: cost_matrix[i][j] = cost # Print the average number of visits to nodes average_visits = round(cost_matrix[0][n], 2) print(average_visits) ``` 运行以上代码可以用于输入样例，输出样例中的测试数据。 ######[AI写代码神器 | 916点数解答 | 2024-06-09 19:52:43]