C4 (высокий уровень, время – 60 мин)

Тема:  Обработка данных, вводимых в виде символьных строк (написать программу средней сложности из 30-50 строк).

Что нужно знать:

·    символьная строка – это цепочка символов, которая может обрабатываться как единое целое

·    для обращения к символу с номером i строки s используется запись s[i], это говорит о том, что строка – особый вариант массива, в котором хранятся символы

·    знак сложения при работе с символьными строками означает сцепку, объединение двух строк в одну (добавление второй строки в конец первой), например:

s := '123' + '456';  { получили '123456' }

·    с помощью функции Ord  можно получить код символа; цифры имеют коды от 48 (цифра 0) до 57 (цифра 9), например

k := Ord('1');     { получили 49 }

то же самое можно сделать с помощью преобразования типа (привести char к integer)

k := integer('1'); { получили 49 }

·    с помощью функции Chr можно сделать обратный переход: получить символ по его коду, например

c := Chr(49);   { получили символ '1' }

то же самое можно сделать с помощью преобразования типа (привести integer к char)

c := char(49);  { получили символ '1' }

·    для работы со строками в наиболее распространенных Паскаль-средах (Turbo Pascal, Borland Pascal, PascalABC, среда АЛГО)  используют стандартные функции (здесь s – это переменная типа string, символьная строка; n и r – целые переменные)

и процедуры

·    структура (в Паскале она называется «запись», record) – это  сложный тип данных, который может включать  в себя несколько элементов – полей;  поля могут иметь различный тип

·    записи в Паскале объявляются с помощью ключевого слова record; в простейшем случае можно выделить память под одну запись так:

var x: record

         name: string;

         code: integer;

       end;

эта запись состоит из двух полей: символьной строки name и целого числа code

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

·    для обращения к полям записи используют точку, например x.name означает «поле name записи x»

·    можно сразу объявить массив записей:

var Info: array[1..100] of record

         name: string;

         code: integer;

       end;

это 100 одинаковых записей, имеющих общее имя Info и расположенных в памяти рядом; в каждой структуре есть поля nаme и code; чтобы работать с полями записи с номером k используют обращения вида Info[k].name  и Info[k].code

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

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

·    сложность  имеет алгоритм с одним или несколькими простыми (не вложенными!)  циклами в каждом из которых выполняется N шагов (как при поиске минимального элемента)

·    количество операций для алгоритма, имеющего сложность , вычисляется по формуле , где a и b – некоторые постоянные

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

·    для алгоритма, имеющего  сложность , количество операций пропорционально квадрату размера массива, то есть, если N увеличить в 2 раза, то количество операций  увеличивается примерно в 4 раза (например, в программе используется два вложенных цикла, в каждом из которых N шагов); сложность  имеют простые способы сортировки массивов: метод «пузырька», метод выбора

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

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

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