Номер 4, страница 11 - гдз по информатике 10 класс учебник Котов, Лапо

4. Опишите последовательность действий для решения задачи «Волк, коза и капуста».

Однажды крестьянину понадобилось перевезти через реку волка, козу и капусту. У крестьянина есть лодка, в которой может поместиться, кроме самого крестьянина, только один объект — или волк, или коза, или капуста. Если крестьянин оставит без присмотра волка с козой, то волк съест козу; если крестьянин оставит без присмотра козу с капустой, коза съест капусту. Как крестьянину перевезти на другой берег и волка, и козу, и капусту в целости и сохранности?

Будет ли полученная последовательность действий алгоритмом? Какое свойство алгоритма не выполняется? Возможно ли переформулировать задачу так, чтобы аналогичная последовательность действий стала алгоритмом?

Последовательность действий для решения задачи:

1. Крестьянин перевозит козу на другой берег.

2. Крестьянин возвращается один.

3. Крестьянин перевозит на другой берег волка.

4. Крестьянин возвращается с козой.

5. Крестьянин перевозит на другой берег капусту.

6. Крестьянин возвращается один.

7. Крестьянин перевозит козу на другой берег.

Полученная последовательность действий не является алгоритмом.

Не выполняется свойство определённости (или детерминированности). На третьем шаге у крестьянина есть выбор: перевезти волка или капусту. Условие задачи не даёт однозначного указания, какой выбор сделать. Так как существует несколько вариантов правильных действий, нарушается требование однозначности каждого шага.

Да, возможно переформулировать задачу так, чтобы последовательность действий стала алгоритмом. Для этого необходимо добавить правило, устраняющее неоднозначность выбора. Например: «При наличии выбора, какой из двух объектов перевезти, следует выбирать тот, чьё название идёт раньше по алфавиту». В этом случае последовательность действий станет строго определённой.