Задачи, решаемые с использованием сортировки

Задача: Дан ряд целых случайных чисел. Преобразуйте его в ряд чисел, между которыми можно было бы расставить знаки "<" и ">" в чередующемся порядке.

Идея решения: Ряд чисел СОРТИРУЕМ. Меняем местами каждую пару чисел.

Решение задачи на Бейсике:

Input "количество чисел"; ndim a(n)for i = 1 to n input "введите число"; a(i)nextrem=====сортируем массив===========for j=n to 2 step -1 for i=1 to j-1 if a(i)>a(i+1) then swap a(i), a(i+1)next i, jrem ====меняем местами пару чисел=====for i = 1 to n-1 step 2 swap a(i), a(i+1)nextprintfor i=1 to n print a(i);next

Решение задачи на Паскале:

var a: array [1..10] of integer; i,j,n,x:integer;begin writeln ('количество чисел'); readln (n); for i:= 1 to n do begin writeln ('введите число'); readln (a[i]); end; {=====сортируем массив==========} for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin x:=a[i]; a[i]:= a[i+1]; a[i+1]:=x; end; {====меняем местами пару чисел====} x:=1; for i:= 1 to (n div 2) do begin x:=a[j]; a[j]:= a[j+1]; a[j+1]:=x; j:=j+2; end; for i:=1 to n do writeln (a[i]);end.

Тест:

Дано:	5, 2, 1, 8, 0, 67, 100.
Результат:	1, 0, 5, 2, 67, 8, 100

Задачи "Подпоследовательности"

1. В последовательности чисел выделить все подпоследовательности подряд идущих чисел.

Идея решения: Ряд чисел СОРТИРУЕМ. Перебираем элементы массива, сравнивая два соседних элемента. Если разница между ними не равна единице, то начинаем печать новой подпоследовательности.

Решение задачи на Бейсике:

Input "количество чисел"; ndim a(n)for i = 1 to n input "введите число"; a(i)nextrem====сортируем массив===============for j=n to 2 step -1 for i=1 to j-1 if a(i)>a(i+1) then swap a(i), a(i+1)next i, jrem ==============================print a(1);for i = 2 to n if a(i) - a (i-1) < > 1 then printprint a(i);next

Решение задачи на Паскале:

var a: array [1..10] of integer; i,j,n,x: integer;begin writeln ('количество чисел'); readln (n); for i:= 1 to n do begin writeln ('введите число'); readln (a[i]); end; {=====сортируем массив=============} for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin x:=a[i]; a[i:= a[i+1]; a[i+1]:=x; end; {=============================} write (a[1]); for i:= 2 to n do begin if (a[i]-a[i-1]) <> 1 then writeln; write (a[i]); end;end.

Тест:

Дано:	N=10 2, 1, 5, 3, 7, 8, 6, 12, 9, 11
Результат:	1, 2, 3 5, 6, 7, 8, 9 11, 12

2. В последовательности чисел найти и вывести подпоследовательность подряд идущих чисел наибольшей длины.

Идея решения: Ряд чисел СОРТИРУЕМ. Перебираем элементы массива, сравнивая два соседних элемента. Если разница между ними равна единице, значит очередное число входит в текущую подпоследовательность. В ячейке К накапливаем ее длину. Применив типовой алгоритм поиска МАКСИМАЛЬНОГО ЭЛЕМЕНТА находим подпоследовательность наибольшей длины.

Решение задачи на Бейсике:

Input "количество чисел"; ndim a(n)for i = 1 to n input "введите число"; a(i)nextrem====сортируем массив==============for j = n to 2 step -1 for i = 1 to j - 1 if a(i) > a(i + 1) then swap a(i), a(i + 1)next i, jrem =выводим отсортированный массив======for i = 1 to n print a(i);nextprintmax = 0k = 1for i = 1 to n - 1 if a(i + 1) - a(i) = 1 then k = k + 1 else k = 1 if k > max then max = k: number = i + 1next iprint "максимальная длина="; maxprint "самая длинная подпоследовательность="for i=(number-max+1) to number print a(i);next

Решение задачи на Паскале:

var a: array [1..10] of integer; max,k,number,i,j,n,x: integer;begin writeln ('количество чисел'); readln (n); for i:= 1 to n do begin writeln ('введите число'); readln (a[i]); end; {=====сортируем массив================} for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin x:=a[i]; a[i]:= a[i+1]; a[i+1]:=x; end; {================================} max:= 0; k:= 1; for i: = 1 to n-1 do begin if a[i+1] - a[i] = 1 then k: = k + 1 else k: = 1; if k > max then begin max: = k; number: = i + 1; end; end; writeln ('максимальная длина=', max); writeln ('самая длинная подпоследовательность='); for i: = (number - max + 1) to number do writeln (a[i]);end.

Тест:

Дано:	N=10 2, 1, 5, 3, 7, 8, 6, 12, 9, 11
Результат:	Max=5 5, 6, 7, 8,9

Задача: Ввести предложение. Поменять порядок слов в нем, расположив их в порядке увеличения букв в словах.

Идея решения: Применив типовой алгоритм "РАЗБОРА" ПРЕДЛОЖЕНИЯ НА СЛОВА, помещаем каждое слово в элемент массива. Далее СОРТИРУЕМ массив слов, сравнивая количество букв в словах.

Решение задачи на Бейсике:

input "введите предложение"; a$n=len (a$)for i=1 to n if mid$(a$,i,1)=" " then k=k+1nextk=k+1 dim a$(k)j=1for i=1 to n if mid$(a$,i,1)=" " then j=j+1 else a$(j)=a$(j)+mid$(a$,i,1)nextrem=====сортируем массив=======================for j=k to 2 step -1 for i=1 to j-1 if len (a(i))>len (a(i+1)) then swap a(i), a(i+1)next i, jrem =======================================for i=1 to k print a(i); " ";next

Решение задачи на Паскале:

var b:array[1..10] of string; a,a1,a2,x: string; n,i,j,k: integer;begin writeln ('введите предложение'); readln (a); n:=length (a); k:=0; for i:=1 to n do if copy(a,i,1)=' ' then k:=k+1; k:=k+1; j:=1; for i:=1 to n do if copy(a,i,1)=' ' then j:=j+1 else b[j]:=b[j]+copy(a,i,1); {=====сортируем массив==============} for j:=k downto 2 do for i:=1 to j-1 do if length (b[i])>length (b[i+1]) then begin x:=b[i]; b[i]:= b[i+1]; b[i+1]:=x; end; { ==============================} for i:=1 to k do writeln (b[i]);end.

Тест:

Дано:	Мой любимый предмет - информатика
Результат:	- Мой предмет любимый информатика

Задачи "Сортировка частей массива"

Среди задач на сортировку элементов массива можно выделить большую группу задач, в которых необходимо отсортировать ЧАСТЬ МАССИВА ПО ВОЗРАСТАНИЮ, ЧАСТЬ ПО УБЫВАНИЮ.

Идея решения: Допустим, дан массив А, заполненный положительными и отрицательными целыми числами (рис. 4.2):

Рис. 4.2.

Необходимо отсортировать положительные элементы массива по возрастанию, отрицательные элементы оставить на своих местах.

· Вводим дополнительный массив В, который заполняем индексами положительных элементов массива А (рис. 4.3):

Рис. 4.3.

· Затем используем ТИПОВОЙ АЛГОРИТМ СОРТИРОВКИ, в качестве индексов перебираемых в цикле элементов массива Аиспользуем элементы массива В. Данное решение задачи также можно выделить в отдельный типовой алгоритм:

Программная реализация на Бейсике:

Input "количество чисел"; ndim a(n), b(n)for i = 1 to n input "введите число"; a(i)nextj=1for i=1 to n if a(i)>0 then b(j)=i: j=j+1:k=k+1next ifor j=k to 2 step -1 for i=1 to j-1 if a(b(i))>a(b(i+1)) then swap a(b(i)),a(b(i+1))next i,jfor i=1 to n print a(i); " ";next i

Программная реализация на Паскале:

const m=10;var a, b: array [1..m] of integer; i, j, n, x, k: integer;begin writeln ('количество чисел'); readln (n); for i:= 1 to n do begin writeln ('введите число'); readln (a[i]); end; j:=1; k:=0; for i:=1 to n do if a[i]>0 then begin b[j]:=i; j:=j+1; k:=k+1; end; for j:=k downto 2 do for i:=1 to j-1 do if a[b[i]]>a[b[i+1]] then begin x:=a[b[i]]; a[b[i]]:=a[b[i+1]]; a[b[i+1]]:=x; end; for i:=1 to n do write (a[i],' ');end.

Тест:

Дано:	N=9 -3, 5, -1, 3, 6, -8, 2, -1, -3
Результат:	-3, 2, -1, 3, 5, -8, 6, -1, -3

Ключевые термины

· Сортировка пузырьком - один из методов упорядочивания элементов одномерного массива.

· Подпоследовательность - фрагмент последовательности данных, выделенный по определенному признаку.

Краткие итоги

Сортировка элементов одномерного массива методом "Пузырька" основывается на сравнении двух соседних элементов. Элементы меняются местами, если больший элемент (при сортировке по возрастанию) оказывается левее меньшего элемента. За один проход элементов массива наибольший элемент оказывается в конце массива. Далее алгоритм повторяется с первого элемента до предпоследнего и т.д.

При сортировке частей массива (в зависимости от критериев отбора элементов в выбираемой части массива) в качестве индексов перебираемых в цикле элементов исходного массива А используем элементы дополнительного массива В (в нем хранятся индексы выбираемых элементов исходного массива).

Набор для практики

Вопросы.

· Что происходит за один проход массива при сортировке "Пузырьком"?

· Объясните зависимость счетчика внутреннего цикла от счетчика внешнего цикла в типовом алгоритме сортировки одномерного массива "Пузырьком".

Упражнения.

· Символьная строка состоит из цифр и латинских букв. Упорядочьте все цифры в порядке убывания, а буквы в алфавитном порядке, оставляя и те и другие на своих местах.

· В массиве натуральных чисел все простые числа упорядочьте по возрастанию, составные по убыванию.

· Найдите в тексте все гласные буквы и расположите их в порядке возрастания номеров алфавита, а все согласные буквы - в порядке убывания номеров алфавита.

· Ввести предложение. Измените порядок слов в предложении, расположив в алфавитном порядке (по первой букве каждого слова).

Задачи, сгруппированные по методам решения. Использование дополнительного массива "флажков"

Для решения некоторых задач на одномерные массивы часто бывает необходимо каким-либо образом отметить элементы, удовлетворяющие условию. Для этого резервируют дополнительный массив Flag, элементы которого заполняют единицами, если соответствующие элементы исходного массива удовлетворяет условию.

Если условий несколько, то "флажки" принимают разное значение (например: "1" и "-1" и др.). Рассмотрим данный прием на практике.

Задача 1: Написать программу для поиска всех простых чисел (до числа N).

Дополнительные сведения: Рассмотрим алгоритм поиска простых чисел на диапазоне от 1 до N методом " Решето Эратосфена ". Проиллюстрируем этот метод:

· 1 шаг: берем "2", отмечаем серым цветом. Вычеркиваем все числа, кратные двум.

· 2 шаг: берем следующее за "2" невычеркнутое число ("3"), отмечаем серым цветом. Вычеркиваем все числа, кратные трем и т.д.

· В "решете" остались числа, отмеченные серым цветом. Это простые числа.

Рис. 6.1.

Идея решения:

· Заполняем одномерный массив А подряд идущими числами до N (например: N=22) включительно (таблица ниже):

· Заполняем элементы массива Flag флажками-единицами, если соответствующие элементы массива А кратны "2" (рис. 6.2):

Рис. 6.2.

· Затем заполняем элементы массива Flag флажками-единицами, если соответствующие элементы массива А кратны "3" (рис. 6.3):

Рис. 6.3.

· и т.д.

· В "решете" (массиве А) остались числа, отмеченные серым цветом (рис. 6.4):

Рис. 6.4.

Для сокращения количества шагов достаточно перебирать элементы массива А до половины (т.к. максимальный делитель n - этоn/2).

Решение задачи на Бейсике:

input "n="; n

dim a(n), flag(n)

for i=1 to n

a(i)=i

next

for i = 2 to n/2

if flag(i)=0 then

for j=i+1 to n

if a(j) mod a(i)=0 then flag(j)=1

next j

end if

next i

for i=1 to n

if flag(i)=0 then print a(i);

next

Решение задачи на Паскале:

Program pr;

Var a,flag:array [1..100] of integer;

I,j,n:integer;

begin

writeln ('n=');

readln (n);

for i:=1 to n do

a[i]:=i;

for i:=2 to n div 2 do

if flag[i]=0 then

for j:=i+1 to n do

if (a[j] mod a[i]=0) then flag[j]:=1;

for i:=1 to n do

if flag[i]=0 then writeln (a[i]);

end.

Тест:

Дано:
Результат:	1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 97

Задача 2: В одномерном массиве, заполненном целыми числами подсчитать число различных элементов.

Идея решения: сравнивая очередной элемент массива А с остальными элементами, заполняем единицей соответствующий повторяющемуся элементу элемент массива Flag. Количество нулевых элементов в массиве Flag и будет равно количеству различных элементов массива А.

Решение задачи На Бейсике:

input "количество чисел"; n

dim a(n), flag(n)

for i = 1 to n

input "введите число"; a(i)

next

for i = 1 to n - 1

if flag(i) = 0 then

for j = i + 1 to n

if a(i)=a(j) then flag(j)=1

next

end if

next

for i = 1 to n

if flag(i)=0 then k = k+1

next

print "k="; k

Решение задачи на Паскале:

Program pr;

var a,flag: array [1..100] of integer;

i,j,n,k: integer;

begin

writeln ('количество чисел');

readln (n);

for i:= 1 to n do

begin

writeln ('введите число');

readln (a[i]);

end;

{==========================}

for i:=1 to n-1 do

if flag[i]=0 then

for j:=i+1 to n do

if a[i]=a[j] then flag[j]:=1;

for i:=1 to n do

if flag[i]=0 then k:=k+1;

writeln ('k=', k);

end.

Тест:

Дано:	n=10 1, 4, 2, 2, 3, 1, 2, 3, 4, 1
Результат:	k=4

Задача 3: Вывести элемент, встречающийся в одномерном массиве чаще других.

Идея решения: При сравнении элементов массива А находим повторяющиеся элементы. Массив Flag заполняем количеством повторений элемента массива А. Затем, применив типовой алгоритм ПОИСКА МАКСИМАЛЬНОГО ЭЛЕМЕТА МАССИВА находим позицию элемента массива А, встречающегося чаще других.

Решение задачи на Бейсике:

input "количество чисел";n

dim a(n), flag(n)

for i = 1 to n

input "введите число"; a(i)

next

for i = 1 to n - 1

if flag(i) = 0 then

for j = i + 1 to n

if a(i) = a(j) then k = k + 1: flag(j) = k

next

k = 0

end if

next

for i = 1 to n

if flag(i) > max then max = flag(i): b = i

next

print "чаще встречается "; a(b);

Решение задачи на Паскале:

var a,flag: array [1..100] of integer;

i,j,n,k,max,b: integer;

begin

writeln ('количество чисел');

readln (n);

for i:= 1 to n do

begin

writeln ('введите число');

readln (a[i]);

end;

{===================}

k:=0;

for i:=1 to n-1 do

if flag[i]= 0 then

for j:=i+1 to n do

begin

if a[i]= a[j] then

begin

k:= k+1;

flag[j]:=k;

end;

k:=0;

end;

max:=flag[1];

for i:=1 to n do

if flag[i]>max then

begin

max:=flag[i];

b:=i;

end;

writeln ('чаще встречается ', a[b]);

end.

Тест:

Дано:	n=10 1, 4, 2, 2, 3, 1, 2, 3, 2, 1
Результат:	Чаще встречается 2

Ключевые термины

· Метод " Решето Эратосфена " - алгоритм поиска простых чисел на диапазоне от 1 до N.

Краткие итоги

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

В алгоритме " Решето Эратосфена " флажками отмечаются элементы, которые необходимо исключить из дальнейшего рассмотрения ("вычеркнуть").

При необходимости флажки могут принимать не только единичные значения - они могут "указывать" на разнообразные состояния элементов рассматриваемого массива.

Набор для практики

Вопросы.

· Продолжите фразу: "Для того, чтобы отметить элементы, удовлетворяющие условию, используют…".

· В чем заключается алгоритм поиска простых чисел на диапазоне от 1 до N методом " Решето Эратосфена "?

Упражнения.

· В одномерном массиве, заполненном целыми числами подсчитать количество повторяющихся элементов.

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

Задачи, сгруппированные по методам решения. Использование дополнительного массива "флажков" (три задачи - один алгоритм)

Рассмотрим несколько практических задач.

Задача 1: В строке, содержащей арифметическое выражение проверить, правильно ли расставлены скобки. В случае лишних скобок - не считать неправильным расстановку скобок (например: ((а+в)) -скобки расставлены верно).

Идея решения:

1. Допустим, дано арифметическое выражение: (а + в ((4а - 8) в + 3) - 15в)

2. Резервируем два массива: А$ и Flag. "Разбираем" строку, в которой хранится арифметическое выражение (применив типовой алгоритм "РАЗБОРА" СТРОКИ НА СИМВОЛЫ), помещая каждый символ в элемент массива А$.

Массив Flag заполняем флажками:

o "1" - если элемент массива А$ - открывающаяся скобка;

o "-1" - если элемент массива А$ - закрывающаяся скобка (рис. 7.1).

Рис. 7.1.

3. Суммируем элементы массива Flag. Если в процессе перебора элементов сумма станет отрицательной, значит скобки расставлены неверно. Итоговая сумма должна быть равна 0.

Решение задачи на Бейсике:

input "введите ар. выражение"; stroka$

n=len(stroka$)

dim a$ (n), flag (n)

rem-

for i=1 to n

a$(i)=mid$(stroka$, i, 1)

next

rem=======================

for i=1 to n

if a$(i)='(' then flag (i)=1

if a$(i)=')' then flag (i)=-1

next

rem=======================

for i=1 to n

s=s+flag (i)

if s<0 then x=1

next

if s=0 and x=0 then?"скобки расставлены верно" else?"скобки расставлены неверно"

Решение задачи на Паскале:

const m=10;

var flag: array [1..m] of integer;

a: array [1..m] of string[1];

stroka: string;

i,s,n,x: integer;

begin

writeln ('введите ар. выражение'); readln (stroka);

n:=length (stroka);

for i:=1 to n do

begin

a[i]:=copy(stroka, i, 1);

flag[i]:=0;

end;

for i:=1 to n do

begin

if a[i]="(" then flag [i]:=1;

if a[i]=")" then flag [i]:=-1;

end;

s:=0;

for i:=1 to n do

begin

s:=s+flag [i];

if s<0 then x:=1;

end;

if (s=0) and (x=0) then writeln ('скобки расставлены верно')

else writeln ('скобки расставлены неверно');

end.

Тест:

Дано:	(4*5+1)*((2/6-2*3)+4))	(6+56))-90*(5-2*(3-7/3)
Результат:	скобки расставлены верно	скобки расставлены неверно

Задача 2: В картинной галерее работают сторожа. Для каждого сторожа известно время прихода на работу и время ухода. Определить, всегда ли галерея охраняется.

Идея решения: Пример (табл. 7.1):

Таблица 7.1.
	Время прихода	Время ухода
1 сторож	8.00	12.00
2 сторож	11.00	16.00
3 сторож	15.00	19.30
4 сторож	20.00	23.50

1. Заполняем массивы:

А: временем прихода и ухода сторожей;

Flag:

o "1" - если соответствующий элемент массива А - время прихода сторожа;

o "-1" - если элемент массива А - время ухода сторожа;

Рис. 7.2.

2. СОРТИРУЕМ массив А, одновременно переставляя элементы массива flag:

Рис. 7.3.

3. Суммируем элементы второго массива. Если текущая сумма обнулилась (но конец массива не достигнут), то, значит, галерея осталась без охраны (в 19.30 сторож ушел, а смена еще не пришла).

Рис. 7.4.

Решение на Бейсике:

input "количество сторожей="; n

dim a(2*n), flag(2*n)

for i=1 to n*2 step 2

input "время прихода="; a(i)

flag (i) = 1

input "время ухода="; a(i + 1)

flag (i + 1) = -1

next

rem==сортировка=======================================

for j = 2*n to 2 step -1

for i = 1 to j - 1

if a(i) > a(i + 1) then swap a(i), a(i + 1): swap flag(i), flag(i + 1)

next i, j

rem================================================

k = 0

for i = 1 to 2*n

s = s + flag(i)

if s = 0 then k = k + 1

next

if k = 1 then print "охранялась всегда" else print "не охранялась "; k - 1; " раз"

Решение задачи на Паскале:

const m=20;

var a, flag: array [1..m] of integer;

i,s,k,n,x: integer;

begin

writeln ('количество сторожей');

readln (n);

j:=1;

for i:=1 to n do

begin

writeln ('время прихода, ухода');

readln (a[j], a[j+1]);

flag [j]:=1;

flag [j+1]:=-1;

j:=j+2;

end;

for j:=2*n downto 2 do

for i:=1 to j-1 do

if a[i]>a[i+1] then

begin

x:=a[i];

a[i]:=a[i+1];

a[i+1]:=x;

x:=flag[i];

flag [i]:=flag [i+1];

flag [i+1]:=x;

end;

k:=0;

s:=0;

for i:=1 to 2*n do

begin

s:=s+flag [i];

if s=0 then k:=k+1;

end;

if k=1 then writeln ('галерея всегда охранялась')

else writeln ('галерея оставалась без охраны',k-1,'раз');

end.

Тест:

Дано:	n=3	n=3
Результат:	охранялась	не охранялась 1 раз

Задача 3: N отрезков на координатной прямой заданы координатами своих концов. Определить количество связных областей.

Идея решения:

1. Заполняем массивы:

А: координатами начала и конца отрезков;

Flag:

o "1" - если соответствующий элемент массива А - координата начала отрезка;

o "-1" - если элемент массива А - координата конца отрезка;

2. СОРТИРУЕМ массив А, одновременно переставляя элементы массива Flag.

3. Суммируем элементы массива Flag. Если текущая сумма обнулилась (но конец массива не достигнут), то, значит, получена одна связная область. Количество обнулений и будет количеством связных областей.

Решение на Бейсике:

input "введите количество отрезков", n

dim a (2*n), flag (2*n)

for i=1 to n*2 step 2

input "первая координата", a(i)

flag (i)=1

input "вторая координата", a(i+1)

flag (i+1)=-1

next

for j=2*n to 2 step -1

for i= 1 to j-1

if a(i)>a(i+1) then swap a(i), a(i+1): swap flag(i), flag(i+1)

next i, j

for i=1 to 2*n

s=s+flag (i)

if s=0 then k=k+1

next

print "количество связных областей ="; k

Решение задачи на Паскале:

const m=20;

var a, flag: array [1..m] of integer;

i,j,s,n,k,x: integer;

begin

writeln ('количество отрезков'); readln (n);

j:=1;

for i:=1 to n do

begin

writeln ('введите координаты начала и конца отрезка');

readln (a[j], a[j+1]);

flag [j]:=1;

flag [j+1]:=-1;

j:=j+2;

end;

for j:=2*n downto 2 do

for i:=1 to j-1 do

if a[i]>a[i+1] then

begin

x:=a[i];

a[i]:=a[i+1];

a[i+1]:=x;

x:=flag[i];

flag [i]:= flag [i+1];

flag [i+1]:=x;

end;

s:=0;

k:=0;

for i:=1 to 2*n do

begin

s:=s+flag [i];

if s=0 then k:=k+1;

end;

writeln ('количество связных областей=', k);

end.

Тест:

Дано:	n=3	n=3
Результат:

Ключевые термины

· Связная область - область, соответствующая объединению отрезков.

Краткие итоги

При решении задач, в условиях которых озвучено наступление и окончание какого-то события (открытие-закрытие скобок, приход-уход сторожа, начало-конец отрезка) используется дополнительный массив "флажков". При наступлении события "флажок" принимает значение "1", при окончании - "-1".

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

Набор для практики

Вопросы.

· Каким образом можно отметить элементы в наборе разнообразных данных, соответствующие разным событиям?

· При необходимости сортировки данных - каким образом учитывается событие, связанное с этим данным?

· Сколько связных областей дадут два отрезка, имеющие одну общую координату (начало одного совпадает с концом другого)?

· Какое количество случаев неохраняемости галереи выдаст программа, если время ухода одного из сторожей совпадает с временем прихода его сменщика?

Упражнения.

· В четырех различных кинотеатрах идут сеансы интересных фильмов. Некий зритель захотел побывать на всех четырех сеансах. Помогите установить - сможет ли зритель попасть на все 4 фильма, если известно время начала и конца каждого фильма, при этом временем "перехода" из кинотеатра в кинотеатр можно пренебречь.

· В строке символов находится программа на языке Паскаль (записанная в одну строку). Выяснить - нет ли ошибок в расстановке ключевых слов Begin и End в программе?