Алгоритмические задачи

Лабораторная №3

Алгоритмические задачи

Реализовать игру “Сапер”. Размер поля - N x N.
Реализовать игру “Жизнь” https://ru.wikipedia.org/wiki/%D0%98%D0%B3%D1%80%D0%B0_%C2%AB%D0%96%D0%B8%D0%B7%D0%BD%D1%8C%C2%BB
Реализовать игру “Морской бой. Размер поля 10 x 10. Компьютер должен интерактивно играть с игроком.
Реализовать игру Packman. Сделать 1 уровень, который загружается и файлы. Алгоритмы движения привидений можно переопределить. https://ru.wikipedia.org/wiki/Pac-Man
Реализовать игру “Города”. БД с городами хранить в текстовом файле.
Реализовать игру “Змейка”.
На плоскости задан треугольник (заданы 3 точки) и точка. Определить, попадает ли точка в треугольник (с использованием трех уравнений прямых)
В таблице из N строк и N столбцов клетки заполнены числами от 0 до 9. Требуется найти такой путь из клетки (1,1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной. Из любой клетки ходить можно только вниз или вправо.
Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти площадь многоугольника. Стороны многоугольника не соприкасаются (за исключением соседних — в вершинах) и не пересекаются.
Два различных натуральных числа называются дружественными, если первое из них равно сумме делителей второго числа, за исключением самого второго числа,а второе равно сумме делителей первого числа, за исключением самого первого числа. Требуется найти все пары дружественных чисел, оба из которых принадлежат промежутку от М до М.
В таблице из N строк и N столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.
Лабиринт представляет собой квадрат, состоящий из N х N сегментов. Каждый из сегментов может быть либо пустым, либо заполненным камнем. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесен сверху, снизу, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри. Помогите ему рассчитать количество краски, необходимой для этого.

Ограничения: 3 < N < 33, размер сегмента 3 х 3 м, высота стен 3 м.

Из прямоугольного листа клетчатой бумаги (М строк, N столбцов) удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.
Дана шахматная доска, состоящая из N х N клеток; несколько из них вырезано. Провести ходом коня через невырезанные клетки путь минимальной длины из одной заданной клетки в другую.
Прямоугольный садовый участок шириной N длиной М метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:

из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).

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

Источники:

Окулов С.М. Программирование в алгоритмах /С.М. Окулов. - М.:БИНОМ. Лаборатория знаний, 2004. - 341 с.: ил. ISBN 5-94774-010-9
Меньшиков Ф.В. Олимпиадные задачи по программированию - СПб.: Питер, 2006 - 315 с.: ил