Задачи повышенной сложности

Задача 4.1

В круге стоят N человек (рис.). Они пронумерованы от 1 до N. Поочередно из круга начинает выходить каждый третий человек. Это продолжается до тех пор, пока в круге не останется последний человек. Определить его номер.
Например, если в круге стояло 7 человек, то его поочерёдно покинут 3, 6, 2, 7, 5, 1. Оставшимся будет человек, стоявший на 4 месте.

Задача 4.2

Вывести на экран цифры числа 3¹⁰⁰⁰. Если попытаться получить число непосредственно умножением, компьютер выдаст сообщение об ошибке.

Задача 4.3

Написать программу для умножения двух чисел, количество цифр в каждом из которых может достигать 100. Например, для умножения вида:
9278969345897569872365*5705782370079678659.

Задача 4.4

Сообщество роботов живет по следующим законам: один раз в год они объединяются в полностью укомплектованные группы по 3 или 5 роботов (причем число групп из 3 роботов - максимально возможное). За год группа из 3 роботов собирает 5, а группа из 5 - 9 новых собратьев. Каждый робот живет 3 года после сборки. Известно начальное количество роботов (К>7), все они только что собраны. Определить сколько роботов будет через N лет.

Задача 4.5

На квадратном клетчатом листе бумаги 8x8 клеток заштрихована часть клеток (пример на рисунке). Определить вписанный в решётку прямоугольник максимальной площади, не содержащий заштрихованных клеток. В качестве ответа вывести площадь прямоугольника и координаты его двух противоположных вершин. (Предполагается, что прямоугольник с максимальной площадью один.)
Для приведенного примера координаты вершин (3,4) и (7,6), площадь 15 клеток.

Задача 4.6

На квадратном клетчатом листе бумаги n на m клеток нарисовано несколько фигур, каждая из которых состоит только из целых клеток. Различные фигуры не накладываются и не соприкасаются (пример на рисунке). Определить фигуру максимальной площади. (В качестве ответа вывести площадь фигуры и координаты одной из её точек. Предполагается, что фигура с максимальной площадью одна.)
Например, на листе 8 на 8 клеток:

Площадь фигуры равна 6. Координаты одной из её клеток (2,3).

Задача 4.7

Подсчитайте количество одно-, двух-, трёх- и четырехпалубных кораблей, расположенных на поле для игры "Морской бой". Корабли не могут быть изогнутыми и друг с другом не соприкасаются. Поле для игры задается в виде таблицы 10x10, каждый элемент которой равен либо 0, если клетка свободна, либо 1, если занята.

Задача 4.8

Лабиринт задан в виде матрицы размером n на m. Стенам лабиринта соответствуют единицы, проходам - нули. Определить, можно ли из точки с координатами (i ₁, j ₁) попасть в точку с координатами (i ₂, j ₂). Для усложнения задачи можно предложить указать самый короткий путь из заданной точки, причем из всех путей одинаковой длины выбирать путь с наименьшим числом поворотов.

Задача 4.9

На рисунке изображен треугольник из чисел. Вычислите наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке треугольника и заканчивающемся на его основании. Каждый шаг на пути может идти вниз по диагонали влево или вниз по диагонали вправо. Число строк в треугольнике больше1 и не больше100. Треугольник составлен из целых чисел от 0 до 99.

Задача 4.10

Имеется n населенных пунктов, пронумерованных от 1 до n. Некоторые пары пунктов соединены дорогами (в том числе дорогами с односторонним движением). Определить, можно ли попасть по этим дорогам из одного заданного пункта в другой. (Для усложнения задачи можно предложить указать все возможные пути без петель и тупиков из одного пункта в другой).

Задача 4.11

Заданы две фразы. Определить наибольшую последовательность отличных от пробелов символов, входящую в обе фразы в одном и том же порядке. Например, в предложениях:
ПРИШЛА ВЕСНА и РАСТАЯЛ СНЕГ такая последовательность - Р,А,С,Н.

Задача 4.12

В морском порту города Владивостока хранятся N контейнеров (N - чётное число). Для погрузки контейнеров на судно, чтобы обеспечить равномерную загрузку, их необходимо разделить на две половины так, чтобы их массы были максимально близки. Решить эту задачу, предполагая, что информация о массах контейнеров (в тоннах) хранится в массиве M(N). В качестве ответа указать номера контейнеров одной половины и получаемые массы для каждой из половин.
Например:
Если M(6)=(10, 15, 18, 20, 16, 14), то одну половину составят 1, 4, 5 контейнеры (другую 2, 3, 6). Масса первой группы m1=10+20+16=46 т., масса второй группы m2=15+18+14=47 т.

Задача 4.13

На шахматной доске необходимо расставить 8 ферзей так, чтобы они не угрожали друг другу.

Задача 4.14

На шахматной доске размером 4x4 клетки расставить 4 ладьи так, чтобы они не угрожали друг другу. Определить все такие расстановки (всего их будет 24).