Контрольная работа структуры и алгоритмы обработки данных. Контрольная работа. Контрольная работа по предмету Структуры и алгоритмы обработки данных
 Скачать 100.46 Kb.
|
|
В данном случае произошло С=14 сравнений и М=27 перестановок Строим таблицу выполнения 1-сортировки по результатам выполнения 3-сортировки:
Жёлтым цветом обозначены символы, которые сравниваются с проверяемым элементом. В данном случае произошло С=23 сравнений и М=24 перестановок Количество сравнений и перестановок для 1-сортировки с предварительной 3-сортировкой С=23+14=37 и М=24+27=51. Ответ: АААВЕЛНННОПХ; 37 сравнений, 51 перестановка. Задание 4. Для набора из 12 букв своих фамилии, имени, отчества, построить пирамиду. Решение: Набор символов ФИО: ПЛЕХАНОВААНН Пирамидой называют последовательность из элементов: ai, ai+1, …, ak (где i – номер элемента массива, k – конечный элемент массива), при условии, что неравенство aj≤min(a2j, a2j+1) выполняется для каждого j, (j=i, …, k), для которого хотя бы один из элементов a2j, a2j+1 существует. Построим пирамиду из ФИО студента с расширением влево. При первом проходе сравниваются первый и последний элемент массива. Если первый оказывается больше последнего, то они меняются местами и продолжается сравнение. Если первый оказывается меньше последнего или равен ему, то они остаются на своих местах и продолжается сравнение. В последующих проходах сравнивается первый символ массива и следующие два после предыдущего. При равенстве всех сравниваемых элементов с первым, они остаются на своих местах и продолжается сравнение. Так же происходит, когда два последних элемента больше первого. Если хотя бы один сравниваемый элемент меньше первого, то они меняются местами и продолжается сравнение. Если оба элемента меньше первого, то меняются местами первый и наименьший из двух сравниваемых элементов. Пирамида заканчивается, когда оба сравниваемых элемента меньше первого. После каждого сравнения на следующую строку ниже добавляется новый крайний элемент массива, который будет сравниваться по выше указанным правилам. Построение пирамиды заканчивается, когда не остаётся возможности обмена первого символа. Пирамидой будет называться последовательность, удовлетворяющая условиям: Первый элемент массива ≤ последнему или двум сравниваемым элементам массива. Обозначим: Красный цвет – первый элемент массива Жёлтый цвет – сравниваемый(ые) с первым элементом массива Построим пирамиду:
|