Распределенные вычисления
Лабораторная работа № 5
Сетевое взаимодействие в Windows
Задание
Доработать программу задания лабораторной работы №1 или №2 или №3 (по указанию преподавателя) таким образом, чтобы для взаимодействия между сервером и клиентом использовались протокол IP и сокеты.
Выдается (преподавателем) один из двух вариантов:
1. Клиент (исполнитель) должен подключаться к серверу (менеджеру) по указанному IP и посылать необходимые команды. Клиент и сервер должны взаимодействовать друг с другом по TCP протоколу. Причем к одному серверу могут подключиться несколько клиентов. Каждому клиенту необходимо сгенерировать уникальное имя. Сервер выполняет синхронизацию и необходимые вычисления. Клиенты дают команды серверу по каждому действию моделируемого объекта. Количество клиентов может динамически меняться.
2. Менеджер должен делить задачу на равные части (например, по количеству строк изображения) согласно количеству исполнителей в сети, рассылать индивидуальные задания серверам и получать от них результат. Формат сообщений разработать самостоятельно. Программа должна уметь работать с не менее 3-мя исполнителями. Если задача позволяет использовать большее количество исполнителей, то программа должна раздавать задания всем имеющимся исполнителям, иначе обосновать причину ограничения числа исполнителей. Менеджер и исполнитель должны поддерживать между собой соединение (TCP протокол). Если необходимо по условию заданию, сделать назначение роли каждому исполнителю. Количество исполнителей может динамически меняться.
Все остальные тонкости уточняются у преподавателя конкретно по соответствующему заданию.
Варианты заданий:
1. Задача од инвентаризации по книгам. После нового года в библиотеке СФУ обнаружилась пропажа каталога. После поиска и наказания, виноватых ректор дал указание восстановить каталог силами студентов. Фонд библиотека представляет собой прямоугольное помещение, в котором находится М рядов по N шкафов по К книг в каждом шкафу. Требуется создать многопоточное приложение, составляющее каталог. При решении задачи использовать метод «портфель задач», причем в качестве отдельной задачи задается внесение в каталог записи об отдельной книге.
2. Задача о Винни-Пухе или правильные пчелы. В одном лесу живут N пчел и K медведей, которые используют L (2*L<N) горшков меда, вместимостью M глотков. Сначала горшки пустые. Пока какой-нибудь горшок не наполнится, медведи спит. Как только горшок заполняется, медведи просыпается и съедает весь мед, после чего снова засыпает. Каждая пчела многократно собирает по одному глотку меда и кладет его в горшки случайным образом. Если горшок заполнен, то пчела кладет в ближайший горшок. Пчела, которая обнаружила, что один из горшков заполнен, будит медведей. Создать сетевое приложение, моделирующее поведение пчел и медведей.
3. Задача о Винни-Пухе, или неправильные пчелы. Неправильные пчелы, подсчитав в конце месяца убытки от наличия в лесу Винни-Пуха (количество Винни-Пухов задается параметром), решили разыскать его и наказать в назидание всем другим любителям сладкого. Для поисков медведя они поделили лес на участки, каждый из которых прочесывает одна стая неправильных пчел. В случае нахождения медведя на своем участке стая проводит показательное наказание и возвращается в улей. Если участок прочесан, а Винни-Пух на нем не обнаружен, стая также возвращается в улей. Требуется создать многопоточное приложение, моделирующее действия пчел. При этом медведь через определенный интервал времени t (который не меньше времени прочесывания участка леса пчелами) переходит из одного на другой участок леса. Каждая стая пчел реализуется клиентом. Медведь и лес сервером.
4. Даны результаты сдачи экзамена по дисциплине «Средства разработки параллельных программ» по группам. Требуется создать сетевое приложение, вычисляющее количество двоечников и отличников. Исполнители должны осуществлять вычисления параллельно по группам. Задание каждому исполнителю дает менеджер, предварительно разбив задание на части. В любой момент может появится новый исполнитель и/или выпасть из работы один исполнитель.
5. Задача о каннибалах. Племя из N дикарей ест вместе из K больших горшков, который вмешают по M (задается параметром) кусков тушеного миссионера. Когда дикарь хочет обедать, он встает в очередь к горшку где есть варится или раздается очередная порция (1. если есть горшки с готовым обедом, то дикарь встает в меньшую очередь, иначе к горшку, котором варится обеду осталось меньшее время. 2. Если есть очереди к горшкам где только варится обед, то, он выбирает горшок с меньшим временем если длина очереди меньше M, иначе в меньшую очередь), затем берет из горшка один кусок. Если еды нет или остался один горшок с очередью >= M, то дикарь будит одного повара (если есть спящий повар) и ждет, пока тот не сварит обед в горшке. Работает P поваров, варят обеды во всех горшках. Повар засыпает, когда закончил варить свою часть горшков. Повар спит T времени. Создать сетевое приложение, моделирующее обед дикарей. Каждый дикарь реализуется исполнителем (клиентом).
6. Вторая задача об Острове Сокровищ. Шайка пиратов под предводительством Джона Сильвера высадилась на берег Острова Сокровищ. Не смотря на добытую карту старого Флинта, местоположение сокровищ по-прежнему остается загадкой, поэтому искать клад приходится практически на ощупь. Так как Сильвер ходит на деревянной ноге, то самому бродить по джунглям ему не с руки. Джон Сильвер поделил остров на участки, а пиратов на небольшие группы. Каждой группе поручается искать клад на нескольких участках, а сам Сильвер ждет на берегу. Группа пиратов, обшарив одну часть острова, переходит к другой, еще необследованной части. Закончив поиски, пираты возвращаются к Сильверу и докладывают о результатах. Требуется создать многопоточное приложение с управляющим потоком, моделирующее действия Сильвера и пиратов.
7. Военная задача. Диктатор 1, объявил войну диктатору 2, диктатору 3 и т д. Диктатор 2 объявил войну 3 и т. д до диктатор N-1 объявил войну диктатору N. У каждого диктатора очень мало солдат, но очень много снарядов для минометов, привезенных с последней американской гуманитарной помощью. Поэтому армии всех сторон просто обстреливают наугад территорию противника, надеясь поразить что-нибудь ценное. Стрельба ведется по очереди до тех пор, пока либо не будут уничтожены все цели, либо стоимость потраченных снарядов не превысит суммарную стоимость всего того, что ими можно уничтожить. Создать сетевое приложение, моделирующее военные действия. Каждый Диктатор реализуется клиентом. В любой момент может появится новый диктатор или погибнут один из существующих (клиент закрылся).
8. Вычислить 
используя метод прямоугольников. Входные данные: числа а и b. Функция f(x) определяется с помощью программной функции. При суммировании использовать принцип дихотомии.
9. Найти определитель матрицы А. Входные данные: целые положительные числа n и m, произвольная матрица А размерности n х m. Решить задачу двумя способами: 1) количество потоков является входным параметром, при этом размерность матриц может быть не кратна количеству потоков: 2) количество потоков заранее неизвестно и не является параметром задачи. Числа m и n не одинаковы.
10. Задача о супермаркете. В супермаркете работают K кассиров, покупатели заходят в супермаркет, делают покупки и становятся в очередь к случайному кассиру. Пока очередь пуста, кассир спит, как только появляется покупатель, кассир просыпается. Покупатель спит в очереди, пока не подойдет к кассиру. Создать сетевое приложение, моделирующее рабочий день супермаркета. Менеджер реализует бесконечную последовательность покупателей. Исполнитель реализует кассира (отдел). Магазин может расширяться (появляется новый исполнитель) или сокращаться (закрытие отдела). При закрытии отдела покупатели стоящие в очереди к данному отделу переходят к другим кассирам.
11. Задача о магазине. В магазине работают K (задается параметром) отделов, каждый отдел обслуживает один продавец. Покупатель, зайдя в магазин, делает покупки в произвольных отделах, и если в выбранном отделе продавец не свободен, покупатель становится в очередь и засыпает, пока продавец не освободится. Создать сетевое приложение, моделирую шее рабочий день магазина. Каждый покупатель реализуется клиентом. Считать, что покупатель не выходит из магазина, а входит в другой отдел за новыми покупками.
12. Представить выражение 
в виде 
.Входные данные: числа а и b. Целое положительное число n. 1) Количество исполнителей выбирается в зависимости от показателя степени. 2) Степень определяется количеством исполнителей.
13. Задача о гостинице. В гостинице K (задается параметром) номеров, клиенты гостиницы снимают номер на одну ночь, если в гостинице нет свободных номеров, клиенты устраиваются на ночлег рядом с гостиницей и ждут, пока любой номер не освободится. Создать сетевое приложение, моделирующее работу гостиницы. Каждый исполнитель реализует номер, менеджер реализует бесконечную последовательность клиентов. Решение о заселении принимает исполнитель.
14. Задача о гостинице-2 (умные клиенты). В гостинице 2*K (задается параметром) номеров с ценой 200 рублей, 2*K (задается параметром) номеров с ценой 400 рублей и K номеров с ценой 600 руб. Клиент, зашедший в гостиницу, обладает некоторой суммой и получает номер по своим финансовым возможностям, если тот свободен. Если среди доступных клиенту номеров нет свободных, клиент уходит искать ночлег в другое место. Создать сетевое приложение, моделирующее работу гостиницы. Каждый исполнитель реализует номер. Количество номеров может меняться динамически. Менеджер реализует бесконечную последовательность клиентов. На менеджере реализовать графический интерфейс (параметры можно менять в ходе работы программы): ползунок регулирования интенсивности появления новых клиентов (клиентов в секунду от K до 100*K); поле ввода числа K от 1 до 1000; диапазон разброса интенсивности появления новых, в пределах которого по синусоидальному закону меняется интенсивность появления новых клиентов. Решение о заселении принимает исполнитель.
15. Задача о гостинице - 3 (дамы и джентльмены). В гостинице 2*K (задается параметром) номеров рассчитаны на одного человека и 3*K (задается параметром) номеров рассчитаны на двух человек. В гостиницу приходят клиенты замужные/не замужные дамы и клиенты женатые/не женатые джентльмены, и конечно они могут провести ночь в номере только с представителем своего пола или со супругом(ой). Заселение происходит по одному человеку за операцию. При поселении супруга(и) учитывать наличие уже супруги(а) в гостинице, при условии что в ее(его) номере есть место. Если для клиента не находится подходящего номера, он уходит искать ночлег в другое место. Создать сетевое приложение, моделирующее работу гостиницы. Каждый исполнитель (клиент) реализует бесконечную последовательность клиентов. Менеджер (сервер) гостиницу.
16. Задача о клумбе. На клумбе растет K (задается параметром к серверу) цветов, за ними непрерывно следят N садовника и поливают увядшие цветы, при этом оба садовника очень боятся полить одни и тот же цветок. Создать сетевое приложение, моделирующее состояния клумбы и действия садовников. Для изменения состояния цветов создать отдельный поток (время через которое надо снова поливать цветок задается двойным параметром – время в течении, которого нельзя поливать 2-ой раз (чтобы не сгнили корни) и время в течении которого надо полить, чтобы цветок не сгорел на палящем солнце). Также садовники боятся перелить цветок, либо не успеть полить. Каждый садовник реализуется исполнителем (клиентом). Количество исполнителей может меняться динамически. Садовники поливают постоянно, прошли весь сад, через небольшой перерыв начинают снова. Реализовать графический интерфейс для отображения динамики состояний цветов на клумбе в менеджере.
17. Задача о нелюдимых садовниках. Имеется пустой участок земли (трехмерный массив) и план сада (размера X*Y*Z), который необходимо реализовать. Эту задачу выполняют N садовников, которые не хотят встречаться друг с другом. Первый садовник начинает работу с верхнего левого угла сада и перемешается слева направо, сделав ряд, он спускается вниз. Второй садовник начинает работу с нижнего правого угла сада и перемещается снизу вверх, сделав ряд, он перемещается влево. Третий садовник начинает аналогично первому, только вместо смещения по X он смещается по Z. Условия аналогично задаче садовников 4 лабор. работы, но с учетом 3-ого пространства. Если садовник видит, что участок сада уже выполнен другим садовником, он идет дальше. Садовники должны работать параллельно. Создать сетевое приложение, моделирующее работу садовников. Каждый садовник реализуется клиентом.
18. Задача о картинной галерее. В галерее N залов, в каждом из котором для обозрения может быть представлено M картин. В каждом зале сидит вахтер за зал, который следит, чтобы посетителей было не больше К. Посетитель ходит от картины к картине, и если на картину любуются более чем T посетителей, он стоит в стороне и ждет, пока число желающих увидеть картину не станет меньше. Посетитель может покинуть галерею. Создать сетевое приложение, моделирую шее работу картинной галереи. Исполнитель реализует одну картину и все действия связанные с картиной. Менеджер генерирует последовательность посетителей (частота генерации задается, динамика количество клиентов по синусоидальному закону). При этом количество картин может меняться динамически. Среди исполнителей одного зала один исполнитель берет на себя функции сервера по функционирования зала, который напрямую работает со сервером, а остальные исполнители (картины зала) работают через него. Разрешается динамически изменять количество залов для балансировки (по желанииюс тудента).
19. Задача о Винни-Пухе - 3 пли неправильные пчелы – 2. N пчел живет в улье, каждая пчела может собирать мед и сторожить улей (N>3). Ни одна пчела не покинет улей, если кроме нее в нем нет других пчел. Каждая пчела приносит за раз одну порцию меда. Всего в улей может войти M порций меда (задается параметром к серверу). Винни-Пух спит пока меда в улье меньше M/K, где K – количество Винни-Пухов, но как только его становится достаточно, он просыпается и пытается достать весь мед из улья. Если в улье находится менее чем T пчелы, Винни-Пух забирает мед, убегает, съедает мед и снова засыпает. Если в улье пчел больше, они кусают Винни-Пуха, он убегает, лечит укус, и снова бежит за медом. При этом одна из этих пчел сразу вылетает лечится и собирать мед (тратит двое больше времени, чем обычно). Создать сетевое приложение, моделирующее поведение пчел и медведей. Каждый клиент представляет Винни-Пуха. Количество Винни-Пухов может изменяться динамически: запуск нового клиента пользователем и/или завершения работы клиента пользователем.
20. Задача о болтунах. N болтунов имеют N*K телефонов, ждут звонков и звонят друг другу, чтобы побеседовать. Причем болтун может звонить на K1 телефонов одновременно и отвечать на K2 телефонов (K1+K2 <= K). Если телефон занят, болтун будет звонить, пока ему кто-нибудь не ответит. Побеседовав, болтун не унимается или ждет звонка или звонит на другой номер. Создать сетевое приложение, моделирующее поведение болтунов. Каждый болтун реализуется клиентом. Болтуны могут входить (запуск нового клиента пользователем) и выходить (завершения работы клиента пользователем) из сети. К клиенту задается параметр k (k <= K) – возможность данного болтуна работать с k телефонами одновременно.
21. Задача о магазине - 2 (забывчивые покупатели). В магазине работают K (задается параметром) отделов, каждый отдел обладает уникальным ассортиментом. В каждом отделе работает один продавец. В магазин ходят исключительно забывчивые покупатели, поэтому каждый покупатель носит с собой список товаров, которые желает купить. Покупатель приобретает товары точно в том порядке, в каком они записаны в его списке. Продавец может обслужить только одного покупателя за раз. Покупатель, вставший в очередь, засыпает пока не дойдет до продавца. Продавец засыпает, если в его отделе нет покупателей, и просыпается, если появится хотя бы один. Создать сетевое приложение, моделирующее работу магазина. Каждый клиент (исполнитель) реализует покупателя. Когда покупатель купил все по списку, выходит из магазина. Затем исполнитель создает нового покупателя с новым списком.
22. Задача о программистах. В отделе работают N программистов. Всего K отделов задается параметром к менеджеру. Каждый программист пишет свою программу и отдает ее на проверку другому программисту. Программист проверяет чужую программу, когда его собственная уже написана. По завершении проверки, программист дает ответ: программа написана правильно или написана неправильно. Программист спит, если не пишет свою программу и не проверяет чужую программу. Программист просыпается, когда получает заключение от другого программиста. Если программа признана правильной, программист пишет другую программу, если программа признана неправильной, программист исправляет ее и отправляет на проверку тому же программисту, который ее проверял. Создать сетевое приложение, моделирующее работу программистов. Количество программистов может меняться динамически (приходить и/или уходить). Каждый программист реализуется исполнителем. Менеджер реализует отдел. Если отделов больше двух, то работу одного отдела делегирует одному из исполнителю. В сети допускается работа нескольких отделов, которые не взаимодействуют с друг другом. Если отделы от одного менеджера, то исполнитель с отделом сообщает менеджеру текущее положение дел в отделе за определенный период (задается параметром к менеджеру – от 30 сек до 600 секунд).
23. Определить ранг матрицы. Входные данные: целые положительные числа n и m произвольная матрица А размерности n х m. Решить задачу двумя способами: 1) количество потоков является входным параметром, при этом размерность матриц может быть не кратна количеству потоков: 2) количество потоков заранее неизвестно и не является параметром задачи. Числа m и n неодинаковы.
24. Найти обратную матрицу для матрицы А. Входные данные: целые положительные числа n и m произвольная матрица А размерности n х m. Решить задачу двумя способами: 1) количество потоков является входным параметром, при этом размерность матриц может быть не кратна количеству потоков: 2) количество потоков заранее неизвестно и не является параметром задачи. Числа m и n неодинаковы.
25. Определить множество индексов i, для которых (A[i] - B[i]) или (A[i] + B[i]) являются простыми числами. Входные данные: массивы целых положительных чисел А и В, произвольной длины > 1000. Количество потоков зависит от размерностей массивов, и не является параметром задачи.
26. Определить множество индексов i, для которых A[i] и B[i] не имеют общих делителей (единицу в роли делителя не рассматривать). Входные данные: массивы целых положительных чисел А и В, произвольной длины > 1000.
27. Вывести список всех целых чисел, содержащих от 4 до 9 значащих цифр, которые после умножения на n, будут содержать все те же самые цифры в произвольной последовательности и в произвольном количестве. Входные данные: целое положительное число n, больше единицы и меньше десяти.
28. Вычислить используя метод трапеций. Входные данные: числа а и b. Функция f(x) определяется с помощью программной функции. При суммировании использовать принцип дихотомии.
29. Вычислить используя метод Симпсона. Входные данные: числа а и b. Функция f(x) определяется с помощью программной функции. При суммировании использовать принцип дихотомии.
30. Определить, делится ли целое число А, содержащее от 1 до 1000 значащих цифр, на 2, 3, 4, 5, 6, 7, 8, 9, 10. Входные данные: целое положительное число А, записанное в файле. Количество исполнителей – количество запущенных клиентов.
31. Задача об инвентаризации по рядам. После нового года в библиотеке СФУ обнаружилась пропажа каталога. После поиска и наказания виноватых, ректор дал указание восстановить каталог силами студентов. Фонд библиотека представляет собой прямоугольное помещение, в котором находится М рядов по N шкафов по К книг в каждом шкафу. Требуется создать многопоточное приложение, составляющее каталог. При решении задачи использовать метод «портфель задач», причем в качестве отдельной задачи задается составление каталога одним студентом для одного ряда.
32. Пусть дано большое количество тел (планет, звезд и т. д.), для каждого из которых известна масса, начальное положение и скорость. Под действием гравитации положение тел меняется, и требуемое решение задачи состоит в моделировании динамики изменения системы N тел на протяжении некоторого задаваемого интервала времени. При столкновении тела отталкиваются друг от друга. Вертикальная линия это линия суперпозиции векторов скоростей. 
Направление силы задается единичным вектором от 𝑖 к 𝑗 и противоположным вектором от 𝑗 к 𝑖. Общая сила, действующая на тело, есть сумма сил воздействия всех остальных тел. Приведём формулы для вычисления скорости и положения тела: ускорение: 𝑎 = 𝐹/𝑚, изменение скорости: d𝑣𝑖 = 𝑎 d𝑡, изменение положения тела: d𝑝𝑖 = 𝑣𝑖 +d𝑣𝑖/2d𝑡 на интервале времени d𝑡. При реализации задачи можно использовать модель «взаимодействующие равные», или «круговой конвейер», или алгоритм Барнса-Хата (Barnes-Hut), или быстрый метод мультиполей. Реализовать графическое отображения действий в режиме реального времени. Параметр скорости итераций задается параметром к менеджеру.
33. Промоделировать движение шаров на бильярдном столе (2D графика или выше). Задать начальные положения и скорости всех шаров, количеством шаров задается параметром к менеджеру, все шары должны помещаться на столе – размер стола увеличивается размер луз при этом изменяется в изменение стола в степени 0,5 (т. е. если стол увеличился в 2 (3 или 4 и т .д.) раза, то лузы в 1,44 ( 1,73 или 2) раза), если шары занимают более 50% стола или размер шаров уменьшается, а размер луз уменьшается в изменение шара в степени 0,5. Реализовать с учетом трения (задается параметром от 0 до 0,8 - задается параметром к менеджеру) и столкновение с бортом (задается параметром от 0 до 0,6 - задается параметром к менеджеру). Игра заканчивается, когда все шары окажутся в лузах! При достижении условия остановки шаров (1) или длительные повторяющиеся движения шаров при отсутствии трения (2), то моделируется удар по шару (тип удара задается): либо случайный удар и/или пользователем.
Реализовать параллельное решение. Реализовать графическое отображения действий в режиме реального времени. Параметр скорости итераций задается параметром к менеджеру.
34. Нужно расставить на шахматной доске размера MxN K ферзей так, чтобы они не атаковали друг друга. Найти все решения (или требуемое количество). Использовать модель «менеджер-исполнитель». Менеджер задаёт (либо автоматически генерируют, либо через файл – реализовать оба варианта) начальные позиции ферзей. Числа M и N и K задаются параметрами к менеджеру. Реализовать графическое отображения в режиме реального времени (показываются поочередно позиции ферзей с сохранением в файл данных). Реализовать возможность просмотра позиций ферзей из файла.
35. Игра́ «Жизнь-2». Волки и Зайцы. Место действия этой игры — «вселенная» — это размеченная на клетки поверхность (квадрат, размер которого задается сервером от 10*10 до 100*100). Дано двумерное поле клеток, каждая из которых либо содержит волка (1), либо зайца (2), либо пуста (0). Каждая клетка проверяет состояние своих соседей (их 8) и изменяет своё по правилам:
1. Волки и зайцы живут по измененным правилам задачи «Жизни». Число игры «Жизнь» для волков (W) и зайцев (Z) задается параметром (пользователем при запуске). W задается параметром от 2 до 4, Z – от 2 до 4.
2. Волк съедает одного зайца-соседа, в любом порядке на ваш выбор, за один шаг. Рождение нового волка по условию W (см. правила игры «Жизнь»).
3. Порядок следования правил: волк съедает зайца, заяц умрёт сам, заяц умирает, если соседей (зайцев) меньше Z-1 или больше Z+K. K – задается (задается параметром от 0 до 2).
4. Рождение нового зайца (не зависит от того съедает ли зайца волк) по условию Z (см. правила игры «Жизнь»).
5. Число W (определяет необходимое количество волков для рождения нового волка) и, если за G (задается параметром от 2 до 4) поколений волк не съест зайца, то он умирает.
6. Если на исполнителе заданы параметры (задаются пользователем) w и z и g и k, тогда расчет он делает не параметрам W и Z и G и K, а по своим параметрам w и z и g и k.
Реализовать параллельное решение игры. Реализовать графическое отображения действий в режиме реального времени. Параметр скорости итераций (смена поколения) задается параметром к менеджеру.
36. Задача «пожар». Дано двумерное поле клеток (размерность задается параметром к серверу но не менее 10*10), каждая из которых либо содержит супердерево (3), дерево (2), либо куст (1), либо пуста (0). Пожар начинается в одной клетке (либо выбирается случайным образом, либо задаётся явно). Теперь клетка может гореть (5), или быть потушенной (0). Каждая клетка проверяет состояние своих соседей (их 4) и изменяет своё по правилам:
1. Куст или дерево загорается, если любой из соседей горит.
2. Куст горит 1 поколение, дерево 2 поколения, супердерево – t (задается сервером от 3 до 5) поколений.
3. Куст загорается, если его окружают K1 (задается параметром к серверу от 1 до 3) горящие клетки по диагонали. Или K2 (от 1 до 2, или 0 – не загорается) сосед по горизонтали (или вертикали).
4. Дерево загорается, если его окружают D1 (задается параметром к серверу от 2 до 4, или 0 – не загорается) горящие клетки по диагонали, или горят D2 (задается параметром к серверу от 1 до 3, или 0 – не загорается) соседа по горизонтали (и/или вертикали).
5. Супердерево загорается, если горят T2 (задается параметром к серверу от 2 до 3, или 0 – не загорается) соседа по горизонтали (и/или вертикали), или его окружают T1 (задается параметром к серверу от 3 до 4, или 0 – не загорается) горящие клетки по диагонали.
Задаются все условия по каждому объекту.
Показать картину пожара поля, пока пожар не закончится.
Реализовать параллельное решение игры. Реализовать графическое отображения действий в режиме реального времени (автоматическая смена поколений, также реализовать пошаговую смену – нажатием кнопки). Параметр скорости итераций (смена поколения) задается параметром к менеджеру.
.
37. Игра «Лабиринт жизни». «Лабиринт жизни» - игра-головоломка, придуманная Андреа Гилберт (Andrea Gilbert, http://www. /) по мотивам широко известной игры «Жизнь» и ее правил, описывающих поведение колонии организмов. Изменения свелись к введению в игру одной «умной» клетки, которой разрешается перемещаться на любую свободную соседнюю ячейку при смене поколений. В зависимости от ситуации, «умная» клетка может также оставаться на своем месте. Во всем остальном, включая влияние на «рождения» и «смерти» соседей, поведение «умной» клетки описывается классическими правилами игры «жизнь».
Цель игры – поддерживая «умную» клетку живой, привести ее к «цели», т. е. в заданную ячейку игровой решетки. В случае если «умная» клетка погибает, не достигнув заданной ячейки, игра считается проигранной.
Постановка задачи: написать параллельное приложение, находящее одно или несколько решений игры «лабиринт жизни». Входные данные приложения представляют собой текстовый файл, имя которого передается программе как аргумент командной строки. Файл с исходными данными содержит изначальное состояние игрового поля. Результат работы программы необходимо вывести в файл, имя которого задано вторым аргументом командной строки. Результатом является путь «умной» клетки из своей начальной позиции в заданную ячейку с учетом взаимодействия с другими живыми клетками колонии из поколения в поколение.
Формат файла исходных данных: программа принимает данные из текстового файла, заданного аргументом командной строки. В первой строке файла содержатся два целых числа, определяющих размерность игрового поля, число строк и столбцов соответственно. Условимся, что координаты левой верхней ячейки (1 1). Во второй строке файла содержится пара координат «цели». В третьей строке содержатся начальные координаты «умной» клетки. Оставшаяся часть исходного файла содержит позиции «живых» клеток первого поколения игры. В каждой строке следуют пять пар целых чисел, разделенных как минимум одним пробелом. Т. о. строка содержит координаты пяти живых клеток. Признаком окончания списка клеток является пара нулевых координат (0 0). Таким образом, последняя строка секции может содержать менее чем 5 пар координат.
Формат файла результата: приложение должно сгенерировать файл, содержащий последовательные перемещения «умной» клетки по направлению к цели. Каждое перемещение описывается целым числом от ‘0’ to ‘8’: ‘0’ означает, что клетка осталась на своем месте; ‘1’ соответствует перемещению по диагонали в левую верхнюю ячейку, ‘2’ – перемещению вверх, и так далее по часовой стрелке.
Строки файла результата должны содержать по 40 символов без пробелов, за исключением последней строки, которая, возможно, будет содержать менее 40 символов.
В случае если решение найти невозможно, следует вывести соответствующее сообщение.
Пример командной строки: ./mazeoflife gridin. txt pathout. txt
Пример файла с исходными данными, gridin. txt:
7 7
4 6
4 2
1 4 2 3 2 5 3 4 5 4
6 3 6 5 7 4 0 0
Пример файла результата, pathout. txt:
Solution Path:
3845524
Реализовать графическое отображения действий в режиме реального времени.
38. Головоломка Masyu была разработана японской компанией Nikoli, специализирующейся на издании книг и журналов с головоломками. Игра происходит на прямоугольном поле, в ячейках которого расположены белые и черные круги. Цель – соединить круги вертикальными и горизонтальными отрезками таким образом, чтобы получилась замкнутая линия. Линия не должна пересекать саму себя, ветвиться или проходить через одну клетку дважды. Чтобы усложнить задачу, введены два дополнительных правила:
Линия, проходящая через ячейку с белым кругом, должна пройти ячейку прямо, не меняя направления, и повернуть на 90 градусов в следующей ячейке (хотя бы с одной стороны).
Пример прохождения линии через белую ячейку (оба варианта возможны и корректны):
Линия, проходящая через ячейку с черным кругом, должна повернуть на 90 градусов в этой же ячейке и далее пройти прямо как минимум до середины второй ячейки.
Постановка задачи: написать параллельное приложение, которое решает головоломки Masyu. Входные данные приложения представляют собой текстовый файл, имя которого передается программе как аргумент командной строки. В файле содержится размерность игрового поля и координаты ячеек с черными и белыми кругами. В файл результата, определяемый вторым аргументом командной строки, необходимо вывести решение головоломки, т. е. путь замкнутой линии по игровому полю согласно описанным выше правилам.
Формат файла исходных данных: программа принимает данные из текстового файла, заданного аргументом командной строки. В первой строке файла содержатся два целых числа, определяющих размерность игрового поля, соответственно число строк и число столбцов. Условимся, что координаты левой верхней ячейки (1 1). Далее следуют две секции, описывающие координаты ячеек с кругами. Каждая секция начинается со строки с единственным символом ‘B’ или ‘W’, что соответствует началу блоков координат белых и черных кругов. Далее в каждой строке следуют пять пар целых чисел, разделенных как минимум одним пробелом. Числа представляют координаты пяти кругов. Признаком окончания секции является пара нулевых координат (0 0). Таким образом, последняя строка секции может содержать менее чем 5 пар координат. Ячейки, координаты которых не встречаются ни в одной из двух секций, являются «пустыми», т. е. не содержат кругов.
Формат файла результата: приложение должно сгенерировать файл, описывающий замкнутую ломаную линию, проходящую по игровому полю через черные и белые круги. В первой строке необходимо вывести пару координат любой ячейки, через которую проходит путь. Это «стартовая» ячейка. Далее, каждый отрезок пути размером в одну ячейку необходимо вывести в виде одного символа по направлению движения, т. е. ‘U’ – вверх, ‘D’ – вниз, ‘R’ – вправо, ‘L’ – влево.
Строки файла результата должны содержать по 40 символов без пробелов, за исключением последней строки, которая, возможно, будет содержать менее 40 символов.
Если решение головоломки найдено, последний шаг должен привести в ячейку, заданную в первой строке файла результата. В случае если решение найти невозможно, следует вывести соответствующее сообщение.
Пример командной строки: ./masyu gridin. txt pathout. txt
Пример файла с исходными данными, gridin. txt:
7 7
B
6 1 1 3 5 6 1 5 0 0
W
3 1 4 2 4 3 7 4 4 4
7 5 2 6 5 7 0 0
Пример файла результата, pathout. txt:
1 7
DDDDDLDLLLULLUUUURDDDRUUUURRDDLDDRRUUUU
R
Наглядный пример исходных данных
Реализовать графическое отображения действий в режиме реального времени.
