Гарвард CS50: задания третьей недели (лекции 7 и 8), часть 2

Лекции Гарвардского курса по основам программирования CS50 Дополнительные материалы: асимптотическая нотация, алгоритмы сортировки и поиска Задания третьей недели, часть 1. Сортировка и поиск.

Игра начинается!

Настало время поиграть! Большинство людей знакомы с головоломкой «Пятнашки». Если формализовать, «Пятнашки» — это двумерное поле 4х4, в этом поле расположены не 16, а 15 квадратиков, то есть один слот остается пустым. Каждый из квадратиков пронумерован и может двигаться внутри поля по горизонтали или вертикали (если, конечно, есть куда двигаться). Цель — расположить числа по порядку, от 1 до 15 слева направо сверху вниз. Тогда пустое место окажется в правом нижнем углу. Движение любой плитки (или нескольких) является «шагом» в этом игровом пространстве. Представленная на картинке выше комбинация уже сложена, но обратите внимание, что плитка 12 или 15 могут быть сдвинуты в пустое пространство. Правила гласят, что плитка не может перемещаться по диагонали или извлекаться из игральной доски. На самом деле конфигураций для начала игры — много (можете посчитать, сколько именно), но давайте для простоты расположим плитки в порядке от наибольшей к наименьшей и оставим пустое пространство в правом нижнем углу доски. Единственное, давайте поменяем местами 1 и 2, чтобы головоломка была разрешимой. Теперь перейдите в директорию ~/ рабочей среды, затем — в /pset3/fifteen и откройте файл fifteen.c. В нем — код «движка» игры. Задание состоит в том, чтобы дописать код игры. Но для начала давайте откомпиллируем наш «движок» (вы наверняка уже знаете, как это сделать). Невзирая на то, что игра не закончена, запустить приложение можно. Будет удобнее запустить его в большем, чем обычно, окне терминала, которое можно открыть, нажав на зеленый плюс (+) рядом с одной из вкладок кода и выбрав New Terminal. Или же можно открыть терминальное окно на полный экран, кликнув на иконку Maximize в правом верхнем углу консоли. Вы видите, что кое-что кое-как работает. Но на самом деле большая часть игры ещё не написана. И вот тут — приготовьтесь — ваш выход!

Исследование

Изучите код и комментарии fifteen.c, после чего ответьте на вопросы ниже:

1. Помимо доски 4х4, какую размерность поля допускает наш движок?
2. Какой структурой данных является игровое поле?
3. Какая функция вызывается для приветствия игрока в начале игры?
4. Какие функции вам необходимо реализовать?
5. Примечание: если вы хотите, чтобы автопроверка ответила вам, правильно ли вы ответили на вопросы, рядом с файлом fifteen.c найдите файл fifteen.txt и запишите в него ответы на эти вопросы.

Реализация

Что ж, начнем реализовывать игру. Помните, двигаемся крохотными шажками, не пытайтесь сделать всё и сразу. Вместо этого давайте реализовывать функции по очереди и убедитесь, что они работают прежде, чем двигаться вперед. В частности, мы предлагаем вам реализовать функции игры в следующем порядке: init (инициализация), draw (прорисовка), move (сделать шаг), won (выигрыш). Дизайнерские решения (например, сколько пробелов нужно вставлять между нашими плитками-числами) — остаются за вами. Игровое поле должно выглядеть примерно так: 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _ Еще раз обращаем внимание, что в стартовой позиции 1 и 2 расположены в обратном порядке (это касается классического поля 4х4 если количество плиток — нечетное). Если количество плиток чётное, а поле — 3х3, менять две «младших» плитки местами не нужно. 8 7 6 5 4 3 2 1 _ Чтобы протестировать вашу реализацию «Пятнашек», нужно попробовать поиграть в них (не забывайте, аварийный выход из программы до её естественного завершения можно вызвать комбинацией клавиш crtl+c). Убедитесь, что программа будет работать, если будут введены неправильные числа. И помните, что точно так же, как вы автоматизировали ввод в find, вы можете автоматизировать «прохождение» игры. На деле, в папке ~cs50/pset3 есть файлы 3x3.txt и 4x4.txt, где собраны все последовательности шагов для победы на полях размерности 3х3 и 4х4. Чтобы протестировать программу, например, с помощью первого из файлов, выполните следующую команду: ./fifteen 3 < ~cs50/pset3/3x3.txt Настройте нужный вам аргумент для ускорения анимации. Да и вообще, при желании вы всегда можете изменить игру. Чтобы поразвлекаться с «управляющими последовательностями ANSI», включая цвет. Обратите внимание на нашу реализацию clear и проверьте http://isthe.com/chongo/tech/comp/ansi_escapes.html чтобы усвоить новые трюки. При желании напишите свои собственные функции или поменяйте прототипы функций, которые писали мы. Единственное ограничение — не меняйте логику функции main, иначе мы не сможем применить к ней некоторые автоматические тесты для подтверждения корректности работы вашей программы. В частности, main должна возвращать 0, в том и только том случае, если пользователь сложил головоломку. Не нулевые значения нужно вернуть для всех вариантов ошибок. Если возникают какие-то ошибки, пишите нам. Ну а если захотите поиграть с реализацией приложения, подготовленного ассистентами CS50, выполните следующую команду: ~cs50/pset3/fifteen Если вам интересно увидеть более крутую реализацию, с автоматическим решением головоломки, посмотрите «Хакерскую» версию программы: ~cs50/hacker3/fifteen Вместо того, чтобы ввести номер в окошке игры, напечатайте слово GOD. Здорово, не так ли? Если хотите проверить правильность вашей программы официально с check50, обратите внимание, что check50 предполагает, что пустое пространство игрового поля заполнено 0; если вы выбрали другое значение, для корректной проверки замените его на нуль. Кроме того, check50 предполагает, что вы индексируете поля игрового поля в порядке [ряд] [столбец], а не доска [столбец] [строка]. check50 2015.fall.pset3.fifteen fifteen.c

Подробнее о реализации функций игры Fifteen

• init (инициализация)
• draw (прорисовка)
• move (сделать шаг)
• won (выигрыш)

init

В этой функции мы представляем игровое поле. Для этого используем двумерный массив целых чисел. Размерность массива — MAX x MAX, где MAX — константа, обозначающая максимальное количество плиток, которые могут поместится в строке или столбце поля. Таким образом нам нужно определить переменную int board[MAX][MAX] Однако вспомним, что размерность игрового поля определяет пользователь. Поэтому нужно определить переменную, которая бы обозначала размерность доски, которую должен ввести пользователь. Это int d. где d — размерность доски, d <= MAX. Однако в Cи вы не можете менять размер массива, поэтому придется довольствоваться максимальной размерностью. В init вам нужно поместить значения на доску. Почитайте больше о двумерных массивах, если вы с ними ещё не работали. Вкратце, у них два индекса, первый обозначает номер строки, второй — номер столбца. Для нашей задачи мы начинаем с максимального числа и заканчиваем в случае d = 3 («Восьмяшки») единицей и пустым углом. Если у нас все-таки «Пятнашки», тогда 1 и 2 меняем местами. Что же делать с пустым местом? Наш массив состоит из целых чисел, поэтому и пустота должна быть заполнена неким целым. Поэтому вы должны выбрать некое целое число для инициализации пустой плитки (а в случае физической игры, её отсутствие). Чтобы инициализировать игровое поле и заполнить его стартовым набором плиток, можно использовать циклы. Ведем циклы по индексам i и j, где board[i][j] — плитка, которая находится в строке номер i и столбце номер j. Заполняем доску в убывающем порядке. В случае, если количество плиток (без пустой) — нечетное, меняем местами 1 и 2.

draw

Эта функция должна напечатать текущее состояние игрового поля. Помним, что у нас могут быть значения с одним или двумя разрядами, поэтому для красивого форматирования после чисел 1-9 функция должна печатать пробел (#s). Это можно организовать с помощью плейсхолдера %2d. printf (“%2d”, board[i][j]); Также не забывайте о пустой клетке. Выберите символ, который будет её представлять (в нашем примере — это нижнее подчеркивание). Функция draw должна отрисовывать этот символ, как только вы попадаете на пустую клетку. Итак, наш цикл будет примерно таким: for каждой строки for каждого элемента строки print значение и пробел print новую строку Запомните, что порядок, в котором функция draw выводит на экран плитки, должен отображать порядок, в котором они находятся в массиве, определенном в функции init.

move

Как только вы инициализировали игровое поле и нарисовали начальные позиции плиток, нужно позволить пользователю редактировать положение плиток, то есть, совершать движения. Итак, в Fifteen.c программа принимает вывод от пользователя, строит игровое поле и затем вызывает функцию move, и говорит, какую плитку он хочет подвинуть. Будьте внимательны: вы применяете функцию именно к номеру на плитке, а не к её положению на доске (в массиве). Таким образом, вам нужно найти актуальное положение плитки. Кроме того, вы должны позволить пользователю подвинуть плитку только тогда, когда это возможно. На картинке выше мы можем подвинуть только плитки номер 2, 5 и 8. Как это определить? По значению пустой плитки. Таким образом, функция move работает примерно так:

• Принимает номер плитки, который пользователь хочет подвинуть
• Ищет положение в массиве (на игровом поле) этой плитки
• Запоминает позицию пустой плитки
• Если пустая плитка соседствует с той, которую пользователь хочет подвинуть, они меняются местами в массиве.

won

Эта функция проверяет, завершилась ли игра после каждого шага пользователя. Она возвращает true, если плитки стоят в правильном порядке (в том числе и положение пустой плитки в правом нижнем углу). В таком случае программу можно завершить. Если же плитки всё еще разбросаны, функция возвращает false и передает бразды правления функции move. Как организовать проверку? Как и в случае инициализации и рисования доски — с помощью двух вложенных циклов for. Например, можно поставить условие, что каждое последующее число в массиве должно быть больше предыдущего. Обратите внимание на то, какое значение записано в пустой плитке. Или другой способ — используйте счетчик, чтобы убедиться, что все плитки на местах, если справитесь и напишете формулу, чтобы это получить. Желаем удачи в экспериментах!

Как подтвердить правильность кода и получить оценки

Внимание! Если вам важно проверить только правильность задач, после того, воспользуйтесь cs50check. Если же вы ходите получить оценки на платформе edx, проделайте процедуру, описанную ниже. Имейте в виду, эта процедура для проверки задач использует ту же cs50check. Разница только в том, что она запоминает результаты и подсчитывает общую оценку.

1. Залогиньтесь в CS50 IDE
2. Рядом с левым верхним углом CS50 IDE, там, где расположен её файловый браузер (не в терминальном окне), кликните правой клавишей мыши по вашей директории pset3 и нажмите Download. Вы должны увидеть, что браузер загрузил архив pset3.tar.gz.
3. В отдельном окне или вкладке залогиньтесь в CS50 Submit
4. Кликните по иконке Submit в левом верхнем углу экрана
5. В списке папок слева кликните по директории Problem Set 3, затем нажмите на кнопку Upload New Submission. Она находится справа.
6. На появившемся экране кликните по кнопке Add files…. Откроется окно выбора файлов с вашего компьютера.
7. Перейдите к той папке, где вы сохранили pset3.tar.gz. Скорее всего, он находится в папке Downloads(«Загрузки») или там, куда ваш браузер складывает файлы по умолчанию. Когда найдете pset3.tar.gz, кликните по нему один раз чтобы выбрать, затем кликните Open («Открыть»).
8. Нажмите Start upload. Ваши файлы будут загружены на серверы CS50.
9. На появившемся экране вы должны увидеть окно No File Selected. Если вы переведете курсор мыши влево, вы увидите список загрузившихся файлов. Для подтверждения кликните по каждому из них. Если вы в чём-то не уверены, вы можете перезагрузить файлы, повторив те ж шаги. Вы это можете делать сколько угодно раз до конца 2016 года.