Оптимальное поведение отгадывающего в точности повторяет схему бинарного поиска. Сначала надо предложить число, расположенное в середине интервала, т. е. N/2. Затем, сузив интервал поиска вдвое, повторить аналогичный маневр. Попадание в цель произойдет не более чем через log2N шагов.
Приведенные ниже тексты программ реализуют оптимальную тактику отгадывания чисел из диапазона [0,100], затрачивая на это не более 7 шагов. На вопросы программы загадавший должен нажимать клавишу Y или у (в случае положительного ответа) или любую другую клавишу, если вопрос программы не соответствует загаданному числу.
Программа 4_02.bas
'Программа угадывания задуманного числа в интервале [0,100]
DEFINT A-Z
CLS
LEFT=0: RIGHT=100:
DO
MIDDLE=(LEFT+RIGHT)\2
PRINT "Задуманное Вами число больше, чем"; MIDDLE; " (Y/N) - ";
INPUT "",A$
IF RIGHT-LEFT <= 1 THEN
IF A$="Y" OR A$="y" THEN
PRINT "Вы задумали ";RIGHT: END
ELSE
PRINT "Вы задумали ";LEFT: END
END IF
END IF
IF A$="Y" OR A$="y" THEN LEFT=MIDDLE+1 ELSE RIGHT=MIDDLE
LOOP
END
Программа 4_02.с
/* Программа угадывания задуманного числа в интервале [0,100] */
#include <stdio.h>
#include <conio.h>
main ()
{
int left=0, right=100, middle, ok;
char ch;
clrscr();
for (;;)
{
middle={left+right)/2;
printf("\n Задуманное Вами число больше, чем % d (Y/N) - ", middle);
ch=getche();
if(right-left <= 1)
if (ch=='Y' || ch == 'y') { ok=right; break; }
else { ok=left; break;}
if(ch=='Y' II ch== 'y') left=middle+l;
else right=middle; }
printf("\пВы задумали %d",ok); getch(); }
Программа 4_02.pas
{ Программа угадывания задуманного числа в интервале [0,100] }
uses Crt;
var
ch: char;
left, right, middle, ok: byte;
begin
left:=0;
right:=100;
clrscr;
repeat
middle := (left + right) div 2;
write('Задуманное Вами число больше, чем ',middle,' (Y/N) - ');
ch:=readkey;
writeln(ch);
if (right-left <= 1) then
if (ch='Y') or (ch = 'y') then begin ok:=right;
break;
end else begin ok:=left;
break;
end; if(ch='Y') or (ch='y') then left := middle + 1
else right := middle;
until false;
writeln('Вы задумали ',ok);
readln;
end.