ULAM SEARCHING GAME WITH 2 LIES

被引：28

作者：

GUZICKI, W

机构：

[1] Mathematics Institute, University of Warsaw, 00-901 Warsaw, PKiN, IXp

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES A | 1990年 / 54卷 / 01期

关键词：

D O I：

10.1016/0097-3165(90)90002-E

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We determine the minimal number of yes-no queries sufficient to find an unknown integer between 1 and n if at most two of the answers may be erroneous. This solves completely the problem of Ulam on searching with two lies, partially solved by Czyzowicz, Mundici, and Pelc. Their solution applied only to the case when n is a power of 2. © 1990.

引用

页码：1 / 19

页数：19

共 10 条

[1]

Berlekamp E. R., 1968, Error correcting codes, P61

[2] SOLUTION OF ULAMS PROBLEM ON BINARY SEARCH WITH 2 LIES [J].