Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Сортировка

[Назад]    [Содержание ]    [Вперед]

  


Сортировка



  Номер 1

К »


Задача 1. Предположим, что имеется некоторый кусок ленты, разделенный на кадры. Кадры занумерованы с двух сторон. Полоска ленты склеена в лист Мебиуса. Необходимо составить алгоритм упорядочения этой последовательности, предположив, что соседние кадры можно переставлять, (естественно, в упорядоченной последовательности будет один "скачок" от минимального элемента к максимальному). Следует учесть, что при перестановки кадров переставляются числа с обеих сторон кадров. Пример: Есть 2 кадра А1, В1 - одна сторона кадров, А2, В2 - другая. Пусть А1=1, А2=2, В1=7, В2=3. Тогда после перестановки содержащего А< В будет А1=7, А2=3, В1=1, В2=2). Всегда ли такое упорядочение возможно?

Решение


  Номер 2

К »


Задача 2. Имеется N камней веса А1,А2,...,АN. Необходимо разбить их на две кучи таким образом, чтобы веса куч отличались не более чем в 2 раза. Если этого сделать нельзя, то указать это.

Решение


  Номер 3

К »


Задача 3. Условие задачи 2, только веса куч отличаются не более, чем в 1,5 раза.

Решение


  Номер 4

К »


Задача 4. Имеется N человек и целые числа А1, ..., AN; человека i необходимо познакомить с Аi людьми. Можно ли это сделать?

Решение


  Номер 5

К »


Задача 5. Условие задачи 4. Кого с кем знакомить, чтобы это сделать?

Решение


  Номер 6

К »


Задача 6. Даны две целочисленных таблицы А [1:10] и В[1:15]. Разработать алгоритм и написать программу, которая проверяет, являются ли эти таблицы похожими. Две таблицы называются похожими, если совпадают множества чисел, встречающихся в этих таблицах.

Решение


  Номер 7

К »


Задача 7. Задается словарь. Найти в нем все анаграммы (слова, составленные из одних и тех же букв).

Решение


  Номер 8

К »


Задача 8. Задано семейство множеств букв. Найти такое k, для которого можно построить множество, состоящее из k букв, причем каждая из них принадлежит ровно k множествам заданного семейства.

Решение


  Номер 9

К »


Задача 9. На прямой окрасили N отрезков.Известны координата L[I] левого конца отрезка и координата R[I] правого конца I-го отрезка для I=1, ..., N. Найти сумму длин всех окрашенных частей прямой. Примечание. Число N столь велико, что на выполнение N*N даже простейших операций не хватит времени. МОДИФИКАЦИЯ. На окружности окрасили N дуг. Известны угловая координата L[I] начала и R[I] конца I-ой дуги (от начала к концу двигались, закрашивая дугу, против часовой стрелки). Какая доля окружности окрашена?

Решение


  Номер 10

К »


Задача 10. Имеется 2*N чисел. Известно что их можно разбить на пары таким образом, что произведения чисел в парах равны. Сделать разбиение, если числа а) натуральные; б) целые.

Решение


  Номер 11

К »


Задача 11. Имеются числа А1,А2,...,АN и B1,B2,...,BN. Составить из них N пар (Аi, Bj) таким образом, чтобы сумма произведений пар была максимальна (минимальна). Каждое Ai и Bj в парах встречаются ровно по одному разу.

Решение


  Номер 12

К »


Задача 12. В музее регистрируется в течение дня время прихода и ухода каждого посетителя. Таким образом за день получены N пар значений, где первое значение в паре показывает время прихода посетителя и второе значения - время его ухода. Найти промежуток времени, в течение которого в музее одновременно находилось максимальное число посетителей.

Решение


  Номер 13

К »


Задача 13. Упорядочить по невозрастанию 5 чисел за 7 операций сравнения.

Решение


  Номер 14

К »


Задача 14. Задаются число n>1 - размерность пространства и pазмеpы М n-мерных параллелепипедов (ai1 , ..., ain), i=1,...,M. Паpаллелепипед может располагаться в пространстве любым из способов, при которых его ребра параллельны осям координат. Найти максимальную последовательность вкладываемых друг в друге паpаллелепипедов.

Решение


  Номер 15

К »


Задача 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

К »


Задача 16. Дано положительное целое число К и К целых чисел А(1),...,А(К). Вычислить а) наибольшее, b) наименьшее, c) наиболее близкое к нулю, d) наиболее близкое к заданному числу Р возможное значение суммы S(М,N)=А(М)+А(М+1)+...+А(N-1)+А(N), где 1<=М<=N<=К. Примечание. Число К столь велико, что числа А(1),А(2), ..., А(К) занимают примерно одну пятую памяти, отводимой для хранения данных, а на выполнение К2 даже простейших операций не хватает времени.

Решение


  Номер 17

К »


Задача 17. Даны целые M и N и вектор действительных чисел X[1..N]. Найти целое число i (1<=i<=N-M), для которого сумма x[i]+...+x[i+M] ближе всего к нулю.

Решение


  Номер 18

К »


Задача 18. Есть два отсортированных в порядке неубывания массива A[1,N] и B[1,M]. Получить отсортированный по неубыванию массив C[1,N+M], состоящий из элементов массивов A и B ("слить" вместе массивы A и B).

Решение


  Номер 19

К »


Задача 19. Дан массив X[1..N]. Необходимо циклически сдвинуть его на k элементов вправо (т.е. элемент X[i] после сдвига должен стоять на месте X[i+k]; тут мы считаем что за X[N] следует X[1]). Разрешается использовать только несколько дополнительных слов памяти (Дополнительного массива заводить нельзя!).

Решение


  Номер 20

К »


Задача 20. Построить максимальное множество, состоящее из попарно не сравнимых векторов v. Векторы v определяются парами чисел, выбираемые из данной последовательности чисел а1, ...аn , n>=1. Два вектора v=(а,в) и v'=(а',в') называются сравнимыми, если а<=а' и в<=в' или а>=а' и в>= в', в противном случае не сравнимыми.

Решение



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017