Составление линейных таблиц – Задача упорядочения линейной таблицы


§ 65. Составление линейных таблиц

Изучив этот пункт, мы:

Познакомимся с задачей упорядочения линейных таблиц;

Узнаем, какие идеи составляют основу простых методов составления таблицы; выясним, как складываются алгоритмы упорядочения таблицы методом выбора и при

Методом вставки;

Познакомимся с программами, которые реализуют составления таблиц по методам выбора и вставки.

==== 65.1.Задача упорядочения линейной таблицы ================================

Мы знаем, что в линейной таблицы все ее элементы перенумерованы. Линейная таблица является Упорядоченной, если с ростом номеров ее элементов возрастает или убывает их верный признак. В первом случае говорят, что таблица упорядочена по возрастанию, во втором — по убыванию этого признака. Если некоторые элементы таблицы могут иметь одинаковое значение признака, то речь идет не о ее возрастания или убывания, а о неубывания и невозрастания.

Одну и ту же таблицу можно отсортировать по различным признакам. Например, линейная таблица, содержащая фамилии учеников, может быть упорядоченной по алфавиту, по длине фамилий учеников и тому подобное. Таблица, содержащая целые числа, может быть упорядоченной по значению самых цифр или суммы цифр, из которых состоят эти числа и т. Д.

Будем рассматривать методы упорядочения линейных таб-ликов на примере таблицы с числовыми элементами.

Задачу Упорядочения таблицы сформулируем следующим образом: дано таблицу a, которая состоит из n целочисленных элементов. Переставить элементы таблицы так, чтобы они были расположены по возрастанию (неубывания) их значений.

Рассмотрим два простых методы решения этой задачи. Они просты том, построенные на вполне понятных идеях.

==== 65.2.Составление методом выбора =======================================

Идея Метода выбора заключается в последовательном поиске сначала наименьшего элемента в таблице и переносе его на первое место, затем — на следующий по величине и переносе его на второе место и т. Д. При переносе элемента в определенное место то, что там находился, занимает его место.

Покажем, как происходит упорядочение таблицы методом выбора в примере таблицы из следующих элементов: 4, 7, 2, 8, 17, 19, 5. Количество элементов N = 7.Элементы, которые были перенесены на начало таблицы, будем выделять жирным шрифтом.

Этапа

Диапазон таблицы,

Рассматриваемой

Наименьший

Элемент

Место, на которое

Переносим

Результат

Переноса

1 От 1 до 7:

4, 7, 2, 8, 17, 19, 5

2 1 2, 7, 4, 8, 17, 19, 5
2 От 2 до 7:

7, 4, 8, 17, 19, 5

4 2 2, 4, 7, 8, 17, 19, 5
3 От 3 до 7:

7, 8, 17, 19, 5.

5 3 2, 4, 5, 8, 17, 19, 7
4 От 4 до 7:

8, 17, 19, 7.

7 4 2, 4, 5, 7, 17, 19, 8
5 От 5 до 7:

17, 19, 8

8 5 2, 4, 5, 7, 8, 19, 17
6 От 6 до 7:

19 17

17 6 2, 4, 5, 7, 8, 17, 19

 

==== 65.3.Разработка алгоритма упорядочения таблицы методом выбора ================

Для разработки алгоритма упорядочения таблицы методом выбора обратим внимание на приведенный выше пример. Как видим, шаг за шагом меняется нижняя граница диапазона просмотра таблицы: от 1 на первом шаге к n-1 на последнем шаге. Обозначим нижнюю границу как ng и представим весь процесс упорядочения таблицы в виде цикла:

Для ng От 1 До n-1

Пс

<найти наименьший среди элементов таблицы от A [ng] к A [n]>

<поменять местами наименьший элемент с элементом A [ng]>

Кс

Рассмотрим поочередно составляющие нашего цикла.

Первой составляющей является поиск наименьшего среди элементов таблицы от a [ng] к a [n].Кроме наименьшего элемента (обозначим его min), нам нужно найти и его место в таблице, то есть его индекс (обозначим его m).Таким образом, min = a [m].Напомним, что аналогичную задачу мы решали при определении победителя спортивных соревнований.

Запишем алгоритм первой составляющей нашего цикла:

Min = a [ng] m = ng

Для i От ng + 1 До n

Если a [i] <min То Пс

Min = a [i] m = i

Кс

Вторая составляющая цикла — это обмен местами двух элементов таблицы, то есть наименьшего элемента (это элемент a [m]) и элемента a [ng].Обменять элементы местами значит дать переменной a [m] значение, которое сохраняет переменная a [ng], а переменной a [ng] — значение, которое сохраняет переменная a [m].Попробуем это сделать.

По команде a [m] = a [ng] значение переменной a [ng] будет предоставлено переменной a [m], и она потеряет свое прежнее значение. К счастью, оно сохраняется еще и в переменной min, ведь min = a [m].Мы воспользуемся этим и предоставим переменной a [ng] новое значение командой: a [ng] = min.

Таким образом, вторая составляющая нашего цикла содержит всего две команды:

A [m] = a [ng]; a [ng] = min;

Теперь для записи алгоритма не хватает только описания переменных.

==== 65.4.Программа «Благоустройство таблицы методом выбора» ======================

Рассматриваемый нами алгоритм упорядочения таблицы методом выбора превратим в программу на языке Паскаль. Программа будет иметь такие составляющие: введение элементов неупорядоченной таблице (воспользуемся для этого датчиком случайных чисел); упорядочения таблицы; вывода элементов таблицы после ее благоустройства. Вывод элементов таблицы осуществляется так же, как и их введение в цикле. Элементы таблицы при введении и выведении будем нумеровать. На экране разместите их в колонке для удобства наглядного сравнения, поэтому количество элементов ограничим: возьмем n = 10.

Program sorting_by_choosing;

Uses Crt;

Const n = 10;

Var i, m, min, ng: Integer; a: Array [1..n] Of integer;

Begin Clrscr; randomize;

Writeln ( ‘Таблица к упорядочению:’);

For i: = 1 To n Do {Формируем Таблицу}

Begin

A [i] = Random (50); {Определяем элементы Таблицы}

Writeln (i, ‘. «, a [i]); {Выводим их с номерами на Экран}

End;

For ng = 1 To n-1 Do {Упорядочиваем таблицу с n-1 Проход}

Begin

Min = a [ng]; m = ng;

For i = ng + 1 To n Do {Начинаем просмотр Таблицы}

If a [i] <min Then {для поиска наименьшего Элемента}

Begin

Min = a [i]; m = i;

End; {Просмотр таблицы Завершено}

A [m] = a [ng]; {обмениваем Местами}

A [ng] = min; {маленький и начальный Элементы}

End;

Writeln ( ‘Благоустроенная таблица: ‘); {Выводим упорядоченную Таблицу}

For i: = 1 To n Do

Writeln (i, ‘.’, a [i]);

Readln end.

Мы записали программу для упорядочения целочисленной таблицы, однако ее можно применить и для таблицы величин типа String, так как для них выполняются операции сравнения (в алфавитном порядке).Нужно только внести соответствующие изменения в описательную часть программы.

==== 65.5.Составление таблицы методом простых вставок ========================

Идея Метода вставки заключается в том, чтобы поочередно вставлять один элемент за другим в соответствующее его значению место.

Представьте, что на плацу выстроились шеренга солдат. Солдаты стоят друг рядом с другом по росту. Место правофлангового на плацу является определенным. Командир ведет к взвода новичка, чтобы поставить его в строй. Командир проводит новичка вдоль строя, двигаясь с левого фланга к правому. Каждый солдат, начиная с левофлангового, меньше ростом за новичка, делает шаг влево, пропуская новичка вперед, пока очередь НЕ дойдет к солдата, который НЕ меньше

Новичка по росту. Теперь новичок становится в шеренгу на свободное место. Если же новичок оказался выше всех солдат, он становится правофланговым.

Теперь представьте, что нам нужно расставить по росту учеников класса. Воспользуемся описанным выше способом. Сначала поставим на место правофлангового первого из списка, затем определим место второго, далее — третьего, и так по списку по очереди ищем весь класс. Каждый раз мы будем решать одну и ту же задачу: найти место очередного ученика в упорядоченном строю предыдущих. Именно такая идея лежит в основе метода простых вставок.

Покажем, как работает метод простых вставок на примере порядок числовой таблицы с элементами 7, 9, 4, 6, 8 (n = 5).Введем вспомогательную переменную x, которой будем придавать значение элемента вставляется в таблицу. Как только значение элемента передано переменной x, место элемента можно считать свободным. Будем обозначать перенос значения элемента в переменную X знаком «↑» (например, 9 ↑ X) перемещение элемента на одну позицию вправо — знаком «→» (например, 7 →) вставки значение X в свободное место таблицы — знаком «x ↓».Рассмотрены элементы будем выделять жирным шрифтом.

Поскольку мы имеем упорядочить 5 элементов, по методу вставок это будет осуществлено в 4

Этапа.

Этап Выполняемые действия Значение X Таблица

7, 9, 4, 6, 8

1 9 ↑ 9 7, _, 4, 6, 8
7> 9 «Нет», X 7, 9, 4, 6, 8
2 4 ↑ 4 7, 9, _, 6, 8
9> 4 «да», 9 → 7, _, 9, 6, 8
7> 4 «да», 7 → _, 7, 9, 6, 8
Край таблицы, X 4, 7, 9, 6, 8
3 6 ↑ 6 4, 7, 9, _, 8
9> 6 «да», 9 → 4, 7, _, 9, 8
7> 6 «да», 7 → 4, _, 7, 9, 8
4> 6 «Нет», X 4, 6, 7, 9, 8
4 8 ↑ 8 4, 6, 7, 9, _
9> 8 «да», 9 → 4, 6, 7, _, 9
7> 8 «Нет», X 4, 6, 7, 8, 9

Обратите внимание на то, что в завершение каждого этапа просмотрена часть таблицы (она выделена подсветкой) является упорядоченной.

==== 65.6.Разработка алгоритма упорядочения таблицы методом простых вставок ========

Из приведенного выше примера можно увидеть, что процесс составления таблицы осуществляется поочередно для 2-го, 3-го, …, последнего (n-го) ячеек таблицы. Итак, имеем цикл для и от 2 к n, где через и обозначено номер элемента в таблице:

Для I От 2 До N

Пс

Предоставить переменной X значение A [i]

Передвинуть элементы слева от A [i], больше X, на одну позицию вправо и запомнить номер элемента, оказался не крупнее X

Вставить X в таблицу

Кс

Рассмотрим поочередно составляющие нашего цикла.

Первая составляющая совсем простой: она осуществляется командой x = a [i].

Вторая составляющая предусматривает проверку и передвижения элементов слева a [i], то есть

Элементов, индекс которых k меньше i и приобретает поочередно следующих значений:

K = i-1, i-2, …, 1

Для каждого значения k проверяем условие: a [k]> X.Если результатом проверки является

«Да», то a [k] смещаем на одну позицию командой a [k + 1] = a [k] и переходим к просмотру следующего элемента: k = k-1.Если для некоторого элемента a [k] результатом проверки умвы является «нет», то номер этого элемента запоминаем в переменной j: (j = k), и дальнейшая проверка должна прекратиться.

Может случиться, что все проверки дали результат «да», тогда выход из цикла должна завершиться из-за исчерпания всех значений k> 0.

Реализуем проверку и передвижения элементов таблицы в виде цикла с предусловием. к

Начала цикла переменным j и k нужно предоставить начальных значений: k = i-1, j = 0.Цикл должен выполняться, пока Не найдено элемента, который передвигать не нужно (об этом будет свидетельствовать нулевое значение переменной j), и Не завершено просмотр таблицы (об этом будет свидетельствовать значение переменной k> 0).Итак, условием цикла являются: (j = 0) И (k> 0).Если переменная j вступит ненулевого значения или переменная k уменьшится до нуля, произойдет выход из цикла.

Запишем алгоритм второй составляющей нашего алгоритма:

J = 0; K = I -1

Пока (j = 0) И (k> 0)

Если A [k]> X

То Пс

A [k + 1] = A [k] K = K -1

Кс Иначе

J = K

Третья составляющая должна обеспечивать вставки элемента x на определенное для него место. переменная j или сохраняет значение места первого элемента таблицы, не более x или равна нулю, если такого не нашлось. Итак, в любом случае место элемента x в таблице определяется значением суммы j + 1, и его вставки в таблицу осуществляется командой: a [j + 1] = x.

Теперь наш алгоритм разработан полностью. Для его представления в окончательном виде нужно совместить соответствующим образом все его составляющие и дополнить алгоритм описанием переменных.

==== 65.7.Программа «Благоустройство таблицы методом простых вставок» ==============

По разработанному алгоритму составления таблицы методом простых вставок можно составить программу благоустройства заданной таблицы элементов. Мы можем реализовать разработанный алгоритм на языке Паскаль, действуя по такой схеме, как и для упорядочения таблицы методом выбора. Однако интереснее сделать по-другому.

Применим разработан алгоритм для приведения списка слов (например, английских слов), которые вводятся с клавиатуры поочередно, друг за другом. Каждый раз после вставки слова в таблицу будем выводить ее на экран. Это даст нам возможность наблюдать в динамике, как работает метод.

Приведем программу.

Program sorting_by_ inserting;

Uses Crt;

Const n = 10;

Var i, j, k: Integer; x: String; a: Array [1..n] Of string;

Begin Clrscr;

Writeln ( ‘Введите очередное слово’);

For i: = 1 To n Do {Цикл для ввода Слов}

Begin

Readln (x); {Ввод очередного Слова}

J = 0; {Реализация метода Вставки}

K = i-1;

While (j = 0) And (k> 0) Do {Цикл для поиска места Очередного

If a [k]> x {слова среди ранее введенных Слов}

Then begin a [k + 1] = a [k]; k = K-1;

End

Else j = K;

A [j + 1] = X; {Вставление очередного слова в Список}

Writeln; {Пропуск Строки}

Writeln ( ‘Список:’);

For k: = 1 To i Do {Вывод текущего Список Слов} Writeln (k, ‘. «, a [k]); {с номерами В Столбик} End;

Readln end.

Этой программой можно воспользоваться и для упорядочения последовательности чисел, если внести соответствующие изменения в описание переменных.

ВЫВОДЫ

Составление массивов данных является чрезвычайно важной задачей, так как при бессистемном накоплении они становятся недоступными для использования человеком и теряют свою ценность. Составление означает размещение данных в определенном порядке — по возрастанию или убыванию определенного признака. Один и тот же массив данных может быть упорядоченным по различным признакам. Для упорядочения данных существуют различные методы. Метод выбора предполагает многократный просмотр таблицы для поиска сначала малейшего всех элементов и его переноса в начало таблицы, затем — на следующий по величине и т. Д. Основу метода вставки составляет последовательный просмотр элементов с целью изобретения места для вставки нового элемента в упорядоченную таблицу. Эти методы не являются быстродействующими. На практике для упорядочения больших массивов данных применяют более совершенные, но и более сложные методы.

Контрольные вопросы и упражнения

1. Таблица объединяет 10 элементов. Для ее упорядочения применен метод выбора.  Сколько раз будет выполнена операция сравнения элементов в процессе упорядочения таблицы?

А) 9;

Б) 10;

В) 45;

Г) 10 февраля.

2. Таблица объединяет 10 элементов: 1, 2, 3, 4, 5, 6, 7, 8, 10, 9. По каким методом ее можно быстрее отсортировать по ростом?

А) по методу выбора; б) методом вставки.

3. Первая таблица содержит элементы: 10, 2, 3, 4, 5, 6, 7, 8, 9, 1. Вторая — элементы 1, 2, 3, 4, 5, 6, 7, 8, 10, 9. Для упорядочения таблиц по возрастанию применили метод выбора. Какую из таблиц было упорядочено быстрее?

А) первую; б) вторую;

В) скорость составления таблиц одинакова.

4. Для которой из таблиц метод вставки скорее завершит ее упорядочение по возрастанию? а) 1, 2, 3, 4, 5, 7, 6, 8, 10, 9;

Б) 10, 2, 3, 4, 5, 6, 7, 8, 9, 1;

В) 1, 2, 3, 4, 5, 6, 10, 9, 8, 7

Г) 5, 2, 3, 4, 1, 6, 7, 8, 9, 10;

Д) для всех таблиц количество действий одинакова.

5. Модифицируйте программу благоустройства таблицы методом выбора так, чтобы она осуществляла упорядочение заданной числовой таблицы с убыванию.

6. Модифицируйте программу благоустройства таблицы методом выбора так, чтобы она располагала слова в списке по алфавиту.

7. Модифицируйте программу благоустройства таблицы методом вставки так, чтобы она из чисел, вводимых с клавиатуры, образовала их список, упорядоченный по ростом.

8. Модифицируйте программу благоустройства таблицы методом вставки так, чтобы она упорядочивала заданную таблицу чисел с убыванию.

9. Модифицируйте программу благоустройства таблицы методом вставки так, чтобы она упорядочивала заданную таблицу слов в алфавиту.

10. Таблица, созданная с помощью датчика случайных чисел, содержит n целых чисел. Составьте программу определения количества цифр, которые стоят на своем месте, то есть занимают место в таблице, на котором они оказались бы после ее упорядочения по неубывания.

11. Составьте программу изъятия из заданного списка фамилий, повторяются.

12. В супермаркете осуществляется регистрация каждой покупки, сделанной покупателем. Составьте программу, которая по списку наименований товаров, приобретенных в течение дня, определяет, какой товар пользовался наибольшим спросом.

[Всего голосов: 3    Средний: 5/5]

Читать  Понятие о языке программирования Turbo Pascal, главное окно Turbo