Погода
Календарь
Январь 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 123456
78910111213
14151617181920
21222324252627
28293031  
Страницы сайта

Обработка символьных строк.

Решение задания требует знания следующих тем и понятий:

Работа со строками

  • строку можно представить, как одномерный массив, в котором хранятся символы;
  • для того чтобы обратиться к символу строки s с номером i (например, вывести его на экран) используется запись s[i]:
s:='лес';  
write(s[1]); {на экране буква 'л'}
  • при работе со строками используется операция конкатенации или объединения строк в одну; в качестве нее используется знак сложения (+), например:

s := ’56’ + ’78’; { получили ‘5678’ }

  • в кодовой таблице ASCII цифры имеют коды от 48(соответствует цифре 0) до 57 (соответствует цифре 9); функция Ord() служит для получения кода символа, например:

k := Ord(‘0’); { k = 48 }

  • то же самое можно сделать с помощью преобразования типа (перевод типа char к типу integer)
k := integer('0'); { k = 48 }
  • функция Chr() служит для обратного перевода: получения символа по его коду, например:
c := Chr(48);  { получили в с символ '0' }
  • то же самое можно сделать с помощью преобразования типа (привести тип integer к типу char)
c := char(48); { получили символ '0' }

Работа с записями

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

Сложность алгоритмов

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

  • временная сложность;
  • пространственная (емкостная) сложность (определяется количеством ячеек памяти, используемых в процессе его выполнения).

Одним из вариантов оценки сложности алгоритма является подсчет количества выполняемых в нем операций.

сложность O(N)

N — размер массива данных

если сложность алгоритма характеризуется, как O(N), это значит, что для больших N увеличение в два раза размера массива данных приведет к примерно такому же увеличению (в два раза) количества операций;

такая сложность O(N) характерна, например, для алгоритма с одним (или несколькими) простыми циклами без вложенности, в которых выполняется N итераций (проходов цикла);

примером алгоритма со сложностью O(N) может служить алгоритм поиска максимального элемента в одномерном массиве:

{поиск максимального элемента массива array из N элементов} 
...
max := array[1];
for i:=2 to N do
if array[i] < max
max := array[i];
writeln (max);
...
Подсчитаем количество операций для данного алгоритма: 
N — 1 операция присваивания счетчику цикла i очередного значения;
N — 1 операция сравнения счетчика со значением N;
N — 1 операция сравнения очередного элемента массива со значением max;
от 1 до N операций присваивания значения переменной max.

существует формула для определения количества операций для алгоритма со сложностью O(N):

p = a * N + b

где a и b – постоянные, которые имеют свои значения для определенных классов задач;

  • так, если задача решена двумя способами: в одном используется несколько циклов от 1 до N, а во втором используется только один цикл, то хотя оба алгоритма имеют сложность O(N), но эффективнее в большинстве случаев является алгоритм с одним циклом, так как постоянная a при подсчете количества операций будет больше в случае с алгоритмом с несколькими циклами.

сложность O(N2)

  • сложность алгоритма O(N2) означает, что при увеличении в два раза N количество операций возрастет примерно в четыре раза (т.е. количество операций пропорционально квадрату размера массива);
  • примером сложности O(N2) алгоритма является программа с двумя вложенными циклами, в каждом из которых N итераций (проходов); например, алгоритмы сортировки массивов методами «пузырька» или выбора.

алгоритм со сложностью O(N2)менее эффективен, чем алгоритм со сложностью O(N)

  • экспоненциальная сложность означает, что размер массива входит в показатель степени:

например сложность O(2N)

  • для больших N такие задачи не эффективны и не решаются за приемлемое время.

Типы алгоритмов в соответствии с их временной сложностью (перечислены с увеличением их сложности):

  • Постоянный тип — сложность O(1).
  • Логарифмический тип — сложность оценивается как O(log(n)).

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

  • Линейный тип — оценка равна O(n).
  • Квадратный тип — O(n2).

Свойственно алгоритмам, обрабатывающим все пары элементов данных.

  • Кубический, полиномиальный тип — O(n3), O(nm).
  • Экспоненциальный тип — O(tp(n)), t- константа,
  • p(n) — некоторая полиномиальная функция.
  • Факториальный тип — O(n!). Обладает наибольшей временной сложностью среди всех известных типов.
    Присуще алгоритмам, которые выполняют перебор всевозможных сочетаний элементов.

Top