Задача 1.
Предположим, что имеется некоторый кусок ленты, разделенный на кадры. Кадры занумерованы с двух сторон. Полоска ленты склеена в лист Мебиуса. Необходимо составить алгоритм упорядочения этой последовательности, предположив, что соседние кадры можно переставлять, (естественно, в упорядоченной последовательности будет один "скачок" от минимального элемента к максимальному). Следует учесть, что при перестановки кадров переставляются числа с обеих сторон кадров. Пример:
Есть 2 кадра 
А1, В1 - одна сторона кадров,
А2, В2 - другая.
Пусть А1=1, А2=2, В1=7, В2=3. Тогда после перестановки содержащего А« В будет А1=7, А2=3, В1=1, В2=2).
Всегда ли такое упорядочение возможно?
[Решение]
Задача 2.
Имеется N камней веса А1,А2,...,АN.
Необходимо разбить их на две кучи таким образом, чтобы веса куч отличались не более чем в 2 раза. Если этого сделать нельзя, то указать это.
[Решение]
Задача 3.
Условие задачи 2, только веса куч отличаются не более, чем в 1,5 раза.
[Решение]
Задача 4.
Имеется N человек и целые числа А1, ..., AN; человека i необходимо познакомить с Аi людьми. Можно ли это сделать?
[Решение]
Задача 5.
Условие задачи 4. Кого с кем знакомить, чтобы это сделать?
[Решение]
Задача 6.
Даны две целочисленных таблицы А [1:10] и В[1:15]. Разработать алгоритм и написать программу, которая проверяет, являются ли эти таблицы похожими. Две таблицы называются похожими, если совпадают множества чисел, встречающихся в этих таблицах.
[Решение]
Задача 7.
Задается словарь. Найти в нем все анаграммы (слова, составленные из одних и тех же букв).
[Решение]
Задача 8.
Задано семейство множеств букв. Найти такое k, для которого можно построить множество, состоящее из k букв, причем каждая из них принадлежит ровно k множествам заданного семейства.
[Решение]
Задача 9.
На прямой окрасили N отрезков.Известны координата L[I] левого конца отрезка и координата R[I] правого конца I-го отрезка для I=1, ..., N. Найти сумму длин всех окрашенных частей прямой.
Примечание. Число N столь велико, что на выполнение N*N даже простейших операций не хватит времени.
МОДИФИКАЦИЯ. На окружности окрасили N дуг. Известны угловая координата L[I] начала и R[I] конца I-ой дуги (от начала к концу двигались, закрашивая дугу, против часовой стрелки). Какая доля окружности окрашена?
[Решение]
Задача 10.
Имеется 2*N чисел. Известно что их можно разбить на пары таким образом, что произведения чисел в парах равны. Сделать разбиение, если числа
а) натуральные;
б) целые.
[Решение]
Задача 11.
Имеются числа А1,А2,...,АN и B1,B2,...,BN. Составить из них N пар (Аi, Bj) таким образом, чтобы сумма произведений пар была максимальна (минимальна). Каждое Ai и Bj в парах встречаются ровно по одному разу.
[Решение]
Задача 12.
В музее регистрируется в течение дня время прихода и ухода каждого посетителя. Таким образом за день получены N пар значений, где первое значение в паре показывает время прихода посетителя и второе значения - время его ухода. Найти промежуток времени, в течение которого в музее одновременно находилось максимальное число посетителей.
[Решение]
Задача 13.
Упорядочить по невозрастанию 5 чисел за 7 операций сравнения.
[Решение]
Задача 14.
Задаются число n>1 - размерность пространства и pазмеpы М n-мерных параллелепипедов (ai1 , ..., ain), i=1,...,M.
Паpаллелепипед может располагаться в пространстве любым из способов, при которых его ребра параллельны осям координат. Найти максимальную последовательность вкладываемых друг в друге паpаллелепипедов.
[Решение]
Задача 15.
Пусть A - множество из N натуральных чисел. Ваша программа должна определить, существует ли по крайней мере одно подмножество B множества A, имеющие cледующее свойство (*) для любых X,Y,Z из B, X<>Y<>Z<>X,
X+Y+Z <=е {t: t из B\{X,Y,Z}},
тут B\{X,Y,Z} означает 'множество B без элементов X,Y и Z'.
В случае положительного ответа программа должна найти подмножество B, удовлетворяющее условию (*) и состоящее из максимально возможного числа элементов.
[Решение]
Задача 16.
Дано положительное целое число К и К целых чисел А(1),...,А(К). Вычислить
а) наибольшее,
b) наименьшее,
c) наиболее близкое к нулю,
d) наиболее близкое к заданному числу Р возможное значение суммы
S(М,N)=А(М)+А(М+1)+...+А(N-1)+А(N),
где 1<=М<=N<=К.
Примечание. Число К столь велико, что числа А(1),А(2), ..., А(К) занимают примерно одну пятую памяти, отводимой для хранения данных, а на выполнение К2 даже простейших операций не хватает времени.
[Решение]
Задача 17.
Даны целые M и N и вектор действительных чисел X[1..N]. Найти целое число i (1<=i<=N-M), для которого сумма x[i]+...+x[i+M] ближе всего к нулю.
[Решение]
Задача 18.
Есть два отсортированных в порядке неубывания массива A[1,N] и B[1,M]. Получить отсортированный по неубыванию массив C[1,N+M], состоящий из элементов массивов A и B ("слить" вместе массивы A и B).
[Решение]
Задача 19.
Дан массив X[1..N]. Необходимо циклически сдвинуть его на k элементов вправо (т.е. элемент X[i] после сдвига должен стоять на месте X[i+k]; тут мы считаем что за X[N] следует X[1]). Разрешается использовать только несколько дополнительных слов памяти (Дополнительного массива заводить нельзя!).
[Решение]
Задача 20.
Построить максимальное множество, состоящее из попарно не сравнимых векторов v. Векторы v определяются парами чисел, выбираемые из данной последовательности чисел а1, ...аn , n>=1. Два вектора v=(а,в) и v'=(а',в') называются сравнимыми, если а<=а' и в<=в' или а>=а' и в>= в', в противном случае не сравнимыми.
[Решение]
|
