首页 > 试题广场 >

假设在某程序中有如下一个if-then嵌套的语句 if(C1

[问答题]
假设在某程序中有如下一个if-then嵌套的语句
if(C1)
if(C2)
if(C3)
…
if(Cn)
S;
其中Ci为布尔表达式。显然，只有当所有的Ci都为TRUE时，语句S才能执行。假设t(i)为判别Ci是否为TRUE所需时间，p(i)为Ci是TRUE的概率，试讨论这n个布尔表达式Ci (i=1,2,…,n)应如何排列才能使该程序最有效地执行?
添加回答
推荐
赞花婆头像 赞花婆
应该先列出该语句执行时间的期望值。
假设语句S的执行时间为T，则该语句执行时间的期望值为
T=(1-p(1)t(1)+p(1)(1-p(2))(t(1)+t(2)+…
+p(1)p(2)…p(n-1)(1-p(n))(t(1)+t(2)+…
+t(n)+p(1)(2)…p(n)(t(1)+t(2)…t(n)+t)
令p(0)=1,则上式可写为

可以证明：当这n个布尔表达式Ci的排序满足
时将使T达到极小值，则若依
从小至大的次序来排列，将使该语句的执行最有效。
发表于 2018-03-25 09:50:35 回复(0)
提交观点

问题信息

排序
上传者：赞花婆
难度：
1条回答 1465浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号