угловая клетка как 2, остальные клетки имеют числа доступности 3, 4 или 6 в соответствии с таблицей:

23444432 34666643 46888864 46888864 46888864 46888864 34666643 23444432

Теперь напишите вариант программы Путешествие Коня, используя эвристику доступности. В любом случае конь должен ходить на клетку с наименьшим числом доступности. В случае равенства чисел доступности для разных клеток конь может ходить на любую из них. Таким образом, путешествие можно начать в любом из четырех углов. (Замечание: По мере перемещения коня по доске ваша программа должна уменьшать числа доступности тем больше, чем больше клеток оказываются занятыми. Таким образом, в каждый данный момент путешествия число доступности каждой имеющейся в распоряжении клетки будет делаться равным количеству клеток, из которых можно пойти на данную клетку.) Выполните эту версию вашей программы. Смогли ли вы совершить полное путешествие? Теперь модифицируйте программу для выполнения 64 путешествий, каждое из которых начинается со своей клетки шахматной доски. Сколько полных путешествий удалось сделать?

d) Напишите версию программы Путешествие Коня, которая при встрече с двумя или более альтернативными клетками с равными числами доступности решала бы, какую клетку выбрать, просматривая вперед достижимость клеток из этих альтернативных клеток. Ваша программа должна ходить на клетку, для которой следующий ход достигал бы клетки с наименьшим числом доступности.

4.25. (Путешествие коня: методы решения в лоб ) В упражнении 4.24 вы разрабатывали решение задачи о Путешествии Коня. Использованный подход, названный эвристикой доступности , генерирует множество решений и работает эффективно.

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

a) Используйте генерацию случайного числа для предоставления коню возможности ходить по шахматной доске случайным образом (конечно, только допустимыми для коня ходами). Ваша программа должна запускать путешествие и печатать окончательный вид шахматной доски. Насколько далеко смог пойти конь?

b) Наиболее вероятно, что предыдущая программа совершит относительно короткое путешествие. Теперь модифицируйте вашу программу так, чтобы она сделала 1000 попыток путешествия. Используйте одномерный массив для регистрации количества путешествий каждой длины. По окончании 1000 попыток путешествия программа

******** **

* ♦

Рис. 4.26. 22 клетки, исключаемые при размещении ферзя в верхней левой клетке

должна напечатать эту информацию в строгом табулированном формате. Каков наилучший результат?

c) Наиболее вероятно, что предыдущая программа даст вам несколько приличных , но не полных путешествий. Теперь проигнорируйте все остановы и просто позвольте вашей программе выполняться до получения полного путешествия. {Предупреждение: эта версия программы может выполняться часами даже на мощном компьютере.) Снова заведите таблицу для регистрации количества путешествий каждой длины и напечатайте эту таблицу, как только будет выполнено первое полное путешествие. Сколько путешествий попыталась совершить программа перед выполнением полного путешествия? Сколько времени это заняло?

d) Сравните жесткий силовой вариант Путешествия Коня с вариантом эвристики доступности. Какой из них требует более тщательного изучения проблемы? Разработка какого алгоритма более трудна? Какой из них требует более высокой мощности компьютера? Могли бы вы заранее быть уверенным в выполнении полного путешествия на основе эвристики доступности? Могли бы вы заранее быть уверенным в выполнении полного путешествия на основе жесткого силового подхода? Аргументируйте доводы за и против методов решения проблемы в лоб вообще.

4.26. {Восемь Ферзей) Другой шахматной головоломкой является задача о Восьми Ферзях: можно ли поставить на пустой шахматной доске восемь ферзей так, чтобы ни один из них не атаковал другого, т.е. никакие два ферзя не стояли бы на одном и том же столбце или на одной и той же строке или на одной и той же диагонали? Используйте размышления, приведенные в упражнении 4.24, чтобы сформулировать эвристику для решения задачи о Восьми Ферзях. Запустите вашу программу. {Совет: можно присвоить значение каждой клетке шахматной доски, указывая, сколько клеток пустой шахматной доски исключается , если ферзя поместить на эту клетку. Каждому углу должно быть присвоено значение 22, как на рис. 4.26.) Как только эти числа исключения будут присвоены всем 64 клеткам, можно предложить эвристику: ставить каждого следующего ферзя на клетку с наименьшим числом исключения. Почему эта стратегия интуитивно привлекательна?

4.27. (Восемь ферзей: методы решения в лоб ) В этом упражнении вы будете развивать методы решения в лоб задачи о Восьми Ферзях, с которой вы познакомились в упражнении 4.26.

a) Решите задачу о Восьми Ферзях, используя технику случайного лобового подхода, развитую в упражнении 4.25.

b) Используйте исчерпываюш;ий лобовой подход, т.е. попробуйте все возможные комбинации восьми ферзей на шахматной доске.

c) Почему вы полагаете, что исчерпываюш;ий лобовой вариант может не подойти для решения задачи о Восьми Ферзях?

d) Сравните и сопоставьте случайный лобовой подход и исчерпывающий лобовой подход в целом.

4.28. (Путешествие Коня: проверка замкнутости путешествия) В Путешествии Коня полное путешествие означает, что конь сделал 64 хода, проходя каждую клетку шахматной доски один и только один раз. Незамкнутое путешествие имеет место тогда, когда 64-й ход - это ход вдали от места, в котором конь начал путешествие. Модифицируйте программу Путешествие Коня, которую вы написали в упражнении 4.24, чтобы проверить, является ли выполненное полное путешествие замкнутым.

4.29. (Решето Эратосфена) Простое число - это любое целое число, которое точно делится без остатка только само на себя и на 1. Решето Эратосфена - это способ нахождения простых чисел. Он работает следующим образом:

1) Создайте массив, все элементы которого имеют начальные значения 1 (истина). Элементы массива с простыми индексами останутся равными 1. Все другие элементы массива в конечном счете установятся равными нулю.

2) Начиная с индекса массива 2 (индекс 1 должен быть простым), каждый раз отыскивается элемент массива с единичным значением, циклически обрабатывается оставшаяся часть массива и устанавливается в нуль каждый элемент массива, чей индекс кратен индексу элемента с единичным значением. Для индекса 2 все элементы в массиве с большим чем 2 индексом и кратные 2 установятся равными нулю (индексы 4, 6, 8 и тому подобные); для индекса 3 все элементы с индексом свыше 3 и кратные 3, установятся равными нулю (индексы 6, 9, 12 и тому подобные) и т.д.

Когда процесс закончится, элементы массива с единичным значением указывают, что их индексы - простые числа. Эти индексы могут быть напечатаны. Напишите программу, которая использует массив с 1000 элементами для определения и печати простых чисел между 1 и 999. Элемент О массива во внимание не принимайте.

4.30. (Блочная сортировка) Блочная сортировка требует наличия одномерного массива положительных целых чисел, который нужно сортировать, и двумерного массива целых чисел со строками, проиндексированными от О до 9, и столбцами, проиндексированными от О до п - 1, где п - количество значений в массиве, который должен сортироваться. Каждая строка двумерного массива рассматривается