Программная реализация стека на основе статического массива.

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

Понятие сложности алгоритма, оценки времени исполнения.

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

Время поиска оценивается как О(n) (O большое от n)

O(log n) потребуется 20 микросекунд, O(n²) – более 12 дней

Если n – длина строки, то <кол-во операций>=2*n² - для сложения матриц, 3² (n²) раз – для перемножения матриц.

2*n³ - алгоритм кубической сложности О(n³).

O() показывает исключительно асимптотику!

Основание логарифма не пишется.

Пусть есть O(log₂ n).

log ₂ n = log ₃ n / log ₃ 2,

O(log ₂ n) = O(log ₃ n)

Общая классификация вычислительных алгоритмов.

Вычислительные алгоритмы – для вычисления математических объектов(констант, функций, уравнений и тд)

1. Теория чисел – вычисление констант и математических функций

2. Решение алгебраических задач

3. Нахождение корней уравнений

4. Приближение функций

5. Вычислит. и геометрия и др.

 

 

Точность представления чисел.

Для реальных вычислений нужно использовать тип double.

Нормальной формой числа с плавающей запятой называется такая форма, в которой мантисса (без учёта знака) в десятичной системе находится на полуинтервале [0; 1). Распространена также другая форма записи — нормализованная, в которой мантисса десятичного числа принимает значения от 1 (включительно) до 10 (не включительно), а мантисса двоичного числа принимает значения от 1 (включительно) до 2 (не включительно).

Число одинарной точности (float) — компьютерный формат представления чисел, занимающий в памяти одно машинное слово (в случае 32-битного компьютера — 32 бита или 4 байта). Используется для работы с вещественными числами везде, где не нужна очень высокая точность.

Число двойной точности (double) — компьютерный формат представления чисел, занимающий в памяти два машинных слова (в случае 32-битного компьютера — 64 бита или 8 байт). Часто используется благодаря своей неплохой точности, даже несмотря на двойной расход памяти и сетевого трафика относительно чисел одинарной точности.

 

 

4. Вычисление «машинного нуля».

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

#include <stdio.h>
void main ()

{
float e, e1;
int k=0;
e=1.0;
m: e=e/2.0;
e1=e+1.0;
k++;
if (e1>1.0) goto m;
printf ("\n Число делений на

2 %6d\n", k);
printf ("машинный нуль

%e\n", e);
}

 

 

Понятие стека. Операции над стеком.

Стек – это последовательный список переменной длины, включение и исключение элементов из которого выполняется только с одной стороны(вершины) (FILO).

Операции:

- включение нового элемента

- исключение элемента

- определение текущего числа эл-ов в стеке

- очистка стека

- неразрушающее чтение из вершины стека

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

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

 

 

Программная реализация стека на основе статического массива.

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

На уровне машинных команд существуют функции push и pop, в основе организации исполняемой среды один из 4 базовых регистров называется стековым и работает по стековому принципу, поэтому стек является основной структурой, используемой при организации компьютерных процессов.