Транскрипт
1 среднее ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВанИЕ И.Г.Семакин, А.П.шестаков основы алгоритмизации и программирования Учебник Рекомендовано Федеральным государственным автономным учреждением «Федеральный институт развития образования» (ФГАУ «ФИРО») в качестве учебника для использования в учебном процессе образовательных учреждений, реализующих программы среднего профессионального образования по специальностям «Компьютерные системы и комплексы», «Информационные системы (по отраслям)», учебная дисциплина «Основы алгоритмизации и программирования» укрупненной группы специальностей «Информатика и вычислительная техника» Регистрационный номер рецензии 308 от 25 июня 2012 г. ФГАУ «ФИРО»
2 УДК (075.32) ББК 22.18я723 С30 Р е ц е н з е н т ы: канд. физ.-мат. наук, преподаватель ГАОУ СПО «Колледж предпринимательства 11» Е.И.Ночка; старший научный сотрудник ГНУ ГОСНИТИ Россельхозакадемии А. А. Соломашкин С30 Семакин И. Г. Основы алгоритмизации и программирования: учебник для студ. учреждений сред. проф. образования / И. Г. Семакин, А. П. Шестаков. М. : Издательский центр «Академия», с. ISBN Рассмотрены основы принципы алгоритмизации и программирования на базе языка Паскаль (версия Турбо Паскаль 7.0). Даны основные понятия объектно-ориентированного программирования и его реализация на языке Турбо Паскаль. Описана интегрированная среда программирования Delphi и визуальная технология создания графического интерфейса программ. Показана разработка программных модулей в этой среде. Учебник может быть использован при изучении общепрофессиональной дисциплины ОП «Основы алгоритмизации и программирования» в соответствии с требованиями ФГОС СПО для специальностей «Компьютерные системы и комплексы» и «Информационные системы (по отраслям)» укрупненной группы специальностей «Информатика и вычислительная техника». Для студентов учреждений среднего профессионального образования. УДК (075.32) ББК 22.18я723 Оригинал-макет данного издания является собственностью Издательского центра «Академия», и его воспроизведение любым способом без согласия правообладателя запрещается ISBN Семакин И. Г., Шестаков А.П., 2013 Образовательно-издательский центр «Академия», 2013 Оформление. Издательский центр «Академия», 2013
3 Ув а ж а е м ы й ч и т а т е л ь! Данное издание является частью учебно-методического комплекта по специальностям «Компьютерные системы и комплексы» и «Информационные системы (по отраслям)» укрупненной группы специальностей «Информатика и вычислительная техника». Учебник предназначен для изучения общепрофессиональной дисциплины «Основы алгоритмизации и программирования». Учебно-методические комплекты нового поколения включают традиционные и инновационные учебные материалы, позволяющие обеспечить изучение общеобразовательных и общепрофессиональных дисциплин и профессиональных модулей. Каждый комплект содержит в себе учебники и учебные пособия, средства обучения и контроля, необходимые для освоения общих и профессиональных компетенций, в том числе и с учетом требований работодателя. Учебные издания дополняются электронными образовательными ресурсами. Электронные ресурсы содержат теоретические и практические модули с интерактивными упражнениями и тренажерами, мультимедийные объекты, ссылки на дополнительные материалы и ресурсы в Интернете. В них включен терминологический словарь и электронный журнал, в котором фиксируются основные параметры учебного процесса: время работы, результат выполнения контрольных и практических заданий. Электронные ресурсы легко встраиваются в учебный процесс и могут быть адаптированы к различным учебным программам. Учебно-методический комплект разработан на основании Федерального государственного образовательного стандарта среднего профессионального образования с учетом его профиля.
4 Пр е д и с л о в и е Программирование все в большей степени становится занятием лишь для профессионалов. Объявленный в середине 1980-х гг. лозунг «Программирование вторая грамотность» остался в прошлом. В понятие «компьютерная грамотность» сегодня входит, прежде всего, навык использования многообразных средств информационных технологий. При решении той или иной информационной задачи сначала следует попытаться подобрать адекватное программное средство (электронные таблицы, системы управления базами данных, математические пакеты и др.), и только если эти средства не позволяют решить поставленную задачу, использовать универсальные языки программирования. Различают программистов двух категорий: системных и прикладных. Системные программисты это разработчики базовых программных средств ЭВМ (операционных систем, трансляторов, сервисных средств и т. д.), являющиеся профессионалами высочайшего уровня. Прикладные программисты разрабатывают средства программного обеспечения ЭВМ, предназначенные для решения задач в отдельных областях деятельности (науке, технике, производстве, сфере обслуживания, обучении и т. д.). Требования к качеству прикладных программ так же высоки, как и к качеству системных. Любая программа должна не только правильно решать задачу, но и иметь современный интерфейс, быть высоконадежной, дружественной к пользователю и т. д. Только такие программы могут выдержать конкуренцию на мировом рынке программных продуктов. По мере развития компьютерной техники развивались методика и технология программирования. Сначала возникли командное и операторное программирование, в 1960-х гг. бурно развивались структурное программирование, линии логического и функционального программирования, а в настоящее время широко распространяются объектно-ориентированное и визуальное программирование. Задача, которую следует ставить при первоначальном изучении программирования, это освоение основ его структурной мето- 4
5 дики. Структурная методика до настоящего времени остается основой программистской культуры. Не освоив ее, человек, взявшийся изучать программирование, не имеет никаких шансов стать профессионалом. В 1969 г. швейцарским профессором Никлаусом Виртом был создан язык программирования Паскаль, предназначавшийся для обучения студентов структурной методике программирования. Язык получил свое название в честь Блеза Паскаля изобретателя первого вычислительного механического устройства. Позднее фирма Borland International, Inc (США) разработала систему программирования Турбо Паскаль для персональных компьютеров, которая вышла за рамки учебного применения и стала использоваться для научных и производственных целей. В Турбо Паскаль были внесены значительные дополнения к базовому стандарту Паскаля, описанного Н. Виртом. Со временем язык развивался. Начиная с версии 5.5, в Турбо Паскаль вводятся средства поддержки объектно-ориентированного программирования. В дальнейшем это привело к созданию Object Pascal языка с возможностями объектно-ориентированного программирования. В начале 1990-х гг. объединение элементов объектно-ориентированного программирования в Object Pascal с визуальной технологией программирования привело к созданию системы программирования Delphi. В главе 1 настоящего учебника рассматриваются базовые понятия, относящиеся к любому процедурному языку программирования высокого уровня. Основное внимание уделяется структурной методике построения алгоритмов: использованию базовых алгоритмических структур, выделению в решаемой задаче подзадач и составлению вспомогательных алгоритмов. На этой основе можно переходить к изучению любого процедурного языка, поддерживающего структурную методику. В главе 2 дается описание языка Паскаль в варианте Турбо Паскаль (версия 7.0). В языках Object Pascal и Delphi сохраняется преемственность к Турбо Паскалю. Содержание главы 3 ориентировано на глубокое освоение учащимися базовых понятий языков программирования высокого уровня на примере Паскаля. Такая подготовка облегчает изучение других языков программирования в будущем. В главе 4 излагаются основы объектно-ориентированного программирования на примере их реализации в Object Pascal. Здесь же рассматривается язык программирования Delphi, являющийся объектно-ориентированным расширением языка Паскаль, с реализацией технологии визуального программирования. 5
6 При подготовке к изучению данного курса желательно усвоение учащимися основ алгоритмизации в рамках школьного базового курса информатики. Обычно в школе алгоритмизация изучается с использованием учебных исполнителей, позволяющих успешно освоить основы структурной методики: построение алгоритмов из базовых структур; применение метода последовательной детализации. Желательно также иметь представление об архитектуре ЭВМ на уровне машинных команд (достаточно на модельных примерах учебных компьютеров, изучаемых в школьной информатике, т. е. не обязательно знание реальных языков команд или ассемблера). Это позволяет усвоить основные понятия программирования (переменной, присваивания); «входить в положение транслятора» и не делать ошибок, даже не помня каких-то деталей синтаксиса языка; предвидеть те «подводные камни», на которые может «напороться» программа в процессе выполнения. По существу все эти качества и отличают профессионального программиста от дилетанта. Еще одно качество профессионала это способность воспринимать красоту программы, т. е. получать эстетическое удовольствие от хорошо написанной программы. Нередко это чувство помогает интуитивно отличить неправильную программу от правильной. Однако основным критерием оценки программы должна быть, безусловно, не интуиция, а грамотно организованное тестирование. Процесс изучения и практического освоения программирования подразделяется на три части: изучение методов построения алгоритмов; изучение языка программирования; изучение и практическое освоение определенной системы программирования. Решению задач первой части посвящены главы 1 и 3 данного учебника. В главе 1 даются основные, базовые, понятия и принципы построения алгоритмов работы с величинами. В главе 3 излагаются некоторые известные методики полного построения алгоритмов, рассматриваются проблемы тестирования программ и оценки сложности алгоритмов. Языки программирования Турбо Паскаль и Delphi излагаются соответственно в главах 2 и 4 учебника. Однако подчеркнем, что данная книга это, прежде всего, учебник по программированию, а не по языкам Паскаль и Delphi, поэтому исчерпывающего описания данных языков вы здесь не найдете, они излагаются в 6
7 объеме, необходимом для начального курса программирования. Более подробное описание этих языков можно найти в книгах, указанных в списке литературы. В данном учебнике нет инструкций по работе с конкретными системами программирования для изучаемых языков, с ними студенты должны ознакомиться в процессе выполнения практических работ на ЭВМ, используя специальную литературу.
8 Глава 1 Основные принципы алгоритмизации и программирования 8 Из данной главы вы узнаете: последовательность этапов решения задачи на компьютере средствами программирования; что такое алгоритм решения задачи на компьютере; с какими данными работает компьютер; с помощью какого набора команд (системы команд) можно построить любой алгоритм решения задачи на компьютере; правила описания алгоритмов на блок-схемах и на учебном алгоритмическом языке; три основные алгоритмические структуры следование, ветвление, цикл; что такое трассировка алгоритма; логические основы программирования; сущность понятий «логическая величина», «логическое выражение», «логические операции»; правила выполнения логических операций и вычисления логических выражений; что такое вспомогательный алгоритм и как он описывается на алгоритмическом языке в форме процедуры; как происходит обращение к процедуре в основном алгоритме; в чем состоят принципы структурного программирования; историю развития языков и технологий программирования; классификацию языков программирования;
9 что такое трансляция и какие существуют способы трансляции; состав и структуру процедурных языков программирования высокого уровня; способы описания синтаксиса языков программирования. Вы научитесь: описывать алгоритмы различной структуры (линейные, ветвящиеся, циклические) в виде блок-схем и на учебном алгоритмическом языке; записывать логические выражения в качестве условий в ветвлениях и циклах; выполнять трассировку алгоритмов; описывать процедуры на алгоритмическом языке и обращения к ним из основного алгоритма Алгоритмы и величины Этапы решения задачи на ЭВМ. Работа по решению любой задачи с использованием компьютера включает в себя следующие шесть этапов: 1. Постановка задачи. 2. Формализация задачи. 3. Построение алгоритма. 4. Составление программы на языке программирования. 5. Отладка и тестирование программы. 6. Проведение расчетов и анализ полученных результатов. Часто эту последовательность называют технологической цепочкой решения задачи на ЭВМ (непосредственно к программированию из этого списка относятся п. 3 5). На этапе постановки задачи следует четко определить, что дано и что требуется найти. Важно описать полный набор исходных данных, необходимых для решения задачи. На этапе формализации чаще всего задача переводится на язык математических формул, уравнений и отношений. Если решение задачи требует математического описания какого-то реального объекта, явления или процесса, то ее формализация равносильна получению соответствующей математической модели. 9
10 Третий этап это построение алгоритма. Опытные программисты часто сразу пишут программы на определенном языке, не прибегая к каким-либо специальным средствам описания алгоритмов (блок-схемам, псевдокодам), однако в учебных целях полезно сначала использовать эти средства, а затем переводить полученный алгоритм на язык программирования. Первые три этапа это работа без компьютера. Последующие два этапа это собственно программирование на определенном языке в определенной системе программирования. На последнем шестом этапе разработанная программа уже используется в практических целях. Таким образом, программист должен уметь строить алгоритмы, знать языки программирования, уметь работать в соответствующей системе программирования. Основой профессиональной грамотности программиста является развитое алгоритмическое мышление. Понятие алгоритма. Одним из фундаментальных понятий в информатике является понятие алгоритма. Сам термин «алгоритм», заимствованный из математики, происходит от лат. Algorithmi написание имени Мухамеда аль-хорезми (), выдающегося математика средневекового Востока. В XII в. был осуществлен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение «столбиком», деление «уголком» многозначных чисел это первые алгоритмы в математике. Правила алгебраических преобразований и вычисление корней уравнений также можно отнести к математическим алгоритмам. В наше время понятие алгоритма трактуется шире. Алгоритм это последовательность команд управления каким-либо исполнителем. В школьном курсе информатики с понятием алгоритма и методами построения алгоритмов ученики знакомятся на примерах учебных исполнителей: Робота, Черепахи, Чертежника и др. Эти исполнители ничего не вычисляют. Они создают рисунки на экране, перемещаются в лабиринтах, перетаскивают предметы с места на место. Таких исполнителей принято называть исполнителями, работающими в обстановке. В разделе «Программирование» информатики изучаются методы программного управления работой ЭВМ, т. е. в качестве исполнителя выступает компьютер. Компьютер работает с величинами различными информационными объектами: числами, сим- 10
11 Рис Уровни данных относительно программы волами, кодами и др., поэтому алгоритмы, предназначенные для управления компьютером, называются алгоритмами работы с величинами. Данные и величины. Совокупность величин, с которыми работает компьютер, принято называть данными. По отношению к программе различают исходные, окончательные (результаты) и промежуточные данные, которые получают в процессе вычислений (рис. 1.1). Например, при решении квадратного уравнения ax 2 + bx + c = 0 исходными данными являются коэффициенты a, b, c, результатами корни уравнения x 1, x 2, а промежуточными данными дискриминант уравнения D = b 2-4ac. Для успешного освоения программирования необходимо усвоить следующее правило: всякая величина занимает свое определенное место в памяти ЭВМ, иногда говорят ячейку памяти. Термин «ячейка» для архитектуры современных ЭВМ несколько устарел, однако в учебных целях его удобно использовать. Любая величина имеет три основных свойства: имя, значение и тип. На уровне команд процессора величина идентифицируется адресом ячейки памяти, в которой она хранится. В алгоритмах и языках программирования величины подразделяются на константы и переменные. Константа неизменная величина, и в алгоритме она представляется собственным значением, например: 15, 34.7, k, True и др. Переменные величины могут изменять свои значения в ходе выполнения программы и представляются в алгоритме символическими именами идентификаторами, например: X, S2, cod15 и др. Любые константы и переменные занимают ячейку памяти, а значения этих величин определяются двоичным кодом в этой ячейке. Теперь о типах величин типах данных понятии, которое встречается при изучении в курсе информатики баз данных и электронных таблиц. Это понятие является фундаментальным в программировании. В каждом языке программирования существует своя концепция и своя система типов данных. Однако в любой язык входит 11
12 минимально необходимый набор основных типов данных: целые, вещественные, логические и символьные. Типы величин характеризуются множеством допустимых значений, множеством допустимых операций, формой внутреннего представления (табл. 1.1). Типы констант определяются по контексту (т. е. по форме записи в тексте), а типы переменных устанавливаются в описаниях переменных. По структуре данные подразделяются на простые и структурированные. Для простых величин, называемых также скалярными, справедливо утверждение одна величина одно значение, а для структурированных одна величина множество значений. Таблица 1.1. Основные типы данных Целые Тип Значения Операции Вещественные Логические Логические операции: И (and), ИЛИ (or), НЕТ (not). Операции отношений Символьные Целые положительные и отрицательные числа в некотором диапазоне, например: 23, -12, 387 Любые (целые и дробные) числа в некотором диапазоне, например: 2.5, -0.01, 45.0, True (истина) False (ложь) Любые символы компьютерного алфавита, например: a, 5, +, $ Арифметические операции с целыми числами: сложение, вычитание, умножение, целое деление и деление с остатком. Операции отношений (<, >, = и др.) Арифметические операции. Операции отношений Операции отношений Внутреннее представление Формат с фиксированной точкой Формат с плавающей точкой 1 True; 0 False Kоды таблицы символьной кодировки, например: ASCII один символ 1 байт; Unicode один символ 2 байт 12
13 Рис Компьютер как исполнитель программ на языке Паскаль К структурированным величинам относятся массивы, строки, множества и др. ЭВМ исполнитель алгоритмов. Как известно, каждый алгоритм (программа) составляется для конкретного исполнителя, т. е. в рамках его системы команд. О каком же исполнителе идет речь при изучении темы «Программирование для ЭВМ»? Ответ очевиден: исполнителем здесь является компьютер, а точнее говоря, комплекс ЭВМ + система программирования (СП). Программист составляет программу на том языке, на который ориентирована СП. Схематически это изображено на рис. 1.2, где входным языком исполнителя является язык программирования Паскаль. Независимо от того, на каком языке программирования будет написана программа, алгоритм решения любой задачи на ЭВМ может быть составлен из следующих команд: присваивания, ввода, вывода, обращения к вспомогательному алгоритму, цикла, ветвления. Далее для описания алгоритмов будут использоваться блоксхемы и учебный алгоритмический язык (АЯ), применяемый в школьном курсе информатики Линейные вычислительные алгоритмы Основным элементарным действием в вычислительных алгоритмах является присваивание значения переменной величине. Если значение константы определено видом ее записи, то переменная величина получает конкретное значение только в результате присваивания, которое может осуществляться двумя способами: с помощью команды присваивания и с помощью команды ввода. Рассмотрим пример. В школьном учебнике математики правило деления двух обыкновенных дробей описано следующим образом: 13
14 1) числитель первой дроби умножить на знаменатель второй дроби; 2) знаменатель первой дроби умножить на числитель второй дроби; 3) записать дробь, числитель которой есть результат выполнения п. 1, а знаменатель результат выполнения п. 2. Алгебраическая форма записи этого примера следующая: a b: c a d m = = d b c n. Теперь построим алгоритм деления дробей для ЭВМ, сохранив те же обозначения переменных, которые были использованы в алгебраическом выражении. Исходными данными здесь являются целочисленные переменные a, b, c, d, а результатом целые величины m и n. Блок-схема алгоритма деления дробей приведена на рис Данный алгоритм на учебном алгоритмическом языке будет иметь следующий вид: алг деление дробей нач цел a, b, c, d, m, n ввод a, b, c, d m:= a d n:= b c вывод m, n кон Формат команды присваивания следующий: переменная:= выражение Знак «:=» следует читать как «присвоить». Команда присваивания означает следующие действия, выполняемые компьютером: 1) вычисляется выражение; 2) полученное значение присваивается переменной. 14 Рис Блок-схема алгоритма деления дробей
15
В приведенном алгоритме присутствуют две команды присваивания. В блок-схемах команды присваивания изображаются в прямоугольниках. Такой блок называется вычислительным. При описании алгоритмов не обязательно соблюдать строгие правила записи выражений, это можно делать в обычной математической форме, так как это еще не язык программирования со строгим синтаксисом. В рассматриваемом алгоритме имеется команда ввода: ввод a, b, c, d В блок-схемах команда ввода записывается в параллелограмме блоке ввода-вывода. При выполнении этой команды процессор прерывает работу и ожидает действий пользователя. Пользователь должен набрать на устройстве ввода (клавиатуре) значения вводимых переменных и нажать клавишу ввода
16 Таблица 1.2. Изменение значений переменных при выполнении команды присваивания Kоманда a b a:= 1 1 b:= 2 a 1 2 a:= b 2 2 b:= a + b 2 4 Таблица 1.3. Обмен значениями между переменными Kоманда X Y Z ввод X, Y 1 2 Z:= X X:= Y Y:= Z Рассмотрим алгоритм, который часто используется при программировании. Даны две величины: X и Y. Требуется произвести между ними обмен значениями. Например, если сначала было X = 1, Y = 2, то после обмена должно стать X = 2, Y = 1. Этой задаче аналогична следующая ситуация. Имеются два стакана: один с молоком, другой с водой. Требуется произвести между ними обмен содержимым. Ясно, что в этом случае необходим третий стакан пустой. Последовательность действий при обмене будет такой: 1) перелить молоко из 1-го стакана в 3-й; 2) воду из 2-го стакана в 1-й; 3) молоко из 3-го стакана во 2-й. Аналогично для обмена значениями двух переменных требуется третья дополнительная переменная. Назовем ее Z. Тогда задачу обмена значениями можно решить последовательным выполнением трех команд присваивания (табл. 1.3). Пример со стаканами не совсем точно характеризует ситуацию обмена между переменными, так как при переливании жидкостей один из стаканов становится пустым. В результате же выполнения команды присваивания (X:= Y) переменная, стоящая справа (Y), сохраняет свое значение. Алгоритм деления дробей имеет линейную структуру, т. е. в нем все команды выполняются в строго определенной последовательности, каждая по одному разу. Линейный алгоритм состоит из команд присваивания, ввода, вывода и обращения к вспомогательным алгоритмам (что будет рассмотрено далее). При описании алгоритмов с помощью блок-схем типы данных, как правило, не указываются (но подразумеваются). В учебных алгоритмах (на А Я) для всех переменных типы данных указываются 16
17 явно и их описание производится сразу после заголовка алгоритма. При этом используются следующие обозначения: цел целые, вещ вещественные, лит символьные (литерные), лог логические. В алгоритме деления дробей все переменные целого типа Ветвления и циклы в вычислительных алгоритмах Составим алгоритм решения квадратного уравнения ax 2 + bx + c = 0. Эта задача хорошо знакома из математики. Исходными данными здесь являются коэффициенты a, b, c, а решением в общем случае два корня (x 1 и x 2), которые вычисляются по формуле x b b ac = - ± - 2a ,. Все используемые в этой программе величины вещественного типа. Алгоритм решения кваратного уравнения будет иметь следующий вид: алг корни квадратного уравнения вещ a, b, c, d, x1, x2 нач ввод a, b, c d:= b 2-4ac x1:= (-b + d)/(2a) x2:= (-b - d)/(2a) вывод x1, x2 кон Недостаток такого алгоритма виден «невооруженным глазом». Он не обладает важнейшим свойством, предъявляемым к качественным алгоритмам: универсальностью по отношению к исходным данным. Какими бы ни были значения исходных данных, алгоритм должен приводить к получению определенного результата и выполняться до конца. Результатом может быть числовой ответ, но может быть и сообщение о том, что при таких данных задача решения не имеет. Недопустимы остановки в середине алгоритма 17
18 из-за невозможности выполнения какой-либо операции. Данное свойство в литературе по программированию называют результативностью алгоритма (получение какого-то результата в любом случае). Для построения универсального алгоритма сначала требуется тщательно проанализировать математическое содержание задачи. Решение квадратного уравнения зависит от значений коэффициентов a, b, c. Проанализируем эту задачу, ограничиваясь поиском только вещественных корней: если a = 0, b = 0, c = 0, любое значение х решение уравнения; если a = 0, b = 0, c 0, уравнение решений не имеет; если a = 0, b 0, это линейное уравнение, имеющее одно решение x = - c/b; если a 0 и d = b 2-4ac 0, уравнение имеет два вещественных корня x 1, x 2 ; если a 0 и d < 0, уравнение не имеет вещественных корней. Блок-схема алгоритма решения квадратного уравнения показана на рис Этот же алгоритм на алгоритмическом языке будет иметь следующий вид: 18 алг корни квадратного уравнения вещ a, b, c, d, x1, x2 нач ввод a, b, c если a = 0 то если b = 0 то если c = 0 то вывод «Любое х решение» иначе вывод «Нет решений» кв иначе x:= -c/b вывод х кв иначе d:= b 2-4ac если d < 0 то вывод «Нет вещественных корней» иначе x1:= (-b + d)/(2a); x2:= (-b - d)/(2a) вывод «x1 =», x1, «x2 =», x2 кв кв кон
19 Рис Блок-схема алгоритма решения квадратного уравнения 19
20 В данном алгоритме многократно использована структурная команда ветвления, общий вид которой в виде блок-схемы показан на рис На алгоритмическом языке команду ветвления можно записать в следующем виде: 20 если условие то серия 1 иначе серия 2 кв В соответствии с приведенной блок-схемой команды ветвления сначала проверяется условие (вычисляется логическое выражение). Если условие истинно, то выполняется последовательность команд, на которую указывает стрелка с надписью «Да» (положительная ветвь) «Серия 1». В противном случае выполняется отрицательная ветвь команд «Серия 2». На АЯ условие записывается после служебного слова «если», положительная ветвь после слова «то», а отрицательная после слова «иначе». Буквами «кв» в такой записи обозначают конец ветвления. Если на ветвях одного ветвления содержатся другие ветвления, значит, алгоритм имеет структуру вложенных ветвлений. Именно такую структуру имеет алгоритм решения квадратного уравнения (см. рис. 1.4), в котором для краткости вместо слов «Да» и «Нет» использованы соответственно знаки «+» и «-». Рассмотрим следующую задачу: дано целое положительное число n. Требуется вычислить n! (n-факториал). Вспомним определение факториала: 1, если n = 0; n! = n, если n 1. Блок-схема алгоритма вычисления n! c тремя переменными целого типа: n аргумент, i промежуточная переменная, F результат приведена на рис Для проверки правильности указанного алгоритма построим трассировочную табл. 1.4, в которой для конкретных значений исходных данных по шагам прослеживается изменение переменных, входящих в алгоритм. Данная таблица составлена для случая n = 3. Приведенная трассировка доказывает правильность рассматриваемого алгоритма. Теперь запишем этот алгоритм на алгоритмическом языке:
21 Рис Блок-схема команды ветвления Рис Блок-схема алгоритма вычисления n! 21
22 Таблица 1.4. Трассировка алгоритма вычисления n! Шаг n F i Условие, да, да, да, нет 14 Вывод 22 алг факториал цел n, i, F нач ввод n F:= 1; i:= 1 пока i n, повторять нц F:= F i i:= i + 1 кц вывод F кон Данный алгоритм имеет циклическую структуру. В нем использована структурная команда цикл «Пока», или цикла с предусловием. Блок-схема команды цикла «Пока» показана на рис На АЯ она имеет следующий вид: пока условие, повторять нц серия кц
23 Рис Блок-схема команды цикла «Пока» Выполнение серии команд (тела цикла) повторяется пока условие цикла истинно. Когда условие становится ложным, выполнение цикла заканчивается. Служебные слова «нц» и «кц» обозначают соответственно начало и конец цикла. Цикл с предусловием это основная, но не единственная форма организации циклических алгоритмов: существует цикл с постусловием. Вернемся к алгоритму решения квадратного уравнения, рассмотрев его со следующей позиции: если a = 0 это уже не квадратное уравнение и его можно не решать. В данном случае будем считать, что пользователь ошибся при вводе данных, поэтому ввод следует повторить (рис. 1.8). Иначе говоря, в алгоритме будет предусмотрен контроль достоверности исходных данных с предоставлением пользователю возможности исправления ошибки. Наличие такого контроля еще один признак хорошего качества программы. На АЯ алгоритм решения квадратного уравнения с контролем ввода данных будет иметь следующий вид: алг квадратное уравнение вещ a, b, c, d, x1, x2 нач повторять ввод a, b, c до a 0 d:= b 2-4ac если d 0 то x1:= (-b + d)/(2a) x2:= (-b - d)/(2a) вывод x1, x2 иначе вывод «Нет вещественных корней» кв кон 23
24 Рис Блок-схема алгоритма решения квадратного уравнения с контролем ввода данных Блок-схема структурной команды цикла с постусловием или цикла «До» показана на рис На АЯ данную команду можно записать следующим образом: 24 повторять серия до условие Здесь используется условие окончания цикла, т. е. когда оно становится истинным, цикл заканчивает работу. Составим алгоритм решения следующей задачи: даны два натуральных числа M и N. Требуется вычислить их наибольший общий делитель НОД (M, N).
Программа по учебному предмету «Информатика» для 8 классов Рабочая программа составлена на основе Федерального государственного образовательного стандарта основного общего образования (Приказ МО РФ от
ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКЦИИ ЭТАПЫ РЕШЕНИЯ ЗАДАЧ НА ЭВМ: постановка задачи; математическое описание задачи; выбор и обоснование метода решения; алгоритмизация вычислительного процесса; составление
Пояснительная записка Рабочая программа базового уровня по информатике и ИКТ для обучающихся 8 класса 2016-2017 года составлена на основе: Федерального компонента государственного образовательного стандарта
Муниципальное бюджетное общеобразовательное учреждение «Средняя общеобразовательная школа 1» г. Губкинский РАССМОТРЕНО на заседании МО учителей математики и информатики Протокол 1 от 30.08.2016г Руководитель
Тема 7. Программирование на языке Паскаль. Основные конструкции. Реализация линейной и разветвляющейся структур. Общие сведения о языке программирования Паскаль Язык программирования Паскаль (Pascal) является
Урок 2. Запись арифметических выражений. Операторы вывода и вывода информации Запись арифметических выражений на языке КУМИР, как и на любом языке программирования, несколько отличается от обычной математической.
Powered by TCPDF (www.tcpdf.org) Пояснительная записка Рабочая программа по информатике и ИКТ для 9 класса разработана на основе: Федерального закона Российской Федерации «Об образовании в Российской Федерации»
Алгоритмизация и основы программирования Алгоритмизация Понятие алгоритма Алгоритм это точное предписание, которое определяет процесс, ведущий от исходных данных к требуемому конечному результату. Алгоритмами,
ЛЕКЦИЯ 1. Понятие алгоритма. Изображение алгоритма в виде блок схемы. Алгоритмы линейной и разветвляющейся структуры. Цель лекции: Знакомство с понятием алгоритма и возможностью его изображения в виде
Федеральное государственное бюджетное образовательное учреждение высшего образования «Казанский национальный исследовательский технический университет им. А.Н. Туполева КАИ» (КНИТУ КАИ) Зеленодольский
Лабораторная работа. Составление блок-схем алгоритмов. Цель работы Усвоить понятия: алгоритм как фундаментальное понятие информатики, способы описания, основные типы алгоритмов, освоить принципы решения
Лекция 3 БАЗОВЫЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ. ТИПЫ АЛГОРИТМОВ 1. Базовые алгоритмические структуры. 2. Представление алгоритмических структур с помощью команд. 3. Комбинации базовых команд. 4. Вспомогательные
) Планируемые результаты освоения учебного предмета Изучение информатики в основной школе направлено на достижение следующих результатов образования:. В направлении личностного развития: формирование ответственного
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Рабочая программа по информатике и ИКТ составлена в соответствии со следующими нормативными документами:. Федеральным компонентом государственного стандарта основного общего образования
Цель пособия помочь абитуриентам Образовательного частного учреждения высшего образования «Московский финансово-экономический институт» при подготовке к вступительным испытаниям по дисциплине «Информатика
Основы алгоритмизации Этапы решения задачи. Под решением конкретной задачи понимают не только определение результатов с помощью ЭВМ, а также всю подготовительную работу, которую необходимо выполнить для
Object Pascal Алфавит языка Лексическая структура языка Ячейка Значение Константа Переменная Операторы присваивания Система типов Арифметические выражения Логические выражения Строковые выражения Object
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА НОРМАТИВНЫЕ ДОКУМЕНТЫ Рабочая программа составлена на основе: федерального закона Российской Федерации от 29.12.2012 года 273-ФЗ «Об образовании в Российской Федерации» положения
СОДЕРЖАНИЕ стр. ПАСПОРТ РАБОЧЕЙ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ 3 СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ УСЛОВИЯ РЕАЛИЗАЦИИ РАБОЧЕЙ ПРОГРАММЫ УЧЕБНОЙ 8 ДИСЦИПЛИНЫ КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ
Муниципальное бюджетное общеобразовательное учреждение городского округа Тольятти «Школа 75 имени И.А. Красюка» Рассмотрено на заседании МО Протокол 1 от 27.08.2015 г. Согласовано на Педагогическом совете
Среднее ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВанИЕ И. г. семакин, а. п. Шестаков основы алгоритмизации и программирования Практикум Рекомендовано Федеральным государственным автономным учреждением «Федеральный институт
Программа дополнительного образования «ПРОГРАММИРУЕМ НА ЯЗЫКЕ ПАСКАЛЬ» Возраст обучающихся 11-16 лет (7,8,9 класс) Срок реализации 3 года Количество часов 102/1 Составитель: Сафиуллова Л.Е. Учитель информатики
Автономное учреждение профессионального образования Ханты-Мансийского автономного округа - Югры «Нефтеюганский политехнический колледж» Алгоритм. Компьютер как исполнитель команд. План 1. Понятие алгоритма
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ» (Н И У «Б е л Г У») ФАКУЛЬТЕТ
Муниципальное бюджетное общеобразовательное учреждение г. Астрахани «Основная общеобразовательная школа 31» Согласовано Утверждаю: Зам. директора по УВР Директор МБОУ г. Астрахани Е.В. Леонтьева «ООШ 31»
1 ОДОБРЕНА Предметной (цикловой) комиссией по спец.дисциплинам Разработана на основе Федерального государственного образовательного стандарта по специальности среднего профессионального образования 3001
Демонстрационный вариант контрольных измерительных материалов для проведения в 217 году промежуточной аттестации по ИНФОРМАТИКЕ и ИКТ в 8 классе Пояснения к демонстрационному варианту экзаменационной работы
2 Основы алгоритмизации 2.1 Основные определения и понятия 2.1.1 Алгоритм и алгоритмизация Понятие алгоритма такое же основополагающее для информатики, как и понятие информации. Термин «алгоритм» обязан
Алгоритмы с ветвящейся структурой Рассмотрим несколько задач, решение которых на компьютере получается с помощью ветвящихся алгоритмов. Первая задача: даны два числа, выбрать наибольшее из них. Пусть исходными
Министерство общего и профессионального образования Свердловской области ГБОУ СПО СО «ЕКАТЕРИНБУРГСКИЙ КОЛЛЕДЖ ТРАНСПОРТНОГО СТРОИТЕЛЬСТВА» Программа учебной дисциплины «Основы» для специальности 0115
Министерство общего и профессионального образования Свердловской области ГБОУ СПО СО «ЕКАТЕРИНБУРГСКИЙ КОЛЛЕДЖ ТРАНСПОРТНОГО СТРОИТЕЛЬСТВА» Программа учебной дисциплины «Теория алгоритмов» для специальности
Решение заданий из контрольного теста. Тема Алгоритмизация 1. Дан фрагмент алгоритма. Логическая операция and используется для обозначения одновременности выполнения условий. При начальных значениях переменных
Урок 1. Знакомство со средой программирования Кумир. Понятие величины Данная программная среда позволяет получить практические навыки построения и выполнения основных алгоритмических конструкций, применяемых
ЛЕКЦИЯ 2. Алгоритмы циклической структуры. Цель лекции: Знакомство с понятием алгоритма циклической струк туры. Приобретение навыков построения алгоритмов циклической с трук т уры. 5. Алгоритмы циклической
Аннотация к дисциплине «Основы программирования и алгоритмизации» Направление подготовки (специальность) 09.03.02 «Информационные системы и технологии» Профиль Информационные системы и технологии в строительстве
Программа вступительного испытания по общеобразовательному предмету «Информатика и ИКТ», входящего в перечень вступительных испытаний по основной образовательной программе высшего образования. Программа
Лекция 4. Алгоритмы. Языки программирования 1 План лекции П. 1. Понятие алгоритма, его свойства... 1 П. 2. Блок-схемы, базовые алгоритмические структуры... 2 П. 3. Виды языков программирования... 5 П.
Рабочая программа предмета Информатика и ИКТ для 9 класс Рабочая программа по информатике для 9 классов составлена на основе следующих нормативных документов: 1) Информатика. Программы для образовательных
Федеральное государственное автономное образовательное учреждение высшего профессионального образования «СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» Институт математики и фундаментальной информатики Базовая кафедра
Тема 6. Алгоритмы и языки программирования Алгоритмы основные понятия Существует несколько определений алгоритма, начиная с бытового, как набора предписаний, и заканчивая формальными определениями на основе
Определение алгоритма Три базовые структуры Свойства алгоритма Исполнитель алгоритма Формы записи алгоритма 1 Алгоритм описание последовательности действий (план), строгое исполнение которых приводит,
Глава 5 Элементы теории алгоритмов 31 Уточнение понятия алгоритма Ключевые слова: алгоритм теория алгоритмов универсальный исполнитель машина Тьюринга машина Поста нормальный алгорифм Маркова Зачем нужно
Аннотация рабочей программы по учебной дисциплине ОП.05 Основы программирования и баз данных Область применения рабочей программы Рабочая программа учебной дисциплины является частью образовательной программы
Рабочая программа по факультативному курсу «Программирование и другие вопросы к подготовке к ОГЭ по информатике» Составитель: Шадрина Наталья Михайловна учитель физики и информатики С. Июльское, 2017 Пояснительная
ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ УПРАВЛЕНИЕ ДИСТАНЦИОННОГО ОБУЧЕНИЯ И ПОВЫШЕНИЯ КВАЛИФИКАЦИИ Кафедра «Естественные науки» ИНФОРМАТИКА АЛГОРИТМЫ И АЛГОРИТМИЗАЦИЯ Учебно-методическое пособие
Министерство образования и Еауки Хабаровского края Краевое государственное авто омное общеобразовательеое учреждение Краевой центр образования Рассмотрено на заседании методического ччителеи Согласовано
Материалы для сайта по информатике база 10 класс Учитель: Александрова Т.А, Володькин Е.Г.. Тема Знать Уметь Банк заданий Алгоритмы, структуры алгоритмов, структурное программирование Учащиеся должны знать
Г л а в а 7 ОСНОВЫ АЛГОРИТМИЗАЦИИ Цель: ввести понятие алгоритма, изучить свойства алгоритма. Надо знать: определение алгоритма, свойства алгоритма, способы записи алгоритма, элементы блоксхемы алгоритма
Содержание. Пояснительная записка 3 2. Содержание учебного предмета 4 3. Организация контроля 5 4. Требования к уровню подготовки обучающихся 6 5. Учебно-методическое обеспечение 7 6. Материально-техническое
Класс: 8А, 8Б Сроки: 14-19 марта Форма: устный зачет по программированию Вопросы к зачеты по программированию 8А, 8Б класс 1. Понятие алгоритма и его свойства 2. Исполнитель алгоритмов. СКИ (система команд
Лекция: Понятие об архитектуре компьютера. Системы счисления. Цель: сформировать первичные представления о читаемой дисциплине, рассмотреть возможности перевода чисел в различные системы счисления и так
Введение в программирование Корюков И.В., 2012 г Базовые понятия программирования. Модели. Нас окружает огромное множество объектов дома, машины, деревья, животные Человек, познавая окружающий мир, изучает
КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ В НЕПРЕРЫВНОМ ОБРАЗОВАНИИ ОСНОВЫ АЛГОРИТМИЗАЦИИ 2 ТЕМЫ ЗАНЯТИЯ 1) Понятие алгоритма 2) Изображение алгоритма в виде блок-схемы 3) Алгоритмы линейной и разветвляющейся
Глава1. Передача информации в компьютерных сетях 6 часов (3+3) Вводное занятие Календарно-тематическое планирование 9а ТЕМА (РАЗДЕЛ) и КОЛ-ВО ЧАСОВ 9б ТЕМЫ УРОКОВ ВИДЫ ДЕЯТЕЛЬНОСТИ ДОМАШНЕЕ ЗАДАНИЕ 3.09
КАЛЕНДАРНО-ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ КУРСА «ИНФОРМАТИКИ и ИКТ» В 10 КЛАССЕ Тема урока 1 Правила техники безопасности в кабинете информатики. Инструктаж по пожарной безопасности. 2 Представление числовой
Основные элементы языка Язык Pascal (Паскаль), изобретенный в начале 70-х годов 20-го века Н. Виртом и названный в честь французского математика и философа Блеза Паскаля, является одним из наиболее распространенных
Основы алгоритмизации и программирования. Семакин И.Г., Шестаков А.П.
3-е изд. - М.: 2016. - 304 с.
В учебнике рассмотрены основы принципы алгоритмизации и программирования на базе языка Паскаль (версия Турбо Паскаль 7.0) Даны основные понятия объектно-ориентированного программирования и его реализация на языке Турбо Паскаль. Описана интегрированная среда программирования Delphi и визуальная технология создания графического интерфейса программ. Показана разработка программных модулей в этой среде. Учебник может быть использован при изучении общепрофессиональной дисциплины ОП «Основы алгоритмизации и программирования» в соответствии с требованиями ФГОС СПО для специальностей 230113 «Компьютерные системы и комплексы» и 230401 «Информационные системы (по отраслям)» укрупненной группы специальностей 230000 «Информатика и вычислительная техника». Для студентов средних профессиональных учебных заведений.
Формат: pdf
Размер: 7,3 Мб
Смотреть, скачать: drive.google
ОГЛАВЛЕНИЕ
Предисловие 4
Глава 1. Основные принципы алгоритмизации и программирования 8
1.1. Алгоритмы и величины 9
1.2. Линейные вычислительные алгоритмы 13
1.3. Ветвления и циклы в вычислительных алгоритмах 17
1.4. Логические основы алгоритмизации 26
1.5. Вспомогательные алгоритмы и процедуры 30
1.6. Основы структурного программирования 33
1.7. Развитие языков и технологий программирования 39
1.8. Структура и способы описания языков программирования высокого уровня 44
Глава 2. Программирование на языке Паскаль 49
2.1. Первое знакомство с языком Паскаль 50
2.2. Некоторые сведения о системах программирования на Паскале 56
2.3. Элементы языка Турбо Паскаль 57
2.4. Концепция типов данных 59
2.5. Арифметические операции, функции, выражения. Оператор присваивания 64
2.6. Ввод данных с клавиатуры и вывод на экран 70
2.7. Управление символьным выводом на экран 75
2.8. Логические величины, операции, выражения 81
2.9. Функции, связывающие различные типы данных 83
2.10. Программирование ветвящихся алгоритмов 86
2.11. Программирование циклических алгоритмов 90
2.12. Подпрограммы 96
2.13. Вычисление рекуррентных последовательностей 104
2.14. Графические средства Турбо Паскаля 113
2.15. Символьные строки 123
2.16. Массивы 129
2.17. Рекурсивные подпрограммы 139
2.18. Множества 144
2.19. Файлы 151
2.20. Комбинированный тип данных 162
2.21. Указатели и динамические структуры данных 168
2.22. Внешние подпрограммы и модули 179
Глава 3. Методы построения алгоритмов 189
3.1. Метод последовательной детализации 190
3.2. Рекурсивные методы 19В
3.3. Методы перебора в задачах поиска 201
3.4. Методы сортировки данных и сложность алгоритмов 208
Глава 4. Объектно-ориентированное программирование 217
4.1. Что такое объектно-ориентированное программирование 218
4.2. Объекты в Турбо Паскале 221
4.3. Интегрированная среда программирования Delphi 230
4.4. Компоненты Delphi. Свойства компонентов 234
4.5. Событийно-управляемое программирование 248
4.6. Технология создания приложенийв Delphi 253
4.7. Примеры разработки приложений Delphi 256
4.8. Иерархия классов 269
Приложения 275
Турбо Паскаль. Модуль CRT 275
Турбо Паскаль. Модуль GRAPH 278
DELPHI, Некоторые подпрогаммы 291
Список литературы 298
СРЕДНЕЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАНИЕ
И.Г.СЕМАКИН, А.П.ШЕСТАКОВ
ПРОГРАММИРОВАНИЯ
Допущено Министерством образования Российской Федерации
в качестве учебника для студентов образовательных учреждений среднего профессионального образования, обучающихся
по специальностям 2202 «Автоматизированные системы обработки инаюрмации и управления (по отраслям)», 2203 «Программное обеспечение вычислительной техники и автоматизированных систем»
ИЗДДТЕЛЬС МастерствоФ
УДК 681.3.06 ББК22.18
Р е ц е н з е н т - зав. кафедрой прикладной математики и информатики Пермского
государственного университета, д-р физ.-мат. наук, проф.С. В. Русаков
Семакин И. Г., Шестаков А. П.
С12 Основы программирования: Учебник. - М.: Мастерство, 2002. - 432 с.
ISBN 5-294-00054-7
Изложены основы структурной методики построения алгоритмов. Рас смотрены основы программирования на базе языка Паскаль (в версии Тур бо Паскаль-7.0). Изложен стандартный язык Си с некоторыми элементами его расширения в версии Си++. Представлены задачи по программирова нию, предназначенные для организации практикума на ЭВМ (более 800 заданий).
Для студентов средних профессиональных учебных заведений. Может быть использован учениками старших классов средней школы и студента ми начальных курсов высших учебных заведений.
УДК 681.3.06 ББК 22.18
Оригинал-макет данного издания является собственностью издательства «Мастерство», и его воспроизведение любым способом без согласия издательства запрещается
ПРЕДИСЛОВИЕ
Программирование все в большей степени становится заняти ем лишь для профессионалов. Объявленный в середине 1980-х гг. лозунг «Программирование - вторая грамотность» остался в про шлом. В понятие «компьютерная грамотность» сегодня входит преж де всего навык использования многообразных средств информа ционных технологий. Решая ту или иную информационную зада чу, необходимо выбрать адекватное программное средство. Это могут быть электронные таблицы, системы управления базами дан ных, математические пакеты и т.п. И только в том случае, когда подобные средства не дают возможности решить задачу, следует прибегать к универсальным языкам программирования.
Принято различать программистов двух категорий: приклад ных и системных. Системные программисты - это разработчики базовых программных средств ЭВМ (операционных систем, транс ляторов, сервисных средств и т.п.). Они являются профессиона лами высочайшего уровня в программировании. Прикладные про граммисты разрабатывают средства прикладного программного обеспечения ЭВМ, предназначенные для решения задач из раз личных областей (наука, техника, производство, сфера обслу живания, обучение и т.п.). Требования к качеству как приклад ных программ, так и системных сегодня очень высоки. Програм ма должна не только правильно решать задачу, но и иметь современный интерфейс, быть высоконадежной, дружественной по отношению к пользователю и т.д. Только такие программы могут выдерживать конкуренцию на мировом рынке программ ных продуктов. Программирование на любительском уровне се годня никому не нужно.
По мере развития компьютерной техники развивались также и методика, и технология программирования. Сначала возникает командное и операторное программирование, в 1960-х гг. бурно развивается структурное программирование, появляются линии логического и функционального программирования, а в после днее время - объектно-ориентированное и визуальное програм мирование.
Задача, которую следует ставить при первоначальном изучении программирования, - освоение основ структурной методики про граммирования. Для указанной цели наиболее подходящим сред ством является язык программирования Паскаль. Автор языка Пас каль - швейцарский профессор Никлаус Вирт - создавал его имен-
но для этого. Структурная методика остается основой программист ской культуры. Не освоив ее, человек, взявшийся изучать програм мирование, не имеет никаких шансов стать профессионалом.
Реализации Паскаля в версиях фирмы Borland для IBM, извест ных под названием Турбо Паскаль, значительно расширили язык по сравнению с вариантом Вирта. Начиная с версии 5.5 Турбо Паскаль становится также и языком объектного программирования.
Содержание третьей главы настоящего учебника ориентирова но на глубокое освоение студентами базовых понятий языков про граммирования высокого уровня в их реализации на Паскале. Та кая подготовка облегчает изучение других языков программиро вания. Изложение основ языков Си/Си++ в четвертой главе опирается на знания и навыки, полученные учащимися при изу чении Паскаля.
При изучении данного курса студентам понадобятся знания основ алгоритмизации в рамках школьного базового курса ин форматики. Обычно в школе алгоритмизация изучается с исполь зованием учебных исполнителей, с помощью которых можно ус пешно освоить основы структурной методики, а именно:
построение алгоритмов из базовых структур;
применение метода последовательной детализации. Желательным является знакомство с архитектурой ЭВМ на уров
не машинных команд (достаточно на модельных примерах учеб ных компьютеров, изучаемых в школьной информатике; совсем не обязательно изучение реальных языков команд или ассембле ра). Эти знания позволяют освоить основные понятия программи рования, такие как переменная, присваивание; «входить в поло жение транслятора» и благодаря этому не делать ошибок, даже не помня каких-то деталей синтаксиса языка; предвидеть те «под водные камни», на которые может «напороться» ваша программа в процессе выполнения. По существу, все эти качества и отличают профессионального программиста от дилетанта.
Еще одно качество профессионала - способность восприни мать красоту программы, получать эстетическое удовольствие оттого, что она хорошо написана. Нередко это чувство помогает интуитивно отличить неправильную программу от правильной. Однако основным критерием правильности является, безуслов но, не интуиция, а грамотно организованное тестирование.
Процесс изучения и практического освоения программирова ния делится на три части:
изучение методов построения алгоритмов;
изучение языка программирования;
изучение и практическое освоение определенной системы про граммирования.
Решению первой задачи посвящены вторая и пятая главы учеб ника. Во второй главе даются основные, базовые понятия и прин-
ципы построения алгоритмов работы с величинами. В пятой главе излагаются некоторые известные методики полного построения алгоритмов, обсуждаются проблемы тестирования программ, оцен ки сложности алгоритмов.
Языки программирования Турбо Паскаль и Си/Си++ излага ются в третьей и четвертой главах учебника соответственно. Под черкнем, что данная книга - это прежде всего учебник по про граммированию, а не по языкам Паскаль и Си. Поэтому исчерпы вающего описания данных языков вы здесь не найдете. Языки излагаются в том объеме, который необходим для начального курса программирования. Более подробное описание языков можно найти
в книгах, приведенных в списке литературы.
В учебнике нет инструкций по работе с конкретными система ми программирования для изучаемых языков. С ними студенты должны познакомиться в процессе практики на ЭВМ, используя другие источники.
Шестая глава представляет собой достаточно большой задач ник по программированию. Этот задачник можно использовать для организации практических и лабораторных занятий по любо му из изучаемых языков.
ГЛАВА 1. ОСНОВЫ АЛГОРИТМИЗАЦИИ
1.1. Алгоритмы и величины
Этапы решения задачи на ЭВМ. Работа по решению любой за дачи с использованием компьютера делится на следующие этапы:
1. Постановка задачи.
2. Формализация задачи.
3. Построение алгоритма.
4. Составление программы на языке программирования.
5. Отладка и тестирование программы.
6. Проведение расчетов и анализ полученных результатов.
Часто эту последовательность называют технологической цепоч кой решения задачи на ЭВМ. Непосредственно к программирова нию в этом списке относятся пункты 3, 4, 5.
На этапе постановки задачи должно быть четко сформулирова но, что дано и что требуется найти. Здесь очень важно определить полный набор исходных данных, необходимых для получения ре шения.
Второй этап - формализация задачи. Здесь чаще всего задача переводится на язык математических формул, уравнений, от ношений. Если решение требует математического описания ка кого-то реального объекта, явления или процесса, то форма лизация равносильна получению соответствующейматемати ческой модели.
Третий этап - построение алгоритма. Опытные программисты часто сразу пишут программы на языках, не прибегая к какимлибо специальным способам описания алгоритмов (блок-схемам, псевдокодам). Однако в учебных целях полезно использовать эти средства, а затем переводить полученный алгоритм на язык про граммирования.
Первые три этапа предусматривают работу без компьютера. Даль ше следует собственно программирование на определенном язы ке, в определенной системе программирования. Последний (шес той) этап - это использование уже разработанной программы в практических целях.
Таким образом, программист должен обладать следующими зна ниями и навыками:
уметь строить алгоритмы;
знать языки программирования;
уметь работать в соответствующей системе программирования.
Основой программистской грамотности является развитое ал горитмическое мышление.
Понятие алгоритма. Одним из фундаментальных понятий в ин форматике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происхо дит отAlgorithmi - латинского написания имени Мухаммеда альХорезми (787 - 850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математи ческого трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики много значных чисел. Именно эти правила в то время называли алго ритмами. Сложение, вычитание, умножение столбиком, деле ние уголком многозначных чисел - вот первые алгоритмы в ма тематике. Правила алгебраических преобразований, способы вычислений корней уравнений также можно отнести к матема тическим алгоритмам.
В наше время понятие алгоритма трактуется шире. Алгоритм -это последовательность команд управления каким-либо исполните лем. В школьном курсе информатики с понятием алгоритма, с ме тодами построения алгоритмов ученики знакомятся на примерах учебных исполнителей: Робота, Черепахи, Чертежника и т.д. Эти исполнители ничего не вычисляют. Они создают рисунки на экра не, перемещаются в лабиринтах, перетаскивают предметы с мес та на место. Таких исполнителей принято называтьисполнителями, работающими в обстановке.
В разделе информатики под названием «Программирование» изучаются методы программного управления работой ЭВМ. Сле довательно, в качестве исполнителя выступает компьютер. Ком пьютер работает с величинами - различными информационны ми объектами: числами, символами, кодами и т. п. Поэтому алго ритмы, предназначенные для управления компьютером, принято называть алгоритмами работы с величинами.
Данные и величины. Совокупность величин, с которыми рабо тает компьютер, принято называтьданными. По отношению к про грамме данные делятся наисходные, результаты (окончательные данные) ипромежуточные (рис. 1), которые получаются в про цессе вычислений.
Например, при решении квадратного уравнения ах 2 + Ьх + с = 0 исходными данными являются коэффициентыа, Ь, с; результата-
ми - корни уравнения х и х 2 ; промежуточным данным - дискри минант уравненияD =Ь 1 -4ас.
Для успешного освоения программирования необходимо ус воить следующее правило: всякая величина занимает свое опреде ленное место в памяти ЭВМ (иногда говорят - ячейку памяти). Хотя термин «ячейка» с точки зрения архитектуры современных ЭВМ несколько устарел, однако в учебных целях его удобно ис пользовать.
У всякой величины имеются три основных свойства: имя, зна чение итип. На уровне команд процессора величина идентифи цируется при помощи адреса ячейки памяти, в которой она хра нится. В алгоритмах и языках программирования величины де лятся наконстанты ипеременные. Константа - неизменная величина, и в алгоритме она представляется собственным значе нием, например: 15, 34.7,k, true и т.д. Переменные величины мо гут изменять свои значения в ходе выполнения программы и пред ставляются символическими именами - идентификаторами, на пример:X, S2, cod15. Любая константа, как и переменная, занимает ячейку памяти, а значение этих величин определяется двоичным кодом в этой ячейке.
Теперь о типах величин - типах данных. С понятием типа дан ных вы уже, возможно, встречались, изучая в курсе информати ки базы данных и электронные таблицы. Это понятие является фундаментальным для программирования.
В каждом языке программирования существует своя концеп ция типов данных, своя система типов. Тем не менее в любой язык входит минимально необходимый набор основных типов дан ных, к которому относятся: целый, вещественный, логический исим вольный типы. С типом величины связаны три ее характеристики: множество допустимых значений, множество допустимых опера ций, форма внутреннего представления. В табл. 1.1 представлены эти характеристики основных типов данных.
Т а б л и ц а 1.1
Внутреннее |
|||||
Значения | Операции | представле |
|||
Целые положитель | Арифметические опе | ||||
ные и отрицатель | рации с целыми чис | фиксирован |
|||
ные числа в некото | лами: +, -, , целое | ной точкой |
|||
ром диапазоне.венный | дробные) числа в | операции: +, -, , /. | плавающей |
||
некотором диапа | Операции отношений | ||||
Примеры: 2,5,-0,01, | |||||
45,0, 3,6- 109 | |||||
Логичес | True (истина), | Логические опера | |||
False (ложь) | ции: И (and), ИЛИ | ||||
Операции отношений | |||||
Символь | Любые символы | Операции отношений | Коды табли |
||
компьютерного | цы символь |
||||
алфавита. | ной кодиров |
||||
Примеры: "а", "5", "+", | ки. 1 символ - |
||||
Типы констант определяются по контексту (т.е. по форме за писи в тексте), а типы переменных устанавливаются в описаниях переменных.
Есть еще один вариант классификации данных - классифи кация по структуре. Данные делятся на простые иструктуриро ванные. Для простых величин (их еще называют скалярными) справедливо утверждение: одна величина - одно значение, для структурированных: одна величина - множество значений. К структурированным величинам относятся массивы, строки, множества и т.д.
ЭВМ - исполнитель алгоритмов. Как известно, всякий алго ритм (программа) составляется для конкретного исполнителя в рамках его системы команд. О каком же исполнителе идет речь при обсуждении вопроса о программировании для ЭВМ? Ответ очевиден: исполнителем является компьютер. Точнее говоря, ис полнителем является комплекс ЭВМ + Система программирова ния (СП). Программист составляет программу на том языке, на который ориентирована СП. Иногда в литературе такой комплекс называют виртуальной ЭВМ. Например, компьютер с работаю щей системой программирования на Бэйсике называют Бэйсикмашиной; компьютер с работающей системой программирования на Паскале называют Паскаль-машиной и т.п. Схематически это изображено на рис. 2.
