Теоретическая часть
Методы, используемые при поиске и сортировке
Оценки времени исполнения
Приложение на Delphi, в котором представлена работа некоторых методов сортировки и поиска
Пример выполнения
Вопросы для самопроверки
Представление множеств и отношений в программах
Алгоритмы генерации множеств
Then
Варианты заданий
Теоретическая часть
Примеры выполнения
Вариантв заданий
Перевод даты рождения в двоичную систему
Вопросы для самопроверки
Вопросы для самопроверки
Процедура основного обработчика
Вопросы для самопроверки
Практическая часть
Дешифраторы
Навигация
Пример выполнения
Основы дискретной математики
179431
знак
27
таблиц
82
изображения
1.3.3 Пример выполнения
Задание: заданы два одномерных массива А и В, содержащие по n элементов каждый. Объединить эти два массива в один, исключив повторяющиеся элементы. Считать, что массивы А и В отсортированы по убыванию.
Теоретическое описание метода
Метод пузырька, как таковой, не требует глубокого рассмотрения. Смысл метода заключается в том, что мы находим в определённой области максимальный (или минимальный элемент) и помещаем его в начало исследуемой области, далее уменьшаем область поиска на 1 и повторяем те же действия, не имеет худшего случая, всегда O(n2).
Рисунок 1.15 – Форма с результатами расчета
Код программы на Delphi:
const n=5;
var
a:array [1..n] of Byte;
b:array [1..n] of Byte;
c: array of Byte;
i:byte;
implementation
procedure TForm1. Button1Click (Sender: TObject);
var m, x:byte;
begin
randomize;
for i:=1 to n do begin
a[i]:=random(200);
b[i]:=random(200);
end;
for m:=n downto 2 do begin
for i:=1 to m‑1 do begin
if a[i]<a [i+1] then begin
x:=a[i];
a[i]:=a [i+1];
a [i+1]:=x;
end;
if b[i]<b [i+1] then begin
x:=b[i];
b[i]:=b [i+1];
b [i+1]:=x;
end;
end;
end;
for i:=1 to n do begin
StringGrid1. Cells [i – 1,0]:=IntToStr (a[i]);
StringGrid2. Cells [i – 1,0]:=IntToStr (b[i]);
end;
end;
procedure TForm1. Button2Click (Sender: TObject);
label m1;
var k, l, x:byte;
begin
k:=1;
l:=1;
x:=0;
SetLength (c, 1);
while (k<=n) or (l<=n) do begin
m1: if a[k]>b[l] then begin
x:=x+1;
SetLength (c, x);
c [x‑1]:=a[k];
k:=k+1;
goto m1;
end;
if a[k]<b[l] then begin
x:=x+1;
SetLength (c, x);
c [x‑1]:=b[l];
end;
l:=l+1;
end;
For i:=0 to high(c) do ListBox1. Items. Add (IntToStr(c[i]));
end;
end.
1.3.4 Варианты заданий
Варианты 1 – 27 имеют пояснения к выполнению решений в [7].
1) Для заданного массива A размером n требуется выполнить проверку на упорядоченность. Результат присвоить переменной строкового типа (сделать вывод, каким именно образом упорядочен массив, если он окажется упорядоченным: по возрастанию, по убыванию, по неубыванию, по невозрастанию). Пояснения в [7], стр. 245.
2) Выполнить поиск заданного элемента в упорядоченном массиве. Пояснения в [7], стр. 246.
3) Требуется объединить два упорядоченных по возрастанию массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2N также упорядоченный по возрастанию. Пояснения в [7], стр. 247.
4) Требуется объединить два упорядоченных по убыванию массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2N также упорядоченный по убыванию. Пояснения в [7], стр. 247.
5) Требуется объединить два массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2N, упорядоченный по возрастанию. [7], стр. 247.
6) Требуется объединить два массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2N, упорядоченный по убыванию. Пояснения в [7], стр. 247.
7) Требуется объединить два упорядоченных массива A и B одного размера N (N – заданное натуральное число) по возрастанию в один массив размером 2N, упорядоченный по неубыванию. [7], стр. 247; [9], стр. 75.
8) Требуется объединить два упорядоченных массива A и B одного размера N (N – заданное натуральное число) по убыванию в один массив размером 2N, упорядоченный по невозрастанию. Пояснения в [7], стр. 247.
9) Требуется определить количество совпадающих элементов двух упорядоченных по убыванию массивов A и B. Размеры массивов не обязательно одинаковые. Пояснения в [7], стр. 248.
10) Требуется определить количество совпадающих элементов двух неупорядоченных массивов A и B. Размеры массивов не обязательно одинаковые. Пояснения в [7], стр. 248.
11) Требуется определить количество совпадающих элементов двух упорядоченных по убыванию массивов A и B. Размеры массивов одинаковые. Пояснения в [7], стр. 248.
12) Требуется определить количество совпадающих элементов двух неупорядоченных массивов A и B. Размеры массивов одинаковые. Пояснения в [7], стр. 248.
13) Требуется определить количество совпадающих элементов двух упорядоченных по возрастанию массивов A и B. Размеры массивов не обязательно одинаковые. Пояснения в [7], стр. 248.
14) Фамилии участников соревнований по фигурному катанию после короткой программы расположены в порядке, соответствующем занятому месту. Составить список участников в порядке их стартовых номеров для произвольной программы (участники выступают в порядке, обратном занятым местам). Пояснения в [7], стр. 255.
15) Японская радиокомпания провела опрос 250 радиослушателей по трём вопросам:
1) Какое животное Вы связываете с Японией и японцами?
2) Какая черта характера присуща японцам больше всего?
3) Какой неодушевлённый предмет или понятие Вы связываете с Японией?
Большинство опрошенных прислали ответы на все или на часть вопросов. Составить программу получения первых пяти наиболее часто встречающихся ответов по каждому вопросу и доли (в%) каждого такого ответа. Предусмотреть необходимость сжатия столбца ответов в случае отсутствия ответов на некоторые вопросы. Пояснения в [7], стр. 264.
16) В памяти компьютера хранится список фамилий абонентов в алфавитном порядке их номеров телефонов. Составить программу, обеспечивающую быстрый поиск фамилии абонента по номеру телефона. Пояснения в [7], стр. 266.
17) В памяти ЭВМ хранятся списки номеров телефонов и фамилий абонентов, упорядоченные по номерам телефонов, для каждого из пяти телефонных узлов города. Один телефонный узел включает несколько АТС (не более 10). Номера АТС (первые две цифры номера телефона), относящихся к каждому телефонному узлу, также хранятся в памяти ЭВМ. Составить программу, обеспечивающую быстрый поиск фамилии абонента по заданному номеру телефона (количественные данные по телефонной сети не относятся к г. Москва). Пояснения в [7], стр. 266
18) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по возрастанию методом пузырька.
19) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом пузырька.
20) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по возрастанию методом Шелла.
21) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом Шелла.
22) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по возрастанию методом прямого включения. Пояснения в [9], стр. 78 – стр. 80.
23) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по возрастанию методом прямого выбора. Пояснения в [9], стр. 79 – стр. 80.
24) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом прямого включения. Пояснения в [9], стр. 78.
25) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом прямого выбора. Пояснения в [9], стр. 79 – стр. 80.
26) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом сортировки прямым обменом (шейкерная сортировка).
27) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом улучшенной сортировки разделением (быстрая сортировка с рекурсией).
28) Составить программу сортировки, используя деревья сортировки (улучшенная сортировка выбором – сортировка с помощью дерева).
29) Составить программу сортировки в файле (сортировка последовательного файла).
30) Составить программу сортировки в файле (сортировка последовательного файла слиянием).
31) Дан одномерный массив А, состоящий из N элементов (N – заданное натуральное число). Если элементы массива А составляют строго монотонную последовательность, то все положительные элементы массива заменить единицей, иначе отсортировать массив по возрастанию.
32) Дан одномерный массив А, состоящий из N элементов (N – заданное натуральное число). Если имеется хотя бы одна пара совпадающих элементов, то упорядочить элементы этого массива по неубыванию, иначе записать элементы этого массива в обратном порядке.
33) Заданы два одномерных целочисленных массива А и В, состоящие из N элементов каждый (N – заданное натуральное число). Объединить элементы этих двух массивов в один и упорядочить их по неубыванию, удалив из него элементы, являющиеся четными положительными числами.
34) Дан одномерный целочисленный массив А, состоящий из N элементов (N – заданное натуральное число). Присвоить переменной F значение 1, если элементы массива составляют строго возрастающую последовательность, F=-1, если строго убывающую, F=2, если элементы массива составляют знакочередующуюся последовательность, F=0, если она не является строго монотонной или знакочередующейся.
35) Дан одномерный массив А, состоящий из N элементов (N – заданное натуральное число). Упорядочить массив А по неубыванию, воспользовавшись следующим алгоритмом сортировки. Отыскивается максимальный элемент и переносится в конец. Затем этот алгоритм применяется ко всем элементам кроме последнего и т. д.
36) Даны два одномерных целочисленных массива А и В, состоящих из N элементов каждый (N – заданное натуральное число). Сформировать массив, элементы которого являются пересечением указанных массивов, и расположить его элементы по неубыванию. Одинаковые значения заносить только один раз. Если пресечение массивов есть пустое множество, то выдать соответствующее текстовое сообщение.
37) Даны два одномерных целочисленных массива А и В, состоящих из N элементов каждый, N – заданное натуральное число. Сформировать массив С, элементы которого являются объединением указанных массивов, и расположить его элементы по неубыванию. Одинаковые значение заносить только один раз.
38) Дан одномерный массив А, состоящий из N элементов (N – заданное натуральное число). Присвоить переменной F=1, если элементы массива составляют строгую возрастающую арифметическую прогрессию, и F=-1, если строго убывающую арифметическую прогрессию.
39) Дан одномерный целочисленный массив А, состоящий из N элементов, N – заданное натуральное число. Пусть МАХ – наибольшее, а MIN – наименьшее значения среди элементов массива. Составить одномерный массив В из простых чисел из сегмента [MIN, МАХ], которые не являются элементами массива А, записав его элементы в порядке неубывания. Если таких элементов нет, то выдать соответствующее текстовое сообщение.
40) Каждый из 12 магазинов имеет свой список товаров с известными ценами и в известном количестве. Число товаров в каждом списке различно и заранее не определено. Подсчитать, на какую сумму денег имеет товаров каждый магазин, расположив список в порядке убывания этой суммы.
41) Каждая из 30 групп студентов имеет свой процент успеваемости (от 0 % до 100 %). Составить список номеров групп, которым необходимо повысить успеваемость до среднего уровня. Список расположить в порядке убывания процента успеваемости этих групп.
42) В магазине имеются товары различных наименований. В течение дня каждый из М покупателей (М – заданное число) сообщил о своем намерении приобрести определенное количество товара одного из наименований. Требуется определить суммарный спрос на товары каждого наименования, расположив товары в порядке убывания дневного спроса на них.
43) Опросили 200 подписчиков. Каждый из них назвал три любимые газеты. Напечатать пронумерованный список первых 10 наиболее популярных газет, расположив названия газет в списке в порядке уменьшения числа поданных за них голосов. Предусмотреть, что каждый из опрошенных должен назвать три разные газеты, а общее число названных газет может быть как больше, так и меньше 10.
44) Каждый из X магазинов в течение месяца работал Di дней (N и Di – заданные числа, где i=l, 2,…, X). Известна прибыль каждого магазина в каждый день его работы. Необходимо напечатать упорядоченный по месячным доходам список названий магазинов, имеющих прибыль в пересчете на один день работы выше средней дневной прибыли по всем магазинам.
45) В гостинице N этажей по M номеров на этаже (N и М заданы, а нумерация гостиничных номеров сплошная). Требуется для каждого номера ввести его стоимость и информацию о том, свободен он, занят или забронирован, а затем получить ведомости всех свободных, занятых и забронированных номеров в порядке возрастания их стоимости с указанием стоимости проживания, этажа и номера гостиницы.
46) В итоговой таблице первого круга футбольного чемпионата, каждая из N команд (N и названия команд заданы) представлена количеством забитых и пропущенных голов в каждой из встреч с противниками. Перечислить команды, которые в сумме забили в чужие ворота голов больше, чем пропустили в свои, в порядке убывания разности забитых и пропущенных голов.
47) По результатам опроса прошлого года известен список 10 политических деятелей в порядке убывания их популярности. Проведен новый опрос. Каждый из N журналистов (N – заданное число) назвал три различные фамилии из этого списка. Требуется получить новый список в порядке убывания популярности политических деятелей и показать место, которое занимал каждый деятель в предыдущем опросе. Предусмотреть проверку: каждый из опрошенных журналистов называл разные фамилии и только из имеющихся в старом списке.
48) Опросили 30 кинологов, каждый из которых 3 раза назвал одну породу собак или разные породы собак в любом сочетании, как самую популярную (популярные) по его мнению. Вывести на экран список пород, попавших в первую десятку в порядке убывания популярности, с указанием числа полученных ими голосов опрошенных.
49) Каждая из М библиотек района (М – задано) составляет заявку на приобретение книг. Заявка содержит перечень книг, состоящий из не более 20 наименований. Каждая библиотека в каждой строке заявки указывает название книги, фамилию автора, а также количество экземпляров. Определить суммарный спрос на каждую из указанных книг, и напечатать общий список книг в порядке убывания спроса.
50) 200 учеников шести школ города (номера школ заданы) принимают участие в тестировании по математике. Правильные численные ответы к пяти предложенным задачам даны. О каждом ученике известно: фамилия, номер школы и пять ответов на задачи. Сведения об учениках не имеют определенной упорядоченности. Составить списки учеников по школам, расположив в каждом списке фамилии в порядке убывания количества решенных задач. Предусмотреть возможный ответ «не решил».
51) Каждое из М садоводческих товариществ (М – заданное число) направляет на базу свой список-заявку с указанием наименований требуемых и семян и их количества в кг. Число наименований семян в заявке для каждого товарищества не превышает 20‑ти. Составить суммарный запрос на базу, указав общее необходимое количество семян каждого вида, расположив наименования в списке в порядке убывания спроса.
52) В массив размерности N (N – заданное натуральное число) ввести слова длиной не более 15 символов каждое. Вывести на экран эти слова в порядке увеличения их длины с указанием количества букв «i» в каждом из них. Выполнить проверку вводимой информации.
53) Имеются сведения о каждом рейсе Аэрофлота с номерами от 1 до 100: пункт назначения и количество перевезенных пассажиров. Определить количество пунктов назначения и построить списки номеров рейсов для каждого из них в порядке уменьшения числа пассажиров, перевезенных этими рейсами.
54) Ввести в массив N произвольных чисел (N – заданное натуральное число). Отсортировать отрицательные числа по убыванию, положительные – по возрастанию, оставив отрицательные на местах, принадлежащих отрицательным, а положительные на местах, принадлежащих положительным. Постараться дополнительных массивов не использовать. Вывести на экран исходный и полученный массивы.
55) Ввести произвольные числа в два одномерных массива одинакового размера N (N – заданное натуральное число). Переставить элементы первого массива так, чтобы его максимальный элемент находился на месте, расположения максимального элемента из второго массива, а каждый очередной по убыванию элемент из первого массива располагался на месте, соответствующем расположению очередного по убыванию элемента второго массива. Напечатать модифицированный массив.
56) В массив заданного размера N (от 3 до 10) ввести произвольные числа. Изменить порядок следования элементов в нем на обратный отдельно до и отдельно после К-го элемента массива (К задано). Напечатать модифицированный массив. При вводе данных осуществить проверку.
57) В массив заданного размера N (от 3 до 10) ввести произвольные числа. Не изменяя состояния этого массива и используя лишь один дополнительный массив, напечатать номера элементов исходного массива, соответствующие порядку убывания значений элементов. При вводе данных осуществить проверку.
58) В два одномерных массива одинакового размера N (N – заданное натуральное число) ввести произвольные числа. Не изменяя исходных массивов, сформировать из элементов первого массива третий массив так, чтобы максимальный элемент первого массива в третьем находился на месте, соответствующем расположению максимального во втором, а каждый очередной по убыванию элемент из первого массива располагался в третьем на месте, соответствующем расположению очередного по убыванию элемента второго массива. Напечатать все три массива.
59) Напечатать в возрастающем порядке все четырехзначные натуральные числа, все цифры которых являются соседями в натуральном ряду. Примерами таких чисел являются 4756 и 7645. Найти количество и среднее арифметическое этих чисел.
60) Ввести числовую матрицу размером NxM (N, M заданы). Найти максимальный элемент среди расположенных в тех строках матрицы, которые являются упорядоченными (либо по возрастанию, либо по убыванию), или сообщить, что такого элемента нет.
Похожие работы
... Е и множество и мы рассматриваем все его подмножества, то множество Е называется униварсельным. Пример: Если за Е взять множество книг то его подмножества: художественные книги, книги по математике, физики, физики … Если универсальное множество состоит из n элементов, то число подмножеств = 2n. Если , состоящее из элементов E, не принадлежащих А, называется дополненным. Множество можно задать: ...
в и формальных систем является центральной в дисциплине. В настоящие время от нее возникли ответвления, например, разработка алгоритмических языков программирования.Одной из важнейших проблем в дискретной математики является проблема сложности вычислений.Теория сложности вычислений помогает оценить расход времени и памяти при решении задач на ЭВМ. Теория сложности позволяет выделить объективно ...
... которой были разработаны в последней четверти 19 века Георгом Кантором. Цель контрольной работы – ознакомится с основными понятиями и методами решения по дискретной математике, уметь применить полученные знания при решении практического задания. Задание 1 Представить с помощью кругов Эйлера множественное выражение . Используя законы и свойства алгебры множеств, упростить заданное ...
элементы теории нечетких множеств можно применять для решения экономических задач в условиях неопределённости. 1. применение Логических функций 1.1 Применение методов дискретной математики в экономике При исследовании, анализе и решении управленческих проблем, моделировании объектов исследования и анализа широко используются методы формализированного представления, являющегося предметом ...
0 комментариев