Алгоритм и его свойства.
Для выполнения алгоритма исполнитель должен понимать и выполнять шаги алгоритма. Набор простейших предписаний алгоритма называется алгоритмическим языком. Алгоритмические языки бывают разной степени детализации, но набор команд всегда ограничен. Свойства алгоритма: Конечность-алгоритм представляет собой конечную последовательность действий. Дискретности-шаги алгоритма должны быть всегда четко отделены друг от друга. Массовость- алгоритм решает задачу из круга таких же ближних задач. При изменении алгоритма можно получить решение другой задачи из этого круга. Направленность-алгоритм всегда направлен на получение какого либо результата. Детерминированность (однозначность)-при вводе одних и тех же исходных данных должен получаться один и тот же результат.
Машинный язык. Трансляция.
Исполнителем алгоритма может быть компьютер, имеющий свой машинный язык. Состоит из след. конструкций: (1) Переслать содержимое памяти из одной ячейки памяти в другую.(2) Сложить содержимое в двух ячейках памяти и переслать в третью. Положительные числа хранятся в прямых кодах, а отрицательные в дополнительных кодах. В соответствии с архитектурой Фон Неймона выделяют арифметико-логическое устройство, оперативно-запоминающее устройство, постоянно-запоминающее устройство, устройство шины данных, которые объединяют эти устройства и внешние устройства. Любая программа записанная на языке высокого уровня должна быть переведена в машинный эквивалент-трансляция. Трансляторы бывают 2-х типов: компиляторы, интерпретаторы. Компилятор целиком переводит программу в машинный эквивалент, результат сохраняет и выполняет. Интерпретатор производит перевод построчно, результаты перевода не сохраняет и сразу выполняет.
Понятие сегмента и регистра. Структура ЦП.
Байты памяти упорядочены и пронумерованы с 0. Такие номера называются адресами. Набор байт памяти называется полем. Несколько полей объединяются в сегменты, размер которых 64КБайта. Обращение к байту памяти происходит по схеме: адрес сегмента: смещение. При переводе в машинный эквивалент программа занимает 3 сегмента памяти: код, стек, данные. ЦП-состоит из АЛУ и собственной памяти. Ячейки памяти ЦП называются регистрами. Имеет собственное имя и относится к некоторой группе регистров общего назначения. Регистры сегментов: ADD, AX, BX, DS, CS, SS, ES. Индексные сегменты: IP, DF, SI. Регистры: AX, BX, CX, DX.
Функции ЯП. Основные свойства ЯП.
ЯП является средством алгоритмического решения. Коммутативная функция, с помощью ЯП можно хранить и передавать алгоритмически знания между различными субъектами. Например: алг.знания: сортировка; поиски максимума или минимума. Свойства ЯП: (1) Алгоритмическая универсальность-любой язык должен содержать в своем составе достаточное кол-во средств для решения любой потенциально возможной задачи. Набор средств может быть минимальным: (а) оператор присваивания; (б) условный оператор; (в) цикл. Любой язык обладает ориентированностью т.е он направлен на решение задач определенного круга. Различают процедурные языки (паскаль, питон, с++), системные управления БД (СУБД) (Мy SQL, Oracle), если прогнозирование (питон), нейронные сети, веб-дизайн (open GL), сайты (PHP). (2) Формальность-определения ЯП должны допускать формальность определения для однозначной трассировки конструкций языка. (3) Свойство простоты-конструкции ЯП должны быть просты до такой степени, чтобы допускался переход в машинный язык. (4) Естественность ЯП-конструкции языка должны быть понятны программисту.
Основные сегменты изучения ЯП.
(1) Алфавит-это конечный набор символов из которых строится конструкция языка. (2) Лексика ЯП-совокупность простейших элементов, имеющих самостоятельный смысл. Такие элементы называются лексемы, существует (одно-) и (много-)символьные лексемы. Пример: много символьная система-cout, одно символьная >=; +=. (3) Синтаксис ЯП-совокупность правил, задающих структурно-корректные конструкции языков. (4) Семантика ЯП-набор правил, задающих смысл синтаксически верных конструкций языка. (5) Грамматика-способы и методы применения конструкций для решения практических задач.
Метаязыки описания языков программирования.
Метаязык-язык, служащий для описания других языков. Блок схемы-один из простых метаязыков. У нас Бэкус Наур или БНР
<>-в такие скобки заключаются понятия требующие определения.
::= -есть
|-служит для разделения альтернатив примера.
<цифра>::=0|1|2|3|4|5|6|7|8|9
<целое без знака>::=<цифра>|<целое без знака>
В этом определении одна из альтернатив рекурсивная, т.е определение дается само через себя, однако, чтобы рекурсивное определение было корректно, необходимо наличие нерекурсивной альтернативы.
<целое>::=<знак>|<целое без знака>|<целое со знаком><знак>::=+-
Виртуальная машина. Типы ошибок, распознание ВМ.
{} Заключая, понятия могут отсутствовать или повторяться несколько раз.
 <цикл>::=[<знак>]<цифра>[<цифра>]
 Любая программа, написанная на ЯП перед выполнение должна быть переведена в машинный эквивалент. Иногда удобно считать, что в нашем распоряжении имеется абстрактный компилятор, способный понимать и выполнять конструкции языка-такой абстрактный компилятор называется виртуальная машина. Выполняя программы на ВМ можно изобразить:
Структура ВМ:
ВМ может содержать 2 реальных компа, т.к трансляция и выполнение программы могут быть разделены как во времени, так и в пространстве.
Если пк1 и пк2 имеют разные типы архитектур, то процесс трансляции называется кросскомпиляцией.
Тип ошибки 1: Ошибка времени компиляции (синтаксическая). Такие ошибки легко формализоват, они выявляются практически на 100%. Например if(a>0)
Тип ошибки 2: Ошибка времени выполнения семантической ошибки. Например cout<<5/a; while(a>0); Такие ошибки плохо формализуются и устраняются только программистом.
Структура программы процедурных языков.
Программа, написанная на ПЯ содержит 2 типа команд: описание и операторы. В строго типизированных языках (паскаль)-описание располагается в определенной секции, в других языках описание располагается между операторами и могут переопределяться. Const-секция описания констант. Программа на языке С++ имеет сл.структуру: #Директива предпроцессора \\ void main() \\ { \\ операторы; \\ } Программа обязательно должна содержать одну функцию с именем main() –точка входа в программу, т.е команда с которой компилятор начинает выполнение. Директивы процессора управляют преобразованием программы до ее компиляции. Программа проходит сл. 2 операции: (а) предпроцессорное преобразование исходного текста. (б) компиляция. (в) компоновка. Существуют сл. Директивы: #define-указывает правило замены в тексте. #include-имя заголовка файла.
Понятие типа. Структура типов языка С++.
Тип-некоторое множество значений и набор операций значений. Типы классифицируются по двум критериям: по критерию скалярности и по критерию предопределенности. По критерию скалярности типы делятся на скалярные и структурированные. Скалярные типы-это типы, значения которых не имеют составных частей с самостоятельным смыслом. Структурированные типы состоят из значений, части которых имеют самостоятельный смысл. По критерию предопределенности типы делятся на встроенные и констатируемые. Встроенные типы являются стандартными и входят в состав языка. Констатируемые типы –типы создаваемые программистом. Диапазон значений любого типа определяется кол-вом байт, выделяемых под значение цифр. В языках низкого уровня директивы (определения памяти ДВ)-позволяют выделить пару под переменную и соответствуют понятию типа. В языках высокого уровня такие директивы обозначаются специальными ключевыми словами.
Существуют следующие скалярные типы: int-целые. char–символьные, w\char –расширенные символьные, bool-логический, float-вещественный, dooble-двойной вещественный. Существуют 4 спецификатора типа: short- короткий, long-длинный , signed-знаковый , unsigned-беззнаковый.
Целочисленные типы.
Int(16)
|
-32767;32767
|
2
|
Int(32)
|
-32767;32767
|
4
|
Short int
|
-32767;32767
|
2
|
Long int
|
-2147483647;2147483647
|
4
|
Signed int
|
То же самое, что и int
|
|
Unsigned int
|
0;65535
|
| Целочисленные типы могут быть симметричными и асимметричными. Целочисленные значения в памяти компьютера представляются в прямом или дополнительном двоичном коде. Символьный тип является скалярным, встроенным, дискретным, упорядоченным типом. Константы символьного типа заключаются в апострофы. Существует расширенный w\char\t – под его значения отводится 2 байта и 2^16.
Булевский (логический) тип.
Булевский тип называется скалярным, строгим, дискретным, упорядоченным. Состоит из значений true и false. Источником булевских значений являются сравнения, имеющие следующую структуру: <выражение>< значение сравнения><выражение>. В общем случае выражения должны быть одного типа <, >, <=, >=, ==, !=. над значениями логического типа определены операции: [!, &&, ||]
Вещественный тип.
Знак мантиса
|
Абс. величина мантисы
|
Знак порядка
|
Абс. величина порядка
|
1 бит
|
Сколько применим, сколько и будет. Опред. Точность.
|
1 бит
|
Сколько применим, сколько и будет. Диапазон объема.
| Вещественный тип характеризуется 2-мя характеристиками. Диапазоном принимаемых значений с точностью представления этих значений. Точностью представления определяется кол-вом значащих цифр в записи числа. Диапазоном значений определяется порядком представлений числа. В памяти ПК вещественные числа хранятся в полуэкспоненциальной и записывается: р-порядок. A=M*Q (Q-основание системы счисления, M-мантиса (значащие числа числа)). 256=256*10^0=25,6*10^1. Для того, чтобы представление было однозначным , используют нормализованную полуэкспоненциальную форму, где на мантиссу накладывают дополнительное условие и чтобы мантисса была менее 0. 1/Q<=M<=1. В компьютере, в качестве Q-основания системы счисления используют 2 и 16 системы счисления. Структура представления следующая: Float-занимает 4 байта (под порядок 8 бит или 1 байта). 22 бита на мантиссу. Double занимает 8 байт или 64 бита. Тип void относится к основным типам. Множество значений этого типа пусто.
Описание переменных и констант.
Константа-лексема, изображающая числовое, строковое или символьное значение. Константы делятся на 5 групп: целые, вещественные (с плавающей точкой), перечисление, символьные, строковые. Компилятор определяет тип константы, относя ее к той или иной группе. Целый константы, зависящие от значения, компилятор относит к тому или иному типу. Вещественные константы имеют 2 формы представления: с фиксированной точкой и плавающей. [цифры].[цифры]. Структура константы с плавающей точкой: [цифра][.][цифра][Ele][+|-][цифра] 5.12 Е-2. Символьные константы – это 1 или 2 символа заключенные в апострофы. ‘a’, ’t’, ‘+’, ‘5’, ‘\n’, ‘\t’, ‘\a’. Двухсимвольные константы-это управляющие константы, начинаются со знака \ и служат для (1) Изображения символов не имеющих графического изображения. (2) \, ‘, ?, “, \\, \?, \”. (3) для представления символов с помощью 16(сист) или 8(сист) кодов ‘L073’, ‘DF05’. (4) Строковая константа-это последовательность символов, заключенные в “ “, внутри константы могут использовать управляющие символы. Переменная в C++ это наименьшая область память, в которой хранятся данные определенного типа. У переменной есть имя и значение. Переменная должна быть описана. Общий вид оператора описания: [класс памяти][const]тип имя[инициатор]; \\ int a; \\ auto, extern, static, register. Класс памяти определяет время жизни и область видимости переменной. Если класс памяти не указан, то компилятор разбирает его из контекста. Время жизни переменной может постоянной внутри программы или переменной внутри блока. Область видимости-это часть текста программы из которой допустим доступ переменной. Инициализатор при описании переменной можно при присвоении начального значения. (1) Auto-автоматическая и локальная переменная. Класс может быть задан только переменной, определенной внутри блока. В этом случае память под переменную выделяется в начале блока и за пределами блока переменная недоступна. (2) Extern-глобальная переменная (внешняя). Она находится в другом файле программы и к ней имеется доступ из любого файла программы. (3) Static-переменная, доступная только в пределах текущего файла. (4) Register-аналлогичен классы auto, но память выделяется в регистрах процессора. Пример: int a; \\ void main() \\ { \\ int b; \\ extern int x; \\ static int c; \\ a=1; \\ int=a; \\ a=2; \\ ::a=3; \\ } \\ int x=4; ::-доступ к глобальной переменной. Описание переменной может быть выполнено как объявление или как определение, объявление содержит информацию о классе памяти и типе переменной, а определение добавляет к этому указание выделить память.
Арифметические операции.
Стандартные арифметические операции: int c; \\ c=a+b; \\ c=a-b; \\ c=a*b; \\ c=a/b; \\ cout<<(int) a/b;. Остаток от деления применим только для целых чисел: d%f. Существуют специальные операции: инкремент и декремент, например: i++, ++i, j--, --j. Размещение инкремента, декремента определяет приоритет операций, префиксная форма в отличие от постфиксной формы имеет наивысший приоритет. Например: int i=10, j=5; \\ int a=i++; \\ int b=++j;. Пример: int a1=4, a2=4; \\ double b=2, 4*++a1; \\ double c=2,4*a2++; \\ b=12; a2=5; \\ c=9,6; a2=5;. Пример: a+++b; \\ a+++++b; - складываем с а, после увеличиваем с в (но только после его увеличения)
Условное выражение (операция).
Инв
|
Unsigned char var=159;||1001 1001
Unsigned char not=var;||0110 0110
|
И
|
Unsigned char ask=0*11;||0001 0001
Unsigned char ask=var&mast;||0001 0001
|
или
|
Unsigned char res2=var|mask;||1001 1001
Var&=mask;
| Эта операция использует 3 операнда. -2- это унарная операция (т.к перед цифрой 2 стоит -). <выражение 1> ? <выражение2> : <выражение3>. Семантика: вычисляется выражение 1, если оно истинно (не 0), то вычисляется выражение 2 и оно является результатом. Если при вычислении выражения 1 получается значение 0, то результатом условной операции является вычисленное выражение 3. Пример: cout<3? “yes” : “no”; Выражения состоят из констант, переменные, разделителей и знаков операций. Правила выражения определяет результат выражения. Если выражение формирует число, то оно называется арифметическим выражением. Арифметические выражения, объединенные знаком сравнения называются отношениями.
Поразрядные операции языка С++. Примеры
Поразрядные операции: (1) отрицание (2) логическое и (3) логическое или. При выполнении поразрядного описания все одиночные биты устанавливаются в 0, а нулевое в 1. Unsigned char res3=var|mask;||1000 1000
Операторы языка. Оператор присваивания.
Оператором языка называется элементарная структура языка записи алг.действий, а так же для указаний порядка выполнения других действий. Операторы отделяются друг от друга точкой с запятой. Операторы делятся на простые. Они не содержат внутри себя других операторов. Так же делятся на составные. Операторы присваивания используются для задания значения некоторой переменной. Пример: a=0 \\ short: a_chat=-10; \\ short: a_long; \\ a_long=a_short; \\ float a_f=8,7 \\ int a_i; \\ a_i=a_f; Этот оператор присваивания означает выполнение преобразование типа и потери данных не произойдет. Автоматическое преобразование типов данных произойдет с потерей данных. Дл корректного преобразования типов используются след. конструкцию. <имя.пер1>=(тип данных)<имя.пер2> a_i=(int)a_f. К составным операторам относят собственно составленные операторы и блоки. В обоих случаях это последовательность операторов, заключенных в фигурных скобках {}. В блоке в фигурных скобках присутствует описание int n; \\ n++; \\ a--;
Средства ввода-вывода.
В языке С++ существует 2 способа для ввода-вывода. Функции унаследованы из языка С. Объекты С++ описаны в специальных библиотеках.(1) (Форматированная строка, список аргументов). Форматированная строка-строка символов в кавычках, которая показывает как должны быть напечатаны аргументы. If (“Сум a=%d, cp stay=%f”) –форматированная строка. В С++ существует понятие потока данных. Существует 2 стандартных потока: cin-стандартный поток ввода, cout-стандартный поток вывода. Операторы ввода и вывода: << >> ,,’’ 2 потока cin и cout связаны с библиотекой и для того, чтобы явно не ссылаться на класс этой библиотеки где они описаны, определяют пространство имен: using namespace std; \\ endl \\
Условные операторы. Вложенность условных операторов.
Синтаксис: (1) Вычислить выражение в. Если значение !=0, то выполняется оператор S1. Если выражение =0, выполняется оператор S2. Допускается краткая форма условного оператора. Условный оператор является составным, а значит в качестве оператора S может указываться другой условный оператор. В условном операторе доступно использование сложных условий.
Оператор выбора.
Иногда программе необходимо организовать выбор из нескольких вариантов. Можно использовать несколько условных операторов, но существует отдельный оператор выбора. Case константа 1: <операторы>; case константа 2: <операторы>; Вычисляется выражение- его результат должен быть целочисленным. Результат последовательности сравнивается с константами и при совпадении выполняются операторы, соответствующие этой константе, и все операторы расположены ниже. Если результат выражения не совпал ни с одной константой, то выполняются операторы, соответствующие метке [de fov if:<операторы>;]
Операторы цикла.
Операторы цикла являются управляющими и задают многократное выполнение некоторого участка программы тела цикла. Каждое выполнение тела называется итерацией. Пример: cin>>I; \\ switch (i) \\ { \\ case 1:cout< \\ }). Если условие !=0, то выполняется тело цикла и снова выполняем условие. Если условие =0, то выполняем следующий оператор программы. В некоторых условиях тело цикла может не выполняться ни разу. В других ситуациях тело цикла выполняется бесконечно (зацикливание). Для того, чтобы в теле цикла находился оператор, влияющий на условие. While (a>0)-зацикливание \\ i++; Схема 1: Обработка цифр в числе. Int N; \\ cin>>N; \\ while (N>0) \\ { \\ digit=N%10; \\ обработка digit \\ N=n/10; \\ } Найти сумму цифр, некратных 3. While (N>0) \\ { \\ digit=N%10; \\ if (digit %3!=0) s+=digit; \\ N=N/10; \\ } Схема 2: int n =20, i=1; \\ long S=a; \\ while (i<=N) Схема 3 цикл с постусловием: do Синтаксис \\ тело цикла=a; \\ while (действие) \\ f=n! \\ int n, f=1, i=0; \\ cin>>n; \\ do \\ { \\ i++, f=f*i; } \\ while (i<=n) \\  \\ i=1 \\ float a1*a2; e=0,001, p=1. Операторы цикла с параметром: for (<выр1>;<выр2>;<выр3>)-изменение значения счетчика. Выполняется инициализация счетчика. Вычисляется условное выражение 2 и если оно !=0, то выполняется тело цикла, затем выполняется выражение 3, затем снова выполняется выражение 2. Любое и выражение может отсутствовать, однако ; должны быть. (1) Уменьшение параметра: for (n=10; n>0; n--) {операт} (2) Изменение шага корректировки: for (n=2; n<60; n+=13) Возможность проверять условие, отличное от условия, налагаемое на число итераций: for (t=1, t*t*t ∑216, t++0) Корректировка шага возможна с помощью любой арифметической операции: for (d=100.0; d<100.0; d*=1.1) \\ for (x=i, y=-75, y=5*(x++)+10) Можно использовать несколько инициализирующих и корректирующих выражений: for (x=I, y=0;x=100, x++, y--) \\ int exit=0 \\ for (int num=0, num<100 && !exit; num++) \\ { \\ cin>>mov; \\ if(mov==0) exit=1; \\ cout<>N; \\ for (int del=1 del<=N; del++) \\ if (N%del==0)… S+=del; \\ if (S==N) cout<<”совпадение”, else cout<<:”no”;
Операторы перехода.
Операторы перехода выполняют безусловную передачу управления. (1) Оператор break-прерывание цикла. Break \\ { \\ <оператор> \\ if (<условие>) break; \\ <оператор>;. Пример: найти сумму чисел, вводимых с клавиатуры до тех пор, пока не будет введено 100 чисел или не введен 0. For(S=0; i=1; i<100, i++) \\ { cin>>x; \\ if(x==0) break \\ S+=x; (2) Оператор continue-переход к след. итерации цикла. Он используется, когда тело цикла содержит ветвление. Пример: найти кол-во и сумму положительных чисел. For (k=0, S=0, x=1; x!=0) \\ {cin>>x; \\ if(x<=0) continue; \\ k++; S+=x;. (3) Оператор go to – метки. В теле программы может быть использована метка <оператор>. В качестве метки используют любой идентификатор. Оператор go to может управлять направлением программы вверх и вниз. Int k; \\ go to m; \\ int a=3, b=4; \\ k=a+b; \\ m: int c=k+1; \\ go to h; Однако, нельзя передавать управление во внутрь операторов: if, switch, цикл. Основное свойство оператора go to: кол-во использований оператора в программе обратно пропорционально квалификации программиста. (4) Return [<выражение>]-оператор возврата из функции. Он всегда завершает выполнение функции и передает управление в точку вызова.
Обработка последовательности. Программирование арифметических циклов.
Для арифметических циклов заранее известно кол-во итераций. Схема 3.1: обработка последовательности из n элементов. Cхема 3.2: обработка двух соседних элементов последовательности.
Cin>>N;
For (i=a; i
{cin>>x;
Обработка x;}
|
Пример: дана последовательность из n чисел. Найти сумму четных чисел последовательности.
Cin>>N; S=0;
For (i=0; i
{ cin>>x;
If (x%2==0) S+=x;
| Cin>>N; cin>>0;
For (i=1; i
Cin>>b;
Обработка а и b;
a=b;}
|
Пример: верно ли, что последовательность является возрастающей.
Cin>>N; cin>>a; bool p=1;
For (i=1, i
{cin>>b;
If (a>=b) p=0
A=b }
|
Обработка последовательности. Итерационные циклы.
Для итерационных циклов известно условие выполнения цикла. Обработка последовательности до ввода маркера. Cin>>x; min=x; \\ while (x!=маркер) \\ { int (x>x; } Пример: Дана последовательность чисел, в конце 0, найти наименьшее число последовательности. Схема 4.1: Обработка последовательности, оканчивающейся маркером, в случаях 2-х элементов.
Cin>>x;
While (x!=маркер)
{ cin>>y;
Обработка х и у;
X=y}
|
Пример: верно ли, что последовательность является знакоцередующейся.
Cin>>x; bool p=1;
While (x)
{cin>>y;
If (y!=0)
If (x*y>0) p=0;
X=y;
| |
Скачать 51.04 Kb.