Pascal/С

Рассмотрение особенностей встроенных и производных структур данных. Сравнительный анализ методов сортировки, алгоритмов поиска в программе Pascal/С. Характеристика структуры данных "строка", "линейные списки", "стек" и "очередь", "дерево", "таблица".

Рубрика Программирование, компьютеры и кибернетика
Вид лабораторная работа
Язык русский
Дата добавления 27.09.2017
Размер файла 604,2 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Назначение процедур и функций в модулях реализации СД типа «строка» в C

void InputStr(string1 s). Ввод строки s с клавиатуры.

void OutputStr(string1 s). Вывод строки s на экран монитора.

void InitStr(string1 *s, unsigned n). Выделение динамической памяти под строку st, содержащую от 0 до n символов. Значением n определяется максимальное количество символов, которое может вместить строка (зависит от кол-ва выделенной памяти). Динамическая длина строки есть ее текущая длина.

void WriteToStr(string1 st, char *s). Запись данных в строку st из строки s. Строка s заканчивается нулевым символом '\0'.

void WriteFromStr(char *s, string1 st). Запись данных в строку s из строки st. Строка s заканчивается нулевым символом '\0'.

int Comp(string1 s1, string1 s2). Сравнивает строки s1 и s2. Возвращает 0 если s1 = s2; 1, если s1 > s2; -1, если s1 < s2.

void Delete(string1 s, unsigned Index, unsigned Count). Удаляет Count символов из строки s, начиная с позиции Index.

void Insert(string1 Subs, string1 s, unsigned Index). Вставляет подстроку SubS в строку s, начиная с позиции Index.

void Concat(string1 s1, string1 s2, string1 srez). Выполняет конкатенацию строк s1 и s2. Результат помещает в srez.

void Copy(string1 s, unsigned Index, unsigned Count, string1 Subs). Записывает Count символов в строку Subs из строки s, начиная с позиции Index.

unsigned Length(string1 s). Возвращает текущую длину строки S.

unsigned Pos(string1 SubS, string1 s).Возвращает позицию, начиная с которой в строке s располагается подстрока SubS.

void DoneStr(string1 s). Удаляет строку s из динамической памяти.

Содержание отчета

1. Тема лабораторной работы.

2. Цель работы.

3. Характеристика СД «строка» (пункт 1 задания).

4. Индивидуальное задание.

5. Тексты модулей для реализации СД типа «строка», тексты программ для отладки модулей, тестовые данные, результаты работы программ.

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

Теоретические сведения

Строкой называется последовательность символов.

На абстрактном уровне строка представляет собой линейную структуру -- последовательность.

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

Vстр = K + 1, где K -- максимальное количество символов в строке.

Строка -- это динамическая структура. В процессе выполнения программы количество элементов может изменяться от нуля до K, но размер памяти, выделенный под строку, не меняется. Практически, строка представляет собой массив символов из K + 1 элементов типа char. Нумеруются элементы от нуля до K. В Pascal в нулевом элементе хранится символ с кодом, равным динамической длине строки, т.е. количеству элементов в строке в текущий момент времени. Если там находится символ с кодом 0, то строка не содержит ни одного символа и называется пустой. Элементы, начиная с первого содержат символы строки, количество которых совпадает с динамической длиной строки. В С во внутреннем представлении этот массив (строка) заканчивается нулевым символом '\0', по которому программа может найти конец, т.е. элемент с индексом K равен нулю как признак конца строки. Доступ к элементам строки, также как и к элементам массива -- прямой.

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

В языке Pascal:

Var s1: string;

Экземпляр СД типа строка (string) s1 располагается в статической памяти и занимает 256 байт, количество элементов строки может быть в пределах от 0 до 255.

Type T_str10 = string[10];

Var s2: T_str10;

Экземпляр СД типа строка (T_str10) s2 располагается в статической памяти и занимает 11 байт, количество элементов строки может быть в пределах от 0 до 10.

Type P_str = ^string;

Var ps3: P_str;

Строка будет располагаться в динамической памяти после обращения к процедуре new(ps3). Строка будет занимать в памяти 256 байт, адрес которой запишется в переменную ps3. Количество символов в строке может быть в пределах от 0 до 255.

Type T_str10 = string[10];

P_str10 = ^T_str10;

Var ps4: P_str10;

Строка будет располагаться в динамической памяти после обращения к процедуре new(ps4). Строка будет занимать в памяти 11 байт, адрес которой запишется в переменную ps4. Количество символов в строке может быть в пределах от 0 до 10.

В языке C:

#define STRLENGTH ...// Значение

...

char s[STRLENGTH];

Экземпляр СД типа строка располагается в статической памяти и занимает STRLENGTH байт, количество элементов строки (символов) может быть в пределах от 0 до STRLENGTH - 1.

typedef char t_str10[10];

...

t_str10 s;

Экземпляр СД типа строка (t_str10) s располагается в статической памяти и занимает 10 байт, количество элементов строки может быть в пределах от 0 до 9.

typedef char* p_str;

...

p_str ps;

Строка будет располагаться в динамической памяти после обращения к процедуре выделения памяти (malloc или calloc). Адрес начала строки запишется в переменную ps.

typedef char t_str10[10]:

typedef t_str10* p_str10;

...

p_str10 ps;

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

ps = (p_str10) new p_str10;

Строка будет занимать в памяти 10 байт, адрес которой запишется в переменную ps. Количество символов в строке может быть в пределах от 0 до 9.

Количество допустимых значений СД типа «строка»:

СAR(string) = 1 + 256 + 2562 + ... + 256K ,

где K -- максимальное количество элементов в строке.

Операции над строками:

Операция присваивания.

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

то перед присваиванием происходит усечение присваиваемого значения.

Операция сравнения.

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

больше (по ASCII-коду). Иначе они равны.

Операция конкатенация.

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

операнда второго операнда.

В Pascal определены следующие стандартные процедуры и функции над строками:

Procedure Delete(var S:String; Index,Count:Integer)

Удаляет Count символов из строки S,начиная с позиции Index.

Procedure Insert(Subs:String;var S:String; Index:Integer)

Вставляет подстроку SubS в строку S,начиная с позиции Index.

Procedure Str(X:real; var S:String)

Преобразует численное значение X в его строковое представление S.

Procedure Val(S:String; var X;var Code:Integer)

Преобразует строковое значение S в его численное представление X. Параметр Code содержит признак ошибки преобразования (0 -- нет ошибки).

Function Concat(S1[,S2,..,SN]:string):string

Выполняет конкатенацию последовательности строк.

Function Copy(S: String; Index, Count: Integer):string

Возвращает подстроку из строки S,начиная с позиции Index и длиной Count символов.

Function Length(S: String): byte

Возвращает текущую длину строки S.

Function Pos(SubS, S: String): Byte

Возвращает позицию, начиная с которой в строке S располагается

подстрока SubS (0 -- S не содержит SubS).

Операций над строками как с едиными целыми в языке С нет. Такие возможности, как конкатенация, сравнение строк, являющиеся в языке Pascal встроенными, в С доступны лишь через специальные функции. Одной из возможностей языка С является инициализация строковых констант, например:

char str[64] = "Символьные строки";

Следует отметить, что в языке C автоматически добавляется NULL к строковым константам.

В модуле string.h предусмотрен следующий ряд функций для работы со строками:

int strcmp(const char *s1, const char*s2);

Сравнивает s1 и s2 и возвращает отрицательное число, если s1 < s2; ноль, если s1 = s2; или положительное, если s1 > s2.

char *strcat(char *dest, const char *src);

Выполняет конкатенацию строк (копирует строку с начальным адресом src в конец строки с адресом dest). Возвращает указатель на результирующую строку.

size_t strlen(const char *s);

Возвращает длину строки s.

char *strcpy(char *dest, const char *src);

Копирует строку src в dest, дополняя последнюю символом '\0'.

char *strncpy(char *dest, const char *src, size_t len);

Копирует не более len символов из строки src в dest. Дополняет результат символом '\0', если символов в src меньше len. Возвращает указатель на результирующую строку.

char *strstr(const char *s1, const char *s2);

Возвращает указатель на первое вхождение s2 в s1 или, если такового не оказалось, NULL.

int sprintf (char *s, const char *format [,argument, ...]);

Действует так же, как и printf, только вывод осуществляет в строку s, завершая ее символом '\0'. Строка s должна быть достаточно большой, чтобы вмещать результат вывода. Возвращает количество записанных символов, в число которых символ '\0' не входит. Функция располагается в модуле string.h.

Следующие три функции, описанные в stdlib.h, предназначены для перевода строки s в числовое значение:

double atof(const char *s);

int atoi(const char *s);

long atol(const char *s);

Контрольные вопросы

1. Какие структуры данных называются встроенными, а какие -- производными?

2. Что представляет собой структура данных «строка» на абстрактном уровне?

3. Каков характер изменчивости встроенной структуры данных «строка» в языке Pascal?

4. На каких уровнях представления структур данных различаются встроенные структуры данных «строка» в языках Pascal и С?

5. Как реализованы операции над строками в языках Pascal и С?

Лабораторная работа №3. Сравнительный анализ методов сортировки (Pascal/C)

Цель работы: изучение методов сортировки массивов и приобретение навыков в проведении сравнительного анализа различных методов сортировки.

Задание

1. Изучить временные характеристики алгоритмов.

2. Изучить методы сортировки:

1) включением;

2) выбором;

3) обменом:

3.1) улучшенная обменом 1;

3.2) улучшенная обменом 2;

4) Шелла;

5) Хоара;

6) пирамидальная.

3. Программно реализовать методы сортировки массивов.

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

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

6. Построить графики функций временной сложности алгоритмов сортировки.

7. Определить аналитическое выражение функции временной сложности алгоритмов сортировки.

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

Таблица 9 - Результаты экспериментов

Сортировка

Количество элементов в массиве

500

1000

1500

2000

2500

3000

3500

4000

4500

Включением

Выбором

Обменом

Обменом 1

Обменом 2

Шелла

Хоара

Пирамидальная

Содержание отчета

1. Тема лабораторной работы.

2. Цель работы.

3. Листинг программы.

4. Результаты работы программы.

5. Графики функций временной сложности алгоритмов сортировки.

6. Выводы по работе.

Теоретические сведения

Временная сложность (ВС) алгоритма -- это зависимость времени выполнения алгоритма от количества обрабатываемых входных данных. Здесь представляет интерес среднее и худшее время выполнения алгоритма. ВС можно установить с различной точностью. Наиболее точной оценкой является аналитическое выражение для функции: t = t(N), где t -- время, N -- количество входных данных (размерность). Данная функция называется функцией временной сложности (ФВС).

Например: t = 5N2 + 6N + 1. Такая оценка может быть сделана только для конкретной реализации алгоритма в конкретной вычислительной системе. Математическая запись, позволяющая не учитывать эти условия, называется О-нотацией, предложенная П. Бахманом в 1892 г. Она определяется следующим образом:

если f(N) и g(N) есть функции, определенные в пространстве положительных целых чисел, тогда запись

f(N) = О(g(N))

(читается f(N) есть О большое от g(N)) обозначает, что существует такая константа с, что для всех достаточно больших положительных целых N | f(N)| ? с|g(N)|. При этих условиях можно также сказать, что «f(N) имеет порядок не больший, чем g(N)» или «f(N) растет не быстрее, чем g(N)».

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

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

Формулировка задачи может быть записана следующим образом. Если даны элементы а1, а2 ,…, аn, то сортировка означает перестановку этих элементов в массив ак1, ак2,…,акn, где при заданной функции упорядочения f справедливы отношения f(ак1) ??f(ак2) ? … ??f(акn). Обычно функция упорядочения f не вычисляется по какому-то специальному правилу, а является значением элемента.

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми значениями не меняется при сортировке; неустойчивым -- в противном случае.

Методы сортировки, в зависимости от лежащего в их основе приема, можно разбить на три базовых класса:

1) сортировка включением;

2) сортировка выбором;

3) сортировка обменом.

Сортировка включением

Этот метод обычно используют игроки в карты. Элементы (карты) условно разделяются на готовую последовательность а1,…, аi-1 и входную последовательность аi,…, аn. На каждом шаге, начиная с i=2 и увеличивая i на единицу, берут 1-й элемент входной последовательности и передают его в готовую последовательность, вставляя на подходящее место.

Алгоритм сортировки включением

Запоминаем элемент, подлежащий вставке.

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

Вставляем элемент на освободившееся место. Пункты 1-3 выполняем для всех элементов массива, кроме первого.

При поиске подходящего места для элемента x удобно чередовать сравнения и пересылки, т. е. как бы «просеивать» x, сравнивая его с очередным элементом a[j] и либо вставляя x, либо пересылая a[j] вправо. Просеивание может быть закончено при двух различных условиях:

найден элемент аi с ключом меньшим, чем ключ x;

достигнут левый конец готовой последовательности.

Если первоначальный массив отсортирован, то на каждом просмотре делается только одно сравнение, так что эта сортировка имеет порядок O(N). Если массив первоначально отсортирован в обратном порядке, то данная сортировка имеет порядок O(N2), поскольку общее число сравнений равно 1 + 2 + 3 + ... + (N - 2) + (N - 1) = (N - 1)N / 2, что составляет O(N2). Чем ближе к отсортированному виду, тем более эффективной становится сортировка простыми вставками. Среднее число сравнений в сортировке простыми вставками также составляет O(N2).

Сортировка выбором

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

Алгоритм сортировки выбором

1. Находим наименьший элемент в неупорядоченной части массива.

2. Меняем местами найденный элемент с тем, который соседствует с упорядоченной частью.

3. Пункты 1 и 2 выполняем, пока в неупорядоченной части имеется более одного элемента.

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

Анализ сортировки простым выбором

При сортировке простым выбором число сравнений ключей не зависит от их начального порядка. На первом просмотре выполняется N - 1 сравнение, на втором -- N - 2 и т.д. Следовательно, общее число сравнений равно (N - 1) + (N - 2) + (N - 3) + ... + 1 = N(N - 1) / 2, что составляет O(N2).

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

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

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

Алгоритм сортировки обменом:

1. Перебираем поочередно все пары соседних элементов, начиная с последнего, и меняем местами элементы в парах, нарушающих порядок.

2. Пункт 1 повторяем n - 1 раз.

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

При использовании сортировки обменом число сравнений элементов не зависит от их начального порядка. На первом просмотре выполняется N - 1 сравнение, на втором -- N - 2 и т.д. Следовательно, общее число сравнений равно (N - 1) + (N - 2) + (N - 3) + ... + 1 = N(N - 1) / 2, что составляет O(N2).

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

Улучшенная сортировка обменом 1

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

Анализ улучшенной сортировки обменом 1

Число сравнений для этого метода зависит от числа проходов, необходимых для сортировки. В худшем случае, когда массив упорядочен в обратном порядке, выполняется N - 1 проходов. На первом проходе выполняется N - 1 сравнение, на втором -- N - 2 и т.д. Следовательно, общее число сравнений равно (N - 1) + (N - 2) + (N - 3) + ... + 1 = N?(N - 1) / 2, что составляет O(N2). В этом случае выполняется максимальное число перестановок, что увеличивает время выполнения алгоритма.

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

Улучшенная сортировка обменом 2

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

Анализ улучшенной сортировки обменом 2

Анализ улучшенной сортировки обменом 2 аналогичен анализу улучшенной сортировки обменом 1. Порядок функций ВС этих алгоритмов в лучшем и худшем случаях одинаковый.

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

Сортировка Шелла -- это улучшенный метод сортировки вставками. Был предложен Д.Л. Шеллом в 1959 г. Рассмотрим этот метод на примере (см. ниже). При первом проходе группируются и сортируются элементы, отстоящие друг от друга на 5 позиций: (Х1,Х6), (Х2,Х7), (Х3), (Х4), (Х5), т.е. выполняется сортировка массива с шагом 5; при втором проходе -- элементы, отстоящие друг от друга на три позиции: (Х1,Х4,Х7), (Х2,Х5), (Х3,Х6); при третьем -- на 1 позицию.

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

Алгоритм сортировки Шелла

Определить количество проходов t и шаг сортировки на каждом проходе. Результат сохранить в массиве h.

На i-ом проходе (i=1,…,t) выполнить сортировку включением с шагом h(i).

Анализ сортировки Шелла

Поскольку первый в сортировке Шелла используемый шаг является большим, отдельные подмассивы достаточно малы по отношению к исходному. Таким образом, сортировка включением над этими подмассивами работает достаточно быстро -- O(N2) (эффективно при малом N). Сортировка каждого подмассива приводит к тому, что весь массив становится ближе к отсортированному виду, что также делает эффективным использование сортировки включением. Так как массив становится более упорядоченным, то O(N) < порядок ФBC < O(N2).

Анализ сортировки Шелла математически сложен. В случае правильного выбора шагов порядок ФВС будет выглядеть как O(N1.2). Д. Кнут предложил выбирать шаги из следующего ряда: 1, 4, 13, 40, 121, … , а вычислять их по формуле: hi - 1 = 3? hi + 1; ht = 1; t = [log 3 N] - 1 (количество просмотров), где N -- размерность исходного массива. Т.е. элементы должны быть взаимно простыми числами. Исходя из этого порядок сортировки может быть аппроксимирован величиной О(N(log 2 N)).

Сортировка Хоара

Сортировка Хоара -- лучший из известных до сего времени метод сортировки массивов. Он обладает столь блестящими характеристиками, что его автор Ч. Хоар назвал эту сортировку быстрой. Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно разбить массив на подмассивы и сортировать подмассивы меньшего размера.

Алгоритм быстрой обменной сортировки:

1. Выбираем элемент массива в качестве разделителя (например, первый).

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

3. Если число элементов в левом подмассиве больше 1, то применяем к нему алгоритм в целом, иначе конец алгоритма.

4. Если число элементов в правом подмассиве больше 1, то применяем к нему алгоритм в целом, иначе конец алгоритма.

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

Пример.

Исходный массив (30 10 40 20 15 17 45 60)

Разделитель 30

После выполнения п.2 получаем следующие два подмассива:

(17 10 15 20) (40 30 45 60)

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

Анализ сортировки Хоара

Пусть m = log 2 N, где N -- количество элементов. Будем считать, что количество элементов, меньших разделителя, равно количеству элементов, больших разделителя, т.е. массив разбивается пополам на две равные части. Определим количество сравнений в этом случае:

N + 2?(N / 2) + … + m?(N / m) = O(N?m) = O(N?log2N).

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

Характер разбиения массива, а, следовательно, и порядок функции ВС, зависит от соотношения разделителя и остальных элементов массива. Для определения «хорошего» разделителя имеются различные алгоритмы.

Пирамидальная сортировка

Пирамидальная сортировка является улучшенной сортировкой выбором. Из массива, состоящего из N элементов, выбирается максимальный и меняется местами с последним. Затем рассмат-ривается массив из N = N - 1 элементов. Процесс повторяется до тех пор, пока количество рассматриваемых элементов больше одного. Пира-мидальная сортировка отличается от сортировки выбором поиском максимального элемента. Чтобы понять пирамидальную сортировку, массив нужно интерпретировать как бинарное дерево, в корне которого находится первый элемент массива, на втором уровне -- второй и третий, на третьем -- с четвертого по седьмой и т.д. Для i-го элемента массива можно определить номер P элемента, являющегося родителем, как P = i div 2; номер L элемента, являющегося левым сыном, как L = 2?i; номер R элемента, являющегося правым сыном, как R=2?i+1. Если в массиве (в дереве) N элементов, то последний элемент, имеющий хотя бы одного левого сына, имеет номер (N div 2). Массив M (см. таблицу 10) можно представить деревом на рис.5.

Таблица 10 - Массив М

номер элемента массиваМ

1

2

3

4

5

6

7

8

9

10

значение элемента массива М

42

5

87

1

74

12

63

25

58

33

Рис. 5. Представление массива в виде дерева

Поиск максимального элемента массива в этом алгоритме основан на понятии пирамиды. Дерево (поддерево) является пирамидой, если каждый элемент в нем больше или равен элементам, которые являются его сыновьями. Корень пирамиды -- максимальный элемент массива. Пирамида для массива M (см. таблицу 10) представлена на рис. 6.

Рис.6. Пирамида для массива М

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

Таблица 11 - Массив М

номер элемента массива М

1

2

3

4

5

6

7

8

9

10

значение элемента массива М

5

74

63

58

33

12

42

25

1

87

Рис. 7. Дерево массива М

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

Рис. 8. Пирамида для массива М

Сформулируем алгоритм перестроения дерева, у которого левое и правое поддерево -- пирамиды, в пирамиду.

Алгоритм MakeHeap.

1. Запоминаем корневой элемент.

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

3. Вставляем корневой элемент на освободившееся место.

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

Теперь можем сформулировать алгоритм пирамидальной сортировки.

Алгоритм HeapSort.

1. Построить пирамиду для исходного массива.

2. Пока в массиве более одного элемента, переставить первый и последний элемент, уменьшить размер массива на единицу и перестроить дерево в пирамиду по алгоритму MakeHeap.

Анализ пирамидальной сортировки

Пусть дерево массива на нижнем (нулевом) уровне содержит максимальное число вершин. Для построения пирамиды из произвольного дерева (первая часть алгоритма) нужно обработать все вершины, начиная с первого уровня. Для обработки вершины на i-том уровне число сравнений пропорционально i. Число вершин на i-том уровне равно 2[log2N]-1 , а всего уровней m=[log2N], следовательно, общее число сравнений определяется формулой: 1?2[log2N]-1 + 2?2[log2N]-2 + … + m?2[log2N]-m = O(N).

Во второй части алгоритма последовательно обрабатываются деревья с N, N - 1, … ,2 вершинами. Число сравнений для перестройки дерева, состоящего из i вершин, в пирамиду пропорционально [log2i], следовательно, общее число сравнений

[log 2 N] + [log 2 (N - 1)] + … + [log 2 2] = O(N?log 2 N).

Таким образом порядок функции ВС алгоритма пирамидальной сортировки O(N?log2N).

Примеры программной реализации алгоритмов сортировки

на языке Pascal

{============СОРТИРОВКА ВКЛЮЧЕНИЕМ=============}

{ процедура сортировки включением }

procedure InsertSort(var a:t_mas;n:t_index);

var i,j: t_index;

x : t_el;

begin

for i := 2 to n do

begin

x := a[i];

j := i-1;

while (x < a[j])and(j >= 1) do

begin

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

j := j-1;

end;

a[j+1] := x;

end;

end;

{============СОРТИРОВКА ВЫБОРОМ=============}

{ процедура обмена значений }

procedure Swap_el(var a,b:t_el);

var c:t_el;

begin

c:=a;

a:=b;

b:=c;

end;

{ процедура сортировки выбором }

procedure ChoiceSort(var a:t_mas;n:t_index);

var i,j :t_index;

x :t_el;

begin

for i := 1 to n do

begin

x := a[i];

for j := i+1 to n do

if (a[j] < x) then

x := a[j];

swap_el(a[i],x);

end;

end;

{=================СОРТИРОВКА ОБМЕНОМ================}

{ процедура обмена значений }

procedure Swap_el(var a,b:t_el);

var c:t_el;

begin

c:=a;

a:=b;

b:=c;

end;

{ процедура сортировки обменом }

procedure BblSort(var a:t_mas;n:t_index);

var i,j : t_index;

begin

for i := 2 to n do

for j := n downto i do

if (a[j-1] >= a[j]) then

swap_el(a[j-1],a[j]);

end;

{ процедура улучшенной сортировки обменом 1 }

procedure BblSort_improv1(var a:t_mas;n:t_index);

var i,j : t_index;

fl: boolean;

begin

i := 2;

repeat

fl:= false; //перестановок изначально нет

for j := n downto i do

if (a[j-1] >= a[j]) then

begin

swap_el(a[j-1],a[j]);

fl:= true; //некоторые элементы переставлены

end;

i := i+1;

until (not fl)or(i > n);

end;

{ процедура улучшенной сортировки обменом 2 }

procedure BblSort_improv2(var a:t_mas;n:t_index);

var i,j,k : t_index;

begin

i := 2;

k := n+1;

for j := n downto i do

if (a[j-1] >= a[j]) then

begin

swap_el(a[j-1],a[j]);

k := j-1; //запоминаем индекс последнего обмененного элемента

end;

i := k;

until (i > n);

end;

{============СОРТИРОВКА МЕТОДОМ ШЕЛЛА=============}

{ процедура сортировки методом Шелла }

procedure ShellSort(var a:t_mas;n:t_index);

type t_arr = array [1..65520 div sizeof(word)] of word;

var i,j,hh,t,s : t_index;

k : integer;

h : t_arr;

begin

t := round(ln(n)/ln(3))-1;

if (t < 1) then

t := 1;

h[t] := 1;

for k := t downto 2 do

h[k-1] := 3*h[k]+1;

for s := t downto 1 do

begin

hh := h[s];

for j := hh+1 to n do

begin

i := j-hh;

k := a[j];

while (k <= a[i])and(i > 0) do

begin

a[i+hh] := a[i];

i := i-hh;

end;

a[i+hh] := k;

end;

end;

end;

{============СОРТИРОВКА МЕТОДОМ ХОАРА=============}

{ процедура сортировки методом Хоара }

procedure HoarSort(var a: t_arr; n: integer);

procedure QSort(L,R:integer);

var x,t,i,j:integer;

begin

x:=a[L]; // в качестве разделителя выбираем первый элемент

i:=L;

j:=R;

while i<=j do

begin

while a[i]<x do

inc(i);

while a[j]>x do

dec(j);

if i<=j then

begin

t:=a[i];

a[i]:=a[j];

a[j]:=t;

inc(i);

dec(j);

end;

end;

if L<j then

QSort(L,j);

if i<R then

QSort(i,R);

end;

begin

QSort(1,n);

end;

{=============ПИРАМИДАЛЬНАЯ СОРТИРОВКА==============}

procedure sift(var a:t_mas;L,R:t_index);

var i,j : t_index;

c : t_el;

begin

i := L;

j := 2*L;

c := a[L];

if (j < R)and(a[j] < a[j+1]) then

j := j+1;

while (j <= R)and(c < a[j]) do

begin

Swap_el(a[i],a[j]);

i := j;

j := 2*j;

if (j < R)and(a[j] < a[j+1]) then

j := j+1;

end;

end;

{ процедура пирамидальной сортировки }

procedure HeapSort(var a:t_mas;n:t_index);

var i,L,R : t_index;

begin

L := n div 2+1;

R := n;

while (L > 1) do

begin

L := L-1;

Sift(a,L,R);

end;

while (R > 1) do

begin

Swap_el(a[1],a[R]);

R := R-1;

Sift(a,L,R);

end;

end;

Примеры программной реализации алгоритмов сортировки

на языке C

/*============СОРТИРОВКА ВКЛЮЧЕНИЕМ=============*/

/* функция сортировки включением */

void Sis(int A[],int nn)

{ int i,j,k;

for ( j=1; j<nn; j++ )

{ k = A[j];

i = j -1;

while ( k < A[i] && i >= 0)

{ A[i+1] = A[i];

i -= 1; }

A[i+1] = k;

}

}

/*==============СОРТИРОВКА ВЫБОРОМ===============*/

/*функция сортировки выбором */

void StrSel(int A[],int nn)

{ int i,j,x,k;

for ( i=0; i<nn-1; i++ )

{ x = A[i]; k = i;

for (j=i+1; j<nn; j++)

if (A[j] < x)

{ k = j; x = A[k]; }

A[k] = A[i]; A[i] = x;

}

/*============СОРТИРОВКА ОБМЕНОМ=============*/

/* функция сортировки обменом */

void BblSort(int A[],int nn)

{ int i,j,k,p;

for ( i=0; i<nn-1; i++ )

{ p = 0;

for (j=nn-1; j>i; j--)

if (A[j] <A[j-1])

{ k = A[j]; A[j] = A[j-1]; A[j-1] = k; p = 1;}

/* Если перестановок не было, то сортировка выполнена */

if ( p == 0)

break;

}

}

/*============СОРТИРОВКА МЕТОДОМ ШЕЛЛА=============*/

/* функция сортировки методом Шелла */

void ShellSort(int a [], int n){

int i,j,k,hh,t,s;

int h [1000];

t = round(ln(n)/ln(3))-1;

if (t < 1){

t = 1;

};

h[t] = 1;

for (k=t-1; k >= 1; k--) {

h[k-1] = 3*h[k]+1;

}

for (s=t-1;s>=0;s--){

hh = h[s];

for (j = hh;j<=n;j++){

i = j-hh;

k = a[j];

while ((k <= a[i])&&(i >= 0)){

a[i+hh] = a[i];

i = i-hh;

} ;

a[i+hh] = k;

} }}

/*============СОРТИРОВКА МЕТОДОМ ХОАРА=============*/

void QSort(int a [], int L, int R){

int x = a[L], i = L, j = R, t; // в качестве разделителя выбираем первый элемент

while (i<=j){

while (a[i]<x)

i++;

while (a[j]>x)

j--;

if (i<=j){

t = a[i];

a[i] = a[j];

a[j] = t;

i++;

j--;

} }

if (L<j)

QSort(a,L,j);

if (i<R)

QSort(a,i,R);

}

/*функция сортировки методом Хоара*/

void HoarSort(int a[], int n){

QSort(a,1,n);

}

/*============ПИРАМИДАЛЬНАЯ СОРТИРОВКА=============*/

/* пирамидальная функция сортировки */

void HeapSort(int A[],int nn)

{ int L,R,x,i;

L = nn/2 ; R = nn-1;

/* Построение пирамиды из исходного массива */

while ( L>0 )

{ L = L - 1;

Sift(A,L,R);

}

/* Сортировка: пирамида => отсортированный массив */

while ( R>0 )

{ x = A[0]; A[0] = A[R]; A[R] = x;

R--;

Sift(A,L,R);

} }

/* ============================================ */

void Sift(int A[],int L,int R)

{ int i,j,x,k;

i = L;

j = 2*L+1;

x = A[L];

if ((j<R) && (A[j]<A[j+1]))

j++;

while ((j<=R) && (x<A[j]))

{ k=A[i]; A[i] = A[j]; A[j]=k;

i = j;

j = 2*j+1;

if ((j<R) && (A[j]<A[j+1]))

j++;

} }

/* ***************************************************** */

Контрольные вопросы

1. Что такое временная сложность алгоритма?

2. Почему функцию временной сложности нельзя использовать для оценки алгоритма?

3. Что такое порядок функции? Как определяется порядок функции, заданной многочленом?

4. Как можно определить порядок функции временной сложности алгоритма?

5. Что называется сортировкой?

6. В каком случае метод сортировки называется устойчивым?

7. Как выполняется сортировка включением?

8. Зависит ли время сортировки включением от упорядоченности массива?

9. Зависит ли порядок функции временной сложности сортировки включением от упорядоченности массива?

10. Выполните анализ сортировки включением.

11. Реализуйте алгоритм сортировки включением на языке программирования.

12. Как выполняется сортировка выбором?

13. Зависит ли время сортировки выбором от упорядоченности массива?

14. Зависит ли порядок функции временной сложности сортировки выбором от упорядоченности массива?

15. Выполните анализ сортировки выбором.

16. Реализуйте алгоритм сортировки выбором на языке программирования.

17. Как выполняется сортировка обменом?

18. Зависит ли время сортировки обменом от упорядоченности массива?

19. Зависит ли порядок функции временной сложности сортировки обменом от упорядоченности массива?

20. Выполните анализ сортировки обменом.

21. Реализуйте алгоритм сортировки обменом на языке программирования.

22. Как можно улучшить сортировку обменом?

23. Почему сортировка Шелла быстрее сортировки вставками?

24. Выполните итеративную реализацию сортировки Хоара.

25. Чем пирамидальная сортировка отличается от сортировки выбором?

Лабораторная работа №4. Сравнительный анализ алгоритмов поиска (Pascal/C)

Цель работы: изучение алгоритмов поиска элемента в массиве и закрепление навыков в проведении сравнительного анализа алгоритмов.

Задание

1. Изучить алгоритмы поиска:

1) в неупорядоченном массиве:

- линейный;

- быстрый линейный;

2) в упорядоченном массиве:

- быстрый линейный;

- бинарный;

- блочный.

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

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

4. Построить графики зависимости количества операций сравнения отколичества элементов в массиве.

5. Определить аналитическое выражение функции зависимости количества операций сравнения от количества элементов в массиве.

6. Определить порядок функций временной сложности алгоритмов

поиска.

Содержание отчета

1. Тема лабораторной работы.

2. Цель работы.

3. Листинг программы.

4. Результаты работы программы.

5. Графики функций временной сложности.

6. Выводы по работе.

Таблица 12 - Максимальное количество операций сравнения

Алгоритмы

поиска

Количество элементов в массиве

50

100

150

200

250

300

350

400

450

Линейный (неупорядоченный массив)

Быстрый линейный (неупорядоченный массив)

Быстрый линейный (упорядоченный массив)

Бинарный (упорядоченный массив)

Блочный (упорядоченный массив)

Таблица 13 - Среднее количество операций сравнения

Алгоритмы поиска

Количество элементов в массиве

50

100

150

200

250

300

350

400

450

Линейный (неупорядоченный массив)

Быстрый линейный (неупорядоченный массив)

Бстрый линейный (упорядоченный массив)

Бинарный (упорядоченный массив)

Блочный (упорядоченный массива)

Теоретические сведения

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

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

Алгоритмы поиска в неупорядоченных массивах

Алгоритм линейного поиска

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

Алгоритм быстрого линейного поиска

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

Анализ алгоритмов линейного поиска

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

Оценим среднее время алгоритма, при этом будем исходить из следующего: пусть Pi -- вероятность того, что будет осуществляться поиск элемента со значением ki; предположим, что , т.е. элемент со значением ki не будет отсутствовать (в массиве обязательно есть элемент,

поиск которого осуществляется).

Среднее время (), как следует из алгоритма, пропорционально среднему числу операций сравнения () и равно

~=.

Если ключи имеют одинаковую вероятность P1=P2=...PN=P, а также учитывая, что, , , тогда

,

т.е. при линейном поиске в среднем необходимо просмотреть половину массива.

Для экспериментального определения среднего числа сравнений необходимо найти суммарное число сравнений при поиске всех элементов массива и разделить на количество элементов.

Алгоритмы поиска в упорядоченных массивах

Алгоритм быстрого линейного поиска

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

Алгоритм бинарного поиска

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

Алгоритм бинарного поиска

1. Определить середину массива.

2. Если элемент, находящийся в середине массива, совпадает с искомым, поиск завершен.

3. Если элемент из середины массива больше искомого, применить бинарный поиск к первой половине массива.

4. Если элемент из середины массива меньше искомого, бинарный поиск необходимо применить ко второй половине массива.

5. Пункт 1-4 повторять, пока размер области поиска не уменьшается до нуля. Если это произойдет -- ключа в массиве нет.

Анализ алгоритма бинарного поиска

Порядок функции ВС алгоритма бинарного поиска равен O(log 2 N). Это объясняется тем, что на каждом шаге поиска вдвое уменьшается область поиска. До того, как она станет равной одному элементу, произойдет не более log 2 N таких уменьшений, т.е. выполняется не более log 2 N шагов алгоритма. В лучшем случае, когда искомый элемент находится в середине массива, число сравнений не зависит от количества элементов в массиве и порядок функции ВС будет O(1).

Определим среднее число шагов при поиске элементов в массиве из N элементов. Для этого подсчитаем суммарное число шагов S при поиске каждого элемента массива. Исходя из алгоритма, не более чем N / 2 элементов ищется за log 2 N шагов, N / 4 элементов -- за (log 2 N) - 1 шагов, и т.д. Отсюда.

Среднее число шагов равно S / N, что составляет O(log 2 N).

Алгоритм блочного поиска

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

Анализ алгоритма блочного поиска

Пусть массив состоит из N элементов и при поиске разбивается на X равных блоков. Тогда в каждом блоке будет не более N / X элементов. В худшем случае, если искомый элемент окажется в последнем блоке, то для поиска блока потребуется просмотреть X элементов массива. Выполнить линейный поиск в блоке можно, просмотрев не более чем N / X элементов. Следовательно, общее число обрабатываемых элементов не превышает X + N / X. Эта величина зависит от числа блоков и будет минимальна, когда ее производная равна нулю, т.е. при. Число записей в блоке так же равно . При таком разбиении массива на блоки в худшем случае понадобиться обработать не более чем элементов массива, а в среднем -- элементов.

Контрольные вопросы

1. В чем заключается задача поиска?

2. Всегда ли быстрый линейный поиск быстрее линейного поиска?

3. От чего зависит время поиска в неупорядоченном массиве?

4. Чем алгоритм быстрого линейного поиска в упорядоченном массиве отличается от алгоритма быстрого линейного поиска в неупорядоченном массиве?

5. В чем заключается бинарный поиск?

6. Определите индексы элементов массива, бинарный поиск которых наиболее продолжителен.

7. Разработайте и реализуйте итеративный и рекурсивный алгоритмы бинарного поиска?

8. В чем заключается блочный поиск?

9. От чего зависит время блочного поиска?

10. Как правильно выбрать количество блоков в блочном поиске?

11. Определите максимальное количество элементов массива, которые могут быть обработаны при блочном поиске.

12. Пусть искомый элемент равен i-му элементу массива. Какой алгоритм рациональнее использовать в этом случае?

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

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

15. Реализуйте алгоритмы поиска на языке программирования высокого уровня. Выполните трассировку при поиске в массиве из одного элемента.

16. От чего завист порядок функции временной сложности алгоритмов поиска. Каким он может быть для различных алгоритмов?

Лабораторная работа № 5. Структуры данных «линейные списки» (Pascal/С)

Цель работы: изучить СД типа «линейный список», научиться их программно реализовывать и использовать.

Задание

1. Для СД типа «линейный список» определить:

1.1. Абстрактный уровень представления СД:

1.1.1. Характер организованности и изменчивости.

1.1.2. Набор допустимых операций.

1.2. Физический уровень представления СД:

1.2.1. Схему хранения.

1.2.2. Объем памяти, занимаемый экземпляром СД.

1.2.3. Формат внутреннего представления СД и способ его интерпретации.

1.2.4. Характеристику допустимых значений.

1.2.5. Тип доступа к элементам.

1.3. Логический уровень представления СД.

Способ описания СД и экземпляра СД на языке программирования.

2. Реализовать СД «линейный список» в соответствии с вариантом индивидуального задания (см. табл.14) в виде модулей на языках Pascal и С.

3. Разработать программы на языках Pascal и С для решения задачи в соответствии с вариантом индивидуального задания (см. табл.14) с использованием модуля, полученного в результате выполнения пункта 2 задания.

Таблица 14 - Варианты индивидуальных заданий

Номер варианта

Номер модуля

Задача

1

1

1

2

2

2

3

3

3

4

4

4

5

5

5

6

6

6

7

7

7

8

8

8

9

1

9

10

2

10

11

3

11

12

4

1

13

5

2

14

6

3

15

7

4

16

8

5

17

1

6

18

2

7

19

3

8

20

4

9

21

5

10

22

6

11

23

7

1

24

8

2

25

1

3

26

2

4

27

3

5

28

4

6

29

5

7

30

6

8

Задачи

1. Многочлен P(x)=anxn + an-1xn-1 + ... + a1x + a0 с целыми коэффициентами можно представить в виде списка, причем если ai = 0, то соответствующее звено не включать в список. Определить логическую функцию РАВНО(p, q), проверяющие на равенство многочлены p и q.

2. Дано натуральное число n целые числа a1,a2,...,an. Требуется получить последовательность x1,y1;x2,y2;...;xk,yk, где x1,...,xk -- взятые в порядке следования (слева на право) четные члены последовательности a1,...,an, a y1,...,yk -- нечетные члены, к = min(m,l).

3. Дано натуральное число n и целые числа a1,a2,...,an. Вычислить , где среднее арифметическое чисел a1,...,an.

4. Даны натуральные числа k,m,n, последовательности символов s1,...,sk,t1,...,tm,u1,...,un. Получить по одному разу те символы, которые входят во все три последовательности.

5. Многочлен P(x)=anxn + an-1xn- 1+ ... + a1x + a0 с целыми коэффициентами можно представить в виде списка, причем если ai=0, то соответствующее звено не включать в список. Определить функцию, вычисляющую значения многочлена в точке х.

6. Даны натуральное число n, символы s1,...,sn. Получить символы, принадлежащие последовательности s1,...,sn, которые входят в нее по одному разу.

7. Многочлен P(x) = anxn + an-1xn- 1+ ... + a1x + a0 с целыми коэффициентами можно представить в виде списка, причем если ai = 0, то соответствующее звено не включать в список. Определить процедуру, которая стоит многочлен p -- сумму многочленов q и r;

8. Многочлен P(x) = anxn + an-1xn-1 + ... + a1x + a0 с целыми коэффициентами можно представить в виде списка, причем если ...


Подобные документы

  • Рассмотрение правил записи, способов ввода и вывода, использования функций обработки символьных данных в Pascal. Описание алгоритмизации и программирования файловых структур данных, проектирования структуры файла. Ознакомление с работой данных массива.

    курсовая работа [336,2 K], добавлен 27.06.2015

  • Средства создания динамических структур данных. Формат описания ссылочного типа. Структура памяти во время выполнения программы. Линейные списки, стек, очередь. Организация списков в динамической памяти. Пример создания списка в обратном порядке.

    лабораторная работа [788,2 K], добавлен 14.06.2009

  • Анализ эффективности методов сортировки данных в языке Turbo Pascal. Разработка эскизного и технического проекта программы. Сортировка без и с использованием дополнительной памяти, за исключением небольшого стека (массива). Сортировка связанных списков.

    курсовая работа [359,0 K], добавлен 23.05.2012

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

    контрольная работа [290,6 K], добавлен 17.07.2012

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

    учебное пособие [1,5 M], добавлен 10.12.2010

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

    курсовая работа [451,1 K], добавлен 19.10.2013

  • Методы реализации алгоритмов сортировки и алгоритмов поиска на языках программирования высокого уровня. Программирование алгоритмов сортировки и поиска в рамках создаваемого программного средства на языке Delphi. Создание руководства пользователя.

    курсовая работа [1,7 M], добавлен 16.04.2012

  • Разработка алгоритмов методом пошаговой детализации. Типы данных и операции в Turbo-Pascal. Организация работы с подпрограммами. Составление алгоритмов и программ задач с использованием конечных сумм. Организация работы с динамическими переменными.

    учебное пособие [1,4 M], добавлен 26.03.2014

  • Характеристика вычислительной системы и инструментов разработки. Программирование на языке Pascal в среде Turbo Pascal и на языке Object Pascal в среде Delphi. Использование процедур, функций, массивов, бинарного поиска. Создание базы данных в виде файла.

    отчет по практике [2,1 M], добавлен 02.05.2014

  • Изучение функций и возможностей среды разработки языка программирования Pascal. Рассмотрение работы с одномерными и двумерными массивами, со строками и числами. Математическая формулировка задач. Разработка алгоритмов, описание структуры программ.

    курсовая работа [879,8 K], добавлен 11.02.2016

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

    курсовая работа [747,2 K], добавлен 09.06.2013

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

    лабораторная работа [11,4 K], добавлен 13.05.2011

  • Разработка программ на языке Turbo Pascal на основе использования массивов данных. Особенности хранения данных, способы объявления переменных, действия над элементами массивов, их ввод и вывод. Практическое применение одномерных и многомерных массивов.

    методичка [17,8 K], добавлен 25.11.2010

  • При помощи Turbo Pascal достаточно не просто создать программу, которая бы демонстрировала работу с базами данных. Для этого существует огромное количество специализированных программ. Основа и сущность формирования базы данных при помощи Turbo Pascal.

    курсовая работа [479,7 K], добавлен 04.07.2008

  • Проектирование программ в среде Рascal с интерфейсом типа "Меню". Разработка и отладка программы сортировки массива данных. Освоение методов проектирования Pascal-программ с использованием графических процедур и функций из стандартного модуля Graph.

    контрольная работа [581,1 K], добавлен 16.01.2015

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

    курсовая работа [364,1 K], добавлен 06.04.2014

  • Создание таблицы, содержащей сведения о книгах (фамилия автора, название, год издательства, тираж, цена) с применением встроенных функций сортировки, поиска данных и их замены, автофильтра, расширенного фильтра, баз данных, диаграмм и графиков в MS Excel.

    курсовая работа [3,3 M], добавлен 16.05.2010

  • Исследование основных особенностей алгоритмов быстрой и поразрядной сортировки данных. Построение графиков зависимости времени сортировки от количества элементов в файле и от степени перемешенности элементов. Описания сортировки чисел и строковых данных.

    лабораторная работа [1,2 M], добавлен 23.07.2012

  • Условие задачи: составление программы на языке Pascal для определения оптимального маршрута с ближайшим временем отправления, меньшим пребыванием в пути. Решение методом последовательного испытания. Формы представления данных, набора тестов. Результаты.

    курсовая работа [22,0 K], добавлен 07.11.2009

  • Общая характеристика организации массива в виде двоичного дерева. Особенности линейного и двоичного поиска заданного элемента массива. Методика упорядочения массива методом сортировки деревом. Инструкции и текст программы для нечисленной обработки данных.

    курсовая работа [242,3 K], добавлен 12.11.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.