Решите задачи. Задание A.

Структуры данных
1. Счёт людей
Вокруг считающего стоит N человек, из которых выделен первый, а остальные занумерованы по часовой стрелке числами от 2 до N. Считающий, начиная с первого человека, ведет счет до M. Человек, на котором остановился счет, выходит из круга. Счет продолжается со следующего человека и так до тех пор, пока не останется один человек.
Определить номер оставшегося человека.
2. Карточки
Имеется n черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая под низ стопки, третья- на стол, четвертая — под низ стопки и т.д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т.д.
3. Чиновники
Есть министерство из N чиновников, где N натуральное число. У каждого из чиновников могут быть как подчиненные, так и начальники, причем справедливы правила: подчиненные моего подчиненного — мои подчиненные, начальники моего начальника — мои начальники, мой начальник не есть мой подчиненный, у каждого чиновника не более одного непосредственного начальника.
Для того чтобы получить лицензию на вывоз меди необходимо получить подпись 1-ого чиновника — начальника всех чиновников. Проблема осложняется тем, что каждый чиновник, вообще говоря, может потребовать «визы», т.е. подписи некоторых своих непосредственных подчиненных и взятку — известное количество долларов. Для каждого чиновника известен непустой список возможных наборов «виз» и соответствующая каждому набору взятка. Пустой набор означает, что данный чиновник не требует виз в данном случае. Чиновник ставит свою подпись лишь после того, как ему представлены все подписи одного из наборов «виз» и уплачена соответствующая взятка.
Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость.
N Перебор
1. Выражение
Вводится строка не более чем из 6 цифр и некоторое целое число R. Расставить знаки арифметических операций («+», «-«, «*», «/»; минус не является унарным, т.е. не может обозначать отрицательность числа; деление есть деление нацело, т.е. 11/3=3) и открывающие и закрывающие круглые скобки так, чтобы получить в результате вычисления получившегося выражения число R. Лишние круглые скобки ошибкой не являются.
Например: Строка 505597, R=120: ((5+0)*((5*5)-(9/7)))=120.
2. Прямоугольники.
Написать программу, отвечающую на вопрос, можно ли из N данных прямоугольников Пi размеров (ai, bi), i=1,…,N, сложить один большой прямоугольник П размера (a, b). Нижний левый угол большого прямоугольника имеет координату (0,0), стороны параллельны осям координат; маленькие прямоугольники можно поворачивать, но так, чтобы их стороны после поворота оставались параллельны осям координат. При составлении П прямоугольники Пi могут быть использованы не все. Прямоугольники Пi не перекрываются.
Ограничения: N<8, a, b, ai, bi — целые числа.
Ответ выдать в виде ‘да’ — ‘нет’, и в случае ‘да’ необходимо
выдать для каждого прямоугольника Пi, образующего П, координату
его левого нижнего и правого верхнего углов и его номер i.

Геометрия

1. Квадрат
На двумерной плоскости задано N точек с координатами (X1,Y1), (X2,Y2), …, (Xn, Yn). Написать программу, которая из этих точек выделяет вершины квадрата, содержащего максимальное число заданных точек.
ПРИМЕЧАНИЕ: предполагается, что точки, расположенные на сторонах квадрата, принадлежат ему.
2. Торт
На квадратном торте N свечей. Можно ли одним прямолинейным разрезом разделить его на две равные по площади части, одна из которых не содержала бы ни одной свечи? Свечи будем считать точками, у которых известны их целочисленные координаты (Х1, Y1), …, (Хn, Yn). Начало координат — в центре торта. Разрез не может проходить через свечу.
3. Симметрия
На плоскости задан N-угольник координатами своих вершин в порядке обхода по контуру. Найти сколько осей симметрии у этой фигуры.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

методические материалы по информатике