Основы информатики

Кирьянов Б.Ф. Основы информатики. 101

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

Вопросы: 1) Моделями чего являются глобус, фотография автобуса, программа генератора случайных чисел?

2)Для чего используются модели и моделирование?

3)Как Вы понимаете сущность административного моделирования?

4.8. Об алгоритмах игровых автоматов

Практически все игровые алгоритмы относятся к рекурсивным. В них реализуются два внутренних цикла, повторяющихся по очереди. Один из этих циклов состоит в постоянной проверке: сделал ли игрок свой ход? Если да, то тогда реализуется другой внутренний цикл – ответный ход компьютера. На внешнем цикле каждый раз реализуется проверка: достигнут ли определѐнный результат игры. Так, при игре в шахматы таких результатов должно быть три – ничья или кто-то выиграл.

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

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

Задание. Построить алгоритм игры ―100 и одна семечка‖ (другое название

–―Гнилая семечка‖. Первый ход в этой игре делает игрок (каждый раз берѐтся 1

–3 семечки). Последняя взятая семечка (―гнилая‖) съедается в наказание за проигрыш. В этой игре компьютер всѐ время выигрывает.

4.9. Представление алгоритмов с использованием псевдокода

Псевдокод (pseudocode) – это система представления, с помощью которой можно записывать идеи (соображения по построению алгоритма и его частей) в процессе построения алгоритма. При этом используют менее строгие правила формального языка. Поэтому синтактико-семантические структуры псевдокода подобны аналогичным структурам выходного языка программирования. Упрощение заключается в частности в том, что большинство действий и процедур кратко записывается на русском языке. На английском языке сохраняются только основные операторы, к которым все давно привыкли. Это if, then,

Кирьянов Б.Ф. Основы информатики. 102

else, do, while и некоторые другие. Вместо оператора присваивания используется стрелка.

Примеры: 1) Процедура трѐхкратного вывода на печать слова «Привет»:

procedure Приветствие;

Счѐтчик 3.

while (Счѐтчик > 0) do

(вывести на печать сообщение ‗Привет‘ и Счѐтчик Счѐтчик – 1)

2) Вызов процедуры Сортировка:

Procedure Сортировка (Список) - в скобках указывается список объектов для сортировки.

3) Определение среднесуточной зарплаты CуммаС, выплачиваемой предприятием, при годовом фонде зарплаты СуммаГ:

if (год является високосным) then (СуммаС СуммаГ разделѐнная на 366) else (СуммаС СуммаГ разделѐнная на 365)

4) Теперь запишем алгоритм сортировки L (L>1) имѐн методом простого перебора.

Procedure Сортировка (Список имѐн Im длины не более L)

if (E[N] < E[N-1]) then (Im[N] и Im[N-1] меняются местами и

E[N] и E[N-1] тоже меняются местами

N N – 1 L L – 1

4.10. К оценке эффективности и проверке правильности алгоритмов

При разработке алгоритмов всегда следует помнить о том, что они должны быть эффективными и правильными.

Кирьянов Б.Ф. Основы информатики. 103

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

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

На рис. 4.8 приведены взятые из литературы графики примерной зависимости времени решения задач сортировки T от длины L списка сортируемых элементов для методов вставки (a) и зависимости времени решения задач поиска от длины рассматриваемого списка (б).

T T

Правильность работы алгоритма в простых случаях можно проверить сразу. Для сложных алгоритмов иногда приходится реализовывать их представление в ЭВМ, то есть разрабатывать программы. Запуская эти программы с различными параметрами и исходными данными, для которых результат решения известен или его можно оценить, проверяется и правильность алгоритма.

Контрольный вопрос: Является ли правильным представленный ниже алгоритм деления двух целых чисел с отбрасыванием дробной части частного (целочисленное деление без округления результата). Поясните свой ответ.

Кирьянов Б.Ф. Основы информатики. 104

Счѐтчик 0; Остаток делимое;

Repeat

(Остаток остаток – делитель; Счѐтчик счѐтчик – 1)

Until (Остаток < Делитель) Частное Счѐтчик.

Лабораторные работы, выполняемые при изучении раздела 4:

1.Ознакомление с алгоритмами архивации.

2.Редактор презентационных файлов MS Power Point.

Контрольные вопросы

1.Перечислите 4 основные этапа создания алгоритмов. Кто впервые их сформулировал (применительно к решению задач)?

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

3.Постройте блок-схему алгоритма умножения двоичных чисел в нормальной форме (начиная с младших разрядов).

4.Постройте блок-схему алгоритма двоичного поиска корня функции

0

на отрезке [1, 5].

5.Какое максимальное количество элементов списка нужно рассмотреть (проверить), если алгоритм двоичного поиска применяется к списку, состоящему из 200 элементов? Из 100000 элементов?

6.Какие алгоритмы называются рекурсивными? Приведите пример рекурсивного алгоритма.

7.Что такое моделирование? В чѐм заключается его конечная цель?

8.В чѐм состоит особенность самораспаковывающегося архива?

9.Какая математическая модель называется функционально полной.

10.Каким образом в Microsoft PowerPoint можно назначить отдельную цветовую схему для отдельно взятого слайда?

Кирьянов Б.Ф. Основы информатики. 105

5. АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ КАК СРЕДСТВО

РЕАЛИЗАЦИИ АЛГОРИТМОВ

5.1. Общие сведения об алгоритмических языках

Алгоритмический язык – это синтаксическая конструкция и определяемые ею свойства программы объектов или процесса обработки данных.

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

Условно алгоритмические языки принято делить на пять поколений. К первому поколению (50 – 60 гг.) относится ассемблер, работающий по принципу ―одна инструкция – одна строка‖. Любое перемещение данных программировалось. Например: переписать число из сумматора в выходной регистр АЛУ.

Второе поколение (конец 50-х – начало 60-х годов) – это время использования символического ассемблера, в котором появилось понятие переменной. Стало возможным указывать в программах идентификаторы переменных и действий. Символический ассемблер стал первым полноценным языком программирования. Но им умели пользоваться в основном лишь программисты.

Третье поколение связывают с появлением универсальных языков высокого уровня. К первым таким языкам относятся Fortran, Algol, Cobol, Basic. Разработка их была начата ещѐ в 50 – 60 годы, но полноценные их версии появились в середине 60-х годов. Позднее появились языки Pascal, C (Си), C++ (Cи++) , Plи др. Основными достоинствами языков высокого уровня являются их независимость от типа машины, доступность широкому кругу пользователей.

Четвѐртое поколение языков развивается с начала 70-х годов. Это - про- блемно-ориентированные языки, то есть языки, ориентированные на определѐнную область задач, что позволяет повысить их возможности и эффективность при подготовке программ для решения задач из области, на которую они ориентированы. К проблемно-ориентированным языкам относятся языки программирования для интернета (HTML, XML и др.), программирования удалѐнных баз данных (SQL), задач математической логики с помощью

Кирьянов Б.Ф. Основы информатики. 106

декларативного программирования (Prolog), задач моделирования, векторной графики и т.д.

Кроме универсальных языков программирования, разрабатывались и специализированные языки, предназначенные, например, для управления станками, ракетными комплексами (язык АДА для министерства обороны США, разработанный в 1979 году и названный в честь первой программистки мира Ады Лавлейс).

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

Рис. 5.1. Этапы процесса трансляции программы

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

Пятое поколение языков появилось в середине 90-х годов. На базе этих языков построены и строятся системы автоматического создания прикладных программ с помощью визуальных средств разработки. При этом создатели указанных программ могут обладать лишь поверхностными знаниями и навыками программирования.

Указанные алгоритмические языки реализуют рассматриваемое ниже объектно-ориентированное программирование, а разработанные на их основе

Кирьянов Б.Ф. Основы информатики. 107

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

5.2. Современные принципы построения программ на алгоритмических языках

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

модульное программирование;

структурное программирование;

объектно-ориентированное программирование.

Модульное программирование. Этот принцип программирования предусматривает разбиение программы на последовательность модулей, каждый из которых выполняет одно или несколько действий [2]. При этом выполнение команд модуля всегда начинается с его первой команды, а заканчивается – последней командой модуля. То есть нельзя войти в модуль, минуя его начало и нельзя выйти из него минуя его окончание. Небольшие модули часто называют подпрограммами, то есть последовательностями команд, выполняющими небольшую конкретную задачу. Но иногда модули состоят и из нескольких подпрограмм.

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

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

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

Логические операции могут принимать одно из двух значений – это true (истина, да, включено) и false (ложь, нет, выключено). При записи логических

Кирьянов Б.Ф. Основы информатики. 108

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

Приоритеты всех логических операций ниже, чем приоритеты операций сравнения. Поэтому сравнения выполняются первыми. Рассмотрим пример логического выражения на языке Паскаль:

not((x<=1) and (y=2)).

Приведѐнное выражение имеет значение true, если ложно хотя бы одно из условий: значение переменной x больше единицы или значение переменной y не равно двум.

При записи программ обычно используются комментарии, так как в больших программах назначение отдельных участков программы со временем забывается. Это полезно и для изучения программ, подготовленных другим программистом. В языках Паскаль и Си++ для этой цели используются знаки // для однострочечных и {…} для многострочечных пояснений.

Структурное программирование. Идея структурного программирования заключается в том, что структура программы должна отражать структуру решаемой задачи, чтобы алгоритм решения был ясно виден из исходного текста задачи [2]. Для этой цели в программу вводятся подпрограммы, выполняющие определѐнные части программы. Подпрограммы могут вызываться основной программой несколько раз при вводе в них соответствующих значений параметров. Комбинируя подпрограммы, можно комплектовать итоговый алгоритм уже не из простых операторов, а из законченных блоков, имеющих определѐнную смысловую нагрузку. Таким образом, подпрограммы являются как бы обобщѐнными операторами, определяемыми программистом.

Кирьянов Б.Ф. Основы информатики. 109

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

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

Вязыке Си++ и в других родственных ему языках понятия «процедура» нет, в нѐм имеются только функции. Поэтому если никакого значения функции не вычисляется, то считается, что она возвращает основной программе значение типа «никакое».

Использование модулей и подпрограмм позволяет разрабатывать про-

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

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

Нисходящее программирование удобно тем, что даѐт возможность программисту практически постоянно мыслить на системном уровне, не опускаясь до конкретных операторов и переменных. Кроме того, появляется возможность некоторые подпрограммы не создавать сразу, а временно откладывать, пока не будут закончены другие части программы. Некоторые подпрограмм или модули могут использоваться много раз с различными значениями переменных.

Принцип структурного программирования реализуется также в событий-

но-ориентированном программировании. Такое программирование реализова-

но, например, в организации системы Windows. Главная часть программы Windows представляет собой один бесконечный цикл, который постоянно следит за тем, не произошло ли какое-либо новое событие или не появилось ли какоелибо новое сообщение (например, пользователь щѐлкнул мышкой по ярлыку

Кирьянов Б.Ф. Основы информатики. 110

некоторой папки для еѐ открытия). При их обнаружении запускается соответствующая подпрограмма, предназначенная для обработки произошедшего события. Такой процесс продолжается до получения сообщения «Завершить работу».

Объектно-ориентированное программирование. Развитие идей струк-

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

В начале 80-х годов прошлого века в программировании возникло новое направление, основанное на понятии объекта. В реальном мире различные объекты обладают тремя базовыми характеристиками: они имеют определѐнные наборы свойств, способны изменять эти свойства и реагировать на события, возникающие как в окружающем мире, так и внутри самих объектов.

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

Созданные объекты описываются как самостоятельные единицы, которым с помощью объектно-ориентированных языков программирования предоставляют средства для выражения указанных возможностей. Таким путѐм были созданы операционные среды (системы программирования) различного назначения, позволившие значительно упростить и ускорить разработку программных комплексов различного назначения. Примерами специализированных сред являются популярные Microsoft Office Promt 2007 − профессиональная среда для перевода, Microsoft Office PowerPoint – среда для подготовки слайдов и т.д. Наиболее популярными средами, предназначенными для разработки программных комплексов до начала 21-го века являлись среды на основе объектноориентированных языков программирования Java, ObjectPascal, С и C#. В 21-м веке в основном используются ObjectPascal и C++.

5.3. Представление данных и вычисление стандартных функций на языке Object Pascal

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