Основы алгоритмизации и программирования
Покупка
Основная коллекция
Тематика:
Программирование и алгоритмизация
Издательство:
Издательство ФОРУМ
Год издания: 2020
Кол-во страниц: 431
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
Среднее профессиональное образование
ISBN: 978-5-00091-570-7
ISBN-онлайн: 978-5-16-108363-5
Артикул: 038960.09.01
К покупке доступен более свежий выпуск
Перейти
В учебном пособии рассмотрены основные понятия алгоритмизации и программирования, представлены все виды задач обработки данных, приводятся таблицы сравнительного анализа форматов, операторов, процедур, описания данных для различных языков программирования, дается развернутое и практически полное описание языков и систем программирования Pascal, Basic, С; а также сред Visual Basic и Delphi. Все разделы дополнены примерами и задачами.
Предназначено для учащихся колледжей, может быть рекомендовано студентам вузов.
Тематика:
ББК:
УДК:
ОКСО:
- Среднее профессиональное образование
- 09.02.01: Компьютерные системы и комплексы
- 09.02.02: Компьютерные сети
- 09.02.03: Программирование в компьютерных системах
- 09.02.04: Информационные системы (по отраслям)
- 09.02.05: Прикладная информатика (по отраслям)
- 09.02.06: Сетевое и системное администрирование
- 09.02.07: Информационные системы и программирование
- 10.02.01: Организация и технология защиты информации
- 10.02.02: Информационная безопасность телекоммуникационных систем
- 10.02.03: Информационная безопасность автоматизированных систем
- 10.02.04: Обеспечение информационной безопасности телекоммуникационных систем
- 10.02.05: Обеспечение информационной безопасности автоматизированных систем
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
СРЕДНЕЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАНИЕ Серия основана в 2001 году О.Л. ГОЛИЦЫНА И.И. ПОПОВ ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ УЧЕБНОЕ ПОСОБИЕ 4-е издание, исправленное и дополненное Допущено Министерством образования и науки Российской Федерации в качестве учебного пособия для студентов учреждений среднего профессионального образования, обучающихся по специальности «Информатика и вычислительная техника» Москва 2020 ИНФРА-М
УДК 004.9(075.32) ББК 32.973я723 Г60 Р е ц е н з е н т ы: Романов В.П. — кандидат технических наук, профессор, заведующий кафедрой проектирования автоматизированных информационных систем Российского экономического университета имени Г.В. Плеханова; Максимович Г.Ю. — кандидат технических наук, доцент кафедры автоматизированных информационных систем Российского государственного гуманитарного университета Голицына О.Л. Г60 Основы алгоритмизации и программирования : учебное пособие / О.Л. Голицына, И.И. Попов. — 4-е изд., испр. и доп. — Москва : ФОРУМ : ИНФРА-М, 2020. — 431 с. — (Среднее профессиональное образование). ISBN 978-5-00091-570-7 (ФОРУМ) ISBN 978-5-16-015980-5 (ИНФРА-М, print) ISBN 978-5-16-108363-5 (ИНФРА-М, online) В учебном пособии рассмотрены основные понятия алгоритмизации и программирования, представлены все виды задач обработки данных, приводятся таблицы сравнительного анализа форматов, операторов, процедур, описания данных для различных языков программирования, дается развернутое и практически полное описание языков и систем программирования Pascal, Basic, С; а также сред Visual Basic и Delphi. Все разделы дополнены примерами и задачами. Предназначено для учащихся колледжей, может быть рекомендовано студентам вузов. УДК 004.9(075.32) ББК 32.973я723 ISBN 978-5-00091-570-7 (ФОРУМ) ISBN 978-5-16-015980-5 (ИНФРА-М, print) ISBN 978-5-16-108363-5 (ИНФРА-М, online) © Голицына О.Л., Попов И.И., 2008 © Голицына О.Л., Попов И.И., 2014, с изменениями © ФОРУМ, 2014
Предисловие Вплоть до XVII в. деятельность общества в целом и каждого человека в отдельности была направлена на овладение веществом, т. е. познание свойств вещества и изготовление сначала примитивных, а потом все более сложных орудий труда, вплоть до механизмов и машин, позволяющих изготовлять потребительские ценности. Затем в процессе становления индустриального общества на первый план вышла проблема овладения энергией — сначала тепловой, затем электрической, наконец, атомной. Овладение энергией позволило освоить массовое производство потребительских ценностей и, как следствие, повысить уровень жизни людей и изменить характер их труда. В то же время человечество стремилось познать тайны мироздания, составляя его модели, выделяя общие закономерности, пытаясь увидеть некоторое единство в разнообразии материальных объектов. Одним из первых обобщений нарождающейся науки стало понятие вещества. Эта идея возникла в философии древней Греции и развилась до современных квантовых и волновых теорий вещества. Казалось, что все в мире можно объяснить, описав совокупность взаимодействующих материальных частиц. Следующим принципиальным понятием стала энергия. Его появление было связано с развитием техники, созданием двигателей, технических преобразователей энергии. Физические, химические, биологические процессы стали рассматриваться с позиции передачи и преобразования энергии. Однако исследование все более сложных объектов в технике, биологии, обществе поставило науку перед фактом невозможности детального описания их поведения на языке материальноэнергетических моделей. Потребность человека запомнить и выразить информацию об окружающем мире стала толчком к появлению письменности, книгопечатания, живописи, фотографии, радио, телевидения. В истории развития цивилизации можно выделить несколько информационных революций — преобразование общественных отношений из-за кардинальных изменений в сфере обработки информации, информационных технологий. Следствием подобных преобразований являлось приобретение человеческим обществом нового качества. Первая информационная революция связана с изобретением письменности. Появилась возможность распространения знаний и сохранения их для передачи последующим поколениям. 3
Вторая (конец XVI в.) — вызвана изобретением книгопечатания, которое радикальным образом изменило общество и культуру. Третья (конец XIX в.) — обусловлена открытием принципов электросвязи, благодаря которому появились телеграф, телефон, радио, позволяющие оперативно передавать информацию. Четвертая революция (70-е годы XX в.) связана с созданием персональных компьютеров. Пятая революция (90-е годы ХХ в.) знаменует создание открытого информационного общества на базе глобальной сети Internet, мобильной и спутниковой связи. В конце XX в. человечество вступило в новую стадию развития — стадию построения информационного общества. Информация стала важнейшим фактором экономического роста, а уровень развития информационной деятельности и степень вовлеченности и влияния ее на глобальную информационную инфраструктуру превратились в важнейшее условие конкурентоспособности страны в мировой экономике. Понимание неизбежности прихода этого общества наступило значительно раньше. Австралийский экономист К. Кларк еще в 40-е годы говорил о наступлении общества информации и услуг, общества с новыми технологическими и экономическими возможностями. Американский экономист Ф. Махлуп выдвинул предположение о наступлении информационной экономики и превращении информации в важнейший товар в конце 50-х годов. В конце 60-х годов Д. Белл фиксировал превращение индустриального общества в информационное. Что касается стран, ранее входивших в СССР, то процессы информатизации в них развивались замедленными темпами. Информатика меняет всю систему общественного производства и взаимодействия культур. С наступлением информационного общества начинается новый этап не только научно-технической, но и социальной революции. Меняется вся система информационных коммуникаций. Разрушение старых информационных связей между отраслями экономики, направлениями научной деятельности, регионами, странами усилило экономический кризис конца века в странах, которые уделяли развитию информатизации недостаточное внимание. Важнейшая задача общества — восстановить каналы коммуникаций в новых экономических и технологических условиях для обеспечения четкого взаимодействия всех направлений экономического, научного и социального развития как отдельных стран, так и в глобальном масштабе. В качестве средства для хранения, переработки и передачи информации научно-технический прогресс предложил обществу компьютер (электронно-вычислительную машину — ЭВМ). Но вычислительная техника не сразу достигла необходимого уровня. В ее развитии отмечают предысторию и четыре поколения ЭВМ. Предыстория начинается в 4
глубокой древности с различных приспособлений для счета (абак, счеты), а первая счетная машина появилась лишь в 1642 г. Ее изобрел французский математик Паскаль. Построенная на основе зубчатых колес, она могла суммировать десятичные числа. Все четыре арифметических действия выполняла машина, созданная в 1673 г. немецким математиком Лейбницем. Она стала прототипом арифмометров, использовавшихся с 1820 г. до 60-х годов ХХ в. Впервые идея программноуправляемой счетной машины, имеющей арифметическое устройство, устройства управления, ввода и печати (хотя и использующей десятичную систему счисления), была выдвинута в 1822 г. английским математиком Бэббиджем. Проект опережал технические возможности своего времени и не был реализован. Лишь в 40-х годах ХХ в. удалось создать программируемую счетную машину на основе электромеханических реле, которые могли пребывать в одном из устойчивых состояний — «включено» и «выключено». Это сделать технически проще, чем пытаться реализовать десять различных состояний, необходимых для обработки информации на основе десятичной системы счисления. С каждым новым поколением ЭВМ увеличивались быстродействие и надежность их работы при уменьшении стоимости и размеров, совершенствовались устройства ввода и вывода информации. В соответствии с трактовкой компьютера как технической модели информационной функции человека — устройства ввода приближаются к естественному для человека восприятию информации (зрительному, звуковому) и, следовательно, операции по вводу в компьютер становятся все более удобными для человека. Современный компьютер — это универсальное многофункциональное электронное автоматическое устройство, которое в современном обществе взяло на себя значительную часть работ, связанных с обработкой информации. По историческим меркам компьютерные технологии обработки информации еще очень молоды и находятся в самом начале своего развития. Компьютерные технологии сегодня преобразуют или вытесняют старые технологии обработки информации. Неотъемлемой частью компьютера является программное обеспечение (ПО), которое можно разделить на системное и прикладное программное обеспечение. Операционная система является основой системного ПО, обеспечивает функционирование и взаимосвязь всех компонентов компьютера и предоставляет пользователю доступ к его аппаратным возможностям. Прикладное программное обеспечение можно в свою очередь разделить на две группы программ: средства разработки и приложения. Средства разработки — это инструменты программиста. Традиционными средствами разработки являются системы (среды) программирования (СП), использующие алгоритмические языки программиро5
вания (ЯП). Основой систем программирования являются трансляторы, т.е. программы, обеспечивающие перевод исходного текста программы на машинный язык (объектный код). Приложения — это программы, решающие задачи в конкретных предметных областях, такие как текстовые и графические редакторы, электронные таблицы, издательские системы, системы управления базами данных (СУБД) и т.д. Настоящее учебное пособие посвящено вопросам разработки алгоритмов и программ с использованием языков программирования высокого уровня и систем программирования. В первой главе рассмотрены основные принципы и понятия, связанные с алгоритмизацией и программированием — алгоритмы, структуры данных, кодирование символьной, цифровой, графической информации, интерфейсы и их программирование, языки и системы программирования с общих позиций, внешние устройства и обращение к файлам и базам данных. Дается также необходимое представление о разработке приложений. В последующих разделах последовательно рассмотрены языки программирования Pascal, Basic, C, а также даны краткие характеристики систем программирования Delphi и Visual Basic. В начале каждого раздела приводятся примеры текстов простой диалоговой программы и программы сортировки массива на соответствующем ЯП. Каждый из разделов заканчивается примерами и упражнениями. Во второй главе дается описание ЯП Pascal, в том числе примеры простых программ на языке Pascal, лексика языка, переменные и константы, типы данных. Далее рассматриваются выражения и операции, операторы языка, структурированные типы данных, динамические данные, процедуры и функции. Описываются компоненты структуры программы, методы организации ввода-вывода данных и работы с файлами. В третьей главе представлена интегрированная среда разработки приложений Delphi, базирующаяся на объектно-ориентированном расширении языка Pascal. Описывается интерфейс среды Delphi, характеристика проекта Delphi, компиляция и выполнение проекта, разработка приложения. Рассматриваются средства управления параметрами интегрированной среды разработки, связь между ЯП Pascal и визуальной средой разработки приложений Delphi. В качестве стандартных примеров рассматривается разработка приложений «Калькулятор» и «Редактор текстов». В четвертой главе дается описание ЯП Basic, в том числе примеры программ на языке Basic, лексика языка, переменные и типы данных, операции и операторы, процедуры и функции, методы организации ввода-вывода данных и работы с файлами. 6
В пятой главе дается краткая характеристика интегрированной среды разработки приложений Visual Basic. Рассматривается интерфейс среды, состав проекта, компиляция и выполнение проекта, разработка приложения. В качестве примера приводится разработка программы «Калькулятор» в среде Visual Basic. В шестой главе рассматривается ЯП С (Си), приводятся примеры двух простых программ на Си. Дается описание элементов языка Си, структуры программы. Рассматриваются объявления переменных, выражения и присваивание значений, операторы языка и функции. Описываются средства и процедуры ввода-вывода и доступа к файлам. 7
Глава 1. Основные принципы алгоритмизации и программирования 1.1. Алгоритмы и программы Понятие алгоритма. Понятие алгоритма является одним из основных понятий современной математики. Еще на самых ранних ступенях развития математики (Древний Египет, Вавилон, Греция) в ней стали возникать различные вычислительные процессы чисто механического характера. С их помощью искомые величины ряда задач вычислялись последовательно из исходных величин по определенным правилам и инструкциям. Со временем все такие процессы в математике получили название алгоритмов (алгорифмов). Термин алгоритм происходит от имени средневекового узбекского математика Аль-Хорезми, который еще в IX в. (825) дал правила выполнения четырех арифметических действий в десятичной системе счисления. Процесс выполнения арифметических действий был назван алгоризмом. С 1747 г. вместо слова алгоризм стали употреблять алгорисмус, смысл которого состоял в комбинировании четырех операций арифметического исчисления — сложения, вычитания, умножения, деления. К 1950 г. алгорисмус стал алгорифмом. Смысл алгорифма чаще всего связывался с алгорифмами Евклида — процессами нахождения наибольшего общего делителя двух натуральных чисел, наибольшей общей меры двух отрезков и т.п. Под алгоритмом понимали конечную последовательность точно сформулированных правил, которые позволяют решать те или иные классы задач. Такое определение алгоритма не является строго математическим, так как в нем не содержится точной характеристики того, что следует понимать под классом задач и под правилами их решения. Первоначально для записи алгоритмов пользовались средствами обычного языка (словесное представление алгоритмов). Уточним понятие словесного представления алгоритма на примере нахождения произведения n натуральных чисел — факториал числа n (c = n!), т.е. вычисления по формуле с = 1234...n. 8
Этот процесс может быть записан в виде следующей системы последовательных указаний (пунктов): 1. Полагаем с равным единице и переходим к следующему пункту. 2. Полагаем i равным единице и переходим к следующему пункту. 3. Полагаем c = i c и переходим к следующему пункту. 4. Проверяем, равно ли i числу n. Если i = п, то вычисления прекращаем. Если i < п, то увеличиваем i на единицу и переходим к пункту 3. Рассмотрим еще один пример алгоритма — нахождение наименьшего числа М в последовательности из п чисел a1, а2, …, аn (n 0). Прежде чем записать словесный алгоритм данного примера, детально рассмотрим сам процесс поиска наименьшего числа. Будем считать, что процесс поиска осуществляется следующим образом. Первоначально в качестве числа М принимается a1, т. е. полагаем М = a1, после чего М сравниваем с последующими числами последовательности, начиная с а2. Если М ¶ а2, то М сравнивается с а3, если М ¶ a3, то М сравнивается с а4, и так до тех пор, пока найдется число at < М. Тогда полагаем М = at и продолжаем сравнение с М последующих чисел из последовательности, начиная с at+1, и так до тех пор, пока не будут просмотрены все п чисел. В результате просмотра всех чисел М будет иметь значение, равное наименьшему числу из последовательности (I — текущий номер числа). Этот процесс может быть записан в виде следующей системы последовательных указаний: 1. Полагаем i = 1 и переходим к следующему пункту. 2. Полагаем М = ai и переходим к следующему пункту. 3. Сравниваем i с п; если i < п, переходим к 4 пункту, если i = п, процесс поиска останавливаем. 4. Увеличиваем i на 1 и переходим к следующему пункту. 5. Сравниваем ai с М. Если М ¶ ai , то переходим к пункту 3, иначе (М > ai ) переходим к пункту 2. В первом алгоритме в качестве элементарных операций используются простейшие арифметические операции умножения, которые могли бы быть разложены на еще более элементарные операции. Мы такого разбиения не делаем в силу простоты и привычности арифметических правил. Алгоритмы, в соответствии с которыми решение поставленных задач сводится к арифметическим действиям, называются численными алгоритмами. Алгоритмы, в соответствии с которыми решение поставленных задач сводится к логическим действиям, называются логическими алгоритмами. Примерами логических алгоритмов могут служить алгоритмы поиска минимального числа, поиска пути на графе, поиска пути в лабиринте и др. 9
Алгоритмом, таким образом, называется система четких однозначных указаний, которая определяет последовательность действий над некоторыми объектами и после конечного числа шагов приводит к получению требуемого результата. Свойства алгоритмов. Каждое указание алгоритма предписывает исполнителю выполнить одно конкретное законченное действие. Исполнитель не может перейти к выполнению следующей операции, не закончив полностью выполнения предыдущей. Предписания алгоритма надо выполнять последовательно одно за другим, в соответствии с указанным порядком их записи. Выполнение всех предписаний гарантирует правильное решение задачи. Поочередное выполнение команд алгоритма за конечное число шагов приводит к решению задачи, к достижению цели. Разделение выполнения решения задачи на отдельные операции (выполняемые исполнителем по определенным командам) — важное свойство алгоритмов, называемое дискретностью. Анализ примеров различных алгоритмов показывает, что запись алгоритма распадается на отдельные указания исполнителю выполнить некоторое законченное действие. Каждое такое указание называется командой. Команды алгоритма выполняются одна за другой. После каждого шага исполнения алгоритма точно известно, какая команда должна выполняться следующей. Алгоритм представляет собой последовательность команд (также инструкций, директив), определяющих действия исполнителя (субъекта или управляемого объекта). Таким образом, выполняя алгоритм, исполнитель может не вникать в смысл того, что он делает, и вместе с тем получать нужный результат. В этом случае говорят, что исполнитель действует формально, т.е. отвлекается от содержания поставленной задачи и только строго выполняет некоторые правила, инструкции. Это очень важная особенность алгоритмов. Наличие алгоритма формализовало процесс, исключило рассуждения. Если обратиться к другим примерам алгоритмов, то можно увидеть, что и они позволяют исполнителю действовать формально. Таким образом, создание алгоритма дает возможность решать задачу формально, механически исполняя команды алгоритма в указанной последовательности. Построение алгоритма для решения задачи из какой-либо области требует от человека глубоких знаний в этой области, бывает связано с тщательным анализом поставленной задачи, сложными, иногда очень громоздкими рассуждениями. На поиски алгоритма решения некоторых задач ученые затрачивают многие годы. Но когда алгоритм создан, решение задачи по готовому алгоритму уже не требует каких-либо рассуждений и сводится только к строгому выполнению команд алгоритма. 10
К покупке доступен более свежий выпуск
Перейти