（应用数学专业论文）单目标搜索的最小平均长度：受限制模型.pdf

摘要 本文研究了搜索论中实验集受限制情况下从含有礼个元素的集合中找到唯一未知元 素的经典问题当元素集的概率分布是均匀分布时，该问题的目标是确定在最坏情况下用 序列算法找到未知元素的最小平均实验次数 第一章介绍了本文的研究背景及预备知识 第二章为单个天平受限制模型在该部分是从含有n 个硬币的集合中找到唯一重币 的经典问题，所用的实验装置为一个天平，这是对通常所研究的天平称重模型的推广当 硬币集的概率分布是均匀分布时，我们证明了最坏情况下用序列算法找到重币的最小平均 实验次数 第三章为( g + 1 ) 一维受限制模型在该部分是从含有n 个数的集合中找到唯一秘密数 的经典问题试验方式为问答方式当数集的概率分布是均匀分布时，我们证明了最坏情 况下用序列算法找到秘密数的最小平均实验次数这是对第二章内容的推广，使受限制模 型推广到更一般的情况，并从这种推广中得到解决这类问题的一般方法 关键词：搜索问题；重币；算法；平均长度；h u ，m o n 树 a b s t r a c t i nt h i sp a p e r ，w er e s e a f c ht h ep r o b l e mo ff i n d i n gau n k n o w ne l e m e n to u to fas e to f ne l e m e n t s i ti sac l a s s i c a lp r o b l e mi nt h ec o m b i n a t o r i a ls e a r c ht h e o r y t h ea i mo ft h e p r o b l e mi st of i n dt h eu n k n o w ne l e m e n tu s i n gt h el e a s tn u m b e ro ft e s t s b yt h el e n 昏h o fa na l g o r i t h m ，w em e a nt h el e a s tn u m b e ro ft e s t ss u 伍c e sf o rt h i sk i n do fa l g o r i t h mt o c o m p l e t et h es e a r c ht a s k i nc h a p t e r l ，w ei n t r o d u c et h er e s e a r c hb a c k g r o u n do ft h i sp a p e ra n da l s ot h ep r e l i m i n a r i e s c h a p t e r 2i st h ep a r to fm i n i m a la v e r a g ec o s to fs e a r c h i n gf o rac o u n t e r f e i tc o i n ：r e s t r i c t e dm o d e l i nt h i sp a r t ，t h et e s td e v i c eo fo u rm o d e li sat w o a r m sb a l a n c e ，w h i c hi s t h eg e n e r a l i z a t i o no fo n eb a l a n c et h a ti su s u a l l yu s e di ns e a r c hp r o b l e m s 、7 忆d e t e r m i n e t h el e n g t ho ft h ew o r s t c a s es e q u e n t i a la l g o r i t h mi nt h ea v e r a g ec a s ew h e nt h ep r o b a b i l i t y d i s t r i b u t i o no nt h ec o i ns e ti su n i f b r md i s t r i b u t i o n c h a p t e r 3i st h ep a r to fm i n i m a la e r a g ec o s to fs e a r c h i n gf b ra nu n k n o w ne l e m e n t ： ( q + 1 ) 一a r yr e s t r i c t e dm o d e l i nt h i sp a r t ，t h et e s tp r o c e s s i o ni sq u e i y i n ga n da n s w e r t h i s i 8t h eg e n e r a l i z a t i o no fc h a p t e r 2 ，a n d1 w ep r e s e n ta no p t i m a ls e q u e n t i a la l g o r i t h mr e q u i r i n g t h em i n i m a la v e r a g ec o s to fw e i g h i n g sw h e nt h ep r o b a b i l i t yd i s t r i b u t i o no nt h ec o i ns e ti s u n i f b r md i s t r i b u t i o n k e yw o r d s ：s e a r c hp r o b l e m ；ah e a v i e rc o i n ；a l g o r i t h m ；a v e r a g ec o s t ；h u m n a n t r e e 1 1 第一章总述 此外，在假设分布为均匀分布时，f 1 】中也确定出了序列算法在平均情况下所需的最少提 问次数 当实验装置为一个两臂天平时，1 1 中证明了受限制时在最坏情况下用序列算法找到 伪币所需的最少称重次数对于该问题，在第二章我们证明了当假设分布为均匀分布时， 序列算法在平均情况下所需的最少称重次数 对于任意的g ，如果e = 0 时，这相当于我们通常的( q + 1 ) 一维搜索模型在第三章我 们证明了当假设分布为均匀分布时，序列算法在平均情况下所需的最少提问次数 4 第二章单伪币搜索的最小平均长度：受限制模型 2 1 引言 在n 个硬币集合s 中有且只有一个重币，而其他它n l 枚硬币的重量都一样，通过 两臂天平称重来找出重币，那么怎样用最少的称重次数尽快找到这枚重币哪? 根据不同的 要求通常考虑两种算法：序列算法和预确定算法；而一个算法是否是最优的要往往从两个 角度来评判：最坏情形长度和平均长度现在关于这个模型一些好的结果已经被得到( 见 1 ，1 3 ，1 5 】等) 根据上述模型的特点，用4 ：b 表示一个试验集，其中4 ：b 表示分别放到天平两盘 的硬币，我们知道每次试验集的选取都必须满足川= l b i ( 否则此次试验将得不到任何信 息，见【1 】) 在 1 】中a i l ；i l e r 考虑了上述模型的受限制情况，即a l = i b ls ，l 1 ，是 一给定的常数，并且给出了对于最坏情形下的最优序列算法，同时指出设计对于平均长度 情况下的最优序列算法仍是个未知问题在本文中我们将考虑这样的受限制模型，并在假 设试验集中的元素的概率分布满足均匀分布时给出平均长度情况下的最优序列算法 假设s = 1 ，2 ，) 为n 个硬币的集合那么受限制模型的序列算法可以用一 个有n 个叶子的三维树t 表示，我们将用 ( 7 1 ) 表示该树的外部道路长度，用 c f ( ”) = m i n ( t ) 表示所有满足限制条件的可行树的外部长度的最小值那么平均称重次数的最小 值为三 f ( n ) = 1 5 掣这样我们要找平均长度最小的算法只需找到一棵外部长度为 型( n ) 的可行树，也就是说我们的目标就是对于所有整数三1 和n22 确定k ( n ) 的精确值 下面的三个定理便给出了该篇文章的主要结果( 一些没有定义的术语和符号将在其他 章节给出) ： 定理2 1 1 对于整数，如果3 茎 3 + 1 且2 扎3 ，那么 嗡( n ) ： h ( 卅1 ，( ”6 且2 1 ) 或( 2 甜”一1 且m = 3 曰， ih ( n ) ， 否则 定理2 1 2 对于整数f ，如果3 粤 3 ” 2 ) 或奇数) 5 第二章单伪币搜索的最小平均长度：受限制模型 6 危型( 扎) ： l 2 ”+ 2 日( 2 一u + 日n 一2 。十2 ) ，印，礼) q 1 ) 【咖2 = 礼+ 2 日婵) + 日( 礼一2 0 ) ， ，n ) q 2 喙：瞻篡篡篙：二 豢翟黑篡 i 妒3 ：住t t 2 + 朋+ 2 t 日( d + 日( n 一2 t ) ， ( ，n ) q 3 2 2术语与符号 用s = 1 ，2 ，礼) 表示开始时待测硬币的集合如果4 ，bcs ，anb = 0 且 1 4 i = l b i ( 否则此次试验将得不到任何信息，见【1 ) ，那么a ：b 称为一试验集一次试验 也是进行一次称重，即把a ，b 分别放在天平的左右两个盘中，那么该称重的反馈信息将 有三种情况：“左重”、“右重”、“平”( 分别用，= 一1 、，= 1 、，= 0 表示) 当，= 一1 时，集合a 比集合b 重，也就是说伪币在集合a 中； 当，= l 时，集合b 比集合a 重，也就是说伪币在集合b 中； 当厂= 0 时，集合b 和集合a 一样重，也就是说伪币在s a b 中 当做过一次试验a ：b ，将会得到一个反馈，根据反馈我们将得到下一步试验唯一的 搜索域s ( ，) 一般情况下，对于任意整数i21 ，s ( ，l ，2 ) 常用来表示做i 次试验得到 第二章单伪币搜索的最小平均长度：受限制模型 8 t 的根与叶子i 的距离一棵树丁的外部长度定义如下： n h ( t ) = m i ，丁) ( 2 1 ) t = l 我们令日( n ) = m i n ( ? ；，馨萋剖省露刍刍烈蔫帚鬟第一翌嚣霉繁争i ；一辇三鬟耋 薹j 再蕊薯! 誊螽i 一舅i 三i j ；建二襄羹霜鐾* 攀= s z 一蓼? 售黜荭裂釜 ”i 匿幽雾鞋蝼一璺 瓤糊蕊薰雕，亚“萼4 巍辈丕式组织：第2 节提出一些术语和符号，定理1 2 在第4 节中被证明 第3 节包含了一系列用来证明定理1 2 的引理 3 2术语和符号 设s = 1 ，2 ，礼) 是一个含有礼个数的初始集合如果acs ，i = o ，1 ，q ； ia l ，i = 1 ，2 ，q ；an 如= o ，i j ，那么a o ：a 。叫做一个试验集试验集 a o ：- ：山意味着这样的提问：“z 属于那一个a ，i = 0 ，l ，口? 一每次提问的反 馈必然是q + 1 个可能反馈中的一个：“z a o ”；“。j 4 1 ”；“z 也”( 分别 用，= o ；，= 1 ；，= q 表示) 当，= 0 时，秘密数在集合a o 中； 当，= 1 时，秘密数在集合a - 中； 一， 当，= q 时，秘密数在集合厶中 当我们从提问a o ：厶得到反馈，时，一个搜索域s ( ，) 就被反馈，唯一确定一 般地对任意整数i 1 ，在第i 次提问后搜索域s ( 丘，1 ) 由反馈序列 ，2 唯一确 定如果l s ，2 五) i = 1 ，那么s ( ，丘五) 叫做结束域。如果任意搜索域s ( 丘问 的下一次提问a o - ，：厶满足i a i p ，i = 1 ，2 ，q ，那么当前模型的这个序列算法被 叫 x 第二章单伪币搜索的最小平均长度：受限制模型 现在的模型是和h u m n a n 一问题有关的为了引用方便，在e q ( 2 2 ) 中，令q = 2 ，我 们现在给出日( n ) 的表达式： 日( n ) ：n l l 。9 3 n j + 掣1 ：n l l 。9 3 n j + 3 女+ 2 j ( 2 4 ) 根据引理2 3 1 ，可得到日( n ) 是 掣( n ) 的一个下界，也既是说，对于任意的整数礼2 和都有 c ( 礼) 2 日( n ) 这里我们同样定义丑( o ) = 日( 1 ) = o 引理2 3 2 对于任意的两个整数3 。墨n 3 十1 和d20 ，我们有 日m + 1 ) 一日( n ) ： u 0 9 3 n j + l 如果佗是偶数， ( 2 5 ) l1 1 0 9 3 州+ 2 ，如果钝是奇数 l 1 0 9 3 礼j + 1 日( 礼+ 1 ) 一日( n ) 1 1 0 9 3 礼j + 2 ( 2 6 ) d ( i l 0 9 3 叫+ 1 ) 丑( n + d ) 一j 了( 礼) d ( 【l 0 9 3 ( 礼+ d ) j + 2 ) ( 2 7 ) 日( n + 2 ) 一日( n ) ： 2 u 。9 3 扎j + 4 如果礼= 3 + 1 1 ( 2 8 ) i2 【l 0 9 3 佗j + 3 ，否则 日协十2 d ) 一日( ) sd ( u 0 9 3 + 2 d ) j + 3 ) ，如果n 是奇数 ( 2 9 ) 日。( 礼+ 2 d ) 一日( n ) d ( 2 l l 0 9 3 礼j + 3 ) ( 21 0 ) 证明：把n 表示为n = 3 。+ 2 七+ j 这里o 3 ，o 茎j 1 那么l = l l 0 9 3 礼j ( i ) 当n 为奇数时，易得j = o ，那么l l o g s n j = l l 0 9 3m + 1 ) j = l 因此 日( 礼+ 1 ) 一j 丁( n ) = ( n + 1 ) l + 3 七+ 2 一( n l + 3 南) = i l 0 9 3 叫+ 2 当礼为偶数时，易得j = 1 如果o 1 时，如果n = 3 “1 ，假设a ：b 是我们选的第一个试验，这里4 ，b cs ， 这时我们选取l a i = i b i = 3 。，那么，i c i = i s a b i = 3 。经过此次称重，对 于s ( ，) ，= 一1 ，1 ，o 可以得到三个结果搜索域s ( 一1 ) = a ，s ( 1 ) = b 和s ( o ) = e ，且 i a l ，i b i ，ic rj 1 - 也既是说，这时至少有一个好币可以应用则一定存在3 n 1 一可行树贮。， 对，霜，使得 ( 贮，) = 日( 1 a i ) ， ( 对) = 日( i b l ) ， ( 瑶) = 日“ej ) 因此 ( 丁) = 礼+ 危( 对) + ( 贮。) + 日( 碚) = 佗+ 3 工工+ 3 l 三+ 3 l l = 日( n ) 如果3 礼 3 “，令礼= 3 + 2 女+ j ，这里0s 3 ，0 茎j 1 我们分两种情 况讨论： 情况，c n 当o 2 3 l _ 1 时，假设a ：b 是我们选的第一个试验，这里 1 5 ) 6 r二，k刀邓蜗叭爪”赫瀛跚勰蕊 第二章单伪币搜索的最小平均长度：受限趔壅掣 a ，bcs ，这时我们选取l a i = 1 日i = 3 。一1 + 2 l ；j 3 6 ，那么，i g | = i s a b l = 3 一1 + 2 ( 一2 l ；j ) + j 茎3 。一1 + 2 + 1 3 。同理，经过此次称重，对于s ( ，) ，= 一1 ，1 ，o 可以 得到三个结果搜索域s ( 一1 ) = a ，s ( 1 ) = 口和s ( o ) = c ，且j a i ，i b i ，l a i 1 也既是说，这 时至少有一个好币可以应用则一定存在3 。1 一可行树贮。，矸，瑶，使得 ( 贮1 ) = 日( f a i ) ， ( 碍) = 丑引b 1 ) ，矗( 霹) = 日( 1 c i ) ，因此 ( t ) = 凡+ ( 珂) + ( 丁兰。) = n + 2 日( 3 + 2 l ； = 礼+ 2 ( ( 3 l 一+ 2 l ；j + 3 ( 七一2 l ；j ) + 2 j = 口( n ) 容易验证：t 是3 - 可行树 情况出剀当2 - 3 15 时 j g l = i s a b i = 3 一1 + 2 ( 一 同理可以得到 ( r ) = 札+ ( 霹) + 五( 贮1 ) = n + 2 3 l - l + ( 3 l 一 = 日( n ) + ( 习) j ) + 日( 3 。一，+ 2 ( 一2 l ；j ) + j ) ) ( l 一1 ) + 3 【；j ) + ( 3 l 。+ 2 ( 七一2 【；j ) + j ) ( l 一1 ) ，我们选取第一次试验a ：b 2 3 l 一1 ) + j 3 l 一1 + 2 ( 3 l 一1 使得i a i = | 口i = 3 ，那么 一1 ) + j = 3 l 一2 + j 3 l + 日( 露) 1 + 2 ( k 一2 ，3 。一1 ) + j ) ( l 一1 ) + 3 ( 一2 3 。一1 ) + 2 j 2 4 主要结果的证明 口 定理2 1 1 的证明 ( 1 ) 当礼= 6 且1 时，容易验证对于所有的d 可行树t ，都有 ( t ) = 1 2 = 日( 6 ) + l 见【1 ，p 8 2 ； 第二章单伪币搜索的最小平均长度：受限制模型 ( 2 ) 当n 3 “1 且n 6 时，一方面，对于任意整数都有，。掣( n ) 日( 礼) ；另一方 面，由引理2 3 6 和3 知 f ( n ) 3 。( n ) 日( n ) ( 3 ) 当3 。+ 1sn 3 时，令= 3 + 2 i + j 这里o i 3 。，o j 1 ；令 扎= 3 l + 1 + 2 七+ j ，0 j 1 佗s3 表明0 七3 七+ j 情况p u 当三o m o d ( 3 ) 或三2 m o d ( 3 ) 时，如果三o m o d ( 3 ) ，那么 = ； 如果三2 m o d ( 3 ) ，那么； = 字i 因此，我们选取第一次试验a ：b ，使得a ，bcs ， l a l = l b i = 3 l + 2 ； 3 l + 2 五s 3 l + 1 ，那么l g l = l s a b = 3 l + 2 ( 七一2 ； ) + j 3 + 1 当七一2 1 f ； si 3 和osj 墨1 时有引理2 3 6 ( 2 ) 得一定存在3 一可行 树贮。，矸，霜，使得 ( 贮，) = 日( i a i ) ， ( 矸) = 日( 吲) ， ( 瑶) = 日( i c i ) 那么可以得到 ( t ) = n + ( 碍) + 打( 贮，) + 日( 露) = n + 2 日( 3 。+ 2 罢 ) + 日( 3 。+ 2 ( 女一2 等 ) + j ) d u = 日( n ) 情况p 纠当七三1 m o d ( 3 ) 且 3 i + j 时，有l ；j = 学i 一1 第一次试 验我f 门选取i a | = i b l = 3 。+ 2 【j 3 。+ 2 i 3 + 1 ，那么i c l = i s a b i = 3 + 2 ( 一2 【；j ) + j = 3 + 2 ( 学+ 1 ) + j 墨3 。+ 2 i + j 3 。“有引理2 3 6 ( 2 ) 得一定 存在3 。一可行树贮。，研，霜，使得 ( 贮。) = 日( 1 a 1 ) ，h ( 霹) = 日( 1 b i ) ， ( 船) = 日( i e i ) 那 么可以得到 忍( t ) = n + ( 矸) + ( 贮。) + ( 瑶) = 佗+ 2 日( 3 。+ 2 l ；j ) + 日( 3 l + 2 ( 一2 l ；j ) + j ) = 日m ) 情况p 圳当兰1 m o d ( 3 ) 且= 3 + j 时，有j = 1 当i 3 一1 时，第一次试验我们选取l a l = l b i = 3 。+ 2 l ；j = 3 。+ 2 i 3 。+ 1 那么l e f = l s a b l = n 一2 ( 3 l + 2 i ；j ) = 3 l + 2 ( 七一2 而) + j = 3 l + 2 ( 后+ 1 ) + 歹 3 l + 1 有引理2 3 6 ( 2 ) 得一定存在3 一可行树贮。，砰，霜使得 ( 贮。) = 日( a 1 ) ， ( 研) = 日( i b i ) 和 ( 瑶) = 日( 1 g i ) 那么可以得到 ( 丁) = 礼+ ( 7 ) + 九( 丁兰。) + ( 了孑) = n + 2 日( 3 + 2 i ) + 日( 3 + 2 ( i + j ) + j ) 第二章单伪币搜索的最小平均长度：受限制模型 = 日( n ) 当月= 3 一1 和j = o 时，= 3 + 1 一l 且n = 3 。州一4 = 3 一1 第一次试验我们 选取l aj = i b f = 3 + 2 l ；j = 3 + 2 i = 3 。+ 1 2 3 + 1 ，则j g l = i s a b i = n 一2 ( 3 + 2 【；j ) = 3 。+ 2 ( 女一2 五) = 3 + 2 ( i + j ) = 3 + 1 有引理2 3 6 ( 2 ) 得一定存在 3 可行树贮。，研，霜使得九( 贮。) = 日( i a i ) ，九( 矸) = h ( i 引) ， ( 霹) = 日( | gj ) 那么可 以得到 ( t ) = n + ( 对) + ( 贮。) + ( 四) = n + 2 日( 3 。+ 1 2 ) + 日( 3 。+ 1 ) = 3 工+ 2 4 + 2 ( ( 3 l + 1 2 ) 工+ 3 ( 3 一1 ) ) + 3 工+ 1 ( 三+ 1 ) = 日m ) 当i = 3 。一1 和j = l 时= 3 + 1 一l 且他= 3 。十2 3 = 3 我们将证明 型( 礼) = 日( n ) + 1 为了证明h 型( 礼) 丑( n ) + 1 ，只需证明：对于任意含有n 个叶子的。 可行树t ，有 ( t ) 日( n ) + 1 即可用a ：b 表示丁的第一次称重，这里l a i = i b i = i ， 并用贮1 ，研，弼表示t 的子树，那么i 研i = i 贮。l = i ，i 对i = n 一2 i 因此 ( t ) = n + ( 对) + ( 贮1 ) + ( 霜) 礼+ 2 j 丁0 ) + j 丁( n 一2 i ) ( 2 2 0 ) 如果i 3 ( 一1 ) 和一1 为奇数时危( t ) 扎+ 2 h ( z 一1 ) + 日( 扎一2 + 2 ) = 3 l + 2 3 + 2 日( 3 l + 1 2 ) + 日( 3 工+ 1 + 1 ) = 日( n ) + 1 当i = ，由( 2 2 0 ) 知 ( t ) 礼+ 3 日( ) = 3 + 2 3 + 3 日( 3 。“一1 ) = h ( 礼) + 1 现在我们证明k f ( 佗) 日( 礼) + 1 这只需构造一棵d 可行树t 使它满足 ( t ) = 日( 礼) + 1 即可第一次试验我们选取a ：b ，使得f a l = j b i = 3 1 则l g i = 1 s a b l = 由引理2 3 6 ( 2 ) 知一定存在3 。一可行树贮，矸，霜使得h ( 贮。) = 日( 1 a f ) ， ( 对) = h ( | b 1 ) 和危( 瑶) = 日( 1 g 1 ) 那么可以得到 ( t ) = n + ( 贮1 ) + ( 贮。) + ( 瑶) = n + 3 日( ) = n + 3 日( 3 + 1 一1 ) = 日( n ) + 1 容易验证当3 。墨时，t 是0 可行的 口 推论2 4 1 对于任意3 3 。+ 1 使用，那么一定存在一棵含有n 个叶子的 和佗3 ，如果在试验开始时就有一好币可以 一可行树t 并且使得九( t ) = h ( 礼) 第二章单伪币搜索的最小平均长度：受限制模型 证明：由引理2 3 6 ( 2 ) 和定理2 1 1 ，我们只需要证明，该推论对于= 3 。“一1 且n = 3 时 成立即可选取第一次试验为a ：b u 矿，这里矿是事先已知的好币，使得i a l = 3 机， i b l = 一1 3 如果i = ，那么 2 日( i ) + 日( n 一2 i ) = 2 日( ) + 日一2 ) 兰a 1 ， 如果i l 一1 ，那么n 3 3 ( 一1 ) 并且z 一1 为奇数，由引理2 3 4 可得 2 日( i ) + 日( n 一2 i ) 2 日一1 ) + 日一2 + 2 ) 兰a 2 下面我们确定a = m i n a 。，a z ) 的具体数值明显的我们有： a 2 一a l = 2 ( 日( 一1 ) 一日( ) ) + ( 日( n 一2 + 2 ) 一日( n 一2 ) ) ( 2 2 2 ) 当3 。茎l 3 l + 1 且为偶数时，可得3 茎一1 3 “，i e ，l l o 踟一1 ) j = 三由 ( 2 5 ) 知 日( ) 一丑( 一1 ) = 【1 0 9 3 ( 1 1 ) j + 2 = l + 2 ( 2 2 3 ) 当n 一2 3 “一2 且为偶数时， 3 。 n 一2 3 “一1 因此 l l 0 9 3 ( 礼一2 + 2 ) j = l 由( 2 8 ) 知 日( n 一2 + 2 ) 一日( 礼一2 z ) = 2 l l 0 9 3 ( n 一2 ) j + 3 = 2 l + 3 ( 2 2 4 ) 第二章单伪币搜索的最小平均长度：受限制模型 再由( 2 2 3 ) 和( 2 2 4 ) 可得a 2 一a l ( 2 t + 1 ) p ，因此对于o i ，吐1 茎有m = n n j 0 2 l ( 2 t 一1 ) z 由引理2 3 5 知 壬( m ) = 西t l + t ( 礼一口 一。量1 一c t 1 ) + 日( 咒o i o 生1 一c t 1 ) 三( n n i n 生1 ) t t 2 + 甜+ ( 2 一2 ) 日( ) + 日( 礼一o i 一1 1 2 甜+ 2 功，那么可以得到 ( t ) = ( 佗一n i o 三- 1 ) t t 2 + 理+ ( 2 t 一2 ) 日( ) + 日( n n ；一n 1 1 2 甜+ 2 ) + t ( n ；+ o ! 1 ) + 月。( n i ) + 日( 。! 1 ) n t 一铲+ 删+ ( 2 t 一2 ) h ( g ) + 日( n n i n 三- l 一2 删+ 2 ) + 日( 口：) + h ( o 三_ 1 ) 我们再结合 ( t ) 的下界，根据和礼的具体值计算出日( 0 1 ) + 日( n ! ，) + 日( n 一口i n 二1 2 埘+ 2 f ) 的最小值 情况偿u 当为奇数时，可得到礼一2 艇+ 2 3 p 和o n i ，0 1 1 墨由引理2 3 。4 知日( o i ) + 日( n 1 1 ) + 日( n o i 一。! l 一2 醒+ 2 1 ) 2 日( f ) + 甘( n 一2 理) ，因此 ( t ) 礼t t 2 + 甜+ 2 t 日( ) + 丑( 礼一2 t ) = 妒3 ，n ) ( 2 2 7 ) 情况俾砂当为偶数时，可得到n 一2 棚+ 2 3 如果。 = o ! l = ，那么 日( n i ) + 日( ! 1 ) + 日( 礼一；一n ! l 一2 卯+ 2 1 ) = 2 日( f ) + 日( 几一2 t 1 ) 垒6 1 ； 如果( 8 i 茎一l 且。1 1 = ) 或者( 口! lsz 一1 ，o ：= g ) ，由引理2 ，3 3 知 日( o i ) + 何( o ! 1 ) + h ( n o i n ! l 一2 理+ 2 ) 日( ) + 日心一1 ) + 日( 礼一2 埘+ 1 ) 垒如； 如果n ，o ! ls 1 ，由引理2 34 知 h ( ；) + 日( 8 三1 ) + 日( n n ；口2 l 一2 埘+ 2 1 ) 2 日( 一1 ) + 日( n 一2 卯+ 2 ) 垒6 3 下面我们确定6 = m i n 西，如，如) 的值因3 3 + 1 且为偶数，所以3 s 2 1 3 。+ 1 ，i e ，i l 0 9 3 邸一1 ) j = i l 0 9 3 q = 工由( 2 5 ) 知 月( ) 一日( 一1 ) = l l 0 9 3 纠+ 2 = l + 2 ( 2 2 8 ) 当( 孽，佗) q 1 时，3 l 孽 九一2 埘 n 一2 艇+ 1s3 工+ 1 1 ，所以【l 0 9 3 ( n 一2 ) j = l l 0 9 3 ( n 一2 艇+ 1 ) j = 三由( 2 6 ) 知 日( n 一2 理+ 1 ) 一日( 礼一2 粤) 1 1 0 9 3 ( 礼一2 t 粤) j + 2 = l + 2 ， ( 2 2 9 ) 第二章单伪币搜索的最小平均长度：受垦制模型 j 丁( 礼一2 醒+ 2 ) 一日( 扎一2 删+ 1 ) sl l 0 9 3 ( n 一2 埘+ 1 ) j + 2 = l + 2 ， ( 2 3 0 ) 由( 2 2 8 ) 和( 2 2 9 ) 知如一6 1 o ；又由( 2 2 8 ) 和( 2 ，3 0 ) 知如一6 2 曼o ，所以d = m i n d 1 ，d 2 ，品) = 如，i e ， ( ，) 佗t t 2 孽+ 埘+ ( 2 t 一2 ) 日( 掣) + 2 日( 一1 ) + 日( 他一2 醒+ 2 ) = 妒1 当( ，n ) n 2 时，3 。 扎一2 棚 n 一2 醒+ 1 = 3 + 1 ，因此【l 0 9 3 ( n 一2 螂j = l l 0 9 3 ( n 一2 t + 1 ) j l = l 由( 2 6 ) 知 月( n 一2 醒+ 1 ) 一日( 几一2 t 粤) = l l 0 9 3 ( 礼一2 t 重) j + 1 = l + 1 日( 札一2 钳+ 2 ) 一日( n 一2 删+ 1 ) = 【1 0 9 3 ( 礼一2 删+ 1 ) j + 2 = 工+ 3 ( 2 3 1 ) ( 2 3 2 ) 由( 2 ，2 8 ) 和( 2 3 1 ) 知d 2 6 1 o ；又由( 2 2 8 ) 和( 23 2 ) 知6 2 一如 o ，所以d = m i n 6 l ，6 2 ，西) = 巧2 ，i _ e ， ( 丁) 礼t t 2 + 埘+ ( 2 t 一1 ) 日( 粤) + 7 一1 ) + 日( n 一2 醒+ 1 ) = 【p 2 当n 一2 醒3 l + 1 且f 偶数时，3 + 1 茎n 一2 埘 ( 2 ( t 一1 ) 一1 ) ，该假设表明 垂。一l ( m 一2 ) 2 ( m 一2 ) ( t 一1 ) 一( t 一1 ) 2 + 0 1 ) + 2 0 2 ) 日( 1 ) + 日( m 一2 甜+ 2 ) 结合( 2 1 9 ) ，我们可以得到： 西t ( m ) m t 一产+ 醒+ 2 0 1 ) 日( 1 ) + 日( m 一2 删+ 2 ) ， 这里要用到不等式c t 一2 2 ( t 一2 ) 口 引理2 3 6 门j 如果2 n 3 。+ 1 且札6 ，那么，一定存在一棵含有n 个叶子的 3 可行树t 并且日( t ) = 日( 礼) j 偿j 如果在试验开始时有一好币可以使用，那么对与所有的2 扎s3 。十1 整数礼，我 们都可以构造一棵含有n 个叶子的3 一可行树t