СКАЧАТЬ:  k.zip [114,1 Kb] (cкачиваний: 21)

КУРСОВАЯ РАБОТА

ПО ДИСЦИПЛИНЕ «ИНФОРМАТИКА»

РАЗДЕЛ: АЛГОРИТМИЧЕСКИЙ ЯЗЫК PASCAL

НА ТЕМУ: №16

РАЗРАБОТКА В СРЕДЕ TURBO PASCAL ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ СОРТИРОВКУ МАССИВА РАЗНЫМИ МЕТОДАМИ

Оглавление

Оглавление. 2

Введение. 3

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

Описание основных операторов и используемых модулей. 6

Контрольная задача. 15

Задача 6. 19

Задача 18. 22

Задача 30. 25

Приложение. 26

Список литературы.. 28

Введение

Развитие современной техники идёт по пути все большего усложнения конструкции вновь создаваемых изделий. При их создании используются все более сложные технологии и технологические процессы. Процесс проектирования новых изделий требует привлечения и использования новых нестандартных решений.

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

Язык Pascal считается одним из самых популярных и удобных. Он был создан профессором Виртом, директором Института информатики Швейцарской высшей политехнической школы, и был назван в честь великого французского математика и философа Блеза Паскаля – первого в мире создателя счетно-решающей машины.

По словам автора языка «… разработка языка Паскаль базировалась на двух принципиальных концепциях. Первая состояла в том, чтобы изобрести язык, приспособленный к обучению программированию как систематической дисциплине, базирующейся на некоторых фундаментальных положениях, ясно и естественно отраженных в языке. Вторая предполагала разработку конкретных представлений этого языка, которые были бы надежны и эффективны на современных ЭВМ.» По мнению Вирта, «язык, на котором студент учится выражать свои идеи, существенно влияет на его способ мышления и изобретательность… беспорядок, сопутствующий существующим языкам, непосредственно влияет на стиль программирования студентов.» Сейчас с уверенностью можно говорить о том, что Вирт достиг поставленной перед собой цели.

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

Стройность и лаконичность, широкие возможности в области обработки структур данных обусловили популярность языка Pascal. Его реализация Borland Pascal 7.0 отражает все современные тенденции в области объектно-ориентированного программирования.

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

Алгоритм - это точное предписание исполнителю совершить определенную последовательность действий для достижения поставленной цели за конечное число шагов.

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

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

Разработка в среде Turbo Pascal программы, реализующей сортировку массива разными методами.

Задания:

1)          Изучить работу с массивами и элементами массивов. Решить контрольные задачи: №6, 18, 30.

2)          Проанализировать виды сортировки: выбор, обмен и простые вставки.

Решить контрольную задачу:

Задано натуральное число N и одномерный массив натуральных чисел A₁, A₂, A₃, … A_N, не имеющий одинаковых элементов. Упорядочить этот массив по возрастанию тремя видами сортировки: выбором, обменами и простыми вставками.

Задача 6

В массиве хранятся данные о рыбацких уловах за месяц. Найти:

–    среднемесячный улов;

–    максимальный и минимальный уловы;

–    количество уловов, совпадающих с максимальным;

–    количество дней, когда улов превышал среднемесячный.

Задача 18

Сдвинуть все отрицательные элементы в конец массива, сохраняя порядок их следования в исходном массиве.

Задача 30

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

Описание основных операторов и используемых модулей

     Правила языка Паскаль предусматривают единую для всех программ форму основной структуры:

Program <Имя программы>;
<Раздел описаний>
Begin
<Тело программы>
End. 

Здесь слова Program, Begin и End являются служебными. Правильное и уместное употребление этих слов является обязательным.

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

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

Раздел описаний может состоять из пяти подразделов:
     1. Описание меток (Label).
     2. Описание типов (Type).
     3. Описание констант (Const).
     4. Описание переменных (Var).
Алфавит языка Pascal

Алфавит языка Паскаль составляют:
     1) буквы латинского алфавита;
     2) арабские цифры;
     3) специальные знаки.

.         конец программы, разделение целой и дробной частей вещественного числа (десятичная точка), разделение полей в переменной типа Record;

,             разделение элементов списков;..    указание диапазона;

:             используется в составе оператора присваивания, а также для указания формата вывода в операторе Writeln;

;             отделяет один раздел программы от другого, разделяет операторы;

'             используется для ограничения строковых констант;

-+*/()     арифметические знаки (используются по своему назначению);

< >         знаки отношений;

=            используется в составе оператора присваивания, в разделах описаний констант и типов, используется как знак отношения (равно);

{ }          ограничение комментариев в программе;

[ ]           заключают в себе индексы элементов массивов;

_            символ подчеркивания используется также как любая буква, например, в идентификаторах - вместо пробела;

$            обозначение директивы компилятора, обозначение шестнадцатеричного числа.

Идентификаторы

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

–    идентификатор должен быть уникальным, то есть одним и тем же именем разные объекты не могут быть названы;

–    идентификатор имеет ограничение по длине (зависит от конкретной реализации языка на компьютере);

–    идентификатор может состоять только из символов латинского алфавита, цифр и знака подчеркивания ("_");

–    идентификатор не может начинаться с цифры.

Раздел описания констант

В этом разделе производится присваивание идентификаторам констант постоянных значений. Раздел начинается  зарезервированным словом const, за которым следует ряд выражений, отделяющихся друг от друга точкой с запятой.

Формат:

const <идентификатор> = <значение>;

После того как константа определена, ей нельзя присвоить какое-либо другое значение. Следует обратить внимание на то, что при определении констант применяется знак = (равенства), а не := (присваивание). 

Раздел описания переменных. Типы

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

К базовым типам относятся:

–    Integer – тип целых чисел;

–    Longint – тип "длинных" целых чисел;

–    Real – тип действительных (вещественных) чисел (то есть - с дробной частью);

–    Byte – тип неотрицательных целых чисел от 0 до 255;

–    Word – тип неотрицательных целых чисел от 0 до 65535;

–    Boolean – логический тип,

а также некоторые другие типы, как string и char.

Раздел описания переменных начинается зарезервированным словом var, за которым следует список переменных, двоеточие и тип данных. 

Формат:

   var < идентификатор 1, идентификатор 2,…>  :  <тип>;

Основные операторы и функции

Оператор присваивания

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

Формат:      <Имя переменной> := <Выражение>;

Функция random

Возвращает случайное число, удовлетворяющее условию 0<=x<=диапазон. Тип аргумента и результата – целочисленный. Если необходимы случайные числа из диапазона a<=x<b - используется выражение random(b-a)+a.

Если параметр диапазон не указан, то random возвращает число в диапазоне 0<=x<1. Тип  результата – вещественный. Если необходимы вещественные числа из диапазона a<=x<b, нужно задать его при помощи  random*b+a.

Перед первым обращением к функции random необходимо с помощью вызова процедуры Randomize инициализировать программный генератор случайных чисел, иначе при каждом запуске программы датчик будет выдавать одни и те же числа.

Процедура вывода Write.

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

Формат:

Write (а1, а2, а3, …,аn) ; Writeln;

Writeln (а1, а2, а3, …,аn) ;

где а1, а2, а3, …,аn – выражение типа integer, byte, real, char, boolean.

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

Write(y1:n:m, y2:n:m, …);

Writeln(y1:n:m, y2:n:m, …);

где y1, y2,… - выражение, переменная или константа;

 n – определяет общую ширину поля вывода;

 m – определяет место под дробную часть.

Если заданное n мало, при выводе ширина поля будет увеличена, если мало m – то производится округление.

Кроме того, в операторах вывода можно задавать количество пробелов. Для этого необходимо записать оператор вывода в виде:

Write (‘ ‘ : q);

где q — константа целого типа, указывающая число пробелов.

Составной оператор.

Составной оператор представляет собой группу из произвольного числа операторов, отделенных друг от друга точкой с запятой и ограниченную операторными скобками begin и end. 

Формат:

begin

Оператор1;

…

OпеpaтoрN;

end;

 Условный оператор if.

Условный оператор позволяет проверить некоторое условие и в зависимости от результата выполнить тот или иной оператор или группу операторов. С помощью условных операторов программируются алгоритмы разветвляющейся структуры. 

Формат:

if <условие> then < оператор1> else < оператор2>;

где if, then, else – зарезервированные слова (обозначают если, то, иначе соответственно);

<условие> - произвольное выражение логического типа;

<оператор1>, <оператор2> - любые операторы языка Паскаль.

Условный оператор работает по следующему алгоритму: вначале  вычисляется выражение <условие>. Если результат - true (истина), то выполняется <оператор1>, а <оператор2> пропускается. Если результат - false (ложь), наоборот <оператор1> пропускается, а выполняется <оператор2>.

Часть оператора, стоящая после служебного слова else, может отсутствовать. Тогда при значении true условного выражения выполняется <оператор1>, в противном случае этот оператор пропускается.

Формат:

if < условие > then < оператор>;

Один оператор if может входить в состав другого оператора if. В этом случае говорят о вложенности операторов.

Пример:

if  Условие1  then   if  Условие2  then  Оператор1  else  Оператор2;

Оператор цикла for 

Оператор повтора for часто называют оператором цикла с параметром, так как число повторений задается переменной, называемой параметром цикла, или управляющей переменной, которая на каждом шаге цикла автоматически изменяет свое значение ровно на единицу – поэтому ее и называют счетчиком.

Оператор повтора for применяется в случаях, когда число повторений заранее известно.

Оператор повтора for состоит из заголовка (строка, содержащая for…do ) и тела цикла.

Формат:      for < параметр цикла >:=А to B do < оператор >;

где for, do – зарезервированные слова (обозначают "для", "выполняй" соответственно);

А и В – выражения, определяющие соответственно начальное и конечное значение параметров цикла;

< оператор > - тело цикла.

Если требуется выполнить после do несколько операторов, они обрамляются операторными скобками begin и end, образуя тем самым составной оператор.

Цикл while 

В отличие от цикла for, в цикле while заранее неизвестно сколько раз проработает цикл. Вместо задания параметров счетчика, там задается условие, при котором цикл будет продолжать работать. Если условие будет равно false, то цикл прекратит свою работу.

Формат:

while <условие> do оператор;

В качестве оператора может выступать также и составной оператор.

Массив.

Массив - это упорядоченная последовательность величин, имеющих один и тот же тип и объединённых одним именем

Формат:

<имя> : array[n1..n2] of  <тип>;

Здесь величины n1 и n2 (индексы строки) являются целочисленными константами.

Пример описания двумерных массивов в разделе констант:

Const i=5; Var S: array[ 1..i,] of integer;

Линейная сортировка (сортировка отбором)

Это самый простой и самый очевидный метод сортировки массивов, а также наиболее прост в реализации.

Идея линейной сортировки по невозрастанию заключается в том, чтобы, после­довательно просматривая весь массив, отыскать наибольшее число и поместить его на первую позицию, обменяв его с элементом, который ранее занимал первую позицию. Затем просматриваются все остальные элементы массива и выполняется аналогичная операция по отбору из рассматриваемой части массива максимального элемента и обмену местами этого элемента и первого в рассматриваемой части и т.д.

Сортировка методом пузырька

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

Сортировка вставками

Сортировка вставками  — простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

–    прост в реализации;

–    эффективен на небольших наборах данных;

–    эффективен на наборах данных, которые уже частично отсортированы;

–    это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

–    может сортировать список по мере его получения;

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

Контрольная задача

Блок-схема

Программа

program k;

uses

  crt;

const

  N = 20;

var

  a, b : array[1..N] of byte;

  t : byte;

  i, j, it : integer;

begin

  ClrScr;

  randomize;

  writeln('Исходный массив: ');

  for i := 1 to N do

  begin

    a[i] := random(100);

    write( a[i]:3 );

  end;

  writeln;

  b := a;

  { Сортировка отбором }

  for i := 1 to N-1 do

    for j := i+1 to N do

    begin

      it := it + 1;

      if b[i] > b[j] then

      begin

        t := b[i];

        b[i] := b[j];

        b[j] := t;

      end;

    end;

  writeln('Отсортированный массив: ');

  for i := 1 to N do

  write( b[i]:3 );

  writeln;

  writeln('Итераций(просмотров массива): ');

  writeln('Сортировка отбором : ', it);

  b := a;

  { Сортировка обменом }

  it := 0;

  for i := 2 to N do

    for j := N downto i do

    begin

      it := it + 1;

      if b[j-1] > b[j] then

      begin

        t := b[j-1];

        b[j-1] := b[j];

        b[j] := t;

      end;

    end;

  writeln('Сортировка обменом : ', it);

  b := a;

  { Сортировка вставками }

  it := 0;

  for i := 2 to n do

  begin

   t := b[i];

   j := i-1;

   while (b[j] > t) and (j > 0) do

   begin

     b[j+1] := b[j];

     j:= j - 1;

     it := it + 1;

   end;

   b[j+1] := t;

  end;

  writeln('Сортировка вставками : ', it);

  readln;

end.

Задача 6

Блок-схема

Программа

program p6;

uses

  Crt;

var

  a : array[1..31] of byte;

  min, max, am, ma : byte;

  avg : real;

  i : integer;

begin

  ClrScr;

  Randomize;

  for i := 1 to 31 do

  begin

    a[i] := Random(10)+20;

    write(a[i]:3);

  end;

  writeln;

  min := a[1];

  for i := 1 to 31 do

  begin

    avg := avg + a[i];

    if a[i] > max then max := a[i];

    if a[i] < min then min := a[i];

  end;

  avg := avg / 31;

  for i := 1 to 31 do

  begin

    if a[i] = max then am := am + 1;

    if a[i] > avg then ma := ma + 1;

  end;

  writeln( 'Средний         : ', avg:4:2 );

  writeln( 'Минимальный     : ', min );

  writeln( 'Максимальный    : ', max );

  writeln( 'Максимальных    : ', am );

  writeln( 'Больше среднего : ', ma );

  readln;

end.

Задача 18

Блок-схема

Программа

program p18;

uses

  Crt;

const

  N = 20;

var

  a : array[1..N] of integer;

  i, j, t : integer;

begin

  ClrScr;

  Randomize;

  Writeln('Исходный массив');

  for i := 1 to N do

  begin

    a[i] := random(40)-20;

    write(a[i]:4);

  end;

  writeln;

  i := N;

  j := N;

  repeat

    if a[j] < 0 then

    begin

      t := a[i];

      a[i] := a[j];

      a[j] := t;

      i := i - 1;

    end

    else

      j := j - 1;

  until j < 1;

  Writeln('Преобразованный массив');

  for i := 1 to N do

    write(a[i]:4);

  readln;

end.

Задача 30

Блок-схема

Программа

program p30;

uses

  Crt;

var

  n, i: integer;

begin

  ClrScr;

  write('Введите число: ');

  readln(n);

  write('Делители: ');

  for i := n downto 1 do

    if n mod i = 0 then write(i, ' ');

  readln;

end.