1 Алгоритмические языки и программирование Лектор: к.т.н., доцент каф. ИУ6 Ничушкина Татьяна Николаевна Семестры: 1 – зачет/экзамен; 2 – экзамен. 1 семестр: 40 лекций, 16 семинаров, 16*4 часов практических занятий Структура курса на 1-й семестр: I часть. Алгоритмизация и процедурное программирование II часть. Объектно-ориентированное программирование III часть. Создание приложений Windows Среда программирования: Turbo Delphi 2006 (Free version) Учебники: 1. Иванова Г.С. Основы программирования: Уч. для ВУЗов – М.: МГТУ им. Н.Э. Баумана, Иванова Г.С., Ничушкина Т.Н., Пугачев Е.К. Объектно-ориентированное программирование: Уч. для ВУЗов – М.: МГТУ им. Н.Э. Бау- мана, Посещение всех занятий обязательно!

2 Введение. Две технологии разработки ПО 1. Структурное (процедурное) программирование 2. Объектно-ориентированное программирование Программа Модуль 1Модуль 2Модуль 3 П/п 1.1П/п 1.2П/п 1.3П/п 2.1П/п 1П/п 2.2П/п 3.1П/п 3.2П/п 3.3 Объект 1 П/пП/п Данные Объект 3 П/пП/п Данные Объект 2 П/пП/п Данные Сообщения Данные П/пП/п П/пП/п П/пП/п

3 Часть 1. Основы алгоритмизации и процедурное программирование Введение. Этапы создания ПО 1. Постановка задачи – неформальное описание задачи 2. Анализ и уточнение требований – формальная постановка задачи и выбор метода решения 3. Проектирование – разработка структуры ПО, выбор структур данных, разработка алгоритмов, определение особенностей взаимодействия с программной средой 4. Реализация – составление программ, тестирование и отладка 5. Модификация – выпуск новых версий

4 Пример разработки программы 1. Постановка задачи: Разработать программу, которая определяет наибольший общий делитель двух целых чисел. 2. Анализ и уточнение требований: 1) Функциональные требования исходные данные: a, b – натуральные числа; 0 < a, b < ? ; результат: x – натуральное число, такое, что x = max {y i / i = 1,n}, где ((a mod y i ) = 0) & (b mod y i ) = 0) Метод решения: a) найти делители Y = { y i } и определить x = max {Y}; б) метод Евклида Пример 1: a b = 6 Пример 2: a b = 1

5 Пример разработки программы (2) 2) Эксплуатационные требования: а) процессор – не ниже Pentium; б) операционная система – Windows 2000 и выше (консольный режим); в) предусмотреть запрос на ввод данных с клавиатуры; г) результаты вывести на экран дисплея. 3) Технологические требования: а) язык программирования: Pascal; б) среда программирования: Turbo Delphi (free); в) технология: структурный подход.

6 Пример разработки программы(3) 3. Проектирование Виды проектной документации: Структурная схема ПО – показывает взаимодействие по управлению основной программы и подпрограмм. Основная программа Подпрограмма ввода Подпрограмма вывода

7 Схемы алгоритмов Обозначения ГОСТ – Терминатор (начало/конец) 2. Процесс (вычисления) 3. Анализ (проверка) 4. Модификатор (автоматическое изменение) 5. Предопределенный процесс (подпрограмма) A:=1 6. Ввод/вывод данных 7. Ввод с перфокарт 8. Вывод на принтер 9. Комментарий 10. Соединитель A>5 i:=1,k Sort(A) Ввод a A a a A Начало Условие (1) да-нет

8 Правила выполнения схем алгоритмов Схемы алгоритмов должны быть выполнены аккуратно, желательно с применением карандаша и линейки или графических редакторов на компьютере. Стрелки на линиях, идущих сверху вниз и слева направо, т. е. в направлении нашего письма не ставят, чтобы не затенять схему. Если линия – ломанная, и направление ее хотя бы в одном сегменте не совпадает со стандартными, то стрелка ставится в конце линии, перед блоком, в который она входит. Если схема не умещается на странице или линии многократно пересекаются, то линии разрывают. При этом один соединитель ставится в месте разрыва, второй – в месте продолжения линии. Оба соединителя помечаются одной и той же буквой или цифрой. Для простоты чтения схемы ее начало должно быть сверху, а конец – снизу. При этом количество изгибов, пересечений и обратных направлений линий должно быть минимальным.

9 Пример некорректной схемы алгоритма

10 1-й вариант правильного выполнения схемы алгоритма

11 2-й вариант: выделение подпрограмм

12 Основные структурные конструкции 1. Следование Действие 1 Действие 2 2. Ветвление 3. Цикл-пока Условие да-нет Действие 1Действие 2 Условие да нет Действие … Действие 1 Действие 2 … … Если Условие то Действие 1 иначе Действие 2 Все-если … … Цикл-пока Условие Действие Все-цикл … Псевдокод:

13 Пример разработки программы (4) Алгоритм Евклида: Ввести A,B Цикл-пока A B Если A > B то A := A – B иначе B := B – A Все-если Все-цикл Вывести A Конец Начало Конец A, B A = B A > B A:= A - BB:= B - A да нет A 4. Реализация программы, ее тестирование и отладка. Схема алгоритма

14 Среда Turbo Delphi Схема процесса подготовки программы Текстовый редактор Компилятор Компоновщик Текст Prog.dpr (prog.pas) Prog.dcu (Prog.obj) Библиотеки стандартных п/п Prog.exe Ошибки Объектный модуль Исполняемый модуль Исходный модуль

15 Схема процесса отладки и выполнения Prog.exe Исх. данные Отладчик Отладочная информация Результаты Программа Исх. данные Результаты

16 Delphi Pascal Delphi Pascal – одна из реализаций языка программирования Паскаль, используемая в среде программирования Delphi. Автор языка Паскаль: Николаус Вирт, Цюрих, Швейцария, 1971 г. Среда программирования Turbo Delphi – бесплатная (free) версия среды Borland Delphi, которая является частью пакета разработки Windows-приложений Borland Developer Studio Среду можно переписать на сайте фирмы Borland.

17 Глава 1 Простейшие конструкции языка 1.1 Синтаксис и семантика языков программирования Алфавит языка Pascal включает: 1) латинские буквы без различия строчных и прописных; 2) арабские цифры: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; 3) шестнадцатеричные цифры: 0..9, а..f или A..F; 4) специальные символы: + - * / = := ; и т. д.; 5) служебные слова: do, while, begin, end и т. д. Синтаксис – правила, определяющие допустимые конструкции языка. Семантика – правила, определяющие смысл синтаксически корректных предложений. Пример: синтаксическая диаграмма конструкции «Идентификатор»: Буква Цифра

Структура программы в среде Turbo Delphi Программа – последовательность инструкций, адресованных компьютеру, которая точно определяет, как следует решать задачу. Program Ex1_01;//Определение наибольшего общего делителя {$APPTYPE CONSOLE} Uses SysUtils; Var a,b:integer; begin Write('Input two numbers:'); Readln (a,b); while a<>b do if a>b then a:=a-b else b:=b-a; Writeln('Result:', a); Readln; end. Заголовок Раздел описаний Раздел операторов

Константы и переменные. Типы переменных Константы – данные, не изменяемые в процессе выполнения программы. Литералы – константы, записанные в тексте программы. Примеры литералов: а) -25, 2.5 (=2,5), 0.1e6 (= 0,1·10 6 ) – числовые литералы; б) $2a – шестнадцатеричное число; в) true, false – логические константы; г) 'd', #65 = 'A' – символьные константы; д) 'abcd' – строковая константа; е) nil - адресная константа. Данные Константы Переменные Литералы Поименованные

20 Константы и переменные (2) Поименованные константы – константы, обращение к которым выполняется по имени. Они описываются в разделе описаний: Пример: Const min = 0; max = 100; center = (max - min) div 2;

21 Константы и переменные (3) Переменные – поименованные данные, которые могут изменяться в процессе выполнения программы. Описываются в разделе описаний: Пример: Var a,b:integer; c:real; При установленной опции Extended syntax (расширенный синтаксис) переменные при описании можно инициализировать. Пример: Var a:integer=56;

22 Типы данных Тип – описатель данных, который определяет: а) диапазон изменения значения, задавая размер ее внутреннего представления; б) множество операций, которые могут выполняться над этой переменной Пример: Type date = 1..31; // объявление нового типа Var d1:date; // объявление переменной этого типа

23 Классификация типов данных языка Pascal

24 Стандартные типы 1. Целые типы: Integer, LongInt (4 байта со знаком): ; SmallInt (2 байта со знаком): Short (1 байт со знаком): ; Word (2 байта без знака): ; Byte (1 байт без знака): Символьные типы: Char, AnsiChar (1 байт без знака) – код символа по таблице ANSI; WideChar (2 байта без знака) – код символа по таблице Unicode 3. Булевский тип: Boolean (1 байт без знака: 0 – false, 1 - true) Знак 1 бит Двоичное число

25 Порядковые типы 4. Перечисление – значения переменных этого типа описываются явно (перечисляются). Пример: Туpe Day = (Mon, Tue, Wed, Thu, Fri, Sat, Sun); Var D:Day; или Var D:(Mon, Tue, Wed, Thu, Fri, Sat, Sun); 5. Отрезок – значения переменных входят в определенный диапазон значений ранее описанного типа. Пример: Туpe Date = 1..31; // значения – числа от 1 до 31 Var DataN: Date; или Var DataN: 1..31; Значения переменных

26 Функции порядковых типов данных 1. Ord ( ) – возвращает номер значения по порядку (не применима к 64 битным аргументам). Пример: Ord(A)= 65 // номер символа в таблице ANSI 2. Pred ( ) – возвращает предыдущее значение. Dec ( ) – возвращает значение, уменьшенное на 1. Пример: N:=5; k:= Pred(N){k=4}; l:=Dec(N){l=4}; 3. Succ ( ) – возвращает следующее значение. Inc ( ) – возвращает целое, увеличенное на 1. Пример: N:=5; k:= Succ(N){k=6}; l:= Inc(N){l=6}; 4. High ( ) – возвращает самое большое значение типа, также работает со строками и массивами (см. далее). 5. Low ( ) – возвращает самое маленькое значение типа, также работает со строками и массивами (см. далее).

27 Вещественные типы Вещественные числа представляются с конечной точностью, определяемой разрядной сеткой! Формат внутреннего представления: Стандартные вещественные типы: Тип Значащих Диапазон цифр порядка Real (6 байт) использование нежелательно Single (4 байта) Double (8 байт) Extended (10 байт) Comp (8 байт)

Выражения 1. Арифметические операции – применяют к вещественным и целым константам и переменным: +, -, *, / (вещественное деление), div (целочисленное деление), mod (остаток от деления) Пример: var a: integer = 5; b: integer = 3; … a+b a div b a mod b a / b (a+b)/(a-b*a)

29 Выражения (2) 2. Операции отношения – применяют к числам, символам, строкам – в результате получают логическое значение:, =, <>, = Пример: var a: integer = 5; b:integer = 3; … a > b a = b true false

30 Выражения (3) 3. Логические операции – применяют к логическим значениям – результат логическое значение not a = false, not(a) = true a = true, not(a) = false and a = false, b = false a and b = false a = false, b = true a and b = false a = true, b = false a and b = false a = true, b = true a and b = true or a = false, b = false a or b = false a = false, b = true a or b = true a = true, b = false a or b = true a = true, b = true a or b = true xor a = false, b = false a xor b = true a = false, b = true a xor b = false a = true, b = false a xor b = false a = true, b = true a xor b = true

31 Выражения (4) 4. Поразрядные операции – применяют к целым, результат – целое число: not, and, or, xor, shr (сдвиг вправо), shl (сдвиг влево) Пример: var a:SmallInt = 5; … not a a shl

32 Математические функции В выражениях можно использовать следующие математические функции: Pi // число abs ( ) // абс. значение sqr ( ) // x 2 sqrt ( ) // x exp ( ) // e x ln ( ) // ln x sin ( ) cos ( ) arctan ( ) // arctg x frac ( ) // дробная часть числа int ( ) // целая часть числа random ( ) – генерация случайного числа 0 x < 1; random ( ) – генерация случайного числа 0 i < Целое; randomize – подготовка датчика случайных чисел

33 Правила вычисления выражений 1. Порядок выполнения операций определяется приоритетами и скобками Операции not 1 *, /, div, mod, and, shr, shl 2 +, -, or, xor 3, =, =, <> 4 Пример: 1) x(x+2) y(y-1) 2) (a =1) x*(x+2) / y / (y-1) или x*(x+2) / ( y*(y-1))

34 Правила вычисления выражений (2) 2. При выполнении арифметических операций над числами различных типов автоматически осуществляется неявное преобразование типов. Пример: var a:single; k:integer; … a/k // число k преобразуются к типу single 3. При сравнении вещественных чисел из-за их неточного представления проверку равенства и неравенства следует осуществлять с явным указанием допуска. Пример: Var x,y:single; x <> y abs(x-y) > 1e-10 x = y abs(x-y) < 1e-10

Оператор присваивания Используется для изменения значений переменных. Пример: Var v:integer; a,b:single; … a:= V*b / 2.0; Корректное выполнение предполагает, что результат вычисления и переменная правой части – совместимы по типу. По правилам совместимы: а) все целые типы; б) все вещественные типы; в) отрезок базового типа и базовый тип; г) два отрезка базового типа; д) символ и строка. single

36 Явное и неявное преобразования типов При несовпадении типов для совместимых типов выполняется неявное преобразование типов. Var L:LongInt; E,x:extended; I:integer; R:Single; Begin … R:= I * E / (x+L); Для несовместимых типов необходимо явное преобразование типов, например, посредством специальных функций: trunc ( ) - преобразует вещественное число в целое, отбрасывая дробную часть. round ( ) - округляет вещественное число до целого. ord ( ) – преобразует значение в его номер. Пример: ord(A) = 65. chr ( ) – преобразует номер символа в символ. Пример: chr(65) = A. Single Extended! Преобразование будет выполнено неявно (автоматически)

Процедуры ввода-вывода Ввод – операция по передаче данных от источника в компьютер. Вводимые числа разделяют пробелами или записывают на разных строках. По типу они должны соответствовать типам переменных. ReadLn в отличие от Read после выполнения операции чтения переводит курсор ввода на следующую строку. Read(a,b); а) б) ReadLn(a,b); a) б) ReadLn(a); ReadLn(b); б)

38 Процедуры ввода-вывода (2) Вывод – операция по передаче данных из компьютера. Целое 1 – ширина поля вывода (число прижимается к правой границе); Целое 2 – количество выводимых цифр дробной части числа. WriteLn – после вывода переводит курсор на следующую строку.

39 Программа определения корней кв. уравнения program Ex1_2; {$APPTYPE CONSOLE} Uses SysUtils; Var A,B,C,D,E,X1,X2:Single; Begin WriteLn('Input A,B,C'); ReadLn (A,B,C); WriteLn('A=',A:3:1,' B=',B:3:1,' C=',C:3:1); D:=sqrt(sqr(B)-4*A*C); E:=2*A; X1:=(-B+D)/E; X2:=(-B-D)/E; WriteLn('X1=',X1:10:6,' X2=',X2:10:6); ReadLn; End.