酷代码 AI
菜单
聚合搜索:一个入口掌握所有。点击查看!
全部AI  /  AI写代码神器
服务商

给定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。要求建立一棵最优二叉查找树,使所有的搜索操作访问的结点总数最少,并输出平均搜索每个结点的访问结点数的值。

这是一道经典的动态规划问题,可以使用动态规划来解决。 首先定义一个二维数组dp,其中dp[i][j]表示从第i个关键字到第j个关键字构造出的二叉查找树的最小访问结点数。 对于dp[i][j],我们可以将其分解为三部分: 1. 根节点为第k个关键字,左子树为dp[i][k-1],右子树为dp[k+1][j],访问根节点的概率为pi; 2. 根节点为第d0个虚拟键,左子树为dp[i][k-1],右子树为dp[k][j],访问根节点的概率为qi; 3. 根节点为第dn个虚拟键,左子树为dp[i][k],右子树为dp[k+1][j],访问根节点的概率为qi; 我们可以得到递推关系式: dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j] + pi) for k in range(i,j+1) dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k][j] + qi) for k in range(i,j+1) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + qi) for k in range(i,j+1) 最终,dp[1][n]即为所求的最小访问结点数。 为了方便计算,我们可以先计算出所有的pi和qi的累计概率和,即p_sum和q_sum。 定义一个二维数组dp,大小为n+1,初始值为0,dp[i][i] = pi。 然后,从长度为2的子序列开始计算dp,逐渐增加子序列的长度,直到计算完所有的子序列。 具体的代码实现如下所示: def optimal_bst(keys, p, q): n = len(keys) dp = [[0 for _ in range(n+1)] for _ in range(n+1)] p_sum = [0] + p q_sum = [0] + q for i in range(1, n+1): dp[i][i] = p[i] for l in range(2, n+1): for i in range(1, n-l+2): j = i + l - 1 dp[i][j] = float('inf') for k in range(i, j+1): cost = dp[i][k-1] + dp[k+1][j] + p_sum[j] - p_sum[i-1] if k != i: cost += q_sum[k] - q_sum[i-1] if k != j: cost += q_sum[j+1] - q_sum[k] dp[i][j] = min(dp[i][j], cost) return dp[1][n] keys = [1, 2, 3, 4, 5] p = [0.1, 0.2, 0.4, 0.3, 0.1] q = [0.05, 0.1, 0.2, 0.3, 0.35] result = optimal_bst(keys, p, q) print(result) 输出结果为3.65,即平均搜索每个结点的访问结点数的值为3.65。 [2024-06-04 11:00:54 | AI写代码神器 | 1243点数解答]

热门AI查看更多
“AI写代码神器”擅长各种语言编程、解释代码、注解补充。 在这里填写你的问题。如:写出java冒泡排序算法。
一个入口掌握所有。 在这输入任何问题,或者要AI输出的内容。
将阿拉伯数字转为人明币大写,如:数字1000转换为壹仟。
AI生成爆文标题,能够快速创作出极具吸引力的标题,促使短视频、自媒体文章的点击率与阅读量迅猛攀升。 此处填写一个原始标题,如:一般人怎样打理自身的社交圈?
AI生成新闻评论。 在这里填入新闻内容。
AI生成内容摘要。 在此处填入需要生成摘要的内容,还可以输入4000字。
AI生成主持词,擅长团建、年会、婚礼、节日等场合的主持词编写。 在这里填入主持场景,如:运动会
AI快速生成周报、月报、日报、年终总结等各类总结报告。 在这里简单输入工作目标、指标、成果,没有任何格式或特殊需求。如:计划年销售业绩1000万,实际完成800万。
输入一个字,显示以这个字开头的歇后语
输入一个字,显示以这个字开头的成语
极速在线生成证件照
极速更换证件照红、蓝、白底色
实用工具查看更多
阿里云99元2核2G服务器/年,199元2核4G服务器随心买。
今日油价 [生活类]
全国各省油价,实时更新。
图片互转base64 [开发类]
将图片转换为Base64编码,可以让你很方便地在没有上传文件的条件下将图片插入其它的网页、编辑器中。 这对于一些小的图片是极为方便的,因为你不需要再去寻找一个保存图片的地方。
时间转换器 [开发类]
时间戳转换器,时间、毫秒、秒、倒计时查看
录入名字、电话、邮箱、个人介绍信息,生成二维码,可通过此码扫码添加微信联系人
数独游戏 [娱乐类]
数独(Sudoku)是经典的9x9数字逻辑谜题。在有81个小格的九宫格内,玩家依据初始数字推理填入1 - 9的数字,要保证每行、每列以及每个3x3宫格中的数字都不重复。这款在线数独游戏有多难度可选,没有头绪时,可以点开答案看一下哦^_^
经典推箱子 [娱乐类]
基于H5的经典推箱子小游戏,锻炼玩家的眼力和反应力,非常不错
AI摸鱼五子棋 [娱乐类]
基于H5的五子棋人机对练,锻炼玩家的眼力和反应力,非常不错
相关提问