9 Июнь 2008

Вопрос 5. Алгоритм сортировки массивов «пузырек».

написано в рубрике: Алгоритмизация (Т) — Метки: , , , — Михаил @ 19:13

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

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

Алгоритм:

Слева направо поочередно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два соседних элемента и так далее до конца массива.

После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент («всплыл» первый «пузырек»). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1-го элемента. И так далее. Всего требуется n-1 проход.

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

Program BubbleSort;

Uses Crt;

Const

N=20; {длина массива}

Type

TVector = array [1..n] of Real;

Var

Vector:TVector;

B : Real;

I, k : integer;

Begin

ClrScr;

Writeln (‘Введите элементы массива’);

For I: = 1 to n do Read (Vector[i]); Readln;

{——————————————————}

For k: =n downto 2 do

{“Всплывание”очередного максимального элемента}

{на k-ую позицию}

For I: = 1 to k-1 do

If Vector [i]>Vector [i+1] then

Begin

B: =Vector[i];

Vector[i]: =Vector [i+1];

Vector [i+1]:=B

End;

{——————————————————}

Writeln (‘Отсортированный массив’);

For i: = 1 to n do Write (Vector[i]:8:2);

Writeln;

End.

Сравнение прямых методов сортировки.

Теоретические и практические исследования алгоритмов прямых методов сортировки показали, что как по числу сравнений, так и по числу присваиваний они имеют квадратичную зависимость от длины массива n. Исключение составляет метод выбора, который имеет число присваиваний порядка n*ln(n). Это свойство алгоритма выбора полезно использовать в задачах сортировки в сложных структурах данных, когда на одно сравнение выполняется большое число присваиваний. В таких задачах метод выбора успешно конкурирует с самыми быстрыми улучшенными методами сортировки.

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

Вопрос 4. Понятие рекурсии. Простейшие рекурсивные задачи.

написано в рубрике: Алгоритмизация (Т) — Метки: , , — Михаил @ 19:12

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

Пример вычисления факториала. Подпрограмма получает от компанента edInput целое число N и выводит в компонент mmOutput значение N!, которое вычисляется с помощь рекурсивной функции Faktorial.

Procedure TfmExample.bbRunClick (Sender: TObject);

Function Factorial (N: Word): Extended;

Begin

If N = 0 then

Result :=1

Else

Result:= N * Factorial (N-1)

End;

Var

N: Integer;

Begin

Try

N:= StrToInt (Trim(edInput.Text));

Except

Exit;

End;

mmOutput.Lines.Add(edInput.Text+

‘!=’+FLoatToStr(Factorial(N)));

edInput.Text:=’ ‘;

edInput.SetFocus

end;

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

Procedure A (i: Byte);

Begin

B (i);

End;

Procedure B (j : Byte);

Begin

A (j);

End;

Вопрос 3. Оформление функций на языке Паскаль.

написано в рубрике: Алгоритмизация (Т) — Метки: , , , — Михаил @ 19:10

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

Описание подпрограммы состоит из заголовка и тела подпрограммы. Заголовок процедуры имеет вид: procedure <имя> [(<СП.ф.п.>)] : <тип>; . Здесь: <имя> - имя подпрограммы (правильный идентификатор), <СП.ф.п.>- список формальных параметров, <тип> - тип возвращаемого функции результата. Сразу за заголовком подпрограммы может следовать одна из стандартных директив assembler, external, far, forward, inline, interrupt, near. Эти директивы уточняют действие компилятора и распространяются на всю подпрограмму и только на нее, т.е. если за подпрограммой следует другая подпрограмма, стандартная директива, указанная за заголовком первой, не распространяется на вторую.

Assemblerотменяет стандартную последовательность машинных инструкций, вырабатываемых при входе в процедуру и выходом из нее.

ExternalС помощью этой директивой объявляется внешняя подпрограмма.

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

Near- заставит компилятор создать код, рассчитанный на ближайшую модель памяти.

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

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

Interruptиспользуется при создание процедур обработки прерываний.

Параметры.

Список формальных параметров необязателен и может отсутствовать. Если же он есть, то в нем должны быть перечислены имена формальных параметров и их типы, например: Procedure SB (a: Real; b: Integer; c: Char); Для оператора тела подпрограммы список параметров является своеобразным расширением раздела описаний: все переменные из этого списка могут использоваться в любых выражениях внутри подпрограммы. Таким способом осуществляется настройка алгоритма подпрограммы на конкретную задачу.

Вопрос 2. Оформление процедур на языке Паскаль.

написано в рубрике: Алгоритмизация (Т) — Метки: , , , — Михаил @ 19:09

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

Описание подпрограммы состоит из заголовка и тела подпрограммы. Заголовок процедуры имеет вид: procedure <имя> [(<СП.ф.п.>)]; . Здесь: <имя> - имя подпрограммы (правильный идентификатор), <СП.ф.п.> - список формальных параметров. Сразу за заголовком подпрограммы может следовать одна из стандартных директив assembler, external, far, forward, inline, interrupt, near. Эти директивы уточняют действие компилятора и распространяются на всю подпрограмму и только на нее, т.е. если за подпрограммой следует другая подпрограмма, стандартная директива, указанная за заголовком первой, не распространяется на вторую.

Assemblerотменяет стандартную последовательность машинных инструкций, вырабатываемых при входе в процедуру и выходом из нее.

ExternalС помощью этой директивой объявляется внешняя подпрограмма.

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

Near- заставит компилятор создать код, рассчитанный на ближайшую модель памяти.

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

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

Interruptиспользуется при создание процедур обработки прерываний.

Параметры.

Список формальных параметров необязателен и может отсутствовать. Если же он есть, то в нем должны быть перечислены имена формальных параметров и их типы, например: Procedure SB (a: Real; b: Integer; c: Char); Для оператора тела подпрограммы список параметров является своеобразным расширением раздела описаний: все переменные из этого списка могут использоваться в любых выражениях внутри подпрограммы. Таким способом осуществляется настройка алгоритма подпрограммы на конкретную задачу.

Вопрос 1. Динамическая память. Указатели.

Динамическая память.

Динамическая память - это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (64 Кбайт), стека (обычно 16 Кбайт) и собственно тела программы. Размер динамической памяти можно варьировать в широких пределах. По умолчанию этот размер определяется всей доступней памятью ПК и, как правило, составляет не менее 200…300 Кбайт. Динамическая память - это фактически единственная возможность обработки массивов данных большой размерности.

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

Указатели.

Оперативная память ПК представляет собой совокупность ячеек для хранения информации – байтов, каждый из которых имеет собственный номер. Эти номера называются адресами, они позволяют обращаться к любому байту памяти. Указатель – это переменная которая в качестве своего значения содержит адрес байта памяти. Как правило, указатель связывается с некоторым типом данных. Такие указатели называются типизированными. Для объявления типизированного указателя используется значок ^, который помещается перед соответствующим типом: (пример) p1: ^Integer; p2: ^Real;.

Выделение и освобождение динамической памяти.

Вся динамическая память в Турбо Паскале рассматривается как сплошной массив байтов, который называется кучей. Физически куча располагается в старших адресах сразу за областью памяти, которую занимает тело программы. Начало кучи хранится в стандартной переменной HEAPORG, конец - в временной HEAPEND. Текущую границу незанятой динамической памяти указывает указатель HEAPPTR. Память под любую динамически размещаемую переменную выделяется процедурой NEW. Параметром обращения к этой процедуре является типизированный указатель. В результате обращения указатель приобретает значение, соответствующее динамическому адресу, начиная с которого можно разместить данные.

< 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

© Проект «Студенты-Программеры»., 2008. Все права защищены.
Перепечатка материалов только при наличии активной ссылки на источник.
Powered by WordPress