Задачи для самостоятельного решения. 1.4.2.1. Слияние 3-х упорядоченных массивов

1.4.2.1. Слияние 3-х упорядоченных массивов. Даны три массива целых чисел из k, n и m элементов. Слить все три массива в новый из k+n+m элементов, пройдя по каждому исходному массиву от начала до конца по одному разу. В первой строке задаётся размер первого массива n, во второй строке – сам массив. Второй и третий массивы заданы таким же образом. Вывести массив-результат.

Исходные данные:

1 2 5 6

1 3 5 7 7 9

1 2 3 4 5

Результат:

1 1 1 2 2 3 3 4 5 5 5 6 7 7 9

1.4.2.2, Поиск пересечения 2-х упорядоченных массивов. Даны два массива целых чисел из n и m элементов. Выбрать в новый массив те элементы, которые есть в обоих исходных массивах, пройдя по каждому исходному массиву от начала до конца по одному разу. В первой строке задаётся размер первого массива n, во второй строке – сам массив. Второй массив задан таким же образом. Вывести массив-результат.

Исходные данные:

1 2 5 6

1 3 5 7 7 9

Результат:

1 5

1.4.2.3. Поиск разности 2-х упорядоченных массивов. Даны два массива целых чисел из n и m элементов. Выбрать в новый массив те элементы, которые есть в первом массиве и отсутствуют во втором, пройдя по каждому исходному массиву от начала до конца по одному разу. В первой строке задаётся размер первого массива n, во второй строке – сам массив. Второй массив задан таким же образом. Вывести массив-результат.

Исходные данные:

1 2 5 6

1 3 5 7 7 9

Результат:

2 6

1.4.2.4. Параллельная сортировка. Даны два целочисленных массива из n элементов. Упорядочить элементы первого массива по возрастанию, параллельно переставляя соответствующие элементы и второго массива. В первой строке задаётся размер каждого массива n, во второй и третьей строке – сами массив. Вывести массивы-результаты.

Исходные данные:

3 1 2 5 4 6

1 3 5 7 8 9

Результат:

1 2 3 4 5 6

3 5 1 8 7 9

1.4.2.5. Лексикографическая сортировка строк. Дан массив символьных строк. Напечатать эти строки в словарном порядке. В первой строке задаётся количество строк n, во второй и далее – сортируемые строки. Вывести упорядоченные строки.

Исходные данные:

пример

простого

лёгкого

текста

Результат:

лёгкого

пример

простого

текста

1.4.2.6. Двоичный поиск значения в упорядоченном массиве. Дан упорядоченный по возрастанию массив из n целых чисел и некоторое целое значение x. Напечатать номер элемента массива, который совпадает с заданным значением. Если таких элементов нет, напечатать -1. В первой строке задаётся размер массива n, во второй строке – сам массив. В третьей строке – искомое значение.

Исходные данные:

1 3 5 7 7 9

Результат:

-1

1.4.2.7. Расстояние Хэмминга. В связи с особенностями линии связи, используемой для передачи сообщений из пункта A в пункт B, каждый бит принятого сообщения с вероятностью 0.001 содержит ошибку. Из пункта A в пункт B было послано одно из n сообщений m₁, m₂, ..., m_n. В пункте B было принято сообщение s. Ваша задача заключается в определении наиболее вероятного исходного сообщения. Очевидно, что оно будет одним из тех сообщений, расстояние Хэмминга между которым и строкой s минимально. Расстоянием Хэмминга двух строк a и b одинаковой длины называется количество позиций, в которых эти строки различаются (количество элементов в множестве {i | 1 ≤ i ≤ |a|, a_i ≠ b_i }).

Первая строка содержит s — принятое сообщение. Вторая строка содержит целое число n — количество сообщений, которые могли быть отправлены. Следующие n строк содержат m_i — эти сообщения. Длины всех сообщений равны (|s| = |m₁| = |m₂| = ... = |m_n|). Сообщения состоят только из символов 0 и 1. Размер входного файла не превосходит 60 Кб.

В первую строку вывести k — количество сообщений, на которых достигается минимум расстояния Хэмминга. Во вторую строку выведите в порядке возрастания k чисел — номера этих сообщений.

Исходные данные:

010101
3
110011
011001
000111

Результат:

2 3

1.4.2.8. Пересечение множеств. Даны два неупорядоченных набора целых чисел (может быть, с повторениями). Выдать без повторений в порядке возрастания все те числа, которые встречаются в обоих наборах. В первой строке записано через пробел два целых числа N и М (1 ≤ N, М ≤ 10⁶) — количество элементов первого и второго наборов, соответственно. В следующих строках записано сначала N чисел первого набора, а затем M чисел второго набора. Числа разделены пробелами или символами конца строки. Каждое из этих чисел попадает в промежуток от 0 до 10⁵. Вывесим в возрастающем порядке без повторений все числа, которые входят как в первый, так и во второй набор. Числа разделять одним пробелом. Если таких чисел нет, то выходной файл должен оставаться пустым.

Исходные данные:

11 6
2 4 6 8 10 12 10 8 6 4 2
3 6 9 12 15 18

Результат:

6 12

1.4.2.9. Преобразование последовательности. Задана последовательность, содержащая n целых чисел. Необходимо найти число, которое встречается в этой последовательности наибольшее количество раз, а если таких чисел несколько, то найти минимальное из них, и после этого переместить все такие числа в конец заданной последовательности. Порядок расположения остальных чисел должен остаться без изменения. Например, последовательность 1, 2, 3, 2, 3, 1, 2 после преобразования должна превратиться в последовательность 1, 3, 3, 1, 2, 2, 2. Написать программу, которая решает данную задачу.

Первая строка содержит число n — количество чисел во входной последовательности (3 ≤ n ≤ 200000). Следующая строка содержит входную последовательность, состоящую из n целых чисел, не превышающих по модулю 10⁶. Все числа в строке разделены пробелом.

Выводится последовательность чисел, которая получается в результате названного преобразования. Все числа в последовательности должны быть разделены пробелом.

Исходные данные:

7
1 2 3 2 3 1 2

Результат:

1 3 3 1 2 2 2

1.4.2.10. Несоставляемое число. Дано N натуральных чисел. Требуется найти минимальное натуральное число, не представимое суммой никаких из этих чисел, если в эту сумму каждое исходное число может входить не более одного раза. В первой строке содержит натуральное число N, не превосходящее 10⁴, далее следуют N строк, в каждой из которых записано по одному натуральному числу, каждое из которых не превосходит 10⁹.

Исходные данные:

4
1
1
1
5

Результат:

1.4.2.11. Плавающие числа. Дано N целых чисел. Каждое из них можно один раз изменить не более чем на целую величину L как в сторону увеличения, так и в сторону уменьшения или оставить без изменения. Если после такой операции некоторые из чисел оказываются равными, то они засчитываются за одно. С данными числами произвели указанную операцию таким образом, что осталось минимально возможное количество чисел. Написать программу для определения этого количества. В первой строке находятся натуральные числа L и N (N<=100, L<=3200), во второй строке N чисел (в диапазоне от -32000 до 32000), записанных через пробел.

Исходные данные:

5 3
6 10 27

Результат:

1.4.2.12. Число в последовательности. Последовательность 011212201220200112… строится следующим образом: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, и т.д.

Требуется написать программу, которая по заданному натуральному числу N определяет, какое число стоит на N-ом месте. Вводится число N (1 <= N <= 2147483647).

Исходные данные:

Результат:

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

В первой строке записано натуральное число N (N < 10⁵) – количество зафиксированных посетителей в музее в течении суток. Далее, идут N строк с информацией о времени визитов посетителей: в каждой строке располагается отрезок времени посещения в формате «ЧЧ:ММ ЧЧ:ММ» (00:00 ≤ ЧЧ:ММ ≤ 23:59). Вывести одно целое число — максимальное количество посетителей, одновременно находящихся в музее.

Исходные данные:

6
09:00 10:07
10:20 11:35
12:00 17:00
11:00 11:30
11:20 12:30
11:30 18:15

Результат:

1.4.2.14. Точки и отрезки. Дано N отрезков на числовой прямой и M точек на этой же прямой. Для каждой из данных точек определите, скольким отрезкам она принадлежит. Точка x считается принадлежащей отрезку с концами a и b, если выполняется двойное неравенство min(a, b) <= x <= max(a, b). Первая строка содержит два целых числа N – число отрезков и M – число точек (1 <= N, M <= 10⁵). В следующих N строках по два целых числа a_i и b_i – координаты концов соответствующего отрезка. В последней строке M целых чисел – координаты точек. Все числа во входном файле не превосходят по модулю 10⁹. Вывести M чисел – для каждой точки количество отрезков, в которых она содержится.

Исходные данные:

3 2
0 5
-3 2
7 10
1 6

Результат:

2 0

1.4.2.15. Кассы. На одном из московских вокзалов билеты продают N касс. Каждая касса работает без перерыва определенный промежуток времени по фиксированному расписанию (одному и тому же каждый день). Требуется определить, на протяжении какого времени в течение суток работают все кассы одновременно.

В первой строке располагается одно целое число N (0 < N <= 1000). В каждой из следующих N строк через пробел расположены 4 целых числа, первые два из которых обозначают время открытия кассы в часах и минутах (часы — целое число от 0 до 23, минуты — целое число от 0 до 59), остальные два — время закрытия в том же формате. Числа разделены пробелами. Время открытия означает, что в соответствующую ему минуту касса уже работает, а время закрытия — что в соответствующую минуту касса уже не работает. Например, касса, открытая с 10 ч 30 мин до 18 ч 30 мин, ежесуточно работает 480 минут. Если времена открытия и закрытия совпадают, то это означает, что касса работает круглосуточно. Если первое время больше второго, то это означает, что касса начинает работу до полуночи, а заканчивает — на следующий день.

Вывести одно число — суммарное время за сутки (в минутах), на протяжении которого работают все N касс.

Исходные данные:

3
1 0 23 0
12 0 12 0
22 0 2 0

Результат:

1.4.2.16. Дан массив целых числе. Переставить его элементы так, чтобы их квадраты шли в порядке не убывания. Первая строка содержит число n — количество чисел во входной последовательности (3 ≤ n ≤ 200000). Следующая строка содержит входную последовательность, состоящую из n целых чисел и разделённых одним пробелом. Напечатать упорядоченный массив. Если решение неоднозначно – найти любое.

Исходные данные:

-2 -2 -1 0 0 0 2 2 3 3 5

Результат:

0 0 0 -1 2 -2 -2 2 3 3 5

Продвинутые задачки.

1.4.3.1. Сортировка слиянием. На каждом этапе большой массив разбивается на две части, каждая из которых отдельно упорядочивается (сортируется). Потом обе части снова сливаются в единый (уже упорядоченный) массив за один проход. К каждой части применяется та же процедура. Разбиение продолжается до тех пор, пока в массиве не останется только два элемента, которые упорядочиваются за одно сравнение.

1.4.3.2. Множество М. Вычислить и напечатать первые n ( <=10000) элементов множества M в порядке возрастания.

Определение множества М:

1) 1 принадлежит M;

2) если число x принадлежит M, то и числа 2x+1 и 3x+1 также принадлежат множеству M. Все элементы должны быть различны. Число n вводится.

Исходные данные:

Результат:

1 3 4 7 9 10 13 15 19 21 22

1.4.3.3. Отрицательные влево, положительные вправо. В массиве целых чисел переставить элементы так, чтобы все отрицательные числа оказались в начале массива в том же порядке, что в исходном массиве. Аналогично положительные элементы должны оказаться в конце массива, а нули – между отрицательными и положительными. В первой строке задаётся размер массива n, во второй строке – сам массив. Вывести массив-результат.

Исходные данные:

2 0 -1 3 0 0 -2 2 -2 3 0

Результат:

-1 -1 -2 0 0 0 0 2 3 2 3

1.4.3.4. В упорядоченном массиве для заданного значения найти номер первого элемента с таким значением, если их несколько. Нумерация с 0. В первой строке задаётся размер массива n, во второй строке – сам массив, в третье – искомое значение.

Исходные данные:

-2 -2 -1 0 0 0 2 2 3 3 5

Результат:

1.4.3.5. В упорядоченном массиве целых чисел для заданного значения найти номер последнего элемента с таким значением, если их несколько. Нумерация с 0. В первой строке задаётся размер массива n, во второй строке – сам массив, в третье – искомое значение.

Исходные данные:

-2 -2 -1 0 0 0 2 2 3 3 5

Результат:

1.4.3.6. Закраска прямой. Интервал прямой с целочисленными координатами [a, b) содержит левую границу – точку a и не содержит правую границу – точку b.

Интервал от 0 до 10⁹ выкрасили в белый цвет. Затем было выполнено N операций перекрашивания. При каждой операции цвета в интервале, границы которого задаются, меняются на противоположный (белый на черный, черный на белый). Написать программу, которая найдет самый длинный интервал белого цвета после заданной последовательности операций перекрашивания. В первой строке находится число N (1 <= N <= 500) и затем N строк с границами интервалов (числа в диапазоне от 0 до 10⁹). Вывести одно число – длину самого большого белого интервала.

Исходные данные:

Результат:

1.4.3.7. В массиве целых чисел переставить элементы так, чтобы произведения пар соседних чисел шли в порядке не убывания. В первой строке задаётся размер массива n, во второй строке – элементы массива через пробел.

Исходные данные:

Результат:

Тема 1.5. Символьные строки (тексты)

Цель.

Изучение особенностей массивов, содержащих символьную информацию (строки, тексты).

Основные понятия.

Во многих языках программирования для работы с текстами (символьными строками) используются массивы типа char со специальным символов конца ‘\0’ или специальные классы типа string. Для них разработано много специальных функций и методов классов. Приведём некоторые из них для символьных массивов:

int strlen (char *) – функция вычисляет длину строки

char * strcpy (char *, char *) – копирует вторую строку по первому адресу (массивы нельзя присваивать)

int strcmp (char *, char *) – сравнивает две строки

char * strcat (char *, char *) – присоединяет вторую строку в конец первой

Обычно тексты обрабатываются по символам или по словам (группам символов).

Для ввода символьных строк используют специальные функции, т.к. пробелы играют особую роль и рассматриваются в стандартных функциях и операциях как разделители. При выводе символьных строк можно воспользоваться и стандартными операциями и функциями.

gets (char *)

cin.getline (char *, int)

Ключевые слова.

Строка, текст, слово, символ, нулевой символ, адрес, указатель

ПРИМЕР.

Написать программу, которая вычислит и напечатает количество слов в заданном тексте. Текст состоит из последовательности слов, разделённых пробелами. Слово содержит произвольные символы (буквы), отличные от пробела. Слово не является частью другого слова и не содержит в себе другие слова.

Алгоритм.

Будем последовательно выделять каждое слово и вести их подсчёт. Начало слова определяется как не пробел, конец слова находится по пробелу или концу текста. Схема обработки слов может выглядеть так:

ЦИКЛ до конца текст – будет найдено и обработано ровно одно слово

НАЙТИ начало слова (в цикле пропустить все пробелы)

ЕСЛИ достигли конца текста, ТО ВЫХОД из цикла

ЗАПОМНИТЬ позицию начала слова

НАЙТИ конец слова (в цикле пропустить все не пробелы)

ЗАПОМНИТЬ позицию конца слова

ОБРАБОТАТЬ слов – зависит от конкретной задачи

КОНЕЦ_ЦИКЛА

ПЕЧАТЬ результатов

Решение.

Согласно приведённому алгоритму напишем программу. Наша программа будет содержать большой цикл по словам и внутри него два цикла для поиска начала и конца слова. В зависимости от задачи циклы могут быть и в пункте ОБРАБОТАТЬ СЛОВО.

// C++

# include <iostream>

# include <cstring>

# include <cstdlib>

using namespace std;

const int N = 100000; // заранее заведём большой массив для текста

char text [N];

int main ()

{

setlocale (LC_ALL, "RUS");

cout << "Подсчёт количества слов в тексте." << endl;

cout << "Введите текст." << endl;

cin.getline (text, N-1); // текст может содержать любые символы

int kol=0;

// ЦИКЛ до конца текст – будет найдено и обработано ровно одно слово

for ( int i=0; text [i] != 0; )

{

// НАЙТИ начало слова (в цикле пропустить все пробелы)

for ( ; text [i] == ' '; i++ )

;

// ЕСЛИ достигли конца текста, ТО ВЫХОД из цикла

if (text [i] == 0 ) break;

// НАЙТИ конец слова (в цикле пропустить все не пробелы)

for ( ; text [i] != 0 && text [i] != ' '; i++ )

;

kol++; // ОБРАБОТАТЬ слово – зависит от конкретной задачи

}

cout << kol << endl; // ПЕЧАТЬ результатов

system ("PAUSE");

return 0;

}

// C#

using System;

class Program

{

static void Main (string [] args)

{

Console.WriteLine ("Подсчёт количества слов в тексте.");

Console.WriteLine ("Введите тексте");

string s = Console.ReadLine ();

int kol=0;

for ( int i=0; i < s.Length; )

{

for ( ; (i < s.Length) && (s [i] == ' '); i++ )

;

if ( i == s.Length ) break;

for ( ; (i < s.Length) && (s [i] != ' '); i++ )

;

kol++;

}

Console.WriteLine (kol);

Console.ReadKey ();

}

}