Реферат: Методические указания к лабораторным работам по дисциплине «Программирование на языке высокого уровня»

Методические указания к лабораторным работам

по дисциплине «Программирование на языке высокого уровня»

2-Й СЕМЕСТР


Знакомство с интегрированной средой языка С.

Интегрированная среда С ( а именно язык Turbo C++ version 1.0-. и выше) является частью системы программирования С. Основным достоинством среды С является интеграция необходимых средств разработки С-программ в единую среду программирования-интегрированную среду (ИС). Не выходя из среды, мы имеем возможность создавать, компилировать, выполнять, отлаживать, корректировать программу.

Интегрированная среда С является удобным средством для быстрой разработки программ на языке С. Работа пользователя в среде С базируется на использовании техники меню и окон. К тому же в среде имеется контекстно-чувствительное средство получения справочной информации. Все это делает интерфейс с компилятором легким в изучении.

Предположим, что основные файлы С расположены в каталоге C:\TC. Тогда для запуска интегрированной среды укажите путь C:\TC\BIN\tc.exe, или просто: C\TC\BIN\tc

Когда программа запустится, мы увидим, что .вид экрана изменился. Верхняя строка будет содержать меню основных режимов работы ИС. Нижняя строка коротко описывает основные «горячие» клавиши.(см. рис 1.)

E

File

Edit

Search

Run

Compile

Debug

Options

Window




Fl Help F2 Save F3 Open ALT-F9 Compile F9 Make F10 Menu

Рис. l. Интегрированная среда С.

Для того, чтобы войти в главное меню среды, достаточно нажать клавишу «F10» (обратите внимание на соответствующую подсказку в нижней строке). При этом в одном из пунктов меню в верхней строке появится подсвеченный прямоугольник, который можно передвигать, нажимая на клавиши «→»и «←».

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

По этому списку так же можно передвигать подсвеченный прямоугольник (нажимая клавиши «↑» и «↓»). Пункт подменю, выбирается нажатием клавиши «Enter», (см. рис 2.)

E

File

Edit

Search

Run

Compile

Debug

Options

Window


Open F3

New

Save F2

Save as...

Save all

Change dir

Print

Get Info

Dos shell

Exit Alt-X




Fl Help F2 Save F3 Open ALT-F9 Compile F9 Make F10 Menu

Рис. 2. Работа с пунктом меню «File»

Можно легко передвигаться из одного пункта меню в другое. Для этого используются клавиши «→ » , « ← », « ↑ » , « ↓ » и еще клавиша « Esc ». Клавиша «Esc» нужна, чтобы выйти из данного подменю во «внешнее».

^ Режим редактирования.

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

Первым действием при разработке программ является создание (нажмите клавишу «F3») и сохранение (нажмите клавишу «F2») программы. Для создания новых программ и редактирования уже существующих, в среде С есть встроенный текстовый редактор, содержащий богатый набор операций редактирования. Эти операции дают возможность создавать, сохранять и редактировать программы в среде С.

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

После набора текста программы сохраните (с помощью «F2») а для запуска программы выполните один из следующих вариантов:

1) Нажмите комбинации клавиш «All»+ «F9» (для компиляции) или «Ctrl» + «F9» (для выполнения программы).

2) В верхней строке меню выберите меню « Run» и выполните действие «Run», для этого нажмите «Enter». После этого на экранпоявится результат.

^ Компиляция, выполнение и отладка программ.

После создания и сохранения программы следующими этапами разработки являются компиляция, выполнение и отладка этой программы. Для этих целей в среде Си имеются встроенный компилятор и отладчик. Для управления компиляцией, выполнением и отладкой в среде Си используются команды меню «Run (запуск)» , «Compile (компиляция)», «Debug (отладка)».

^ 1. Меню «Compile» (Компиляция).

Команды меню «Compile» создают объектный файл из текущего сходного файла.

Действиями команд из меню ознакомьтесь самостоятельно, для этого используйте клавиши «↓», «↑». После выбора нужного подменю нажмите «Enter» и выполняется действия.

^ 2. Меню «Run» (Запуск).

Команды меню «Run» (Запуск) начинают или продолжают выполнение программы. Здесь можно осуществлять трассировку и пошаговое выполнение команд программы.

^ 3.Меню «» (Отладка).

Команды меню «Отладка» в сочетании с командами меню «Запуск» управляют отладкой в среде Си.


Лабораторная работа № 1

Тема: Программирование линейных алгоритмов.

^ Стандартные подпрограммы (функции Printf, Scanf).

Цель работы: научить студентов использовать стандартных функций для решений всяких задач. Овладение практическими навыками разработки и программирования вычислительного процесса.
^ Задания для самостоятельной подготовки 1. Изучить:
─ запись констант, переменных, стандартных функций;

─ правила записи арифметических выражений;

─ арифметический оператор присваивания;

─ организацию простейшего ввода-вывода данных.

2. Разработать алгоритм решения в соответствии с заданием.

3.Составить программу решения задачи.


         К наиболее интересным и важным функциям языка относится printf . Она предназначена для форматного вывода данных. Например, чтобы вывести некоторое сообщение на экран дисплея, достаточно использовать вызов функции:

                printf ("Интересное сообщение \n");

   Одним из механизмов взаимодействия являются параметры. Список параметров (аргументов) идет вслед за именем функции в круглых скобках. В данном случае аргументом служит строковая константа - любая последовательность символов, в кавычках. Комбинация " \n " означает переход на новую строку. Первый пример можно заменить вот на такую строчку:

               printf ("Интересное сообщение "); prin tf(" \n "); 

   - результат будет точно таким же, как и в первом случае!

   Первым аргументом служит строка форматов, а вторым, если они есть, - выводимые объекты. Строка форматов может включать обычные символы, которые начинаются со знака %, за ним следует символ преобразования. Каждая спецификация преобразования соответствует одному из аргументов, которые следуют за форматной строкой. Буква d в спецификации преобразования указывает, что значение аргумента должно быть напечатано как десятичное целое число. Из других символов отметим : c - для вывода отдельного символа; s - для печати символьной строки; x и o - для вывода шестнадцатеричных и восьмеричных чисел соответственно; f - для вывода чисел с плавающей точкой. В следующем примере

                 printf(" %c = %d \n",g,g);

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

                 printf(" %c = %5d \n",g,g);

Наша первая программа вводит два числа, вычисляет их сумму и печатает результат с поясняющим текстом "Cумма".

      

#include

{
   int a,b,c;
   a=5; b=7;
   c=a+b;
   printf("Cумма = %d \n",c)
}

      Строка int a,b,c; объявляет a,b,c переменными целого типа. Все используемые в программе переменные должны быть объявлены. Далее идут операторы присваивания к a значение 5, а к b - 7, с -   значение их суммы. Значения переменных типа int лежат в диапазоне [-32768; 32767]. Функция printf выводит на экран: ^ СУММА = 12.

     Рассмотрим теперь функцию scanf предназначенную для форматного ввода данных. Функция scanf в качестве фактических параметров использует адреса переменных, а не их значения. Для этого перед соответствующим параметром ставят знак & - символ взятия адреса. Например, &XL означает     "адрес переменной XL", а не значение, которое переменная имеет в данный момент.

  Строка форматов функции scanf  указывает, какие данные ожидаются на входе. Если функция встречает в форматной строке знак % , за которым следует символ преобразования, то она будет пропускать на входе символы до тех пор, пока не встретит какой-нибудь не пустой символ.

  Предыдущая программа страдает одним недостатком: программа вычисления суммы годится только для одного конкретного случая, когда a=5, b=7. Улучшим ее, заменив соответствующие операторы присваивания вызовом функции scanf:           

/* Ввод двух чисел, вычисление суммы и печать результата*/

#include

{
   int a,b,c;
   scanf(" %d %d",&a,&b);
   c=a+b;
   printf("Cумма = %d \n",c)
}

        Форматная строка предписывает функции scanf  ввести десятичное число, которое надо поместить в переменную a, затем через пробел ввести второе десятичное число, которое надо присвоить переменной b. Обратите внимание,  что программа начинается со строки комментарием : /* .. */ , транслятор пропускает любые символы между /* и */  и их можно использовать для пояснений.


^ Варианты задач.

Вычислить значение функции при заданных значениях параметров. Значения параметров задаются пользователем с клавиатуры.

1. 11.

2. 7 12.

3. 13.

4. 14.

5. 15.

6. 16.

7. 17.

8. 18.

9. 19.

10. 20.


^ Лабораторная работа № 2
Тема: Программы разветвляющихся структур.
Цель работы - овладение практическими навыками разработки и программирования вычислительного процесса разветвляющейся структур. ^ Задания для самостоятельной подготовки
1. Изучить возможности языка программирования для реализации:

─ условной и безусловной передачи управления;

─ вычислительного процесса разветвляющейся структуры
^ 2. Разработать алгоритм решения в соответствии с заданием. 3. Составить программу решения задачи.
Рассмотрим организацию ввода- вывода и реализацию основных управляющих структур. Любой конкретный алгоритм может быть записан на языке программирования, использующем только три управляющий структуры: последовательное выполнение, ветвление и повторение. 

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

   Ветвление в простейшем случае описывается в языке Си с помощью условного оператора. имеющего вид:

    if ( выражение )
        оператор_1;
    else
        оператор_2;   

где часть else может и отсутствовать. Сначала вычисляется "выражение" в скобках; если оно истинно то выполняется оператор_1. Если "выражение" ложно (равно нулю - NULL), то оператор_1 пропускается, а выполняется оператор_2. Если на месте условно выполняемых операторов должна располагаться группа из нескольких операторов языка, то они заключаются в фигурные скобки - { }. Часто "выражение" в скобках представляет условие, заданное с помощью операций отношений и логических операций. Операции отношения обозначаются в Си следующим образом:

            = = равно; ! =   не равно; <  меньше; >  больше;
            < = меньше или равно; > = больше или равно.

  Символ ! в языке Си обозначает логическое отрицание. Есть еще две логические операции: || означает или, а && - логическое И. Операции отношения имеют приоритет ниже арифметических операций, так что выражение вида   k > n%i вычисляется как k > (n%i). Приоритет && выше, чем у ||, но обе логические операции выполняются после операций отношения и арифметических. В сомнительных случаях лучше расставлять скобки.

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

             Пример.

#include <stdio.h>
main()                                                    /* главная функция*/
{
  int x, y, z, max ;                                   /* описание переменных*/
printf(" Введите три числа :\n "); 
scanf(" %d %d %d ", &x, &y, &z);  /*ввод трех чисел*/
if( x > y)                                                 /*операции сравнивания*/
     max=x;
else                
  max=y;
if ( z>max)
  max=z;
printf(" Максимальное из (%d, %d, %d)= %d \n",x, y, z, max);
  }

   Рассмотрим пример программы, в которой применяются несколько вложенных друг в друга условных операторов. В этой программе строка            float A, B, X объявляет эти три переменные как величины вещественного типа. Форматная строка функции scanf предписывает ввести два вещественные числа, которые станут значениями переменных A и B соответственно.

          Пример 1.4

/*РЕШЕНИЕ УРАВНЕНИЯ AX=B*/
#include <stdio.h>
main()
{  

   float A,B,X;
   printf("ВВЕДИ А, В\n");
   scanf("%f %f",&A, &B);
   if(A!=0)
       printf("РЕШЕНИЕ:%f\n", B/A);
   else
   if(B==0)
     printf("X-ЛЮБОЕ ЧИСЛО\n");
   else
     printf("РЕШЕНИЙ НЕТ\n");
}

  Посмотрите, как выглядит ветвление, когда глубина вложенности условных операторов равна трем (пример 1.5). Если хоть одно условие истинно, то все оставшиеся, разумеется, пропускаются. При глубине вложенности условных операторов свыше трех ветвление теряет наглядность и понятность.   
     Для реализации многозадачного ветвления обычно прибегают к управляющей структуре выбор (переключатель) (см. п.9.4). Когда управляющая структура ветвления становится особенно запутанной, определенную ясность могут внести фигурные скобки. Они обязательны, когда в условном операторе содержится более одного оператора или функции, например   

if(a_0)
   {
    printf("...");
    scanf("...")
    другие операторы ...
   }

        Пример 1.5   

/* Программа определяет поведение ракеты,
    стартующей на экваторе, в зависимости
    от ее начальной скорости*/
#include <stdio.h>
main()
  {
   float V;
   printf("ВВЕДИ V\n");
   scanf("%f",&V);
   if(V<7.9)
     printf("РАКЕТА УПАДЕТ НА ЗЕМЛЮ\n");
   if(V<11.2)
     printf("РАКЕТА СТАНЕТ СПУТНИКОМ ЗЕМЛИ\n ");
   if(V<16.4)
     printf("РАКЕТА СТАНЕТ СПУТНИКОМ СОЛНЦА\n");
   else
     printf("РАКЕТА ПОКИНЕТ СОЛНЕЧНУЮ СИСТЕМУ\n");
}

Варианты задач.

Вычислить значение функции при заданных значениях параметров. Значения параметров задаются пользователем с клавиатуры.

1.M=max {a,b,c} 11.

2. 12.

3. 13.

4. 14.

5. 15. U=min {x,y,z}

6. 16.

7. 17.

8. 18.

9. 19.

10. 20.


Лабораторная работа № 3

Тема: Программы циклической структуры.
^ Цель работы - овладение практическими навыками разработки и программирования вычислительного процесса циклической структуры. Задания для самостоятельной подготовки
1. Изучить:

─ организацию алгоритмов циклической структуры с заданным числом повторений;

─ возможности языка программирования для построения таких циклов;
^ 2. Разработать алгоритм решения в соответствии с заданием. 3. Составить программу решения задачи.

В языке Си основной структурой, управляющей повторением, служит цикл с предусловием while (пока). Он имеет следующий формат

                              while (условие) оператор;

Условие всегда заключено в скобки, оно может быть произвольным выражением. Оператор while повторяет выполнение оператора следующего условия, до тех пор, пока это условие истинно. Если это условие не истинно с самого начала или становится не истинным в процессе выполнения данного оператора, то управление передается оператору, следующему за оператором цикла. Если повторяемая часть оператора содержит более одного оператора, то повторяемая группа операторов должна быть заключена в фигурные скобки, например:           

while(условие)
{
   оператор_1;
   оператор_2;
   ....
    оператор
}

      Для описания условий в операторе while используются операции условия такие же, как и в операторе if . Приведенная ниже программа подсчитывает сумму цифр введенного числа N. Цикл while последовательно выделяет и суммирует цифру исходного числа, начиная с последней; для выделения применяется операция взятия остатка от деления - %. При делении целых чисел любая дробная часть отбрасывается, поэтому после операции N=N/10; исходное число уменьшается в 10 раз при каждом "обороте" цикла, пока, наконец, не станет равным нулю, после чего цикл завершается и на экран дисплея выдается значение переменной S, в котором содержится сумма цифр числа N.

         Пример 1.6

#include
main()
  {
    int N,S,Z;
    S=0;
    printf("ВВЕДИ N\n");
    scanf("%d",&N)
    while(N!=0)
{
   Z=N%10
          N=N/10
          S=S+Z;
}
    printf("СУММА ЦИФР=%d\n",S);
  }

            Рассмотрим еще один пример. Здесь приведена программа, которая реализует алгоритм разложения числа на простые множители. Для сокращения времени счета отдельно рассматривается случай множителя, равного двум, чтобы в последующем рассматривать только нечетные множители.   

              Пример 1.7

/^ *РАЗЛОЖИТЬ ЧИСЛО НА МНОЖИТЕЛИ */
   #include
   main()
{
int M,i=3;
printf("ВВЕДИ M\n");
       scanf("%d",&M);
       printf("%d=1",M);
       while(M%2==0)
{
printf("*%d",2);
  M=M/2;
} 
       while(i <=M)
{
if(M%i==0)
{
printf("*%d",i);
M=M/i;
}
              else
    i=i+2
}
}

       Иногда структуры со вложенными друг в друга операторами повторения называются циклами. Следующая программа простая, хотя и содержит вложенные циклы. Она выводит на экран заполненный символом * треугольник, высота которого равна N.
    Во внешнем цикле устанавливается очередная строка вывода (параметр i ), а во внутреннем (параметр j ) в очередную строку вводится ровно i символов " * "   Вызов функции printf("\n")   обеспечивает в нужный момент переход на новую строку. Обратите внимание, что для вывода одного символа в форматной строке функции printf используется спецификация %c.

       Пример 1.8

#include
main()
{
int i,j,N;
printf("ВВЕДИ N \n");
scanf("%d",&N);
i=1;
while(i <=N)
{
j=1;
        while(j <=i)
{
printf("%c",'*');
j=j+1;
}
       i=i+1;
       printf("\n");
}
}

         Рассмотрим еще один пример, в котором используется сложный цикл. Программа позволяет найти в заданном интервале все совершенные числа. Напомним, что натуральное число называется совершенным, если оно равно сумме всех своих делителей, считая его самого. Известно, что все совершенные числа - четные и что первое совершенное число из натурального ряда чисел равно 6. Этим объясняется начальное значение параметра внешнего цикла. Так  как все натуральные числа имеют своим делителем единицу, полагаем начальное значение суммы делителей числа S=1. Во внутреннем цикле организуется перебор всех множителей текущего значения N. Из теории чисел известно, что такому испытанию имеет подвергать числа от 2 до N/2, либо даже до   корень из N. Это очень несовершенный алгоритм и если вы захотите его выполнить на ЭВМ, имейте ввиду, что программа работает слишком долго. Более эффективно алгоритм будет реализован попозже.

             Пример 1.9

#include
main()
{
int j,N,M,S;
printf("ВВЕДИ M\n");
scanf("%d",&M);
N=4;
while(N<=M)
{ S=1;j=2;
   while(j<=N/2)
       {
if(N%j==0) S=S+j;
j=j+1;
}
       if(N==S)
         printf("%d- СОВЕРШЕННОЕ ЧИСЛО\n",N);
         N=N+2;
}
}


^ Варианты задач

Вычислить значение функции при заданных значениях параметров. Значения параметров задаются пользователем с клавиатуры.

z=2n, n

p= n!; n





M=a(a+1)…(a+n-1);





























20.


Лабораторная работа №4

Тема: Алгоритмы сортировки и поиска


Постановка задачи.

Выполнить сортировку целочисленного массива (поиск в массиве) из n элементов. Алгоритм сортировки (поиска) оформить в виде функции. Варианты заданий приведены в табл. 3.

Таблица 3

Варианты заданий

№.

Метод сортировки (поиска)

1

Сортировка простой (линейной) вставкой

2

Бинарный поиск

3

Сортировка слиянием (метод фон Неймана)

4

Сортировка методом бинарной вставки без использования рабочего массива

5

Сортировка Шелла (слияние с обменом)

6

Быстрая сортировка (метод Хоара)

7

Комбинированный метод быстрой сортировки с методом «пузырька»

8

Внешняя двухфазная сортировка прямым слиянием

9

Челночная сортировка (сортировка с просеиванием)

10

Интерполяционный поиск

11

Сортировка методом центрированной вставки (нахождение медианы)

12

Шейкер – сортировка

13

Сортировка методом бинарной вставки с использованием рабочего массива

14

Обменная сортировка

15

Внешняя однофазная сортировка прямым слиянием

16

Внешняя сортировка естественным слиянием

17

Сортировка Шелла (слияние с обменом)

18

Внешняя сортировка сбалансированным слиянием

19

Сортировка простой (линейной) вставкой

20

Бинарный поиск


^ Методические указания

Алгоритмы сортировки и поиска приведены ниже. В приведенных алгоритмах массивы упорядочиваются по возрастанию. Пример программы, выполняющей сортировку массива методом «пузырька», приведен на рис.2.

^ Обменная сортировка.

Последовательно сравнивается элемент а0 с каждым последующим ai и, если ai< а0, то эти два элемента меняются местами; таким образом наименьший элемент оказывается на своем месте в начале массива. Затем этот метод применяется к элементу а1 и т. д.

^ Шейкер – сортировка.

В этом методе проходы массива выполняются поочередно: слева направо, а потом справа налево. Последовательно сравниваются пары соседних элементов (а0 и а1, а1 иа2, и т.д.) и, если надо, переставляются. Запоминается индекс последнего переставляемого элемента (right). Далее массив просматривается справа налево, начиная с индекса right. В этом проходе массива также выполняются сравнения соседних элементов и их перестановка. Запоминается индекс последнего переставляемого элемента (left). Далее опять выполняется проход слева направо от индекса left до индекса right и т.д.

Сортировка Шелла.

Выбирается интервал d между сравниваемыми элементами, и выполняется сортировка массива методом «пузырька», но с шагом d. После этапа сортировки массива с выбранным интервалом, этот интервал уменьшается и опять выполняется сортировка массива методом «пузырька». Рекомендуется следующая последовательность значений d: 1, 3, 7, 15, 31, … ,т.е.

dk=(dk-1-1)/2

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

^ Челночная сортировка.

Последовательно сравниваются пары соседних элементов а0 и а1, а1 и а2, и т.д. и если аi>ai+1, то элемент ai+1 продвигается влево насколько это возможно: он сравнивается со своим предшественником и, если он меньше предшественника, то выполняется обмен и начинается очередное сравнение. Когда передвигаемый влево элемент встречает меньшего предшественника, то процесс передвижения влево прекращается и возобновляется просмотр массива слева направо с той позиции, с которой выполнялся обмен при продвижении слева направо.

^ Быстрая сортировка (метод Хоара).

Идея метода заключается в том, что вначале переставляются элементы, которые находятся друг от друга на больших расстояниях. Выбирается элемент массива (например, центральный), который разбивает массив на два подмножества. Пусть значение этого элемента х. Элементы массива переставляются таким образом, чтобы слева от x находились элементы аi<=x, а справа aj>=x. После перестановок элемент x будет находиться на своем месте. Далее этот алгоритм разделения массива на левую и правую части применяется к левой, а затем к правой частям, затем к частям частей и так до тех пор, пока каждая из частей не будет состоять из единственного элемента. Таким образом, в этой сортировке используется рекурсия. Алгоритм разделения элементов массива начиная с элемента с индексом left до элемента с индексом right относительно «центрального» элемента x: вводятся два индекса i и j, i=left; j=right. Элементы просматриваются слева направо до тех пор, пока не обнаружится элемент ai>=x, затем массив просматривается справа налево, пока не обнаружится элемент aj<=x. После этого элементы меняются местами. Далее процесс просмотра и перестановки повторяется до тех пор, пока не станет i>j.

^ Комбинированный метод быстрой сортировки с методом «пузырька».

В этом методе рекурсивный алгоритм разделения массива быстрой сортировки применяется только для подпоследовательностей массива, длина которых не менее определенного размера m (m<=n). Для сортировки коротких подпоследовательностей используется метод «пузырька».

Линейная вставка

Элементы массива делятся на уже упорядоченную последовательность а0, а1, …, аi-1 и неупорядоченную аi, ai+1, …,an-1. В каждом проходе из неупорядоченной последовательности извлекается элемент аi (в первом проходе i=1) и вставляется в упорядоченную последовательность из i элементов без нарушения упорядоченности в ней. Этот алгоритм повторяется для i=2,3,…,n-1. Алгоритм вставки аiв упорядоченную последовательность из i элементов заключается в продвижении вставляемого элемента в начало последовательности, сравнивая его с аi-1, ai-2 и т.д. Продвижение заканчивается на элементе аj<=aiили при прохождении всей последовательности.

^ Бинарная вставка.

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

^ Центрированная вставка.

Алгоритм использует дополнительный рабочий массив. В позицию, расположенную в центре рабочего массива помещается элемент а0. Он будет медианой. Слева от медианы надо расположить все элемент, меньшие медианы, а справа – большие или равные. Из сортируемого массива последовательно выбирается элемент, сравнивается с медианой и вставляется без нарушения упорядоченности в левую или правую части массива. Если область памяти, выделенная для одной из частей, будет исчерпана, то все элементы рабочего массива сдвигаются в противоположном направлении и значение медианы изменяется. В конце алгоритма упорядоченные элементы должны быть скопированы в исходный массив.

^ Метод фон Неймана.

Упорядочить пары соседних элементов массива а (а0 и а1, а2 и а3 и т.д.) и перенести их во вспомогательный массив b. Затем взять по две соседние пары из b и, слив их в упорядоченные четверки, снова записать в а; затем каждые две четверки из b слить в упорядоченные восьмерки и переписать в а и т.д. Упорядоченный массив должен оказаться в массиве а.

^ Внешняя двухфазная сортировка прямым слиянием.

Внешняя сортировка используется для сортировки файлов, размеры которых не позволяют записать их во временные массивы в оперативной памяти. Для сортировки используются три файла: c (исходный файл), a и b (вспомогательные файлы). Элементы исходного файла с попеременно записываются то в а, то в файл b (фаза разделения). Таким образом, в каждом файле создаются одноэлементные последовательности. Далее формируются двухэлементные упорядоченные последовательности, в которых один элемент берется из а, а другой из b (фаза слияния). Эти двухэлементные последовательности записываются в файл с. Далее двухэлементные последовательности попеременно записываются то в а, то в файл b (фаза разделения). Затем двухэлементные последовательности из файлов a и b сливаются в упорядоченные четверки и записываются в файл с (фаза слияния). Алгоритм разбиения файла с пополам и формирование упорядоченных последовательностей путем слияния пар последовательностей из файлов a и b повторяется до тех пор, пока в файлах a и b не образуется по одной упорядоченной последовательности, которые окончательно сливаются в отсортированный файл с.

В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.

^ Внешняя однофазная сортировка прямым слиянием.

Для сортировки используются четыре файла: c (исходный файл), a, b и d (вспомогательные файлы). При первом проходе элементы исходного файла с попеременно записываются то в а, то в файл b. Далее формируются двухэлементные упорядоченные последовательности, в которых один элемент берется из а, а другой из b. Эти двухэлементные последовательности попеременно записываются в файлы с и d. Затем сливаются пары двухэлементных последовательностей из файлов c и d в упорядоченные четверки, которые записываются попеременно в файлы a и b и т.д. В конце алгоритма единая упорядоченная последовательность должна оказаться в файле с.

В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.

^ Внешняя сортировка естественным слиянием.

Сортировка, при которой сливаются две самые длинные из возможных упорядоченных последовательностей, называется естественным слиянием. В алгоритме используется исходный файл с и два вспомогательных файла a и b. В алгоритме при первом проходе определяются как можно более длинные упорядоченные последовательности файла с. Далее эти последовательности попеременно записываются в файлы a и b. На каждом следующем проходе пары i-х упорядоченных последовательностей файлов a и b (i=1,2,3,…) сливаются в более длинные упорядоченные последовательности и переносятся в файл с, после чего наступает фаза разделения: последовательности попеременно записываются в файлы a. В конце алгоритма единая упорядоченная последовательность должна оказаться в файле с.

В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.

^ Внешняя сортировка сбалансированным слиянием.

В алгоритме используется исходный файл с и три вспомогательных файла a, b, d. В данном алгоритме при первом проходе определяются как можно более длинные упорядоченные участки файла с. Далее эти участки попеременно записываются в файлы a и b. На следующем этапе пары i-х упорядоченных последовательностей файлов a и b (i=1,2,3,…) сливаются в более длинные упорядоченные последовательности и попеременно переносятся в файлы с и d. Затем сливаются пары последовательностей файлов с и d и попеременно переносятся в файлы a и b и т.д. В конце алгоритма единая упорядоченная последовательность должна оказаться в файле с.

В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.

^ Бинарный поиск.

Алгоритм применяется к упорядоченному массиву, в котором надо найти номер элемента с заданным значением x. Сначала х сравнивается со средним элементом массива. Если совпадение найдено, то возвращается индекс среднего элемента, иначе определяется, в какой половине массива следует выполнять поиск, применяя к ней алгоритм бинарного поиска.

^ Интерполяционный поиск.

Алгоритм применяется к упорядоченному массиву, в котором надо найти номер элемента с заданным значением x. Если известно, что х находится между элементами alи ar, то номер очередного элемента для сравнения вычисляется по формуле

m=l+(r-l)*(x-al)/(ar-al)

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


#include

#include

void sort(int a[], int n)

{

int i,j;

int c;

for(j=1;j<=n-1;j++)

for(i=0;i
if(a[i]>a[i+1])

{c=a[i];a[i]=a[i+1];a[i+1]=c;}

}

void main(void)

{

int a[10];

int n;

int i;

cout<<"n? ";

cin>>n;

cout<<"a?";

for(i=0;i
cin>>a[i];

sort(a,n); //вызов функции сортировки

cout<<"a: ";

for(i=0;i
cout<
getch();

}

Рис. 2. Сортировка массива методом «пузырька»


Пример решения (вариант 13).
Задание: Выполнить сортировку целочисленного массива (поиск в массиве) из n элементов. Алгоритм сортировки (поиска) оформить в виде функции. Метод: Сортировка методом бинарной вставки.

^ Текст программы:


//Сортировка массива методом бинарной вставки


/*В программе первый элемент рассматривается как упорядоченный массив.

Далее из оставшейся части массива последовательно берутся элементы

И вставляются без нарушения упорядоченности в уже отсортированную часть

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

Используется метод бинарного поиска*/


#pragma hdrstop

#pragma argsused

#include

#include

#include

#include


//Функция сортировки массива методом бинарной вставки

void sort(int a[], int n)

{

//Объявление переменных

int newElement, left, right, middle, i, j;

for (i=1;i
{

//Обрабатываемый на данном этапе элемент

newElement=a[i];

//Границы отсортированной части массива

left=0; right=i-1;

while (left<=right)

{

//Средний элемент в отсортированной части

middle=(left+right)/2;

//Анализ отношения обрабатываемого и среднего элемента

if (a[middle]<=newElement)

left=middle+1;

else

right=middle-1;

}

//Сдвиг элементов вправо и вставка обрабатываемого элемента

//на новое место

for (j=i;j>right+1;j--) a[j]=a[j-1];

a[right+1]=newElement;

}

}


//Основная программа

void main(void)

{

//Объявление переменных

int a[100],n,i;

//Ввод числа элементов массива

cout<<"Number of elements (from 1 to 100) >"; cin>>n;

cout<
//Заполнение массива и вывод его на экран

randomize();

for (i=0;i
{

a[i]=rand()%100;

cout<
}

cout<
//Вызов функции сортировки массива

sort(a,n);

//Вывод отсортированного массива на экран

for (i=0;i
cout<
//Задержка

getch();

}


^ Тестовый пример:


Number of elements (from 1 to 100) >100


26 16 32 25 32 39 5 77 82 67 12 91 68 91 76 87 8 17 60 32 43 89 30 57 52 49 38 17 19 97 85 50 63 45 7 64 24 5 34 90 18 75 88 85 89 95 76 19 49 47 37 26 41 49 31 86 57 17 55 0 66 7 28 57 36 45 99 18 63 89 46 33 10 85 15 11 31 87 65 11 45 32 2 23 77 11 89 5 80 47 10 21 69 4 97 28 73 53 51 52


0 2 4 5 5 5 7 7 8 10 10 11 11 11 12 15 16 17 17 17 18 18 19 19 21 23 24 25 26 26 28 28 30 31 31 32 32 32 32 33 34 36 37 38 39 41 43 45 45 45 46 47 47 49 49 49 50 51 52 52 53 55 57 57 57 60 63 63 64 65 66 67 68 69 73 75 76 76 77 77 80 82 85 85 85 86 87 87 88 89 89 89 89 90 91 91 95 97 97 99


^ Лабораторная работа №5

Тема: Упорядочивание элементов массива.


Постановка задачи.

Разработать программу, которая вводит целочисленную матрицу из n строк и m столбцов (1
Таблица 2.

Варианты заданий

№

Правило упорядочивания элементов матрицы

1

Упорядочить каждую строку по возрастанию элементов

2

Упорядочить строки по возрастанию последних элементов строк

3

Переместить в каждой строке все отрицательные элементы в начало строки, а неотрицательные – в конец

4

Разместить все положительные элементы в верхнюю левую область матрицы (заполняя ими матрицу по строкам слева направо), а неположительные – в нижнюю правую область

5

Разместить все максимальные элементы в верхнюю левую область матрицы (заполняя ими матицу построчно), а остальные – в нижнюю правую область

6

Упорядочить столбцы по убыванию первых элементов столбцов

7

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

8

Упорядочить каждую строку по убыванию элементов

9

Разместить все минимальные элементы в нижнюю правую область матрицы (заполняя ими матицу построчно), а остальные – в верхнюю левую область

10

Упорядочить каждый столбец по возрастанию элементов

11

Упорядочить столбцы по возрастанию последних элементов столбцов

12

Переместить в каждом столбце все отрицательные элементы в начало столбца, а неотрицательные – в конец

13

Разместить все положительные элементы в левую верхнюю область матрицы (заполняя ими