Программирование на ЭВМ

Автор работы: Пользователь скрыл имя, 26 Апреля 2012 в 21:22, курсовая работа

Описание

За время существования профессии программиста сущность его труда изменилась коренным образом. В 50-х годах программы писали в командах ЭВМ (в “машинных кодах”). При этом вся информация переводилась в двоичную систему счисления. Это очень тяжелый и напряженный труд, требующий от человека особой аккуратности. Облегченно вздохнули программисты при появлении в 1956 г. специального языка для решения вычислительных задач. Это был FORTRAN (Formula Translator). С тех пор были разработаны другие, более совершенные языки, или специализированные применительно к какой-то конкретной области: КОБОЛ, АЛГОЛ, ПЛ/1, ЛИСП, СИМУЛА, ПАСКАЛЬ, СИ, АДА, ПРОЛОГ и др.

Скачать (211.45 Кб) Сколько стоит заказать работу?
Работа состоит из  1 файл

Алгоритмы на Pascal.DOC

— 826.50 Кб (Скачать документ)

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

    Обобщенно наш алгоритм можно записать так.

  1. I:=1;
  2. Пока I ≤ N-1

          Начало

    1. найти минимальный элемент и его номер в последовательности AI, …, AN.
    2. поменять местами AI и минимальный элемент.
    3. I:=I+1;

      Конец

    Алгоритм  поиска минимального элемента и его  номера мы рассмотрели ранее, поэтому

    2.1.

          K:=I;

          X:=A[I];

          J:=I+1;

          WHILE J<=N DO

          BEGIN

                IF A[J]<X

                THEN BEGIN

                      X:=A[J];

                      K:=J;

                END;

                J:=J+1;

          END;

    В результате значением Х будет  значение минимального элемента среди  АI, ... AN, а значением К - номер этого элемента. Поэтому п. 2.2. можно записать конкретнее:

       2.2. поменять местами элементы  Ai и Ak

    Это можно сделать так:

    2.2. C:=A[I]; А[I]:=A[K]; A[K]:=C;

    Однако  в нашей ситуации дополнительная переменная С не нужна, так как  ее роль играет Х из п. 2.1. Поэтому  запишем:

        2.2. A[K]:=A[I]; A[I]:=X;

    Мы  сэкономили на одном присваивании, а так как действие выполняется  в цикле, то это немало.

    Теперь  запишем полностью алгоритм сортировки простым выбором.

    Ввод (последовательность А);

    I:=1;

    WHILE I<=N-1 DO

          BEGIN

          K:=I;

          X:=A[I];

          J:=I+1;

            WHILE J<=N DO

                BEGIN

                      IF A[J]<X

                      THEN

                      BEGIN

                        X:=A[J];

                            K:=J;

                      END;

                      J:=J+1;

                END;

          A[K]:=A[I];

          A[I]:=X;

          I:=I+1;

      END;

                                             Простой обмен

    Обмен (перестановка двух элементов в памяти) присущ любому алгоритму сортировки. Но в этом методе он является основной операцией.

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

    Пусть задана следующая последовательность: 

Номер элемента 1 2 3 4 5
Значение  элемента 7 49 1 12 3

 

    Будем рассматривать последовательность от конца к началу (можно и наоборот). Сравниваем 4-й и 5-й элементы и меняем их местами (расположены не в порядке возрастания). Затем сравниваем 3-й с новым 4-м - оставляем на месте. 2-й и 3-й - меняем. 1-й и 2-й - меняем. Получим следующую последовательность 

Номер элемента 1 2 3 4 5
Значение  элемента 1 7 49 3 12

 

    В результате таких обменов минимальный  элемент перешел на первое место  в последовательности. Поэтому в  следующий просмотр его не включаем, просматриваем N-1 элемент точно так же и т.д. В результате (N-1)-го просмотра получим упорядоченную последовательность.

    Если  вообразить, что элементы последовательности - это пузырьки воздуха в резервуаре с водой, каждый с весом, равным значению элемента, то каждый проход с обменами по последовательности соответствует «всплыванию» пузырька на соответствующий его весу уровень. Благодаря такой аналогии сортировку простым обменом называют также сортировкой методом «пузырька».

     На рис.2.1 первые два элемента уже упорядочены и «всплывает» третий. Знак <= (а не <) показывает условие прекращения сравнений. Этим достигается устойчивость сортировки «пузырьком». 

Рис. 2.1 – Иллюстрация метода «пузырька» 

Рассмотрим  численный пример (табл.2.5). 
 
 

Таблица 2.5 – Пример сортировки простым обменом

Номер элемента 1 2 3 4 5 6 7 8  
Исходная последовательность 72 14 6 98 17 51 25 33 4 обмена
После просмотра      8 элементов 6 72 14 17 98 25 51 33 3 обмена
7 элементов 6 14 72 17 25 98 33 51 2 обмена
6 элементов 6 14 17 72 25 33 98 51 2 обмена
5 элементов 6 14 17 25 72 33 51 98 1 обмен
4 элементов 6 14 17 25 33 72 51 98 1 обмен
3 элементов 6 14 17 25 33 51 72 98  
2 элементов 6 14 17 25 33 51 72 98  
Упорядоченная последовательность 6 14 17 25 33 51 72 98  

    Основой алгоритма, реализующего данный метод, является цикл, выполняющийся N-1 раз. Границы для параметра цикла I могут быть равны 1 и N-1 или 2 и N. Вначале приведем обобщенную запись алгоритма.

  1. I:=2;
  2. WHILE I<=N DO
    BEGIN

    2.1. сравнить попарно элементы AN, AN-1, ... , AI, AI-1

    2.2. I:=I+1;

    END;

    Детализируем  п.2.1. Для попарного сравнения элементов нужен цикл с границей, зависящей от I, так как при каждом новом проходе последовательности ее длина укорачивается. Поэтому

    2.1.1. J:=N;

    2.1.2. WHILE J>=I DO

      BEGIN

    2.1.2.1. Сравнить AJ и AJ-1 и при необходимости поменять их местами.

    2.1.3. J:=J-1;

    END;

    Пункт 2.1.2.1. записать довольно просто.

    2.1.2.1. IF A[J-1]>A[J]

             THEN

                      BEGIN 

                      X:=A[J-1];

            A[J-1]:=A[J];

            A[J]:=X;

            END;

    Объединим наши шаги детализации в алгоритм.

    Ввод (последовательность А);

    I:=2;

    WHILE I<=N DO

    BEGIN

          J:=N;

          WHILE J>=I DO

          BEGIN

                IF A[J-1]>A[J]

                THEN

                BEGIN

                      X:=A[J-1]; A[J-1]:=A[J];

          A[J]:=X;

                END;

      J:=J-1;

      END;

      I:=I+1;

    END;

    Вывод (последовательность А);

                                  

Простые вставки

    Пусть в заданной последовательности А1, А2, ... , АN первые I-1 элементов уже отсортированы. Найдем в этой части место для I-го элемента. Для этого будем сравнивать его по порядку со всеми элементами, стоящими левее него, до тех пор, пока не найдется некоторый AK<=AI. Затем сдвинем часть последовательности AK+1, ... , AI-1 на один элемент вправо и на освободившееся место поставим AI. Знак <= позволяет обеспечить устойчивость сортировки.

    После того, как проделаем эти действия для всех элементов от 2-го до N-го, получим отсортированную последовательность. Важно отметить, что при сравнении может оказаться , что условие АK<=AI не выполнится, так как АK может быть меньше всех левых элементов. Тогда нужно сдвинуть все элементы А1, ... , АI-1 вправо и поставить АI на первое место.

    Рассмотрим  пример, иллюстрирующий работу метода (табл.2.6).  
 
 
 

Таблица 2.6 – Пример сортировки простыми вставками

Номер элемента 1 2 3 4 5 6 7 8
Исходная последовательность 72 14 6 98 17 51 25 33
После вставки элемента        № 2 14 72 6 98 17 51 25 33
                        3 6 14 72 98 17 51 25 33
4 6 14 72 98 17 51 25 33
5 6 14 17 72 98 51 25 33
6 6 14 17 51 72 98 25 33
7 6 14 17 25 51 72 98 33
8 6 14 17 25 33 51 72 98
Упорядоченная последовательность 6 14 17 25 33 51 72 98

Информация о работе Программирование на ЭВМ