Быки и коровы

(модификация задачи А.А. Суханова)

Компьютер и ребенок играют в следующую игру. Ребенок загадывает последовательность из четырех (не обязательно различных) цветов, выбранных из шести заданных. Для удобства будем обозначать цвета цифрами от 1 до 6. Компьютер должен отгадать последовательность, используя информацию, которую он получает из ответов ребенка.

Компьютер отображает на экране последовательность, а ребенок должен ответить (используя для ввода ответа клавиатуру) на два вопроса:

· сколько правильных цветов на неправильных местах;

· сколько правильных цветов на правильных местах.

Пример. Предположим, что ребенок загадал последовательность 4655. Один из возможных способов отгадать последовательность такой:

Написать программу, которая всегда отгадывает последовательность не более чем за шесть вопросов, в худшем случае - за десять.

Правильный выбор структур данных - это уже половина решения. Итак, структуры данных и процедура их инициализации.

Const Pmax=6*6*6*6;

Type Post=String[4];

Var A:array[1..Pmax] of Post;

B:array[1..Pmax] of boolean;

cnt:integer;{счетчик числа ходов}

ok:boolean;{найдено решение}

procedure Init;

var i,j,k,l:integer;

begin

for i:=1 to 6 do

for j:=1 to 6 do

for k:=1 to 6 do

for l:=1 to 6 do A[(i-1)*216+(j-1)*36+(k-1)*6+l]:= Chr(i+Ord(‘0’))+Chr(j+Ord(‘0’))+Chr(k+Ord(‘0’))+Chr(k+Ord(‘0’));

for i:=1 to Pmax do B[i]:=true;

cnt:=0;ok:=false;

end;

Поясним на примере идею решета. Пусть длина последовательности равна двум, а количество цветов - четырем. Ребенок загадал 32, а компьютер спросил 24. Ответ ребенка 1 0, фиксируем его в переменных kr (1) и bk(0).

Итак, было 16 возможных вопросов, после первого осталось четыре - работа решета. Функция, реализующая анализ элемента массива А, по значениям переменных kr и bk, имеет вид:

function Pr(a,b:Post;kr,bk:integer):boolean;

var i,x:integer;

begin

{проверка по “быкам”}

x:=0;

for i:=1 to 4 do if a[i]=b[i] then inc(x);

if x<>bk then begin Pr:=false;exit;end;

{проверка по “коровам”}

x:=0;

for i:=1 to 4 do if (a[i]<>b[i]) and (Pos(b[i],a)<>0) then inc(x);

if x<>kr then begin Pr:=false;exit;end;

Pr:=true;

end;

Логика - “сделать отсечение” по значению хода h.

procedure Hod(h:Post);

var i,kr,bk:integer;

begin

inc(cnt);write(cnt:2,’.’,h,’-’);

readln(kr,bk);

if bk=4 then begin ok:=true;<вывод результата>;end

else for i:=1 to Pmax do if B[i] and Not Pr(A[i],h,kr,bk) then B[i]:=false;

end;

Общая логика.

.....

begin

clrscr;

init;

hod(‘1223’);

while not ok do begin

hod(h);

end;

end.

Дальнейшая работа с задачей требует ответа на следующие вопросы:

· Зависит ли значение cnt от выбора первого хода? Установить экспериментальным путем.

· Как логика выбора очередного хода влияет на результат игры? Исследовать. Например, выбрать тот элемент А (соответствующий элемент В должен быть равен true), в котором количество несовпадающих цифр максимально.