|
|
Для всех заданий предварительно написать процедуру сортировки массива методом прямого включения.1. Дан ряд, содержащий n элементов. Отсортировать их в порядке возрастания, отбрасывая при этом все повторяющиеся элементы. 2. Определить моду данного ряда – значение, встречающееся среди его элементов чаще всего. 3. Исходный набор данных представляет собой последовательность записей, состоящих из фамилии, возраста и стажа работы. Распечатать этот список: 1) в алфавитном порядке; 2) в порядке увеличения возраста; 3) в порядке увеличения стажа работы. 4. Написать процедуру сортировки по убыванию. 5. Дан ряд целых чисел. Получить в порядке возрастания все различные числа, входящие в этот ряд. 6. Дан ряд из n различных целых чисел. Получить различные целые числа 7. Даны целые 8. Даны натуральные 9. Дано n независимых случайных точек, с координатами (xi; yi), равномерно распределенных в круге радиуса 1 с центром в начале координат. Напишите программу, располагающую точки в порядке возрастания расстояния от центра. 10. Даны n целых положительных двузначных чисел. Трактуя каждое число как пару цифр из интервала 0–9, отсортировать их (цифры) по возрастанию. 11. Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся замкнутую ломаную, проходящую через все эти точки. (Соседним отрезкам ломаной разрешается лежать на одной прямой.) Подсказка. Возьмем самую левую точку (т.е. точку с наименьшей x-координатой) и проведем из нее лучи во все остальные точки. Теперь упорядочим эти лучи снизу вверх, а точки на одном луче упорядочим по расстоянию от начала луча (это делается для всех лучей, кроме нижнего и верхнего). Ломаная выходит из выбранной (самой левой) точки по нижнему лучу, затем по всем остальным лучам (в описанном порядке) и возвращается по верхнему лучу. 12. Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую. (Резиновое колечко, натянутое на вбитые в доску гвозди - их выпуклая оболочка.) Указание. Упорядочим точки. Затем, рассматривая точки по очереди, будем строить выпуклую оболочку уже рассмотренных точек.
Лабораторная работа №4 Бинарный поиск Цель работы: Исследовать один из наиболее распространенных методов поиска данных– бинарный (двоичный) поиск. Общие сведения Пусть Областью поиска служит n-элементный ряд, предварительно отсортированный. Вначале диапазон поиска определяется граничными значениями Low = 1 и High = n. Строим первую «гипотезу», полагая, что искомое значение находится в позиции Test – где-то посередине между границами Low и High. Если проверка подтверждает это, то поиск успешно завершен. Если значение в позиции Test меньше искомого, нижней границей (Low) становится Test + 1, а если больше, то модифицируется верхняя (High) граница – для нее принимается значение, равное Test – 1. Описанный процесс постепенного сближения границ поиска с последующей проверкой среднего элемента повторяется многократно, завершаясь одним из двух исходов: либо нужное значение обнаруживается (успех), либо Low становится больше High (неудача). Максимальное количество проверок, необходимое для завершения бинарного поиска (при любом исходе – удачном или неудачном), определяется по формуле, где ceil обозначает функцию, возвращающую ближайшее целое число, большее или равное ее аргументу. Другими словами, k есть наименьшее целое, такое, что 2k равно или больше, чем n + 1. Например, если n = 100, для сортировки потребуется не более семи проверок, поскольку 27 = 128. Пример Пусть b = 6, а массив а состоит из 10 элементов: 3 5 6 8 12 15 17 18 20 25. Шаг 1. Найдем номер среднего элемента: Шаг 2. Рассматриваем лишь первые 4 элемента массива; находим индекс среднего элемента этой части Шаг 3. Рассматриваем два элемента; значение Контрольные вопросы 1. Как в Паскале разделить нацело два числа? 2. Есть ли в Паскале аналог функции ceil? 3. За сколько шагов наверняка завершится поиск элемента в массиве из 1000 элементов? 4. Когда число элементов ряда удваивается, на сколько увеличивается максимально необходимое количество проверок? Варианты заданий Для всех вариантов предварительно написать процедуру поиска 1. Опишите массив записей, содержащих фамилию абонента и номер его телефона. Запрограммируйте двоичный поиск в телефонном справочнике. 2. Индексом называется таблица, содержащая отсортированные значения некоторых ключей и их местоположение в массиве записей. Индексом пользуются для ускорения поиска в массиве (сам массив может быть неотсортирован). Запрограммируйте процедуру составления индекса и 2.1. Последовательного поиска при помощи индекса. 2.2. Бинарного поиска при помощи индекса. 3. Пусть задан в виде последовательности символов некоторый текст T, состоящий из слов и есть два списка из нескольких слов в виде двух массивов A и B. Написать программу, преобразующую текст T в текст S, путем замены каждого вхождения слова A[i] на соответствующее слово B[i]. 4. В нашем примере поиск проводился в массиве, упорядоченном по возрастанию. Напишите процедуру бинарного поиска в массиве, упорядоченном по убыванию. 5. Дан массив из строк (например, фамилий). Отсортировать его по алфавиту и написать процедуру вставки новой фамилии после заданной так, чтобы алфавитный порядок не нарушился. Предусмотреть ситуацию, когда массив заполнен «до отказа» и вставка нового элемента невозможна. 6. Имеется железнодорожное расписание, содержащее номер рейса поезда, времена отправления и прибытия и станцию прибытия. Организовать поиск номера поезда, время отправления и прибытия, если задана станция. 7. Компания с целью определения спроса на свою продукцию организует некоторый опрос. Продукция – компакт-диски с записями шлягеров. Все опрашиваемые делятся на две группы в соответствии с полом. Каждый опрашиваемый должен назвать три песни, которые идентифицируются номерами от 1 до N (пусть N = 10). Файл с данными обрабатывается программой, которая должна печатать: 7.1. Список песен в порядке их популярности. Каждая строка содержит название песни и число упоминаний ее при опросе. Песни, которые ни разу не упоминались, в список не включаются. 7.2. Три наиболее популярные песни (хиты) и два списка (в соответствии с группами) с именами всех тех ответивших, которые поставили на первое место один из этих трех хитов.
Лабораторная работа №5 Рекурсия Цель работы: Познакомиться с одним из эффективных способов решения сложных задач – рекурсией. Общие сведения: Очень часто, разрабатывая программу, удается свести исходную задачу к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме. Например, вычисление функции F(n) может потребовать вычисления F(n-1) и еще каких-то операций. Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции. Алгоритм называется рекурсивным, если он прямо или косвенно обращается к самому себе. Часто в основе такого алгоритма лежит рекурсивное определение какого-то понятия. Например, о факториале числа N можно сказать, что N! = N*(N – 1)!, если N > 0 и N! = 1 если N = 0. Это – рекурсивное определение. Вот еще одно рекурсивное определение. 1. 3 коровы – это стадо коров. 2. Стадо из n коров – это стадо из n – 1 коровы и еще одна корова. Попробуем применить это определение для проверки, является ли стадом группа из пяти коров (обозначим ее К5). Объект К5 не удовлетворяет первому пункту определения, поскольку пять коров – это не три коровы. Согласно второму пункту К5 – стадо, если там есть одна корова, а остальная часть К5, назовем ее К4, – тоже стадо коров. Решение относительно объекта К5 откладывается, пока не будет принято решение относительно К4. Объект К4 снова не подходит под первый пункт, а второй пункт гласит, что К4 – стадо, если объект К3, полученный из К4 путем отделения одной коровы, тоже стадо. Решение о К4 тоже откладывается. Наконец, объект К3 удовлетворяет первому пункту определения, и мы можем смело утверждать, что К3– стадо коров. Теперь и о К4 можно утверждать, что это стадо, а значит, и К5 является стадом коров. Любое рекурсивное определение состоит из двух частей. Эти части принято называть базовой и рекурсивной частями. Базовая часть является нерекурсивной и задает определение для некоторой фиксированной части объектов. Рекурсивная часть определяет понятие через него же и записывается так, чтобы при цепочке повторных применений она редуцировалась бы к базе. Примеры 1. Задача. Написать рекурсивную программу поиска минимального элемента массива. Решение. Опишем функцию Pmin, которая определяет минимум среди первых n элементов массива а. Параметрами этой функции являются количество элементов в рассматриваемой части массива - n и значение последнего элемента этой части – а[n]. При этом если n>2, то результатом является минимальное из двух чисел – а[n] и минимального числа из первых (n-1) элементов массива. В этом заключается рекурсивный вызов. Если же n=2, то результатом является минимальное из первых двух элементов массива. Чтобы найти минимум всех элементов массива, нужно обратиться к функции Pmin, указав в качестве параметров значение размерности массива и значение последнего его элемента. Минимальное из двух чисел определяется с помощью функции Min, параметрами которой являются эти числа. Program Example _1;Const n=10;Type MyArray=Array[1..n] of Integer;Const a: MyArray = (4,2, -1,5,2,9,4,8,5,3);Function Min (a, b: Integer): Integer;Begin if a>b then Min:= b else Min:=a;End;Function Pmin(n, b: Integer): Integer;Begin if n = 2 then Pmin:= Min(n,a[1]) else Pmin:= Min(a[n], Pmin(n-1,a[n]));End;BEGIN Writeln(‘Минимальный элемент массива - ‘, Pmin(n,a[n]));END.2. Задача. Ханойские башни. Имеется три стержня А, В, С. На стержень А нанизано п дисков радиуса 1, 2,..., п таким образом, что диск радиуса i является i-м сверху. Требуется переместить все диски на стержень В, сохраняя их порядок расположения (диск с большим радиусом находится ниже). За один раз можно перемещать только один диск с любого стержня на любой другой стержень. При этом должно выполняться следующее условие: на каждом стержне ни в какой момент времени никакой диск не может находиться выше диска с меньшим радиусом. Решение. Предположим, что мы умеем перекладывать пирамиду из (n-1) диска. Рассмотрим пирамиду из n дисков. Переместим первые (n-1) дисков на стержень С (это мы умеем). Затем перенесем последний n-й диск со стержня А на стержень В. Далее перенесем пирамиду из (n-1) диска со стержня С на стержень В. Так как n-й диск самый большой, то условие задачи не будет нарушено. Таким образом, вся пирамида будет на стержне В. Аналогичным образом можно перенести n – 2, n – 3 и т. д. дисков. Когда n=1, осуществить перенос очень просто: непосредственно с первого стержня на второй. При этом для решения задачи будет достаточно 2n - 1 перекладываний. Program Example_2;Const k = 3;Var a,b,c: Char;Procedure Disk(n: Integer; a, b, c: Char);Begin if n>0 then begin Disk(n-1,a,c,b); Writeln(‘Диск ‘,n, ’ c ‘, a,’->’, b); Disk(n-1,c,b,a); end;End;BEGIN a:= ‘A’; b:= ‘B’; c:= ‘C’; Disk(k,a,b,c); ReadLn;END.Контрольные вопросы 1. На чем основан рекурсивный метод программирования? 2. В чем разница между «циклическим» и «рекурсивным» способами определения? Какой элемент является обязательным в рекурсивном определении? 3. Что такое «фрейм активации»? 4. К каким последствиям приводит «рекурсивное зацикливание»? 5. Какое условие должно обязательно присутствовать в любой рекурсивной процедуре? 6. Что такое явная и косвенная рекурсии? 7. Дайте рекурсивное определение целой степени числа N. Варианты заданий 1. Ввести последовательность чисел (окончание ввода – 0) и вывести их в обратной последовательности. Входные данные взять из текстового файла. 2. Используя команды write(x) лишь при x=0..9, написать рекурсивную программу печати десятичной записи целого положительного числа n. 3. Напишите рекурсивную функцию, которая возвращает среднее из n элементов массива чисел. 4. Найти первые N чисел Фибоначчи двумя способами: с помощью рекурсии и с помощью итерации. Сравнить эффективность алгоритмов. 5. Написать функцию сложения двух чисел, используя только прибавление единицы. 6. Написать функцию умножения двух чисел, используя только операцию сложения. 7. Вычислить сумму элементов одномерного массива. 8. Найти НОД (наибольший общий делитель) двух натуральных чисел. 9. Вычислить несколько значений функции Аккермана для неотрицательных чисел m и n:
10. Напишите рекурсивную функцию, которая вычисляет длину строки. 11. Написать функцию C(m,n) вычисления биномиальных коэффициентов
12. Проверить, является ли фрагмент строки с i-го по j-й символ палиндромом. 13. Вычислить произведение элементов одномерного массива. 14. Написать процедуру сортировки массива методом простого выбора. 15. Подсчитать количество цифр в заданном числе. 16. Написать функцию, проверяющую правильность имени в языке Pascal. 17. Написать функцию 18. В текстовом файле задана последовательность положительных чисел, за которой следует отрицательное число. Написать функцию без параметров для нахождения суммы этих положительных чисел. 19. Написать функцию без параметров, которая подсчитывает количество цифр в тексте, заданном в текстовом файле (за текстом следует точка). 20. Расстояния между городами заданы матрицей (Если между городами i,j есть прямой путь с расстоянием N, то элементы матрицы A(i,j) и A(j,i) содержат значение N, иначе 0). Написать программу поиска минимального пути для произвольной пары городов. 21. Вычислить определитель матрицы, пользуясь формулой разложения по первой строке:
где матрица Bk получается из A вычеркиванием первой строки и k-го столбца. 22. Написать функцию определения, является ли заданное натуральное число простым. 23. Реализовать рекурсивный алгоритм построения цепочки из имеющегося набора костей домино. 24. Расстояния между городами заданы матрицей (Если между городами i,j есть прямой путь с расстоянием N, то элементы матрицы A(i,j) и A(j,i) содержат значение N, иначе 0). Написать программу поиска минимального пути обхода всех городов без посещения дважды одного и того же города (задача коммивояжера). 25. Задан набор слов. Построить из них любую цепочку таким образом, чтобы символ в конце слова совпадал с символом в начале следующего. 26. Задан массив целых. Построить из них любую последовательность таким образом, чтобы последняя цифра предыдущего числа совпадала с первой цифрой следующего. 27. Для данного n напечатайте коэффициенты разложения полинома (1 + x)n. 28. Вычислить, используя рекурсию, выражение
29. Написать процедуру печати всех перестановок из n символов. 30. Написать процедуру перевода числа из десятичной системы счисления в двоичную.
Лабораторная работа №6 Линейные списки Цель работы: Получить практические навыки работы с динамическими переменными и динамическими структурами данных. Общие сведения Для работы с динамическими структурами данных используются указатели. Указатели представляют собой специальный тип данных. Они принимают значения, равные адресам размещения в оперативной памяти соответствующих динамических переменных. Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом. На самый первый элемент (голову списка) имеется отдельный указатель. Из определения следует, что каждый элемент списка содержит поле данных (оно может иметь сложную структуру) и поле ссылки на следующий элемент. После ссылки последнего элемента должно содержать пустой указатель (nil). Число элементов связанного списка может расти или уменьшаться в зависимости от того, сколько данных мы хотим хранить в нем. Чтобы добавить новый элемент в список, необходимо: 1. Получить память для него; 2. Поместить туда информацию; 3. Добавить элемент в конец списка (или начало). Элемент списка состоит из разнотипных частей (хранимая информация и указатель), и его естественно представить записью. Перед описанием самой записи описывают указатель на нее: Type { описание списка из целых чисел } PList = ^TList; TList = record Inf: Integer; Next: PList; end;Примеры Создание списка. Задача. Сформировать список, содержащий целые числа 3, 5, 1, 9. Определим запись типа TList с полями, содержащими характеристики данных – значения очередного элемента и адреса следующего за ним элемента PList = ^TList; TList = record Data: Integer; Next: PList; end;Чтобы список существовал, надо определить указатель на его начало. Опишем переменные.Var Head, x: PList;Создадим первый элемент: New(Head); { выделяем место в памяти для переменной Head } Head^.Next:= nil; { указатель на следующий элемент пуст (такого элемента нет) } Head^.Data:= 3; { заполняем информационное поле первого элемента }
Продолжим формирование списка, для этого нужно добавить элемент в конец списка. Введем вспомогательную переменную указательного типа, которая будет хранить адрес последнего элемента списка: x:= Head; {сейчас последний элемент списка совпадает с его началом}
New(x^.Next); { выделим области памяти для следующего (2-го) элемента и поместим его адрес в адресную часть предыдущего (1-го) элемента }
x:= x^.Next; { переменная x принимает значение адреса выделенной области. Таким образом осуществляется переход к следующему (2-ому) элементу списка }
x^.Data:= 5; { значение этого элемента } x^.Next:= nil; {следующего значения нет }
Остальные числа заносятся аналогично: New(x^.Next); { выделим области памяти для следующего элемента } x:= x^.Next; { переход к следующему (3-му) элементу списка } x^.Data:= 1; { значение этого элемента } x^.Next:= nil; {следующего значения нет } New(x^.Next); { выделим области памяти для следующего элемента } x:= x^.Next; { переход к следующему (4-му) элементу списка } x^.Data:= 9; { значение этого элемента } x^.Next:= nil; {следующего значения нет } Замечание. Как видно из примера, отличным является только создание первого (Head) элемента – головы списка. Все остальные действия полностью аналогичны и их естественно выполнять в цикле. Присоединение нового элемента к голове списка производится аналогично: ……………….. New(x); { ввод значения элемента x^.Data:= … } x^.Next:= Head; Head:= x; ……………….. В этом случае последний введенный элемент окажется в списке первым, а первый – последним. Просмотр списка. Просмотр элементов списка осуществляется последовательно, начиная с его начала. Указатель List последовательно ссылается на первый, второй и т. д. элементы списка до тех пор, пока весь список не будет пройден. При этом с каждым элементом списка выполняется некоторая операция– например, печать элемента. Начальное значение List – адрес первого элемента списка (Head). Digit – значение удаляемого элемента. List:= Head;While List^.Next <> nil do begin WriteLn(List^.Data); List:= List^.Next; { переход к следующему элементу; аналог для массива i:=i+1 } end;  ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...  Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...  Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...  Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
такие, что 
Найти наибольшее значение в этой последовательности после выбрасывания из нее всех членов со значением 
Числа 
– это измеренные в сотых долях секунды результаты n спортсменов в беге на 100 м. Составить команду из четырех лучших бегунов для участия в эстафете 4х100, т. е. указать одну из четверок натуральных чисел i, j, k, l такую, что сумма 
имеет наименьшее значение.
–целочисленный массив и 
и если входит, то каково значение p, для которого ap = b? Эту задачу мы назовем задачей поиска элемента.
(Low=1, High=10). Так как 6< 25. 20 18 17 15 12 8 6 5 3 5: меньше которых индексы элементы, только рассматривать можем далее>
(Low=1, High=4). 6>a[2], следовательно, первый и второй элементы из рассмотрения исключаем: 3 5 6 8 12 15 17 18 20 25.
(Low=3, High=4): 3 5 6 8 12 15 17 18 20 25. a[3] = 6! Элемент найден, его номер – 3.
по следующей формуле:
которая методом деления отрезка пополам (методом дихотомии) находит с точностью eps корень уравнения f(x) = 0 на отрезке [a,b] (
). Метод дихотомии определяется следующим образом. Если f(a) и f(b) имеют разные знаки, то между точками a и b существует корень R. Пусть 
– средняя точка в интервале 
Если f(m) = 0, то корень R=m. Если нет, то либо f(a) и f(m) имеют разные знаки 
, либо f(m) и f(b) имеют разные знаки 
. Если 
В противном случае он лежит в интервале 
Теперь выполним это действие для нового интервала – половины исходного интервала. Процесс продолжается до тех пор, пока интервал не станет меньше eps.
