3 Билет

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

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

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. Алгоритмический язык

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

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

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

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

3. Цикл «while»

4 Билет

Лексемы:

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

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

1. Ключевые слова

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

3. Метка

4. Константы

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

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

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

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

?

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

5 Билет

Основные типы 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)}

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

double8 байт 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.

Оператор	Пример	Описание	Эквивалентное выражение
+ +	i + +;	Постфиксная	i =i+1; или i+=1;
+ +	+ + i;	Префиксная	i =i+1; или i+=1;
- -	i - -;	Постфиксная	i =i-1; или i-=1;
- -	- - i;	Префиксная	i =i-1; или i-=1;

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

Пример.

float a, b=2, c=1, d=1;

a = b + c++;

cout << "\n a=" << a <<"\t c= "<< c;

// Даст результат a=3 c=2.

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

a = ++d + b;

cout << "\n a=" << a <<"\t d= "<< d;

// Даст результат a=4 d=2.

Используется префиксный инкремент. Сначала 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²-ас):(а+с)

начало

ввод данных

операторы

….

……

Вывод

Конец