Построение и анализ алгоритмов
Целочисленная арифметика
Натуральные числа.
Натуральными числами называются числа, полученные при счете. Обозначение:
N = {1,2,3,…n,…}
На множестве натуральных чисел можно ввести операции сложения и умножения. Это означает, что результатом введенной операции будет также натуральное число. Обозначения:
v c = a + b , где a – первое слагаемое, b – второе слагаемое, c – сумма,
v c = a * b , где a– первый сомножитель, b – второй сомножитель, c – произведение.
Аксиомы Пеано.
Аксиомы Пеано позволили формализовать арифметику, доказать многие свойства натуральных и целых чисел, а также использовать целые числа для построения формальных теорий рациональных и вещественных чисел.
ü 0 является натуральным числом;
ü Число, следующее за натуральным, тоже является натуральным;
ü 0 не следует ни за каким натуральным числом;
ü Если натуральное число a непосредственно следует как за числом b, так и за числом c, то b и c тождественны;
ü (Аксиома индукции.) Если какое-либо предложение доказано для 0 (база индукции) и если из допущения, что оно верно для натурального числа n, вытекает, что оно верно для следующего за n натурального числа (индукционное предположение), то это предложение верно для всех натуральных чисел.
Целые числа.
Целыми числами называются натуральные числа, им противоположные и ноль. Обозначение:
Z = {…, -n, … , -2, -1, 0, 1 , 2, …, n, …}
|
|
|
Определение. Числом, противоположным числу a называется число
(-1)*a
В результате появления отрицательных чисел и нуля стало возможным введение операции вычитания, которая, если строго ее определить, есть операция сложения, в которой второе слагаемое заменяется противоположным по знаку:
c = a – bßà c = a + (-b)
Результатом введенной операции также будет целое число (даже если a и b– натуральные числа). Обозначения:
c = a - b, где a – уменьшаемое,b – вычитаемое, c – разность.
Системы счисления.
Система счисления — символический метод записи чисел, представление чисел с помощью письменных знаков.
Система счисления:
· даёт представления множества чисел (целых и/или вещественных);
· даёт каждому числу уникальное представление (или, по крайней мере, стандартное представление);
· отражает алгебраическую и арифметическую структуру чисел.
Системы счисления подразделяются на:
· позиционные (двоичная, троичная, восьмеричная, десятичная, двенадцатеричная(счёт дюжинами), шестнадцатеричная, двадцатеричная, шестидесятеричная(единица измерения времени, углов и тд))
· непозиционные; (биномиальная, система остаточных классов, система счисления Штерна-Броко)
|
|
|
· смешанные. (степенные, показательные, факториальные, фибоначчиева)
Представление целыхчисел в памяти компьютера.
Целые числа являются простейшими числовыми данными, с которыми оперирует электронно-вычислительная машина. Для целых чисел существуют два представления: беззнаковое (только для неотрицательных целых чисел) и со знаком. Очевидно, что отрицательные числа можно представлять только в знаковом виде. Целые числа в компьютере хранятся в формате с фиксированной запятой.
o Для беззнакового представления все разряды ячейки отводятся под представление самого числа. Например, в байте (8 бит) можно представить беззнаковые числа от 0 до 255. Поэтому, если известно, что числовая величина является неотрицательной, то выгоднее рассматривать её как беззнаковую.
o Для представления со знаком самый старший (левый) бит отводится под знак числа, остальные разряды - под само число. Если число положительное, то в знаковый разряд помещается 0, если отрицательное - 1. Например, в байте можно представить знаковые числа от -128 до 127.
Дополнительный код.
Дополнительный код положительного числа равен прямому коду этого числа. Дополнительный код отрицательного числа m равен 2k-|m|, где k - количество разрядов в ячейке.
|
|
|
Дополнительный код используется для упрощения выполнения арифметических операций. Если бы вычислительная машина работала с прямыми кодами положительных и отрицательных чисел, то при выполнении арифметических операций следовало бы выполнять ряд дополнительных действий.
Для получения дополнительного k-разрядного кода отрицательного числа необходимо
1. модуль отрицательного числа представить прямым кодом в k двоичных разрядах;
2. значение всех бит инвертировать:все нули заменить на единицы, а единицы на нули(таким образом, получается k-разрядный обратный код исходного числа);
3. к полученному обратному коду прибавить единицу.
Пример:
Получим 8-разрядный дополнительный код числа -52:
00110100 - число |-52|=52 в прямом коде
11001011 - число -52 в обратном коде
11001100 - число -52 в дополнительном коде
Понятие типа данных.
Тип данных:
1) внутреннее представление данных в памяти компьютера;
2) множество значений, которые могут принимать величины этого типа;
3) операции и функции, которые можно применять к величинам этого типа.
|
Целочисленные типыданных в C++.
Shortint– короткий целый ( память – 2 байта)
int– целый (2 байта).
long– длинный целый (4 байта)
Целочисленное переполнение.
Целочи́сленноепереполне́ние— ситуация в компьютерной арифметике, при которой вычисленное в результате операции значение не может быть помещено в n-битный целочисленный тип данных. Различают переполнение через верхнюю границу представления и через нижнюю
Арифметические операции с целыми числами.
1) Сложение
2) Вычитание
3) Умножение
4) Целочисленное деление и нахождение остатка от деления
5) Возведение в степень
6)
Арифметика остатков по модулю.
?????????????????????????77
Побитовые операции и их свойства: побитовая конъюнкция,дизъюнкция, сложение по модулю 2, битовый сдвиг.
Операция поразрядная конъюкция(поразрядное и).
Бинарная операция, т.е. действует на два операнда, которые должны быть целочисленными.
Операция поразрядная дизъюкция (поразрядное или).
Бинарная операция, т.е. действует на два операнда, которые должны быть целочисленными.
XOR(сложение по модулю 2) – операция, которая принимает значение «истина» только если всего один из аргументов имеет значение «истина».
XOR обладает следующими свойствами:
· a XOR 0 = a
· a XOR a = 0
· a XOR b = b XOR a
· (a XOR b) XOR b = a
Операция сдвигов >>(вправо) и <<(влево).
Бинарная операция, т.е. действует на два операнда, которые должны быть целочисленными.
Над битовым представлением значении левого операнда выполняется действие – сдвиг. Правый операнд определяет величину поразрядного сдвига.
Числа с плавающей запятой
Вещественные числа в математике и в программировании.
Вещественное, или действительное число — математический объект, возникший из потребности измерения геометрических и физических величин окружающего мира, а также проведения таких вычислительных операций, как извлечение корня, вычисление логарифмов, решение алгебраических уравнений, исследование поведения функций.
Вещественные типы ( или типы с плавающей точкой ) представляют значения, имеющие дробную часть.
Представление вещественных чисел вдвоичной системе счисления. Хранение чисел с плавающей запятой в памяти компьютера: знак,мантисса, порядок.
Любое число N в системе счисления с основанием q можно записать в виде N = M .q^p, где M — множитель, содержащий все цифры числа (мантисса), а p — целое число, называемое порядком.
Такой способ записи чисел называется представлением числа с плавающей точкой.
—101.01 = —0.10101 . 211 (порядок 112 = 310)
0.000011 = 0.11 . 2-100 (порядок —1002 = —410).
Мантисса – это целое число фиксированной длины, которое представляет старшие разряды действительного числа.
Порядок – это степень базы (двойки) старшего разряда.
Отрицательный ноль.
−0 (отрицательный ноль) в программировании — число, возникающее при вычислениях с плавающей запятой (а также в некоторых вариантах представления целых со знаком).
В 1+7-битном представлении чисел со знаком, отрицательный ноль представляется двоичным значением 10000000 в прямом коде. В 8-битном одинарном обратном коде −0 представляется двоичным значением 11111111. В стандарте представления чисел с плавающей запятой IEEE 754, отрицательный ноль представляется нулевой экспонентой и мантиссой и знаковым битом равным единице.
Типы данных для чисел с плавающей запятой.
Float – вещественный одинарной точности (4 байта)
double – вещественный удвоенной точности (8 байт)
longdouble - вещественный максимальной точности (10 байт)
Литералыс плавающей запятой.
Литерал — это элемент программы, который непосредственно представляет значение.
Литералы с плавающей запятой задают значения, которые должны иметь дробную часть. Эти значения содержат десятичные точки (.) и могут содержать показатели степени.
Литералы с плавающей запятой имеют «мантиссу», которая определяет значение числа, «экспоненту», которая определяет порядок числа, и необязательный суффикс, задающий тип константы. Мантисса задается как последовательность цифр, затем точка, за которой следует необязательная последовательность цифр, представляющая дробную часть числа.
Показатель степени указывается с помощью символа e или E, которые имеют одинаковое значение, затем следует необязательный знак (+ или -) и последовательность цифр. Если указан показатель степени, десятичная точка в конце целых чисел не требуется, например 18E0.
По умолчанию литералы с плавающей запятой имеют тип double. С помощью суффиксов f или l (или F или L — регистр суффикса не учитывается) литерал можно определить как float или longdouble соответственно.
Операции над числами с плавающей запятой.
· Сложение ( вычитание )
1)Сравниваются порядки (характеристики) исходных чисел путем их вычитания р=р1-р2. При выполнении этой операции определяется, одинаковый ли порядок имеют исходные слагаемые.
2)Если разность порядков равна нулю, то это значит, что одноименные разряды мантисс имеют одинаковые веса (двоичный порядок). В противном случае должно проводиться выравнивание порядков.
3)Для выравнивания порядков число с меньшим порядком сдвигается вправо на разницу порядков Ар. Младшие выталкиваемые разряды при этом теряются.
4)После выравнивания порядков мантиссы чисел можно складывать (вычитать) в зависимости от требуемой операции.
5) Порядок результата берется равным большему порядку.
6)Если мантисса результата не нормализована, то осуществляются нормализация и коррекция значений порядка.
· Умножение
При умножении двух вещественных чисел в представлении с плавающей запятой порядки складываются, а мантиссы перемножаются.
· Деление
При делении вещественных чисел в представлении с плавающей запятой порядки вычитаются, а мантиссы делятся одна на другую.
Модуль с математическимифункциями.
<MATH.H>
· ABS(X) – модуль от Х (|X|).
· SQR(X) – возведение Х в квадрат.
· SQRT(X) – корень от Х.
· Sin, Cos или Arctg(X) — Х должен быть выражен в радианах (X=градусы*П/180).
· Sin X, Cos X, Arctg X.
· Exp(X) – экспонента в степени Х.
· Log(X) – десятичный логарифм в степени Х.
· Ln(X) – натуральный логарифм в степени Х.
· Exp(A*Ln(X)) – Х в степени А.
· Random(X) — случайное число X от 0 до X, где X целое и оно находится в диапазоне X<65536.
· Round(X) – округлённое вещественное число X в целое.
· Int(X) — целая часть числа X.
· Frac(X) — дробная часть числа Х.
· ODD(X) — ODD = True, если Х не чётное.
· PRED(X) — предыдущее значение Х.
· SUCC(X) — последующее значение Х.
Бесконечность и не число.
В математическом анализе, созданном на фундаменте исчисления бесконечно малых[⇨], вводится явно и абстракция бесконечно больших величин: ко множеству действительных чисел добавляются символы бесконечно удалённых точек +бескон и –бескон, применяющиеся для определения граничных значений сходимости.
NaN («нечисло») — одно из особых состояний числа с плавающей запятой. Используется во многих математических библиотеках и математических сопроцессорах. Данное состояние может возникнуть в различных случаях, например, когда предыдущая математическая операция завершилась с неопределённым результатом или если в ячейку памяти попало не удовлетворяющее условиям число.
К операциям, приводящим к появлению NaN в качестве ответа, относятся:
· все математические операции, содержащие NaN в качестве одного из операндов;
· деление нуля на ноль;
· деление бесконечности на бесконечность;
· умножение нуля на бесконечность;
· сложение бесконечности с бесконечностью противоположного знака;
· вычисление квадратного корня отрицательного числа;
· логарифмирование отрицательного числа.
Переполнение чисел с плавающей запятой.
В нашей системе при возникновении состояния "переполнение" результат операции заменяется максимально допустимым числом, а при потере значимости - нулем.
Погрешностьвычислений с плавающей запятой.
?????
Сравнение чисел с плавающей запятой.
????????????????????
Машинный эпсилон.
Машинное эпсилон — числовое значение, меньше которого невозможно задавать относительную точность для любого алгоритма, возвращающего вещественные числа. Абсолютное значение «машинного эпсилон» зависит от разрядности сетки применяемой ЭВМ, типа (разрядности) используемых при расчетах чисел, и от принятой в конкретном трансляторе структуры представления вещественных чисел (количества бит, отводимых на мантиссу и на порядок)
Существует и другое определение. Машинный эпсилон можно определить как минимальное положительное число, которое будучи прибавлено к единице даёт результат отличный от единицы. Читателю предлагается проверить эквивалентность этих определений самостоятельно.
Построение и анализ алгоритмов
Понятие алгоритма.
Алгоритмом называется точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи.Алгоритм решения вычислительной задачи представляет собой совокупность правил преобразования исходных данных в результатные.
Свойства алгоритмов.
Основными свойствами алгоритма являются:
§ детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;
§ результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;
§ массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;
§ дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений.
Вычислительная сложность алгоритма и её оценка.
Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти.
Использование заглавной буквы О (или так называемая О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n).
Асимптотическая нотация для вычислительной сложности.
Рассмотрение входных данных большого размера и оценка порядка роста времени работы алгоритма приводят к понятию асимптотической сложности алгоритма.
Среди типично встречающихся асимптотических оценок вычислительной сложности алгоритмов распространенными являются следующие функции:
§ линейная O(N) (время пропорционально увеличению данных);
§ квадратичная O(N2);
§ полиномиальная сложность O(NM), в частности, кубическая O(N3);
§ экспоненциальная сложность O(2N);
§ факториальная сложность O(N!);
§ логаримфическая сложность O(log(N)) (подразумевают логарифм по основанию 2);
§ линейно-логарифмическая сложность O(N * log(N)) ;
§ константная вычислительная сложность O(1) (время не зависит от количества данных).
Свойства асимптотическихобозначений.
· Если в правой части уравнения находится только асимптотическое обозначение (например n=O(n^2)), то знак равенства обозначает принадлежность множеству (n принадлежит O(n^2) ).
· Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x → 0 формула e^x – 1 = x + o(x) обозначает, чтоe^x – 1 = x + f(x) , где f(x) — функция, о которой известно только то, что она принадлежит множеству o(x). Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения.
· Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило: какие бы мы функции ни выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным. Например, запись x + o(x) = O(x) обозначает, что для любой функции f(x) принадлежит o(x), существует некоторая функцияg(x) принадлежащая O(x) такая, что выражениеx + f(x) = g(x) — верно для всех x.
· Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с предыдущим правилом.
Сложность в худшем случае, в лучшем случае и в среднем.
Рассматривают понятие временной сложности в трех случаях: худшем, лучшем и среднем. Худший случай соответствует наименее удачному набору входных данных, когда алгоритму для решения задачи приходится выполнить максимальное число элементарных операций. В лучшем случае набор входных данных обеспечит минимально возможное число операций. Средний случай определяется гораздо сложнее. Входные данные разбиваются на возможные группы, которыми они могут быть. Далее, определяется вероятность появления каждой группы. После чего досчитывается время работы алгоритма на данных каждой группы. Для нас наибольший интерес представляют наиболее и наименее благоприятные случаи.
Асимптотическая оценкапотребляемой памяти.
???????????????
Рекурсия
Рекурсивные определения, алгоритмы и функции.
Рекурсией называется ситуация, когда подпрограмма вызывает сама себя.
Основной метод построения рекурсивных алгоритмов – это метод декомпозиции. Идея метода состоит в разделении задачи на части меньшей размерности, получение решение для полученных частей и объединение решений. В общем виде, если происходит разделение задачи на b подзадач, которое приводит к необходимости решения a подзадач размерностью n/b.
Класс примитивно-рекурсивных функций определяется путем указания конкретных исходных функций (они называются базисными) и фиксированного множества операций над ними, применяемых для получения новых функций из ранее заданных.
В качестве базисных функций обычно берутся следующие:
· Функция следования [IMG];
· Функция тождества (функция проекции, или функция выбора аргументов)[IMG];
· Функция константы [IMG].
Допустимыми операциями над функциями являются операции:
· суперпозиции (подстановки)[IMG];
· примитивной рекурсии[IMG].
База рекурсии.
База рекурсии – это тривиальный случай, при котором решение задачи очевидно, то есть не требуется обращение функции к себе.
Простая и сложная рекурсия.
Мы будем говорить, что рекурсия простая, если вызов функции встречается в некоторой ветви лишь один раз. Простой рекурсии в процедурном программировании соответствует обыкновенный цикл.
Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией. При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать опережающее описание.
Переполнение стека вызовов.
В программном обеспечении переполнение стека возникает, когда в стеке вызовов хранится больше информации, чем он может вместить. Обычно ёмкость стека задаётся при старте программы/потока. Когда указатель стека выходит за границы, программа аварийно завершает работу
Итерационные и рекурсивные вычислительные процессы.
Итерационный процесс - последовательное приближение и проверка условия достижения искомого результата.
В итерационных алгоритмах необходимо обеспечить обязательное достижение условия выхода из цикла (сходимость итерационного процесса) . В противном случае произойдет зацикливание алгоритма.
Итерация обычно бывает более эффективной, чем рекурсия, поскольку для завершения шага итерации – в отличие от шага рекурсии – не требуется ощущать результатов выполнения последующих шагов.
При выполнении рекурсивной функции программа осуществляет многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока не будет получено тривиальное решение поставленной задачи.
Хвостовая рекурсия.
Хвостовая рекурсия — специальный случай рекурсии, при котором рекурсивный вызов функцией самой себя является её последней операцией. Подобный вид рекурсии примечателен тем, что может быть легко заменён на итерацию, что реализовано во многих оптимизирующих компиляторах. (Итерация в программировании — организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя.)
Хвостовая рекурсия часто применяется в программах на функциональных языках программирования. Многие вычисления на таких языках естественно выражать в виде рекурсивных функций, а возможность автоматической замены транслятором хвостовой рекурсии на итерацию означает, что по вычислительной эффективности она равна эквивалентному коду, записанному в итеративном виде.
Мемоизация и рекурсия с сохранением.
Мемоизация (запоминание, от англ. memoization (англ.) в программировании) — сохранение результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения компьютерных программ. Перед вызовом функции проверяется, вызывалась ли функция ранее:
· если не вызывалась, функция вызывается и результат её выполнения сохраняется;
· если вызывалась, используется сохранённый результат.
Мемоизация может использоваться не только для увеличения скорости работы программы. Например, она используется при простом взаимно-рекурсивном нисходящем синтаксическом разборе в обобщённом алгоритме нисходящего синтаксического анализа
Оценка вычислительной сложностирекурсивных алгоритмов.
Анализ рекурсивного алгоритма требует подсчета количества операций, необходимых для разбиения задачи на части, выполнения алгоритма на каждой из частей и объединения отдельных результатов для решения задачи в целом. Объединяя эту информацию и информацию о числе частей, мы можем вывести рекурентное соотношение для сложности алгоритма.
Анализируя алгоритм, можно получить представление о том, сколько времени займет решение данной задачи при помощи данного алгоритма. Для каждого алгоритма необходимо оценивать, насколько быстро решается задача на множестве (массиве) входных данных длины .
Одну и ту же задачу часто можно решить при помощи различных алгоритмов. Анализ алгоритмов дает инструмент для выбора алгоритма.
Сортировка массива
Задача сортировки массива.
Пусть есть массив из N элементов A(N).
Надо упорядочить N элементов (A[0],A[1],…,A[N-2],A[N-1]) данного массива.
При этом: 1) Справедливо только одно соотношение: a<b, a=b, a>b
2) Если a<bи b<c, то a<c (транзитивность)
Задачей алгоритма сортировки является перестройка первоначальной не отсортированной последовательности в отсортированную(по возрастанию или убыванию).
Сортировка пузырьком.
Расположим массив сверху вниз, от нулевого элемента – к последнему. Далее проходим по массиву снизу вверх. По пути сравниваются соседние элементы. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами. После нулевого прохода по массиву «вверху» оказывается минимальный элемент. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию. Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент.
Время сортировки растёт квадратично относительно количества элементов. Алгоритм не использует дополнительный памяти: все операции происходят «на месте». Устойчивый метод.
Сортировка вставками.
На (i+1)-ом шаге берем элемент A[i+1] и вставляем его в нужное место среди тех, что мы уже обработали (тем самым оставляя их отсортированными). Поиск происходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами и процесс повторяется.
Худшее число сравнений и пересылок оценивается как О(N^2). Время сортировки растет квадратично относительно количества элементов. Алгоритм не использует дополнительной памяти: все операции происходят «на месте». Хорошим показателе сортировки является то, что почти отсортированной массив будет досортирован очень быстро. Устойчивый метод.
Сортировка выбором.
Принцип состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. Алгоритм состоит из N последовательных шагов, начиная от нулевого и заканчивая (N-1)-м. На i-м шаге выбираем наименьший из элементов A[i]..A[N] и меняем его местами с A[i].
Вне зависимости от номера текущего шага i, последовательность А[0]…A[i] является упорядоченной. Таким образом, на (N-1)-м шаге вся последовательность, кроме A[N] оказывается отсортированной, а A[N] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.
Для нахождения наименьшего элемента из N+1 рассматриваемых элементов алгоритм совершает N сравнений. С учетом того, что кол-во рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций: О(N^2)
Время сортировки растет квадратично относительно количества элементов.
Алгоритм не использует дополнительной памяти: все операции происходят «на месте».
Неустойчивый метод.
Оценка вычислительной сложности алгоритмов сортировки массива.
Критериями для сравнительной оценки качества алгоритма сортировки являются объём используемой памяти и время работы программы.
Теоретическая сложность алгоритма O(N) – величина порядка N.
Быстрые алгоритмы сортировки
Принцип «разделяй и властвуй» в программировании и синтез быстрых алгоритмов сортировки.
Разделяй и властвуй в информатике — важная парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче; разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
Сортировка слияниями.
Построена на принципе «разделяй-и-властвуй». Вместо разделения по опорному элементу массив просто делится пополам.
Пусть имеются два уже отсортированных подмассива, надо слить их в один массив , тоже отсортированный.
Сравниваем первые элементы подмассивов. Меньший помещаем в вспомогательный буфер, а следующий за ним элемент берём для следующего сравнения. Продолжаем так, пока один из подмассивов не закончится. Тогда остаток другого приписываем сзади к результату.
1) Сравниваем первые элементы подмассивов: A[0] и B[0]: (A[0] = 4) > (B[0] = 2).
2) Записываем в буферный массив элемент B[0], после чего переходим к элементу B[1] и его сравниваем c A[0]: (A[0] = 4) < (B[1] = 7).
3) Записываем в буферный массив элемент A[0], после чего переходим к элементу A[1] и его сравниваем с B[1]: (A[1] = 20) > (B[1] = 7).
4) Записываем в буферный массив элемент B[1].
5) Теперь подмассив B пуст, приписываем к буферному массиву оставшийся элемент подмассива A.
Быстрая сортировка Хоара.
Общая идея алгоритма состоит в следующем:
· Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность
· Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие».
· Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.
Сортировка подсчётом за линейное время.
Иногда сортируемые элементы имеют небольшой диапазон возможных значений. Например, если необходимо отсортировать список натуральных чисел, каждое из которых не более трех-пяти разрядов в длину. Однако количество сортируемых чисел настолько велико, что нужно обработать список за линейное время.
Исходная последовательность чисел длины n, а в конце отсортированная, хранится в массиве A. Также используется вспомогательный массив C с индексами от 0 до k-1 изначально заполняемый нулями.
Последовательно пройдём по массиву A и запишем в C[i] количество чисел, равных i.
Теперь достаточно пройти по массиву С и для каждого числа number из диапазона допустимых значений последовательно записать в массив А число number C[number] раз.
Строковые алгоритмы
Хранение символов в памяти компьютера.
В вычислительных машинах символы не могут храниться иначе, как в виде последовательностей бит (как и числа). Для передачи символа и его корректного отображения ему должна соответствовать уникальная последовательность нулей и единиц. Для этого были разработаны таблицы кодировок.
Количество символов, которые можно задать последовательностью бит длины n, задается простой формулой C(n) = 2^n. Таким образом, от нужного количества символов напрямую зависит количество используемой памяти.
Кодировки символов.
Каждая буква принадлежит определенному алфавиту, в котором символы следуют друг за другом и, следовательно, могут быть пронумерованы последовательными целыми числами. Каждой букве можно сопоставить целое положительное число и назвать его кодом символа. Соответствие букв определенного алфавита с числами-кодами формирует так называемую таблицу кодирования. Другими словами, каждый символ конкретного алфавита имеет свой числовой код в соответствии с определенной таблицей кодирования.
ASCII-код.
Кодировка символов (часто называемая также кодовой страницей) – это набор числовых значений, которые ставятся в соответствие группе алфавитно-цифровых символов, знаков пунктуации и специальных символов.
Длякодировкисимволовв Windows используетсятаблица ASCII (American Standard Code for Interchange of Information).
В ASCII первые 128 символов всех кодовых страниц состоят из базовой таблицы символов. Первые 32 кода базовой таблицы, начиная с нулевого, размещают управляющие коды.
Строка как массивсимволов.
При определении массива символов необходимо сообщить компилятору требуемый размер памяти.
Компилятор также может самостоятельно определить размер массива символов, если инициализация массива задана при объявлении строковой константой.
Представление строк в C.
В программе строки могут определяться следующим образом:
ü как строковые константы;
ü как массивы символов;
ü через указатель на символьный тип;
ü как массивы строк.
Строки представляются последовательностью изображений символов, заключенных в кавычки.
Ввод и вывод строк.
Ввод строки (прототип функции описан в файле stdio.h):
char * gets (char * string);
Действие: считывает строку stringиз стандартного входного потока (stdin) и помещает её массив, указанный аргументом string. Чтение строки производится пока не будет встречен символ «переход на новую строку», или не будет достигнут конец файла.
Возвращает: в случае успешного чтения строки, возвращается указатель на массив, в который помещены считанные данные (возвращается аргумент string).
Вывод строки ( прототип ф-ции описан в файле stdio.h):
intputs(constchar * string);
Действие: записывает строку string в стандартный поток вывода (stdout). После вывода строки производится переход на новую строку (вывод символа «новая строка»).
Возвращает:
· Неотрицательное число, если вывод прошёл успешно.
· EOF – в случае ошибки.
Для функции puts() наличие нуль-символа (‘\0’) в конце строки является обязательным. В противном случае программа может завершиться аварийно.
Операции со строками: доступ кэлементам, конкатенация.
charthisChar = string1[n] – ДОСТУП К ЭЛЕМЕНТУ СТРОКИ
Конкатена́ция — операция склеивания объектов линейной структуры, обычно строк. Например, конкатенация слов «микро» и «мир» даст слово «микромир».
Операция конкатенации определяется для типов данных, имеющих структуру последовательности (список, очередь, массив и ряд других). В общем случае, результатом конкатенации двух объектов и является объект , полученный поочерёдным добавлением всех элементов объекта , начиная с первого, в конец объекта .
Из соображений удобства и эффективности различают две формы операции конкатенации:
1. Модифицирующая конкатенация. Результат операции формируется в левом операнде.
2. Немодифицирующая конкатенация. Результатом является новый объект, операнды остаются неизменными.
Поиск подстроки в строке.
Поиск информации — одно из основных использований компьютера. Одна из простейших задач поиска информации — поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна — она применяется в текстовых редакторах, СУБД, поисковых машинах и т. п.
В задачах поиска традиционно принято обозначать шаблон поиска как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»). Также обозначим через Σ алфавит, на котором проводится поиск.
Дата добавления: 2018-05-12; просмотров: 968; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!