Жак Арсак - Программирование игр и головоломок
Название: | Программирование игр и головоломок | |
Автор: | Жак Арсак | |
Жанр: | Литература ХX века (эпоха Социальных революций), Советские издания, Программирование игр | |
Изадано в серии: | неизвестно | |
Издательство: | Наука. Гл. ред. физ.-мат. лит. | |
Год издания: | 1990 | |
ISBN: | 5-02-013959-9 | |
Отзывы: | Комментировать | |
Рейтинг: | ||
Поделись книгой с друзьями! Помощь сайту: донат на оплату сервера |
Краткое содержание книги "Программирование игр и головоломок"
Рассматриваются способы программирования различных занимательных игр и головоломок с числами, геометрическими фигурами и др. Изложение большинства игр и головоломок ведется в несколько этапов. Сначала разъясняется сама постановка задачи и требования, предъявляемые к алгоритму ее решения.
В следующем разделе книги обсуждается сам алгоритм и возможные пути его реализации.
В конце книга по многим играм и головоломкам даются наброски их программной реализации. Используемый при этом язык типа Паскаля допускает перевод на другие широко распространенные языки программирования.
Для начинающих программистов, студентов вузов и техникумов.
Читаем онлайн "Программирование игр и головоломок". [Страница - 89]
x := а[i]; р := р + 1; i := i + 1
ВЕРНУТЬСЯ
ПОКА i ≤ n И а[i] ≠ a[i − р] ВЫПОЛНЯТЬ
i : = i + 1
ВЕРНУТЬСЯ
ВЕРНУТЬСЯ
Первый цикл движется по таблице а, пока обнаруживается, что элементы равны между собой. Более точно, р и i изменяются одинаково, так что разность i − р остается постоянной. Все элементы a[i] сравниваются с одним и тем же элементом, и величина x остается постоянной, равной этому элементу, на протяжении всего цикла.
Второй цикл изменяет i до тех пор, пока не обнаружится пара элементов, отстоящих на р + 1.
Уточним ситуацию выхода из первого внутреннего цикла. Мы собираемся найти конец равнины, которая лучше всех предыдущих, мы фиксируем ее длину р и ее значение х, a i обозначает первый элемент после этой равнины. Мы можем надеяться найти пару j, j − р с
a[j] = a[j − р]
только пока j − р остается на равнине, которую мы собираемся пройти. Наименьшее соответствующее i значение j удовлетворяет условию j − р = i, или j = i + р.
Следовательно, можно увеличивать i от р в обоих циклах, не меняя действия программы, что ускоряет ее работу.
Чтобы ускорить и первый внутренний цикл, мы присвоим переменной x ее значение перед циклом и сохраним ее начальное значение в j. Так как i − р остается постоянным, то можно вычислить значение р также и после выхода из цикла. Начальные значения суть i = j и р = р0, а конечные значения i и р удовлетворяют соотношениям i − р = j − р0, откуда р = i + р0 − j:
i := 1; р := 0
ПОКА i ≤ n ВЫПОЛНЯТЬ
x := а[i]; j := i
ПОКА i ≤ n И а[i] = x ВЫПОЛНЯТЬ
i := i + 1
ВЕРНУТЬСЯ
р := i + р − j; i := i + p
ПОКА i ≤ n И а[i] ≠ a[i − р] ВЫПОЛНЯТЬ
i := i + 1
ВЕРНУТЬСЯ
ВЕРНУТЬСЯ
Вы можете получить эту программу непосредственно, минуя механизм преобразования программ. Но этот способ кажется мне требующим больших умственных усилий,
Может быть, это связано с ходом мыслей, который я приобрел, преподавая[30].
Головоломка 35.
Хорошенько учтите то, что вы знаете: обозначим через и таблицу, которая дает последние элементы наилучших возрастающих последовательностей для (всех возможных) длин от 1 до m.
Покажем сначала, что ui < ui+1. Предположим, что это не так: пусть существует такая последовательность длины i + 1, у которой последний элемент не больше ui. Так как эта последовательность возрастает, то ее предпоследний элемент меньше ui+1 и потому меньше ui. Тогда, удаляя последний элемент этой последовательности, мы получили бы последовательность длины i с последним членом, меньшим ui, что противоречило бы предположению, что ui — последний элемент последовательности длины i с наименьшим возможным последним элементом.
Рассмотрим теперь следующий элемент x нашего вектора. Разместим его в упорядоченной таблице u. Может случиться, что x > um. Тогда элемент x можно присоединить к концу последовательности длины m; тем самым получилась бы (впервые) возрастающая последовательность длины m + 1, которая вследствие своей единственности была бы оптимальна.
Если x меньше u1, то им следует заменить для построения новой наилучшей последовательности с длиной 1. Если же, наконец, оказывается, что ui < x < ui+1, то x можно присоединить к концу последовательности с длиной i + 1, чтобы получить последовательность с длиной i + 1, которая лучше уже известной, и поэтому ui+1 следует заменить на х. Так как и упорядочена, то вы можете разместить в ней x с помощью дихотомического поиска.
Эта операция требует порядка log2 m действий для m, не превосходящих n. Так как вам требуется n обращений к таблице, то вы получаете верхнюю границу числа действий порядка n log2 n, что чрезмерно завышено.
Головоломка 36.
Предположим, что вы уже прошли первую цепочку вплоть до индекса i − 1 и получили наилучшие слова длины р, меняющейся от 1 до m. Вы рассматриваете символ в положении i и ищете его в другой цепочке. Его первое положение j1 может быть поставлено в конце некоторого слова — скажем, слова длины р1 — и даст слово длины р1 + 1, которое окажется лучшим, чем предыдущее: действительно, если j1 можно поставить после слова длины p1, то это значит, что его значение больше положения последнего символа в наилучшем слове длины р1, но меньше положения последнего символа в слове длины p1 + 1, Рассмотрим теперь второе появление того же символа во второй цепочке: j2 > j1. Его нельзя поставить в конце елова длины p1 + 1, хотя j2 и больше j1, потому что это — другое появление того же символа, и их не нужно смешивать. Поэтому достаточно ограничиться по поводу этого --">Книги схожие с «Программирование игр и головоломок» по жанру, серии, автору или названию:
Иван Братко - Программирование на языке Пролог для искусственного интеллекта Жанр: Литература ХX века (эпоха Социальных революций) Год издания: 1990 |
У. Маурер - Введение в программирование на языке ЛИСП Жанр: Lisp, Scheme Год издания: 1976 Серия: Математическое обеспечение ЭВМ |
Юрий Алексеевич Семенов - Программирование на языке Форт Жанр: Forth Год издания: 1991 |