Быки и коровы

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

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

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

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

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

Компьютер Ответ ребенка 1234 1 0 5156 2 1 6165 2 1 5625 1 2 5653 1 2 4655 0 4

Пример. Предположим, что ребенок загадал последовательность 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).

A	B	B (после анализа bk)	B (после анализа kr)	Результат
	true		false	false
	true			true
	true		false	false
	true	false		false
	true	false		false
	true	false		false
	true	false		false
	true	false		false
	true		false	false
	true			true
	true		false	false
	true	false		false
	true			true
	true		false	false
	true			true
	true	false		false

Итак, было 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), в котором количество несовпадающих цифр максимально.

Дата добавления: 2014-11-28