Алгоритмы и их характеристики.

Разработка алгоритмов:

1. Определение входа-выхода

2. Осознание идеи связи входа-выхода (тела программы)

3. Описание этой идеи

Свойства алгоритмов:

1. Вход

2. Выход

3. Определённость инструкций

4. Выполнимость инструкций

5. Конечность алгоритма

6. Массовость

Критерии сравнения алгоритмов:

1. Размер входа

2. Временна́ я сложность - T(n)

3. Емкостная сложность - E(n)

4. Алгоритм порядка f(n) - O(f(n))

Описание алгоритмов:

1. Описание блок-схемами

2. Псевдокод

3. Алгоритмический язык

4.

Управляющие структуры.

Минимальный пакет операторов:

1. Структуры следования

2. Развилки (условия if-else)

3. Цикл «while»

Билет

Лексемы:

1) Идентификатор

2) Служебные символы:

a) Ключевые слова

b) Спец. символы: +, -, <, >, < =, > =, знаки операций, знаки разделителей, пробелы

3. Метка

4. Константы

В записи лексической единицы не допускаются пробелы!

Между двумя лекс. единицами, которые не являются математическими символами/пробелами, нужен пробел!

Концепция типов данных:

Переменная, константа, выражение, функция принадлежит какому-либо типу.

?

Тип = {множества: констант, переменных, функций, данных, операций} + {размер области памяти, способ обработки данных}

Билет

Основные типы C++:

1. Стандартные

2. Сложные

int, char, bool float, double, longdouble

| |

целые |

| |

АРИФМЕТИЧЕСКИЕ

Целый тип:

1. Операции: {+₀, -₀; *, /, %; +, -; < <, > >; <, < =, >, > =; ==,! =}

2. Функции: {abs(x), srand(x), rand()}

int 4 байта -2147483648 – 2147483647

short, long, signed, unsigned

shortint 2 байта

longint 8 (4) байта

#include < cstdlib>

0xABC - 16ичная система

0123 - 8ичная система

123 - 10ичная система

Вещественный тип:

1. Операции: {+₀, -₀; *, /; +, -; < =, > =, <, >; ==,! =}

2. Функции: {fabs(x), sin(x), cos(x), log(x), ln(x), lg(x), exp(x), atan(x), asin(x), acos(x), pow(a, x), sqrt(x)}

float 4 байта 1, 17*10^-38 ≤ |x| ≤ 3, 4*10³⁸

double 8 байт 2, 2*10^-308 ≤ |x| ≤ 1, 7*10³⁰⁸

#include < cmath>

Символьный тип:

char 1 байт

unsigned char 0-255

#include < cctype>

1. isalpha(x) – x буква?

2. isalnum(x) – x буква/цифра?

3. isdigit(x) – x цифра?

4. iscntrl(x) – x управляющий символ?

Логический тип:

Операции: {!; <, >, < =, > =; ==,! =; & &, ||}

Булева алгебра

№6. Выражение в C++. Тип выражения. Приоритеты операций. Префиксные и постфиксные операции. Совместимость типов. Преобразование типов. Вычисление выражений.

Выражение.
Состоит из одного или более операндов, в простейшем случае – из одного литерала или объекта.

Типы выражения:

-логические выражения,

-арифметические выражения,

-выражения сравнения

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

Таблица приоритетов в С++:

Операции инкремента (++) и декремента (--)

В языке C++ предусмотрены две уникальные операции, которые увеличивают или уменьшают значение переменной на 1.

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

Пример.

Используется постфиксный инкремент. Сначала произойдет сложение b и c, результат запишется в а, затем с будет увеличена на 1

Используется префиксный инкремент. Сначала d будет увеличена на 1 (и станет равной 2), затем произойдет сложение d и b, результат запишется в а

Преобразование основных типов

В C++ не существует операций, которые, например, обеспечивали бы сложение или умножение операндов различных типов. Выражения вызова функций также требуют соответствия типа параметров типу параметров определения и прототипа.

В общем случае, при определении значения выражения могут возникать следующие ситуации:

1.Присвоение " большему типу" значения " меньшего типа". Безопасное присвоение, гарантирует сохранение значения.

2.Присвоение " меньшему типу" значения " большего типа". Потенциально опасное присвоение, грозит потерей информации.

3.Преобразование значения из " меньшего типа" в " больший тип". Называется расширением типа.

4.Преобразование значения из " большего типа" в " меньший тип". Называется сужением типа. Является опасным преобразованием.

Корректное выполнение действий со значениями различных типов в безопасных случаях и в ряде опасных случаев обеспечивается благодаря реализованной в C++ системе преобразования типов. В арифметическом выражении тип результата выражения определяется самым " широким" типом среди всех образующих выражение операндов. Этот тип называют результирующим типом выражения. К этому типу преобразуются все остальные операнды.

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

№ 7. Простейшие операторы в c++ (запись операторов, их назначение, выполнение).
Операторы ввода-вывода с использованием стандартных потоков; оператор присваивания;
составной оператор. Линейные участки алгоритма.

Все операторы языка СИ могут быть условно разделены на следующие категории:

- условные операторы, к которым относятся оператор условия if и оператор выбора switch;

- операторы цикла (for, while, do while);

- операторы перехода (break, continue, return, goto);

- другие операторы (оператор " выражение", пустой оператор).

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

Операторы ввода - вывода данных также являются операторами – выражениями.

Операторы используют непосредственно входные и выходные потоки из библиотеки классов входных и выходных потоков, описания которых находятся в заголовочном файле iostream.

Препроцессорная директива

#include < iostream>

Подключает к программе библиотеку средств ввода-вывода, построенную на основе механизма классов.

Для работы со стандартными потоками в режиме форматного ввода-вывода определены два оператора:

cin - оператор обработки входного потока

cout - оператор обработки выходного потока

При обращении к оператору cout возможны две формы задания первого параметра:

cout< < *форматная строка< < список аргументов;

cout< < указателъ на форматную строку< < список аргументов;

В обоих случаях оператор cout преобразует данные из внутреннего представления в символьный вид в соответствии с форматной строкой и выводит их в выходной поток.

Форматная строка ограничена двойными кавычками и может включать произвольный текст. Текст и управляющие символы из форматной строки просто копируются в выходной поток. Второй вариант предполагает, что первый фактический параметр - это указатель типа char *, a сама форматная строка определена в программе как обычная строковая константа или переменная. Так же в качестве параметров оператора cout включают выражения, значения которых должны быть выведены из программы.

Форматный ввод из входного потока осуществляется оператором cin.

При обращении к оператору cin возможны две формы задания первого параметра:

cin> > форматная строка> > список аргументов;

cin> > указатель_на_форматную _строку> > список_аргументов;

Оператор cin читает последовательности кодов символов (байты) из входного потока и интерпретирует их в соответствии с форматной_строкой как целые числа, вещественные числа, одиночные символы, строки. В первом варианте вызова функции форматная строка размещается непосредственно в списке фактических параметров. Во втором варианте вызова предполагается, что первый фактический параметр - это указатель типа char *, адресующий собственно форматную строку. Форматная строка в этом случае должна быть определена в программе как обычная строковая константа или переменная.

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

Составной оператор представляет собой два или более операторов, объединенных с помощью фигурных скобок; он называется также блоком.в конце составного оператора точка с запятой не ставится. Выполнение составного оператора заключается в последовательном выполнении составляющих его операторов.

Все операторы языка СИ, кроме составных операторов, заканчиваются точкой с запятой "; ".

Операция присваивания в Си++ также является выражением, в связи с этим различаются операнды, которым можно присвоить новое значение и операнды, значение которых не может меняться. Чтобы операнду можно было присвоить значение, ему должна соответствовать область памяти и компилятору должен быть известен адрес этой памяти.

Присваивание в C++ отличается от аналогичных операций в других языках программирования тем, что, как и другие операторы C++, оператор присваивания не обязан стоять в отдельной строке и может входить в более крупные выражения. В качестве результата оператор возвращает значение, присвоенное левому операнду.
Например, следующее выражение вполне корректно:
valuel = 8 * (value2 = 5);
В данном случае сначала переменной value2 будет присвоено значение 5, после чего это значение будет умножено на 8 и результат 40 будет записан в переменную value1. В результате многократного использования оператора присваивания в одной строке может получиться трудночитаемое, но вполне работоспособное выражение.
Рассмотрим первый прием, который часто применяется для присваивания нескольким переменным одинакового значения:
valuel = value2 = value3 = 0;
Второй прием часто можно встретить в условных выражениях цикла while, как в следующем примере:
while ((с = getchar())! = EOF) {
. }
В линейном алгоритме операции выполняются последовательно, в порядке их записи. Каждая операция является самостоятельной, независимой от каких-либо условий.

Линейные алгоритмы имеют место, например, при вычислении арифметических выражений, когда имеются конкретные числовые данные и над ними выполняются соответствующие условию задачи действия.

На схеме блоки, отображающие эти операции, располагаются в линейной последовательности.

блок – схема алгоритма вычисления арифметического выражения: у=(b²-ас): (а+с)

начало

ввод данных

операторы

….

……

Вывод

Конец

Билет

Условный оператор if используется для разветвления процесса вычислений на два направления.

Его структурная схема:

Формат оператора: if (выражение) оператор_1; [ else оператор_2; ]

Сначала вычисляется выражение, которое может иметь арифметический тип или тип указателя. Если оно не равно 0 (имеет значение true), выполняется первый оператор, иначе – второй. После этого управление передается на оператор, следующий за условным.

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

Конструкция с отсутствующей ветвью else называется «пропуск оператора», поскольку оператор, следующий за условием либо выполняется, либо пропускается в зависимости от выполнения условия. (пример if (a> b) b=1;)

Если требуется проверить несколько условий, их объединяют знаками логических операций:

& & - И; || - ИЛИ (пример if (a> b & & (a> d || a==0)) b++;)

В случае нескольких вложенных условий else относится к ближайшему if и фигурные скобки необязательны (пример if (a< b) if (a< c) m=a; else m=c; else if (b< c) m=b; else m=c;)

Конструкции типа if (a< b) max=b; else max=a; можно записать в виде условной операции:

max = (a< b)? b: a;

Если какая-то переменная используется только внутри условного оператора, рекомендуется объявить её внутри скобок.

Оператор выбора switch предназначен для разветвления процесса вычислений на несколько направлений. Его структурная схема:

Формат оператора: switch (выражение) {

case константное_выражение_1: [ список_операторов_1 ]

case константное_выражение_2: [ список_операторов_2 ]

…

[ default: операторы]

}

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

Выход из переключателя выполняется с помощью break или return. Оператор break выполняет выход из самого внутреннего из объемлющих его операторов swith, for, while и do. Оператор return выполняет выход из функции, в теле которой он написан.

Все константные выражения должны иметь разные значения, но быть одного и того же целочисленного типа. Несколько меток могут следовать подряд. Если совпадения не произошло, выполняются операторы после слова default (а при его отсутствии управление передаётся следующему за switch оператору).

Примечание: В случае синтаксической ошибки в слове default сообщение об ошибке не выдаётся, поскольку компилятор воспримет это слово как допустимую метку оператора.

Оператор безусловного перехода goto имеет формат: goto метка;

В теле той же функции должна присутствовать конструкция вида: метка: оператор;

Оператор goto передаёт управление на помеченный оператор. Метка – это идентификатор, областью видимости которого является функция, в теле которой он задан.

Оператор goto используется в двух случаях:

1.Принудительный выход вниз по тексту программы из нескольких вложенных циклов или переключателей;

2.Переход из нескольких мест функции в одно (например, если перед выходом из функции необходимо всегда выполнять какие-либо действия)

Не следует передавать управление внутрь операторов if, switch и циклов. Нельзя переходить внутрь блоков, содержащих инициализацию переменных, на операторы, использующие эти переменные, поскольку в этом случае инициализация не будет выполнена.(… goto label; … int a=5; label: int b=a; …)

Оператор перехода к следующей итерации цикла continue пропускает все операторы, оставшиеся до конца тела цикла, и передает управление на начало следующей итерации.

Билет

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

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

Начальные установки могут явно не присутствовать в программе, их смысл состоит в том, чтобы до входа в цикл задать значения переменным, которые в нём используются.

Цикл завершается, если условие его продолжения не выполняется. Возможно принудительное завершение как текущей итерации, так и цикла в целом. Для этого служат операторы break, continue, return и goto.

Один проход цикла называется итерацией. Проверка условия выполняется на каждой итерации либо до тела цикла (тогда цикл с предусловием), либо после тела цикла (тогда цикл с постусловием). Разница между ними состоит в том, что тело цикла с постусловием выполняется хотя бы один раз, после чего проверяется, надо ли выполнять его ещё раз. Проверка необходимости выполнения цикла с предусловием делается до цикла, поэтому возможно, что он не выполнится ни разу.

Цикл с предусловием while имеет вид: while (выражение) оператор

Выражение определяет условие повторения тела цикла, представленного простым или составным оператором. Выполнение оператора начинается с вычисления выражения. Если оно истинно, выполняется оператор цикла. Если при первой проверке выражение равно false, цикл не выполнится ни разу. Выражение вычисляется перед каждой итерацией цикла.

В круглых скобках после ключевого слова while можно вводить описание переменной. Областью её действия является цикл.

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

Цикл с постусловием do while имеет вид: do оператор while выражение

Сначала выполняется простой или составной оператор, составляющий тело цикла, а затем вычисляется выражение. Если оно истинно, тело цикла выполняется ещё раз. Цикл завершается, когда выражение станет равным false или в теле цикла будет выполнен какой-либо оператор передачи управления.

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

Цикл с параметром for используется, когда заранее известно число повторений, и имеет следующий формат: for (инициализация; выражение; модификации) оператор;

Инициализация используется для объявления и присвоения начальных значений величинам, используемым в цикле. В этой части можно записать несколько операторов, разделённых запятой (операцией «последовательное выполнение»). Областью действия переменных, объявленных в инициализации цикла, является цикл. Инициализация выполняется один раз в начале исполнения цикла.

Выражение определяет условие выполнения цикла: если его результат, приведённый к типу bool, равен true, цикл выполняется. Цикл с параметром реализован как цикл с предусловием.

Модификации выполняются после каждой итерации цикла и служат обычно для изменения параметров цикла. В части модификаций можно записать несколько операторов через запятую. Простой или составной оператор представляет собой тело цикла. Любая из частей оператора for может быть опущена, но точки с запятой надо оставить на своих местах.