1 1
1 2 1
1 3 3 1
…
Рис. 8.12
16. Постройте матрицу порядка n, записав в нее числа от 1 до n2 согласно схеме (рис. 8.13).
Рис. 8.13
Лабораторная работа 9
Множества, строки
Цель работы: формирование умений и навыков в разработке сложных циклических алгоритмов обработки строк с использованием стандартных процедур и функций над строками; изучение типа данных «множество» и операций над данными этого типа.
Что нужно знать для выполнения работы
1. Стандартные процедуры и функции над строками.
2. Операции над множествами.
3. Особенности использования строк в качестве параметров в процедурах и функциях.
Примеры выполнения задания лабораторной работы
Пример 1. Составьте программу, находящую в данной строке символов длину самой длинной цепочки идущих подряд символов a.
Варианты решения
Вариант 1
program Project1;
{Длина самой длинной цепочки а}
{$APPTYPE CONSOLE}
uses
SysUtils;
var
st:string;
procedure vvodstr(var st:string);
//Ввод строки
var
fin:TextFile;
begin
AssignFile(fin,'File1.txt');
Reset(fin);
readln(fin,st);
CloseFile(fin);
end;
function maxlena(st:string):integer;
//Длина самой длинной цепочки из a
var
td,md,i:integer;
begin
md:=0;
td:=0;
st:=st+' ';
for i:=1 to length(st) do
begin
if st[i]='a' then
inc(td)
else
begin
if td>md then
md:=td;
td:=0;
end;
end;
maxlena:=md;
end;
procedure vivodres;
// Вывод результата
var
fout:TextFile;
begin
AssignFile(fout,'File2.txt');
Rewrite(fout);
writeln(fout,'maxa= ',maxlena(st));
CloseFile(fout);
end;
begin
vvodstr(st);
vivodres;
end.
Вариант 2
program Project1;
{Длина самой длинной цепочки а}
{$APPTYPE CONSOLE}
uses
SysUtils;
var
st:string;
procedure vvodstr(var st:string);
//Ввод строки
var
fin:TextFile;
begin
AssignFile(fin,'File1.txt');
Reset(fin);
readln(fin,st);
CloseFile(fin);
end;
function maxlena(st:string):integer;
//Длина самой длинной цепочки из a
var
td,md,i:integer;
begin
md:=0;
td:=0;
delete(st,1,pos('a',st)-1);
while pos('a',st)<>0 do
if pos('a',st)=1 then
begin
delete(st,1,1);
inc(td);
end
else
begin
if td>md then
md:=td;
td:=0;
delete(st,1,pos('a',st)-1);
end;
if td>md then
md:=td;
maxlena:=md;
end;
procedure vivodres;
// Вывод результата
var
fout:TextFile;
begin
AssignFile(fout,'File2.txt');
Rewrite(fout);
writeln(fout,'maxa= ',maxlena(st));
CloseFile(fout);
end;
begin
vvodstr(st);
vivodres;
end.
Вариант 3
program Project1;
{Длина самой длинной цепочки а}
{$APPTYPE CONSOLE}
uses
SysUtils;
var
st:string;
procedure vvodstr(var st:string);
//Ввод строки
var
fin:TextFile;
begin
AssignFile(fin,'File1.txt');
Reset(fin);
readln(fin,st);
CloseFile(fin);
end;
function maxlena(st:string):integer;
//Длина самой длинной цепочки из a
var
i,md:Integer;
mn:set of byte;
begin
mn:=[];
md:=0;
for i:=1 to length(st) do
if st[i]='a' then
begin
inc(md);
mn:=mn+[md];
end
else
md:=0;
if mn<>[] then
begin
for i:= length(st) downto 1 do
if i in mn then
begin
maxlena:=i;
break; {Выход из цикла}
end;
end
else
maxlena:=0;
end;
procedure vivodres;
// Вывод результата
var
fout:TextFile;
begin
AssignFile(fout,'File2.txt');
Rewrite(fout);
Writeln(fout,'maxa= ',maxlena(st));
CloseFile(fout);
end;
begin
vvodstr(st);
vivodres;
end.
Вариант 4
program Project1;
{Длина самой длинной цепочки а}
{$APPTYPE CONSOLE}
uses
SysUtils;
var
st:string;
procedure vvodstr(var st:string);
//Ввод строки
var
fin:TextFile;
begin
AssignFile(fin,'File1.txt');
Reset(fin);
readln(fin,st);
CloseFile(fin);
end;
function maxlena(st:string):integer;
//Длина самой длинной цепочки из a
var
ts:string;
begin
ts:='a';
while pos(ts,st)<>0 do
ts:=ts+'a';
maxlena:=length(ts)-1;
end;
procedure vivodres;
// Вывод результата
var
fout:TextFile;
begin
AssignFile(fout,'File2.txt');
Rewrite(fout);
Writeln(fout,'maxa= ',maxlena(st));
CloseFile(fout);
end;
begin
vvodstr(st);
vivodres;
end.
Разберите приведенные варианты, выполните программы по шагам, следя за изменением значений переменных.
Пример 2. Найдите все простые числа, не превосходящие данного натурального числа P. Для решения задачи воспользуйтесь известным алгоритмом «решето Эратосфена».
Решение. Суть данного алгоритма в следующем: берем первое простое число «2» и вычеркиваем из множества чисел 2..Р все числа, кратные двум. Затем находим следующее простое число – это «3» и вычеркиваем все числа, кратные трем и т.д., пока исходное множество 2..Р не станет пустым.
Текст программы
program Project1;
{Решето Эратосфена}
{$APPTYPE CONSOLE}
uses
SysUtils;
const
n=255;
procedure prostie;
Var
mn1,mn2:set of 2..n;
x,y:integer;
Begin
mn1:=[2..n];
mn2:=[];
x:=2;
repeat
while not (x in mn1) do
x:=succ(x); {нахождение следующего за x (можно inc(x))}
mn2:=mn2+[x]; {в множестве mn2 результат}
y:=x;
while y<=n do
begin
mn1:=mn1-[y]; {вычеркивание элементов}
y:=y+x;
end
until mn1=[];
for x:=2 to n do {вывод результата}
if x in mn2 then
write(x:5);
readln;
end;
begin
prostie;
end.
Рассмотрим еще один пример.
Пример 3. Из заданной строки удалите все подстроки
AA, BBBB и CCCC
Текст программы
program Project1;
{Из заданной строки удалить все подстроки
AA, BBBB и CCCC}
{$APPTYPE CONSOLE}
uses
SysUtils;
var
st,stdel:string;
procedure vvodstr(var st:string);
//Ввод строки
var
fin:TextFile;
begin
AssignFile(fin,'File1.txt');
Reset(fin);
readln(fin,st);
CloseFile(fin);
end;
procedure delABC(st:string;var stdel:string);
//Преобразование строки
var
flag:Boolean;
begin
flag:=True;
stdel:=st;
while flag do
begin
flag:=False;
if Pos('AA',stdel)<>0 then
begin
flag:=True;
Delete(stdel,Pos('AA',stdel),2);
end;
if Pos('BBBB',stdel)<>0 then
begin
flag:=True;
Delete(stdel,Pos('BBBB',stdel),4);
end;
if Pos('CCCC',stdel)<>0 then
begin
flag:=True;
Delete(stdel,Pos('CCCC',stdel),4);
end;
end;
end;
procedure vivodres(st,stdel:string);
// вывод результата
var
fout:TextFile;
begin
AssignFile(fout,'File2.txt');
Rewrite(fout);
writeln(fout,'st= ',st,#13,#10,'stdel= ',stdel);
CloseFile(fout);
end;
begin
vvodstr(st);
delABC(st,stdel);
vivodres(st,stdel);
end.
Задания
Разработайте программу решения задачи с использованием процедур и функций над строками и операций над множествами.
1. Для каждого слова заданного предложения укажите долю согласных. Определите слово, в котором доля согласных максимальна.
2. Найдите самое длинное симметричное слово заданного предложения и укажите номер позиции, с которого оно начинается.
3. Дана строка, представляющая собой запись числа в десятеричной системе счисления. Преобразуйте ее в строку, представляющую собой запись числа в восьмеричной системе счисления.
4. Дана строка, представляющая собой запись числа в восьмеричной системе счисления. Преобразуйте ее в строку, представляющую собой запись числа в двоичной системе счисления.
5. Дана строка символов, состоящая из произвольных десятичных чисел, разделенных пробелами. Выведите на экран числа этой строки в порядке возрастания их значений.
6. Дана строка, состоящая из групп нулей и единиц, разделенных пробелами. Найдите и выведите на экран самую короткую группу.
7. Дана строка, состоящая из групп нулей и единиц. Каждая группа отделяется от другой одним или несколькими пробелами. Подсчитайте количество символов в самой длинной группе.
8. Дана строка, состоящая из групп нулей и единиц. Каждая группа отделяется от другой одним или несколькими пробелами. Найдите и выведите на экран группы с четным количеством символов.
9. Дана строка, состоящая из групп нулей и единиц. Каждая группа отделяется от другой одним или несколькими пробелами. Подсчитайте количество нулей и единиц в группах с нечетным количеством символов.
10. Дана строка символов, состоящая из натуральных чисел, разделенных пробелами. Выведите четные числа этой строки.
11. Дана строка, представляющая собой запись числа в двоичной системе счисления. Преобразуйте ее в строку, представляющую собой запись числа в шестнадцатеричной системе счисления.
12. Дана строка символов, состоящая из произвольного текста, слова разделены пробелами. Выведите на экран порядковый номер слова, накрывающего k-ю позицию (если на k-ю позицию попадает пробел, то номер предыдущего слова), и найдите в нем количество повторяющихся символов.
13. Дана строка символов, состоящая из произвольного текста, слова разделены пробелами. Разбейте исходную строку на две подстроки, причем первая длиной k-символов (если на k-ю позицию попадает слово, то его следует отнести ко второй строке, дополнив первую пробелами до k-позиций).
14. Дана строка символов, состоящая из произвольного текста, слова разделены пробелами. Выведите на экран порядковый номер слова максимальной длины и номер позиции строки с которой оно начинается.
15. Дана строка символов, состоящая из произвольного текста, слова разделены пробелами. Выведите на экран порядковый номер слова минимальнойдлины и количество неповторяющихся символов в этом слове.
16. Найдите самое длинное симметричное слово заданного предложения и укажите номер позиции, с которого оно начинается.
17. Напишите программу, вычеркивающую из данного слова все буквы «а» так, чтобы, например, из слова «заноза» получилось «зноз».
18. Напишите программу, проверяющую, является ли частью данного слова слово «сок».
19. Напишите программу, подсчитывающую, сколько раз в данном слове встречается сочетание «со».
20. Напишите программу, заменяющую в тексте все прописные латинские буквы на строчные.
21. Напишите программу, заменяющую в тексте все строчные латинские буквы на прописные.
22. Дана строка символов, состоящая из произвольного текста на английском языке, слова отделены пробелами. После каждого гласного символа вставьте символ «*».
23. Выведите все строчные гласные латинские буквы, встречающиеся в данной строке ровно один раз.
24. В заданном тесте найдите количество четырехбуквенных слов и каждое четное из них замените на сочетание «SsSs». Слова отделены друг от друга пробелом.
25. Отредактируйте предложение, удаляя из него лишние пробелы, оставляя по одному пробелу между словами.
26. В заданном предложении укажите слово, в котором доля гласных «А» максимальна.
27. Проверьте, имеется ли в заданном тексте баланс открывающих и закрывающих скобок, имея в виду, что балансом, например, будет комбинация (…), в то время как комбинация )..(..)..( балансом не является.
28. Выведите на экран все символы кодовой таблицы ПЭВМ.
29. Введите слово и все буквы «О» заменить в нем на «А».
30. Напечатайте в столбик числовые коды букв введенного слова.
31. Напишите программу подсчета количества гласных в тексте на английском языке.
32. Напишите программу обращения слова.
33. Напишите программу замены в тексте всех букв «а» на «о» и наоборот.
34. Напишите программу, удваивающую каждый символ в заданном тексте.
35. Напишите программу, выясняющую, является ли данное слово палиндромом («перевертышем»).
36. Для каждого слова заданного предложения укажите долю согласных. Определите слово, в котором доля согласных максимальна.
37. Найдите самое длинное симметричное слово заданного предложения и укажите номер позиции, с которого оно начинается.
38. Отредактируйте заданное предложение, заменяя многоточия точкой, а вместо точки ставьте восклицательный знак.
39. В заданном предложении найдите самое короткое и самое длинное слова и укажите позиции, с которых они начинаются (слова в предложении разделены пробелом).
40. Из заданного текста предложения выберите и выведите на экран только те символы, которые встречаются в нем только один раз (в том порядке, в котором они встречаются в тексте).
41. В заданном тексте замените последовательность символов X(i) на X[i] и вычислите число произведенных замен.
42. В заданном тексте предложения замените строчные буквы на прописные и вычислите количество произведенных замен.
43. Задан текст, состоящий из произвольной последовательности буквенных символов. Расположите их в алфавитном порядке, при этом повторяющиеся символы должны быть удалены.
44. Задана строка символов, состоящая из букв, цифр, точек, символов «+» и «-». Выделите подстроку, состоящую из цифр, соответствующую целому числу (т.е. начинается со знака «+» или «-» или цифры и внутри подстроки нет букв и точки).
45. В заданном тексте предложения расставьте слова по алфавиту в соответствии с его первой буквой.
Задачи второго уровня
1. В заданном предложении поменяйте порядок следования слов на обратный.
2. Введите текст, содержащий группы от 1 до 4 цифровых символов, разделенных пробелом, отображающих целые числа от 1 до 2000. На экран выведите введенные числа и их представление в римской системе счисления.
3. В заданном предложении, составленном из нескольких слов, поменяйте местами слова, стоящие на четных местах, со словами, стоящими на нечетных местах.
4. В заданном тексте в каждом нечетном слове поменяйте местами первые два буквенных символа и замените их на заглавные.
5. В заданном тексте в каждом четном слове замените все строчные буквенные символы на прописные, а каждое нечетное слово заключите в круглые скобки.
6. Для встречающихся в заданном тексте пар рядом расположенных букв укажите, сколько раз встречается каждое из таких двухбуквенных сочетаний.
7. Данный текст на русском языке «перекодируйте» в соответствии с таблицей перекодировки, заданной двумя строками st1 и st2. Например, пусть дан текст «Данный текст на русском языке» и таблица перекодировки: st1 = ’аейкнут’, st2 = ’горелка’. Тогда в результате перекодировки должен получиться текст: «Дгнныр аоест нг ркссеом языео».
8. Определите номер позиции k-го вхождения строки st1 в строку st2. Если такого нет, возвратите 0.
9. Определите номер позиции последнего вхождения строки st1 в строку st2. Если такого нет, возвратите 0.
10. Даны две строки st1 и st2. Разработайте процедуру, которая по значению первого параметра выполняет следующие операции над данными строками: находит символы, встречающиеся в обеих строках, находит символы, встречающиеся только в первой строке, только во второй строке.
Лабораторная работа 10
Методы внутренней сортировки
Цель работы: формирование умений и навыков в разработке сложных циклических алгоритмов обработки массивов; изучение методов внутренней сортировки; реализация отдельных алгоритмов сортировки.
Что нужно знать для выполнения работы
1. Метод пошаговой детализации разработки алгоритмов.
2. Идеи, находящиеся в основе методов сортировки массивов.
3. Особенности использования массивов в качестве параметров в процедурах и функциях.
Основные идеи алгоритма внутренней сортировки
Существуют шесть основных идей внутренней сортировки: подсчетом, обменом, выбором, вставками, слиянием, распределением. Практически каждая из этих идей имеет несколько модификаций, некоторые из которых достаточно сложны для реализации.
Метод сортировки обменом
Рассмотрим один из методов сортировки – метод «пузырька» – один из вариантов обменной сортировки.
Данный алгоритм основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут рассортированы все элементы. Общий замысел любого алгоритма сортировки лучше всего раскрыть на конкретном примере сортировки последовательности целых чисел (табл. 10.1)
Таблица 10.1
Пример сортировки методом «пузырька»
|
Исходный массив |
Номер просмотра |
Отсортированный массив | |||||||
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 | ||
|
45 |
99 |
99 |
99 |
99 |
99 |
99 |
99 | ||
|
81 |
45 |
81 |
81 |
81 |
81 |
81 |
81 | ||
|
13 |
81 |
45 |
76 |
76 |
76 |
76 |
76 | ||
|
04 |
13 |
76 |
45 |
50 |
50 |
50 |
50 | ||
|
76 |
04 |
13 |
50 |
45 |
45 |
45 |
45 | ||
|
50 |
76 |
04 |
13 |
37 |
37 |
37 |
37 | ||
|
28 |
50 |
50 |
04 |
13 |
28 |
28 |
28 | ||
|
22 |
28 |
37 |
37 |
04 |
13 |
22 |
22 | ||
|
99 |
22 |
28 |
28 |
28 |
04 |
13 |
13 | ||
|
37 |
37 |
22 |
22 |
22 |
22 |
04 |
04 | ||
Итак, мы видим, что после первого просмотра наибольший по величине элемент занял свое место в конце массива; после второго – второй по величине элемент занял свое место и т.д.
Начнем разработку алгоритма на алгоритмическом языке (псевдокоде) и покажем использование метода пошаговой детализации. Заголовок и первый шаг могут быть следующими:
алг Сортировка обменами (цел N, цел таб A[1:N])
арг N,A
рез A
нач
Упорядочить элементы линейной таблицы по возрастанию
кон
В дальнейшем мы не будем записывать заголовок, так как он остается без изменений. Очевидно, что для получения отсортированного массива достаточно выполнить (N-1)-й просмотр: после того как (N-1)-е элементы займут свои места, N-му ничего не останется как занять последнее свободное место.
Таким образом, можно сказать, что для выполнения сортировки необходимо организовать цикл на (N-1)-е повторение (второй шаг):
нач
цел i
для i от 1 до N-1
нц
поставить i-й элемент таблицы на свое место
кц
кон
Что необходимо сделать, чтобы поставить i-й элемент на свое место, т.е., в чем суть i-го просмотра? Необходимо сравнивать соседние элементы и, если предыдущий больше последующего, поменять их местами.
Максимальное число сравнений на каждом просмотре N-1. Получаем третий шаг детализации:
нач
цел i,j
для i от 1 до N-1
нц
для j от 1 до N-1
нц
если A[j]>A[j+1]
то
обмен A[j] и A[j+1]
всё
кц
кц
кон
Осталось уточнить процедуру «обмен A[j] и A[j+1]» (четвертый шаг):
нач
цел i,j,T
для i от 1 до N-1
нц
для j от 1 до N-1
нц
если A[j]>A[j+1]
то
T:=A[j]
A[j]:=A[j+1]
A[j+1]:=T
всё
кц
кц
кон
Теперь, когда алгоритм полностью разработан, попытаемся несколько улучшить его. Так как после каждого просмотра хотя бы один элемент займет свое место и в дальнейшем может не участвовать в сравнениях, то с каждым просмотром количество сравнений можно уменьшить на 1. Другими словами, на i-ом просмотре достаточно выполнить N-i сравнений (первое уточнение):
нач
цел i,j,T
для i от 1 до N-1
нц
для j от 1 до N-i
нц
если A[j]>A[j+1]
то
T:=A[j]
A[j]:=A[j+1]
A[j+1]:=T
все
кц
кц
кон
Из табл. 10.1 видно, что после очередного просмотра свои места могут занять сразу несколько элементов, а не один. Таким образом, количество сравнений на очередном просмотре может уменьшиться не на единицу по сравнению с предыдущим просмотром, а на большую величину. Необходимо заметить номер элемента A[j], который участвовал в обмене последним при очередном просмотре. Для чего введем промежуточную величину L. На следующем просмотре будем сравнивать элементы с индексами, меньшими чем L, (второе уточнение):
нач
цел i,j,T,L,K
K:=N-1
для i от 1 до N-1
нц
для j от 1 до K
нц
если A[j]>A[j+1]
то
T:=A[j]
A[j]:=A[j+1]
A[j+1]:=T
L:=j
всё
кц
K:=L-1
кц
кон
Из табл. 10.1 видно также, что необязательно выполнять (N-1)-й просмотр, что последовательность может оказаться отсортированной раньше (возможно в самом начале она уже была упорядочена!).
Введем переключатель P, который в начале каждого просмотра будем выключать, а при обмене элементов включать.
Тогда сортировка будет закончена, если на очередном просмотре не будет ни одного обмена, т.е. переключатель останется выключенным (третье уточнение):
нач
цел i,j,T,L,K
лог P
K:=N-1
P:=истина
пока P
нц
P:=ложь
для j от 1 до K
нц
если A[j]>A[j+1]
то
T:=A[j]
A[j]:=A[j+1]
A[j+1]:=T
L:=j
P:=истина
всё
кц
K:=L-1
кц
кон
Последний алгоритм можно улучшать и дальше. Например: организовать попеременный просмотр массива с разных концов (шейкер-сортировка); сравнивать сначала не соседние элементы, а с определенным шагом (метод Бэтчера); разделить исходный массив на подмассивы (метод Хоара) и др.
Метод простого выбора
Данный метод основан на выборе самого маленького элемента последовательности и обмене его с первым элементом последовательности. Затем находится второй по величине элемент и меняется местами со вторым и т.д. После (n-1)-го просмотра все элементы займут свои места. Одним из улучшений данного метода является метод пирамидальной сортировки.
Метод простых вставок
Согласно методу простых вставок элементы последовательности, начиная со второго, вставляются в уже упорядоченную подпоследовательность. Для того, чтобы не проверять сложное условие в цикле пока, очередной вставляемый элемент ставится на место нулевого и служит барьером, когда вставляемый элемент оказывается меньшим элементом подпоследовательности. Одновременно с поиском места вставки большие элементы сдвигаются на одну позицию к концу подпоследовательности. Одним из лучших методов сортировки является метод Шелла, который основан на методе простых вставок. Этот метод подобен методу Бэтчера, только подмассивы сортируются не методом обмена, а методом простых вставок.
Метод двухпутевых вставок
Считается, что слева и справа от первого элемента имеется n-1 свободное место, и вставляемые элементы сравниваются либо с последним вставленным элементом справа или слева. Этот выбор зависит от того, были ли сдвиги элементов на предыдущем шаге, если были, то направление вставки меняется на противоположное.
Метод бинарных вставок
В методе простых вставок для поиска места вставки выполняются последовательные сравнения вставляемого элемента с предыдущими элементами. Метод бинарных вставок основан на дихотомии, т.е. на бинарном методе поиска места. Например, если 63 элемента уже упорядочены и необходимо найти место 64-го, то 64-й сравнивается с 32-м, затем, в зависимости от результата сравнения, либо с 16-м, либо с 48-м. Таким образом, для нахождения места 64-го элемента достаточно выполнить всего шесть сравнений, а для нахождения места вставки, скажем, 1000-го – десять сравнений.
Метод подсчета
Заготавливаем n счетчиков и обнуляем их (можно заполнить единицами). Далее, сравниваем первый элемент с остальными и, в зависимости от того какой элемент больший, счетчик этого элемента увеличиваем на единицу. Затем второй элемент сравниваем с остальными, начиная с третьего и т.д. В результате, после сравнения (n-1)-го c n-м элементом, счетчики будут содержать номера элементов в отсортированной последовательности без единицы, если счетчики вначале обнулялись, и номера с единицей, если им были присвоены единицы. После этого достаточно одного цикла для получения нового упорядоченного массива из старого.
Метод слияния
Различают две модификации данного метода: простое двухпутевое слияние и естественное двухпутевое слияние. Идея метода основана на том, что если имеются два упорядоченных массива, то за один цикл их можно слить в один упорядоченный массив.
При простом слиянии исходный массив разбивается на n цепочек, в каждой из которых содержится по одному элементу. Далее выполняется слияние первой цепочки с последней, второй с предпоследней и т.д. Результаты цепочки в два раза длиннее, записываются поочередно в начало или в конец нового массива. Так как на каждом шаге слияния длины цепочек удваиваются, то достаточно выполнить log2n шагов.
Естественное двухпутевое слияние отличается от простого только первым шагом первоначальным разбиением на цепочки, которое выполняется естественным способом. Например, если исходная последовательность
37 24 99 08 22 19 28 82,
то начальное разбиение на цепочки будет следующим:
37 | 24 99 | 08 || 22 || 19 | 28 | 82
Как видим, количество цепочек может быть значительно меньше n, что позволит несколько ускорить сортировку. То, что количество элементов в сливаемых цепочках различно, никакой роли при организации слияния не играет. В данном случае незначительно усложняется алгоритм из-за того, что один «средний» элемент может попасть в две цепочки (в нашем случае число 13).
Сортировка распределением
Рассмотрим частный случай сортировки распределением – поразрядную сортировку. Допустим, исходный массив состоит из двухразрядных десятичных чисел
37 24 99 08 22 19 28 82 50 64 11 71 95 76 04 13 81 45 53 17
Заготавливаем 10 карманов по n элементов каждый и выполняем распределение элементов исходного массива по карманам в зависимости от значения младшего разряда. В нашем случае это распределение будет следующим:
Карманы: 0 1 2 3 4 5 6 7 8 9
50 11 22 13 24 95 76 37 08 99
71 82 53 64 45 17 28 19
81 04
Берем последовательно элементы из карманов и получаем последовательность, упорядоченную по первому разряду,
50 11 71 81 22 82 13 53 24 64 04 95 45 76 37 17 08 28 99 19.
Эту последовательность снова упорядочиваем аналогично предыдущей последовательности, но по второму разряду.
Карманы: 0 1 2 3 4 5 6 7 8 9
04 11 22 37 45 50 64 71 81 95
08 13 24 53 76 82 99
17 28
19
Получим упорядоченную последовательность:
04 08 11 13 17 19 22 24 28 37 45 50 53 64 71 76 81 82 95 99.
Если элементы исходной последовательности содержат больше десятичных разрядов, то понадобится просто больше шагов распределения.
П р и м е ч а н и е. На самом деле нет необходимости заготавливать 10 карманов и распределять физически по ним элементы. Достаточно знать о каждом элементе, в какой карман он должен попасть, и по очереди выбирать их из этих виртуальных карманов.
Задания
Разработайте алгоритм методом пошаговой детализации и программу, реализующую этот алгоритм.
1. Найдите элементы каждой строки матрицы, которые повторяются наибольшее число раз в своей строке.
2. Проверьте, являются ли элементы строк данной матрицы перестановками одинаковых элементов.
3. Упорядочите строки данной матрицы в порядке возрастания количества одинаковых элементов в каждой строке.
4. Дана квадратная матрица порядка n. Переставьте строки матрицы так, чтобы в результате получилась матрица, у которой строки упорядочены в порядке возрастания диагональных элементов.
5. Массив записей содержит фамилии участников соревнования и количество набранных баллов. Расположите записи в порядке убывания количества баллов. Если некоторые участники набрали одинаковое количество баллов, то их фамилии выведите в алфавитном порядке.
6. Массив записей содержит фамилии участников соревнования по прыжкам в длину и результаты трех попыток. Расположите записи в порядке занятых спортсменами мест.
7. Массив записей содержит фамилии участников соревнования и количество набранных баллов. Выведите фамилии участников, показавших три лучших результата. Таких участников может быть больше трех (некоторые участники показали одинаковые результаты).
8. Имеется массив слов. Выведите все анаграммы введенного слова, которые имеются в массиве.
9. Найдите самую длинную восходящую подпоследовательность в данной последовательности. Например, в последовательности 3, 6, 2, 7, 4, 8 такой подпоследовательностью будет 3, 6, 7, 8.
10. Расставьте строки данной матрицы в порядке возрастания элементов первого столбца.
11. Расставьте строки данной матрицы в порядке возрастания наибольших элементов в строках.
12. Дан двухмерный массив. Расположите его элементы в порядке возрастания.
13. Дан трехмерный массив. Расположите его элементы в порядке возрастания.
14. Имеется массив кодов групп товаров. Код группы товара – это последовательность четырех цифр. Упорядочите данный массив, не используя операций сравнения.
15. Выведите в порядке возрастания кодов все строчные буквы латинского алфавита, имеющиеся в текстовом файле.
16. Напишите одноцикловую программу сортировки массива.
17. Имеется массив записей, содержащий координаты точек на плоскости. Упорядочите данный массив по первой координате. Если абсциссы некоторых точек равны, то упорядочите их по ординатам.
18. Расположите в порядке возрастания элементы строк данной матрицы, после чего расположите строки по возрастанию первых элементов полученных строк.
19. Расположите в порядке возрастания элементы строк данной матрицы, после чего расположите строки по убыванию последних элементов полученных строк.
20. Имеются три упорядоченных в порядке возрастания массива. Выполните слияние их в один упорядоченный массив.
21. Реализуйте сортировку двухпутевыми вставками.
22. Реализуйте сортировку подсчетом.
23. Реализуйте сортировку простым обменом.
24. Реализуйте сортировку простыми вставками.
25. Реализуйте шейкер-сортировку.
26. Реализуйте сортировку бинарными вставками.
27. Реализуйте сортировку простым выбором.
28. Реализуйте сортировку простым слиянием.
29. Реализуйте сортировку естественным слиянием.
30. Реализуйте поразрядную сортировку.
31. Имеется массив натуральных чисел. Получите массив записей, содержащих различные числа исходного массива и их частоту в исходном массиве.
32. Расставьте данный массив натуральных чисел по количеству их делителей.
Литература
Абрамов С.А. Задачи по программированию / С.А. Абрамов, Г.Г. Гнездилова, Е.Н. Капустина, М.И. Селюн. – М.: Наука, 1988. – 224 с.
Архангельский А.Я. Delphi 7. Справочное пособие. –М:ООО «Бином-Пресс», 2003 –1024 с.:ил.
Архангельский А.Я. Приемы программирования в Delphi. –М: ООО «Бином-Пресс», 2004 –848 с.:ил.
Архангельский А.Я. Программирование в Delphi 6. –М: ЗАО «Изд-во Бином», 2003 –1120 с.:ил.
Ахо А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. – М.: Мир, 1979.
Баженова И.Ю. Delphi 7. Самоучитель программиста. – М.:КУДИЦ-ОБРАЗ, 2003. – 448 с.
Бакнелл Дж. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. –М.: ООО «ДиаСофтЮП»: СПб,: Питер, 2006. – 557 с.:ил.
Бобровский С.И. Delphi 7. Учебный курс. – СПб:Питер, 2003.- 736 с.:ил.
Бондарев В.М. Основы программирования / В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. – Харьков: Фолио; Ростов н/Д: Феникс, 1997. –368 с.
Вирт Н. Алгоритмы и структуры данных / Н. Вирт. – М.: Мир, 1989.
Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. – М.: Мир, 1998. – 703 с.:ил.
Дантеменн А., Delphi 4 (самоучитель), Санкт-Петербург, 1999
Дарахвелидзе П.Г., Марков Е.П. Delphi- среда визуального программирования: - СПб.:- Санкт –Петербург, 1996. – 352 с.
Долинский М.С. Алгоритмизация и программирование на Turbo Pascal: от простых до олимпиадных задач. –СПб: Питер, 2004. 240 с.
Долинский М.С. Решение сложных и олимпиадных задач по программированию. –СПб: Питер, 2006. 366 с.:ил.
Зубов В.С., Шевченко И.В. Структуры и методы обработки данных: Практикум в среде Delphi. – М.:Информационно-издательский дом «Филинъ», 2004.-304 с.
Елманова Н. и др. Delphi и технология COM. Мастер-класс. – СПб:Питер, 2003 698 с.:ил.
Кандзюба С.П., Громов В.Н. Delphi 6/7. Базы данных и приложения. Лекции и упражнения. – СПб:ООО «ДиаСофтЮП», 2002. – 576 с.
Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. – СПб БХВ-Петербург, 2003, - 1104 с.:ил.
Киммел, Пол. Создание приложений в Delphi. – М.: Издательский дом ”Вильямс”, 2003. – 640 с.:ил.
Кирюхин В.М., Лапунов А.В., Окулов С.М. Задачи по информатике. Международные олимпиады 1989-1996. – М.:ABF, 1996. 272c.
Кнут Д. Искусство программирования для ЭВМ: В 3 т. Т. 3 / Д. Кнут. – М.: Мир, 1978. – 844 с.
Котов В.М. Методы алгоритмизации / В.М. Котов, И.А. Волков, А.И. Харитонович. – Мн.: Нар. асвета, 1996. – 127 с.: ил.
Кристофидес Н. Теория графов.: алгоритмический подход. –М: Мир, 1988. 250 с.
Культин Н.Б. Основы программирования в Delphi 7. – СПб.:БХВ-Петербург, 2003. – 608 с.: ил.
Культин Н.Б. Delphi в задачах и примерах. – СПб.:БХВ-Петербург, 2003. – 288 с.: ил.
Липский В. Комбинаторика для программистов / В. Липский. – М.: Мир, 1988. – 213 c.: ил.
Марко Кэнту. Delphi 6 для профессионалов (+СD). – СПб.: Питер, 2002. – 1088 с.: ил.
Новиков Ф.А. Дискретная математика для программистов. СПб.:Питер, 2003. – 304с.:ил.
Окулов С.М. Программирование в алгоритмах./ С.М. Окулов. –М.: БИНОМ. Лаборатория знаний, 2006.-383 с.:ил.
Озеров В. Delphi. Советы программистов. –СПб:Символ-Плюс, 2004. – 976с., ил.
Понамарев В. А. Самоучитель Delphi Studio. — СП.: БХВ-Петербург, 2003. — 512 с.:ил.
Рейнгольд Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. – М.: Мир, 1980. – 476 с.
Свами М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. – М.: Мир, 1984. – 455 с.: ил.
. Суворов К.А., Черемных М.Н. Справочник Delphi. Базовые классы. –СПб:БХВ-Петербург, 2004. 576 с.:ил.
Текстейра С., Пачеко К. Delphi 5. Руководство разработчика в 2-х томах. – М.:Издательский дом «Вильямс», 2001.
.Ускова О.Ф. и др. Программирование алгоритмов обработки данных./-СПБ.: БХВ-Петербург, 2003.-192 с.:ил.
Фаронов В. В. Программирование баз данных в Delphi 7. Учебный курс. СПб.: Питер, 2003. – 459 с.:ил.
Фаронов В.В. Delphi 6. Учебный курс.-М.: Издатель Молгачева С.В.,2001. – 672 с., ил.
Фаронов В.В. Delphi 6. Учебный курс. СПб.:Питер 2002 – 512с.: ил.
Хаггарти Р. Дискретная математика для программистов. М - Техносфера, 2003. – 320с.
Хомоненко А. Д и др. Delphi 7/ Под общей ред. А.Д. Хомоненко. – СПб.:БХВ-Петербург, 2004. – 1216 с.:ил.
Хьюз Дж. Структурный подход к программированию / Дж. Хьюз, Дж. Мичтом. – М.: Мир, 1980. – 278 с.
Филлипс Д. Методы анализа сетей / Д. Филипс, А. Гарсиа-Диас. – М.: Мир, 1984. – 496 с.: ил.