/ Vijos / 讨论 / 分享 /

求救,NOIP2008初赛的一道题。

对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找,等概率情况下,查找成功的平均查找长度(平均比较次数)是()。

A.35/11 B.34/11 C.33/11 D.32/11 E.34/10

哪位神牛可以给点详细点的解释,我给你1000分悬赏(可以VJ没这功能)。。。

15 条评论

  • @ 2009-10-17 09:58:08

    LS,在rq上骂我们白痴是不好的!

  • @ 2009-10-17 09:52:55

    我一时打错了而已

    LS 错了 是’答案肯定是最长那个‘原理!

  • @ 2009-10-16 09:12:36

    答案非小数定理

    NOIP初赛不会太WS

    所以有了答案非小数定理

    只有C是整数

    故选C

  • @ 2009-10-15 19:24:47

    原来我来我的加法错了...

    您的语文啊...

  • @ 2009-10-15 18:32:59

    LZ我才是SB....

  • @ 2009-10-15 17:12:39

    .......

    话说我深深地发现原来我来我的加法错了。。

  • @ 2009-10-15 12:43:30

    楼主 够牛!我SB了。。。。

  • @ 2009-10-14 23:03:25

    ...

    选C啊~

  • @ 2009-10-14 22:54:42

    LZ= =

    我深深地被LZ的态度雷到了!!!

    就是模拟了..

    模拟每个树的比较次数 除一下- -

    PS:话说 赫敏是普及组?= =

    打击啊!!!

  • @ 2009-10-14 22:27:01

    {5,13,19,21,37,56,64,75,88,92,100}

    因为只跟顺序有关,为了简便一点把上面的数字换成1~11,这是等价的。

    你画一颗二叉树

    括号内表示二分的中点。

    [1..11] (6)

    [1..6](3) [7..11](9)

    [1..3](2) [4..6](5) [7..9](8) [10..11](10)

    下面省略不打了........

    然后把每个数找到它的次数数出来累加,次数就是中点等于那个数所在节点的深度。

    比如说2你在第3层找到的,那就是找到它的次数就是3。

    11个数你都数一下,总共33次,平均一下就是33/11。

  • @ 2009-10-14 17:44:22

    回复几位LS

    模拟之后是算不到答案才问你们,要是算得到还问你们?几个SB。

  • @ 2009-10-13 21:11:50

    同学们,我是普及组的...

  • @ 2009-10-13 21:09:46

    我也不会二分

    R.T

    我就会模拟。。。牛吧

  • @ 2009-10-13 20:39:02

    SB啊你

    二分都不会

  • @ 2009-10-13 18:13:55

    每个点的都算出来 。再次被自己朴素到了。。

  • 1