1. Понятие алгоритма. Свойства алгоритма.

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

Свойства:

- дискретность – процесс решения задачи должен быть представлен в виде последовательности шагов, каждый из которых можно назвать командой, или инструкцией. Каждая команда рассматривается как одно целое.

- понятность – команды алгоритма должны быть понятны исполнителю. Для записи алгоритма в этом случае используют систему команд – набор правил записи команд, понятных пользователю.

- определенность – команды, образующие алгоритм, должны быть однозначными. Результат их выполнения не должен зависеть от факторов, не учтенных в алгоритме явно.

- результативность – при корректных начальных данных алгоритм должен заканчивать работу и выдавать результат.

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

Способы записи:

1. словесная форма записи

2. комбинации базовых алгоритмических структур. Таких структур всего три: следование, ветвление и цикл. Наличие одного входа и одного выхода.

3. графический – в виде блок-схемы

4. через метаязык или псевдокод, когда запись алгоритма формализована частично

5. через алгоритмические языки

6.на языке программирования

8. ОДНОРОДНЫЕ ТИПЫ. ВИДЫ ОДНОРОДНЫХ ТИПОВ: МАССИВ, СТРОКА. ХАРАКТЕРИСТИКА ОСНОВНЫХ СОСТАВЛЯЮЩИХ ОДНОРОДНЫХ ТИПОВ.

Массив – это пример сложного (структурированного) типа. Регулярный тип (массив) – это сложный тип с однородной структурой фиксированного размера и прямым вычисляемым доступом к элементам. Размер структуры фиксируется при описании массива. Тип массив –для отображения данных с однородными элементами, имеющих одну природу. Как следствие, все элементы последовательности следуют один за другим. Все значение массива: совокупность всех значений, между которыми нет свободных участков памяти. Физический смысл – адрес, логический – номер элемента. По номеру – вычисление адреса элемента, по которому можно обратится к элементу. Транслятор по номеру вычисляет адрес, а процессор, получая адрес, ведет вычисления и проводит операции. У совокупности массив есть имя – xi, где i – номер элемента.

Значением «строкового» типа является последовательность символов (слово строковый заключено в кавычки, так как в Си явно такой тип не определен и, говоря о строковом типе, мы имеем в виду тип данных, обладающий свойствами строкового типа). «Строковый» тип (или просто строка) в Си рассматривается как подмножество типа массив. Строка задается одномерным массивом, элементы которого символы, последний символ массива – ‘\0’. Эта «нуль-литера», кодируемая нулевым байтом, является признаком конца строки. Литера ‘\0’ также как другие символы входит в строку. Размер строки (количество

символов) определяется решаемой задачей и ограничивается доступным объемом памяти.

Так как строковый тип – это особый массив, то для строки сохраняются все свойства регулярного типа (т.е. над отдельными элементами можно выполнять операции, допустимые для базового типа). С «нуль-литерой» можно работать как и с остальными символами (не забывая о ее основном назначении).

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

текста надо стремиться к тому, чтобы текст занимал минимально необходимый объем памяти, и выбранная структура предоставляла средства для быстрого (непосредственного) обращения к элементам текста, которыми, как правило, являются его слова. Таким требованиям отвечает структура данных – массив.

Текст можно представить:

- двумерным массивом - матрицей, строка которой это слово текста, оканчивающееся символом конца строки-‘\0’. Количество столбцов равно максимальной длине слова плюс один (символ ‘\0’). Количество строк равно максимальному числу слов в тексте. Обращение к строке матрицы это обращение к слову. Чтобы создать такую структуру, надо читать текст посимвольно, помещая каждое очередное слово в новую строку матрицы и добавляя к слову символ ‘\0’.

- одномерным массивом – строкой. Такая структура полностью соответствует внешнему представлению текста. Размер массива равен максимальной длине исходного текста с учетом

разделителей. Чтобы обратиться к слову, необходимо последовательно просматривать символы массива, обнаруживая очередной символ-разделитель, который завершает текущее слово, за ним начинается новое слово. Так продолжаем, пока очередное слово не завершится признаком конца строки. Для

создания массива-строки можно использовать функцию gets из библиотеки stdio.h – cчитывание строки из стандартного входного файла. Исходный текст должен завершаться символом новой строки ’\n’, который не включается в результирующую строку, символ ‘\0’ добавляется к строке автоматически. Также можно использовать функцию scanf со спецификацией преобразования %s, «нуль-литера» добавляется к строке автоматически.

Для выделения слова из строки можно использовать функцию работы со строками strtok.