Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Топ:
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Интересное:
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Дисциплины:
2022-11-14 | 23 |
5.00
из
|
Заказать работу |
|
|
Спецификация
1. Назначение: сортировка части одномерного массива (от индекса first по индекс last), содержащего не более, чем 2n элементов
2. Имя: sort
3. Вид: процедура
4. Перечень параметров:
Таблица 19.6. Перечень параметров
Статус | Назначение | Имя | Тип | Вид |
Вход/ выход | сортируемый массив | b | t1 | параметр-переменная |
Вход | Индекс начала диапазона сортировки | first | integer | параметр-значение |
Вход | Индекс конца диапазона сортировки | last | integer | параметр-значение |
Вход | Признак сортировка (истина – сортировка по возрастанию, ложь – по убыванию) | prs | boolean | параметр-значение |
Примечание: тип t1 и поименованная константа n должны быть определены до текста подпрограммы
type t1=array[1..2*n] of integer;
5. Заголовок подпрограммы: procedure sort(var b:t1;first,last:integer;prs:boolean);
Метод решения
Используем метод сортировки выбором с перестановкой. В этом методе формируем все места с начального по предпоследнее. Для каждого формируемого места
" i:=first(1)last-1:
решаем две задачи:
1) выбор значения, которое должно располагаться на формируем месте i.
2) перестановку. На место экстремального значения заносим значение с формируемого места. На формируемое место записываем экстремальное значение
Задача 1 сводится к поиску экстремального значения и его местоположения, начиная с формируемого места i по последнее сортируемое место last. При сортировке по возрастанию ищется минимальное значение, по убыванию – максимальное. Метод решения этой задачи выглядит следующим образом:
1) переменной extr, в которой будет сформировано экстремальное значение присваивается первое значение, среди которых ищется экстремальное;
2) фиксируется местоположение экстремального значения в массиве. Для этого во вспомогательную переменную nm заносится индекс элемента, из которого взято значение (в данном случае nm:=i);
|
3) перебираются все остальные значения:
" j:= i +1(1) last:
Для каждого j значения при сортировке по возрастанию (pr=истина), если очередное j значение меньше хранящегося в extr, а при сортировке по убыванию (pr=ложь) – больше, то
а) переменной extr присваиваем это очередное значение;
б) фиксируем местоположение текущего значения в массиве. Для этого во вспомогательную переменную nm заносится индекс j.
Задача 2 – это перестановка значений. Так как экстремальное значение существует в двух экземплярах (в переменной extr и в массиве на месте с индексом nm), то метод решения состоит из следующих действий:
1) b[nm]:=b[i];
2) b[i]:=extr.
Информационная модель
Таблица 19.7. Информационная модель
Назначение | Имя | Тип |
Индекс формируемого места | i | integer |
Индекс при поиске экстремального | j | integer |
Экстремальное значение | extr | |
Местоположение экстремального значения | nm |
Текст процедуры
procedure sort(var b:t1;first,last:integer;prs:boolean);
var i,j,nm:integer;
extr:integer;
begin
for i:=first to last-1
do begin
extr:=b[i];
nm:=i;
for j:=i+1 to last
do if prs and (b[j]<extr) or not prs and (b[j]>extr)
then begin
extr:=b[j];
nm:=j
end;
b[nm]:=b[i];
b[i]:=extr;
end
end;
Разработка подпрограммы sortpart
Спецификация
1. Назначение: сортировка определенной в задании части двумерного массива с использованием подпрограммы sort
2. Имя: sortpart
3. Вид: процедура
4. Перечень параметров:
Таблица 19.8. Перечень параметров
Статус | Назначение | Имя | Тип | Вид |
Вход/ выход | сортируемый массив | a | t2n | параметр-переменная |
Примечание: тип t2n и поименованная константа n должны быть определены до текста подпрограммы
type t2n=array[1..2*n,1..2*n] of integer;
5. Заголовок подпрограммы: procedure sortpart(var a:t2n);
Метод решения
Для каждой сортируемой строки двумерного массива (с первой по n-ую)
|
" i:=1 (1) n:
1) переписываем i-ую строку во вспомогательный одномерный массив b. Для этого перебираем все столбцы двумерного массива. Индекс при этом является одновременно индексом одномерного массива и индексом столбца двумерного;
2) обращаемся к процедуре sort сортировки части одномерного массива, задавая границы сортировки. Нижняя граница, исходя из постановки задачи, всегда n+1, а верхняя уменьшается с увеличением номера строки – 2n-i+1 (побочная диагональ);
3) переписываем отсортированный одномерный массив b в i-ую строку двумерного массива.
Информационная модель
Таблица 19.9. Информационная модель
Назначение | Имя | Тип |
Номер (индекс) строки двумерного массива | i | integer |
Номер столбца (индекс) двумерного массива и номер элемента (индекс) вспомогательного одномерного массива | j | integer |
Вспомогательный одномерный массив | b | t1 |
Примечание: тип t1 определяется следующим образом
type t1=array[1..2*n] of integer;
:где поименованная константа n должна быть определены до текста подпрограммы
Текст процедуры
procedure sortpart(var a:t2n);
type t1=array[1..2*n] of integer;
var b:t1;
i,j:integer;
begin
for i:=1 to n
do begin
for j:=1 to 2*n
do b[j]:=a[i,j];
sort(b,n+1,2*n-i+1, true);
for j:=1 to 2*n
do a[i,j]:=b[j]
end
end;
|
|
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!