关于三个相同伪硬币问题的一些新结果.pdfVIP

维普资讯 应 用 数 学 MATHEMATICA APPLICATA 2007。20(4)：697~705 关于三个相同伪硬币问题的一些新结果 綦明男 (重庆文理学院数学与计算机科学系，重庆 402168) 摘要：本文中，给定一台比较型测试装置和确切的三个相同伪硬 币出现 的信息，作者研 究最小测试数的探求问题，这个最小测试数能从 个有 同样外观的硬 币组成的集合中 鉴别出三个相同的伪硬 币，这里 ≥4．作者构造 了对于无限多个 值的一个最优鉴别 分组测试算法，这个最优鉴别分组测试算法改进 了TO萄c的对于无限多个 值的一个最 优鉴别分组测试算法，也改进了Bognjak的对于无限多个 值的一个最优鉴别分组测试 算法．作者还提 出另一个鉴别分组测试算法，并且猜想这个算法是最优的． 关键词：伪硬币；最优分组测试过程；信息论下界；分组测试 ；标准硬币 中图分类号：O236；O232 AMS(2000)主题分类 ：O5A05；68Q25 文献标识码：A 文章编号 ：1001—9847(2007)04—0697—09 1．引言 分组测试是一个有很强实际背景的最优化问题，它也属于动态规划和组合数学的范畴．目 前，分组测试已广泛应用于象印刷 电路板测试 、图像压缩 、模式识别 、筛选 等等的工业 应用中．在分组测试理论中有一个共有的问题 ，经常要对若干个伪硬币有哪些信誉好的足球投注网站它的最优鉴别或挑 选分组测试算法 ，而有哪些信誉好的足球投注网站最优鉴别或挑选分组测试算法又是极为困难 的一项工作．Toglc[研 究了用一台天平从 个硬币中鉴N-个相同伪硬币的问题 ，他给出了对于无 限多个 值 的一 个最优鉴别分组测试算法 ，其中 一4·3，k≥2，k∈N．Bognjak[给出了对于 一3，2．3， k≥2，k∈N的一个鉴别三个相同伪硬币的最优鉴别分组测试算法．本文中，对三个相同伪硬 币，使用一台比较型测试装置 ，我们将构造一个对无限多个 值的一个最优鉴别分组测试算法 O，这无限多个 值组成的集合是 ： U【N([+1，2·3}卜+17uEm+1，3抖+1]uEm+1，4·3抖]))u[4，1o]u[13，14]， 这里[b( )]一3志+e，[。·()]一3k+s，[。·( )]3志+5， [。·g()]一3是+4，[。·g。()]一3是+4，[。·g()]一3忌+3，m，，，∈N，[户，g]表 * 收稿 日期 ：2007—03—20 基金项 目：国家 自然科学基金资助项 目 作者简介：綦明男，男 ，汉，山东，教授，博士，研究方向：组合最优化、组合有哪些信誉好的足球投注网站和动态规划 维普资讯 698 应 用 数 学 示大于等于P且小于等于q的所有整数．显然， {：一 4 ·3，k≥ 2，k∈N)，{：一 3 ，2 ·3 ，k≥ 2，k∈N) C(U([m+1，2·3抖+1]U[m+1，3抖+13U[m +1，4·3抖])) U [4，103U -[13，143． 这说明我们将构造的测试算法改进了Togic和Bognjak的测试算法．另外，我们还将给出 一 个对无限多个 值的一个鉴别分组测试算法O ，这无限多个 值组成的集合是 ：{：≥4， ∈N)，虽然 目前的分组测试理论还不能证明该算法是最优的，但我们通过对 的数值试验结 果分析，猜想这个算法 O是最优的． 2．一些定义和引理 除文中给出的符号和术语外，其它符号和术语参见专著[1Z3．符号X(h，一^)表示由 个硬币组成的集合，这个集合包含 由h 个伪硬币组成的非空子集H，其余 —h个硬币是 标准的． 定义 1 如果 X(h，一^)是 个硬币组成的集合 ，H是x的真子集并且非空，H中的硬 币称为伪硬币．A是由7l维有序组(A ，A ，…，A )所构成的集合 ，其中A ∈P(H)，i一 1，2， … ，7l，A NA，一 ，i≠ ，i，J一 1