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 заданы). Найти максимальный элемент среди расположенных в тех строках матрицы, которые являются упорядоченными (либо по возрастанию, либо по убыванию), или сообщить, что такого элемента нет.
1.4 Вопросы для самопроверки
1) Какими свойствами обладает отношение частичного порядка? Приведите примеры этого отношения.
2) Дайте определение отношения линейного порядка.
3) Сформулируйте постановку задачи сортировки.
4) В чём заключается преимущество отсортированных (упорядоченных) данных?
5) Как рассматривается задача сортировки с точки зрения программирования?
6) От каких факторов зависит эффективность алгоритма сортировки?
7) Перечислите наиболее часто используемые на практике методы поиска и сортировки.
8) Каким образом могут быть представлены данные при поиске и сортировке?
9) Перечислите основные операции при работе с данными.
10) В чём заключается алгоритм линейного поиска?
11) В чём заключается алгоритм бинарного поиска?
12) Опишите кратко поиск в бинарных деревьях.
13) Какие функции используются при оценке времени исполнения алгоритма?
14) В чём заключается метод сортировки вставками?
15) В чём заключается метод сортировки с помощью включения, прямого включения?
16) В чём заключается метод Шелла?
17) Опишите сортировку с помощью обменов.
18) Опишите алгоритм быстрой сортировки, предложенный Ч. Хоаром (QuickSort).
Практическая работа № 2. Представление множеств в компьютере
Цель работы: изучение представлений множеств и отношений в программах, алгоритмов с использованием множеств; представление множеств характеристическими векторами и их практическая реализация.