![](/stc/img/evkova.png)
Алгоритмизация как обязательный этап разработки программы
Содержание:
Введение
Актуальность темы работы обусловлена возникновением новых перспективных тенденций в разработке более качественного программного обеспечения. В работе неслучайно будет сделан акцент на применения понятия алгоритмизации к разработке программного обеспечения,поскольку,согласновсемизвестномуправилу,лишь20%правильно разработанных программприносят80%прибыли организации.
Практическая значимость работы состоит в том, что данная работа содержит обоснование понятия алгоритмизация как обязательного этапа разработки программы.
Цельюработыявляетсяопределениеиосвещениесовременныхтенденцийвразработке программного обеспечения на основе понятий алгоритмизации.
Для достижения поставленной цели были поставлены задачи:
-определить содержание и характеристики основных понятий алгоритмизации как основного аспекта программирования;
-рассмотреть основные понятия алгоритма, его свойства и способы записи;
-рассмотреть основные конструкции построения алгоритмов.
1. Основные понятия алгоритмизации
1.1. Построение информационной модели разработки программного обеспечения
В настоящее время в деятельности каждого человека возрастает доля умственного труда, требуется решать практические задачи, связанные с обработкой, хранением, передачей информации. В то же время растет число людей, профессионально занятых информационной работой. Для ее автоматизации применяется компьютер как универсальное средство работы с информацией.
Решение задачи с применением компьютера предполагает следующие этапы:
Постановка задачи. Построение информационной модели.
Формализация задачи. Представление информационной модели в виде, удобном для компьютерной обработки.
Построение алгоритма решения задачи.
Запись алгоритма на языке программирования, составление программы.
Ввод программы в память компьютера. Пробный запуск.
Отладка и тестирование программы.
Получение и анализ результатов.
Рассмотрим подробнее каждый из перечисленных этапов.
Постановка задачи.Как правило, практические задачи формулируются достаточно понятно с точки зрения пользователя, но такая формулировка не обладает достаточной четкостью и строгостью.
Примеры:
- рассчитать примерную стоимость декоративного ремонта (покраски) школьной мебели;
- разработать наиболее эффективный (калорийный, разнообразный и дешевый) рацион питания в школьной столовойи т.д.
Чтобы такую задачу можно было решить с помощью компьютера, надо выполнить постановку задачи: выяснить, что известно и что явится результатом решения, а также как связаны исходные данные и результаты. Для этого важно определить существенные свойства объектов и явлений, о которых идет речь в задаче, и пренебречь несущественными.
Иногда об этом забывают. Например, если в задаче требуется определить площадь верхней поверхности стола (столешницы), не задумываясь говорят, что надо измерить длину и ширину. Однако существенным свойством стола может оказаться то, что он круглый, тогда затруднительно вести речь о длине и ширине. Кроме того, даже если определили, что столешница имеет прямоугольную форму, следует договориться, что небольшие неровности не оказывают существенного влияния на величину площади.
Важно также определить, в каких единицах и с какой точностью будут произведены измерения и вычисления. Кроме того, следует определить ограничения, налагаемые на возможные значения исходных данных и результатов. В примере с прямоугольным столом длина и ширина не могут быть отрицательными числами, а также иметь нереально большие или малые значения.
Все эти сведения образуют информационную модель задачи.
Главное свойство модели – упрощать изучаемое явление, сохраняя его существенные свойства. Информационной моделью задачи можно назвать информацию об объектах и явлениях, фигурирующих в задаче, значимую с точки зрения задачи и зафиксированную в текстовой, числовой или иной сигнальной форме.
Шаги построения информационной модели:
- Определить существенные и несущественные свойства объектов и явлений, описываемых в задаче.
- Выделить характеристики объектов и явлений, значимые с точки зрения задачи, и на этой основе определить исходные данные. Для исходных данных, выраженных в числовой форме, соотнести единицы измерения, определить точность и указать ограничения, налагаемые на их значения.
- Определить, что является результатом решения задачи и в какой форме он должен быть получен. Указать ограничения.
- Выявить связи между исходными данными и результатами. Если такие связи можно выразить на языке математики, то говорят о математической модели задачи как о частном случае информационной модели.
- Определить метод достижения результата.
На этапе формализации задачи происходит фиксация информационной модели, выбирается форма представления данных, образующих информационную модель, наиболее удобная для компьютерной обработки. Часто первые два этапа не имеют четкой границы и могут рассматриваться как единое целое.
Рассмотрим пример.
Задача. Определить, успеют ли к поезду путешественники, которые отправились от места стоянки к станции на автомобиле.
Построение информационной модели. Существенными характеристиками являются: расстояние от места стоянки до станции; время, которое осталось до отхода поезда; характер движения автомобиля. Предположим, что автомобиль двигался с некоторой начальной скоростью и постоянным ускорением. Тогда время, которое автомобиль находился в пути, надо сравнить с имеющимся запасом времени и сделать соответствующий вывод. Время в пути можно определить из соотношения между расстоянием, начальной скоростью и ускорением, которые будут являться исходными данными. Все эти характеристики имеют числовые значения (вещественные числа) и должны быть положительны. Промежуточный результат – время в пути – также должен выражаться положительным числом. Кроме того, значения начальной скорости и ускорения должны быть в пределах разумного. Единицы измерения: км, час, км/час, км/час за час.
Формализация.
Исходные данные:
S - расстояние от места стоянки до станции
tz - запас времени до отхода поезда
V0 - начальная скорость
а - ускорение
Результат: сообщение о том, успеют ли путешественники на поезд.
Связь между исходными данными и результатом: для получения сообщения следует вычислить промежуточный результат tp – время в пути – и сравнить его с запасом времени. Время в пути вычисляется, исходя из формулы пути при равноускоренном движении.
Это корень квадратного уравнения. Его дискриминант и корни:
Данное уравнение будет иметь как положительный, так и отрицательный корень. Из них следует выбрать положительный, исходя из наложенных ограничений.
На основе выбранного метода определяется точный порядок действий для достижения результата. Такая последовательность действий, выполнение которой приведет к достижению результата, называется алгоритмом. Алгоритм решения задачи может быть составлен с разной степенью подробности. Вначале составляется последовательность из небольшого числа достаточно крупных шагов, затем выполняется более подробное описание каждого шага – детализация алгоритма. Для фиксации алгоритма используются различные способы: словесное описание, язык графических схем,псевдокод и др.
Чтобы алгоритм мог быть выполнен компьютером, он должен быть записан на понятном ему языке. Однако компьютер воспринимает и может обрабатывать только двоичные коды (последовательности нулей и единиц). Следовательно, исходные данные и команды алгоритма должны быть представлены в двоичных кодах. Однако для человека это весьма неудобно, поэтому были разработаны языки, предназначенные для записи алгоритмов, которые, с одной стороны, близки естественным языкам, а с другой стороны, построены по достаточно строгим правилам, чтобы записанные на них алгоритмы можно было автоматически по формальным правилам перевести в двоичные коды. Такие языки называются языками программирования, а алгоритм, записанный на таком языке (так же, как и алгоритм, записанный в двоичных кодах), называется программой.
С появлением персональных компьютеров этап составления алгоритма во многом соединяется с этапом программирования так же, как и со следующим этапом.
На больших вычислительных центрах, при решении достаточно больших и сложных задач вводом программ занимаются люди специальной профессии – операторы ЭВМ. Кроме ввода программ операторы выполняют подготовку данных – ввод данных в память, запись их на внешние носители. Программист, работающий на ПК, вводит программу и данные сам.
После того как программа введена, следует ее пробный запуск. В случаях, которые следует считать исключительными, программа исполняется сразу и выдает некоторый результат. Гораздо чаще приходится отыскивать причины, по которым программа не работает или работает не так, и исправлять их – отлаживать программу.
Процесс поиска и исправления ошибок в программе называется отладкой. Ошибки могут возникнуть при наборе, в результате нарушения правил записи программ на языке программирования – так называемые синтаксические ошибки. Обнаружить и исправить их помогают специальные инструментальные программы (программы синтаксического контроля), входящие в состав системы программирования. Система анализирует программу и выдает сообщение о месте и характере ошибки. Часто ошибки связаны с тем, что некоторая синтаксически правильная конструкция не может быть выполнена (например, деление на нуль или попытка присвоить величине целого типа вещественное значение). В этом случае также появляется сообщение о причине отказа и указывается, какая именно команда не может быть выполнена.
Гораздо сложнее отыскать ошибки, допущенные при составлении алгоритма, которые, в конечном итоге, приводят к неправильной работе программы: отсутствие результата, зацикливание, неверный результат. В этом случае полезен бывает пошаговый контроль выполнения программы.
Важным этапом процесса отладки является тестирование программы, т.е. испытание ее путем введения теста – определенного набора исходных данных, для которого результат работы отдельных блоков или программы в целом известен заранее.
Часто в рамках разработки информационной модели накладываются ограничения на исходные данные. В этом случае программа должна реагировать на ввод неверных значений: останавливать работу или запрашивать повторный ввод. Как правило, в программе предусматривается защита от ввода неверных данных или от других непредусмотренных действий пользователя. Тогда в процессе тестирования проверяется качество такой защиты.
Умение удачно подобрать такой тест, при котором ошибка (если она есть) наиболее вероятна, и предусмотреть разнообразные варианты хода вычислительного процесса, а также действия пользователя (порой весьма непредсказуемые), и, следовательно, защитить работу программы от всяких неожиданностей – большое искусство программиста.
Простейший пример теста: если программа содержит ветвление, т.е. требуется выбор способа действий в зависимости от выполнения условия, надо проверять ее работу с теми исходными данными, при которых условие выполняется, и с теми, при которых оно не выполняется.
До последнего времени IV, V и VI этапы были необходимыми этапами решения задачи с помощью ЭВМ. При этом языки и системы программирования были теми программными инструментами, с помощью которых создавались новые программы для решения задач пользователя. Однако с расширением круга задач, для решения которых используется компьютер, растет число людей, которые, не будучи профессиональными программистами, применяют компьютер в своей работе.
В связи с этим созданы разнообразные программные средства, которые являются основой информационных технологий, применяемых для решения разнообразных практических задач, таких, как обработка текстов и электронных таблиц, создание графических изображений, доступ к информации, хранящейся в базе данных, решение математической задачи, расчет технической конструкции и многое другое. Для их решения в распоряжении пользователя ЭВМ имеется обширное программное обеспечение.
В процессе построения информационной модели задачи пользователь определяет, какие действия ему потребуется выполнить для достижения результата, и в соответствии с этим решает, каким программным средствомвоспользоваться. Если в его распоряжении имеется программа, подходящая для решения данной задачи, то пользователь выбирает ее в качестве инструмента (СУБД, табличный процессор, математический пакет и др.). Если же готовым прикладным программным средством воспользоваться нельзя, придется использовать технологию программирования.
Какая бы технология решения задач на компьютере ни использовалась, необходимым этапом будет получение и анализ результата: проверяется соответствие полученных результатов ожидаемому в рамках построенной информационной модели задачи, а также оценивается, насколько полученный результат соотносится с реальной практикой.
На этом этапе выявляется, насколько построенная информационная модель соответствует реальности. Дело в том, что чем больше свойств объектов и явлений признано существенными и учтено, тем в большей степени модель отражает действительность. Однако учет большого числа характеристик ведет к усложнению модели, затруднениям в математическом выражении связей между характеристиками. Обычно стараются найти баланс между полнотой соответствия информационной модели реальному состоянию дел и ее сложностью в процессе уточнения модели (постепенного увеличения числа учитываемых существенных свойств).
1.2. Алгоритм, его свойства, способы записи
Понятие алгоритм – одно из основных понятий информатики. Это фундаментальное «первоначальное» понятие, которому нельзя дать строгого определения в терминах более простых понятий. Существуют описательные определения алгоритма, каждое из которых уточняет это понятие.
Например:
Алгоритм – организованная последовательность действий.
Алгоритм – понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение поставленной цели или решение поставленной задачи.
В математике существует ряд уточнений понятия алгоритма, каждое из которых в известной степени сужает это понятие, привлекая внимание к различным его сторонам. В качестве уточнений понятия алгоритма рассматриваются машина Тьюринга, нормальные алгорифмы Маркова и др.
В быту каждый человек сталкивается с алгоритмом как с последовательностью действий, приводящих к достижению цели, с первых своих шагов: существует достаточно строго определенный порядок пеленания младенца. Подросшего ребенка мама учит одеваться, не нарушая установленного порядка, и не надевать шапочку раньше трусиков и рубашки – с этих пор у каждого из нас складывается свой определенный порядок совершения утреннего туалета.
В начальных классах школы дети изучают порядок выполнения арифметических действийнад многозначными числами. Этот порядок был предложен выдающимся математиком средневекового Востока Мухаммедом аль-Хорезми и по латинскому написанию его имени (Alhorithmi) был назван алгоритмом. В дальнейшем это понятие в значительной мере расширилось.
В профессиональной деятельности мы также сталкиваемся с необходимостью строго следовать установленному порядку действий: правилам работы на токарном станке, инструкции по заправке нитив швейную машинку, порядку выполнения медицинских процедур (например, инъекций) и др.
Рассмотрим свойства алгоритмов.
Исполнение алгоритма распадается на последовательность отдельных шагов. Выполнить каждый шаг предписывает команда. Таким образом, алгоритм представляет собой последовательность команд, определяющих действия исполнителя. Алгоритм имеет прерывистую (дискретную) структуру: только выполнив одну команду, исполнитель может приступить к выполнению следующей. Это свойство называется дискретностью.
В описании этого свойства использовано важное понятие – исполнитель алгоритма. Это субъект или автоматическое устройство, действующее под управлением алгоритма. Всякий алгоритм составляется для конкретного исполнителя с учетом его возможностей. Чтобы выполнить алгоритм в целом, исполнитель должен быть в состоянии выполнить каждую отдельную команду алгоритма.
Набор команд, которые может выполнить данный исполнитель системой команд исполнителя (СКИ), или набором допустимых действий исполнителя.
Правильно составленный алгоритм содержит только те команды, которые входят в систему команд исполнителя, для которого он написан. Такое свойство называется понятностью. Понятными для исполнителя считаются те команды, которые он может выполнить. Например, человек, не умеющий складывать однозначные числа (не знающий таблицы сложения), не сможет воспользоваться описанным аль-Хорезми порядком сложения многозначных чисел.
Важным свойством алгоритма является точность (определенность, однозначность). Каждая команда алгоритма должна однозначно восприниматься исполнителем и предполагать его определенное действие. Выполнив шаг алгоритма, исполнитель должен точно знать, какой шаг выполнять следующим. Примером неточного алгоритма является фраза из рецепта «всыпать 2-4 столовые ложки сахара» или классическое изречение «казнить нельзя помиловать».
Исполнение алгоритма должно приводить к получению результата (свойство результативности) за конечное число шагов (свойство конечности).
Желательно, чтобы алгоритм удовлетворял свойству массовости, т.е. мог быть применен для решения не только одной конкретной задачи, но и некоторого класса однотипных задач.
Например, правило сложения многозначных чисел не зависит от количества разрядов в слагаемых или их цифрового состава. Оно работает, даже если число представлено не в десятичной системе счисления, а в позиционной системе счисления с любым целочисленным основанием.
Если исполнитель может выполнить каждую команду алгоритма в отдельности и выполняет их последовательно, шаг за шагом, при этом действия исполнителя на каждом шаге однозначно определены, то исполнитель может не задумываться о цели алгоритма и даже не знать о ней, но независимо от этого достичь данной цели, только лишь строго выполняя предписания алгоритма. В этом случае исполнитель действует формально, т.е. отвлекается от цели и лишь строго выполняет инструкции. Формальное исполнение алгоритмов лежит в основе управления автоматическими устройствами. Действительно, простейшие операции, на которые при создании алгоритма расчленяется процесс решения задачи, может реализовать и машина, специально созданная для выполнения отдельных команд алгоритма и выполняющая их в последовательности, указанной в алгоритме.
Однако и человек может быть формальным исполнителем. Если он не знает цели выполняемой работы, ему придется строго следовать инструкциям.
Компьютер является формальным исполнителем алгоритмов. Чтобы он мог решать задачу в строгом соответствии с инструкциями, он должен получить алгоритм решения. Таким образом, алгоритм является управляющей информацией.
Существует несколько способов записи (фиксации) алгоритмов. Для человека основным является словесный способ. Но запись алгоритма на естественном языке весьма громоздка, не всегда однозначно понимается и не может быть формализована, т.е. не будет понятна компьютеру. Если же мы хотим использовать компьютер в качестве исполнителя, то алгоритм должен быть записан на понятном ему языке. В идеале это машинный язык, язык последовательностей двоичных сигналов (машинных кодов), которые несут информацию об исходных данных и командах, которые надо над ними выполнить. Однако это может быть и язык программирования высокого уровня, конструкции которого могут быть переведены в машинные коды по строгим формальным правилам. Такой перевод возможен, ибо для языка программирования высокого уровня характерны строгие правила записи, не допускающие неточности или двусмысленного толкования, а набор символов и слов, принятых в языке (алфавит) жестко ограничен.
В то же время основой для разработки языков программирования высокого уровня является естественный язык (чаще всего английский) в соединении с математическим языком символов и формул, поэтому языки программирования высокого уровня достаточно близки человеку и могут быть им освоены без излишних трудностей.
Компьютер в целом является исполнителем алгоритмов, но каждое программное средство можно также интерпретировать как исполнителя, обладающего определенным набором допустимых действий. Это может быть текстовый редактор, система программирования Турбо Паскаль или исполнитель Горошина, который умеет перемещаться по четырем направлениям на заданное число шагов.
Если алгоритм записан на языке, понятном исполнителю, он превращается в программу.
Программа – алгоритм, записанный на языке программирования.
Перевод алгоритма с естественного языка на язык программирования не всегда прост, поэтому часто используются следующие способы записи алгоритмов:
графические схемы алгоритмов, где различные алгоритмические конструкции изображаются в виде определенных геометрических фигур (блоков), соединенных в последовательности их выполнения;
псевдокоды.
Псевдокод – система обозначений и правил для единообразной и точной записи алгоритмов.
Псевдокод ориентирован на человека, но облегчает перевод на язык программирования, поскольку требует соблюдения определенных правил записи. Примером псевдокода может служить школьный алгоритмический язык.
2. Основные алгоритмические конструкции
Предписание исполнителю о совершении последовательности действий для решения поставленной задачи – алгоритм – представляет собой перечень команд, которые требуется выполнить в определенном порядке, чаще всего последовательно, друг за другом. Но такой последовательный (линейный) порядок выполнения действий недостаточен для решения большинства задач. Во многих случаях требуется многократно повторять некоторую группу действий (циклический процесс), причем количество повторений не всегда известно заранее. Не менее часто приходится делать выбор между несколькими способами действий, проверяя выполнение некоторого условия (ветвление, развилка).
Таким образом, для организации действий в алгоритмах применяются различные формы, называемые алгоритмическими конструкциями.
Выделяют три основные алгоритмические конструкции: следование, ветвление, цикл. В математике доказана теорема о том, что любой алгоритм может быть составлен с использованием только этих трех алгоритмических конструкций, хотя существуют и другие конструкции, которые сокращают запись алгоритма, упрощают работу с ним, облегчают понимание.
2.1. Конструкция следования
Конструкция следования – это такая форма организации действий, когда действия выполняются последовательно, одно за другим.
Об алгоритме, в составе которого нет других конструкций, кроме следования, говорят, что он имеет линейную структуру, что это линейный алгоритм.
На школьном алгоритмическом языке конструкция следования выглядит следующим образом.
Команда 1
Команда 2
Команда 3
………….
Команда N
Здесь представлен лишь фрагмент алгоритма, поэтому отсутствуют указатели его начала и конца. Многоточия показывают, что алгоритм уже начался и далее будет продолжен, на то же указывают входящие и исходящие стрелки в графических схемах. Этот прием будет использоваться и далее.
Последовательно друг за другом могут исполняются не только отдельные команды алгоритма, но и целые блоки – серии команд. Такой общий случай представлен в виде графической схемы (блок-схемы) алгоритма.
Серия команд 1
Серия команд 2
Серия команд N
Здесь в качестве серий команд могут выступать:
- простые команды (одна или несколько);
- обращения к вспомогательным алгоритмам;
- структурные команды (ветвления и циклы).
Фактически, каждый алгоритм можно разбить на достаточно крупные блоки, в состав которых войдут в различном порядке все перечисленные выше объекты, и из таких блоков составить линейный алгоритм.
2.2. Конструкция ветвления
Конструкция ветвления – это форма организации действий, при которой в зависимости от выполнения (невыполнения) некоторого условия выполняется одна из двух серий команд.
Алгоритм, содержащий конструкцию ветвления, имеет разветвляющуюся структуру.
Исполнитель, который в состоянии исполнять такие алгоритмы, должен иметь в своей системе команд команду ветвления, которая, как и цикл, относится к структурным командам. Получив такую команду, исполнитель проверяет, выполняется указанное условие или нет, и в зависимости от этого выбирает один из двух способов действий. Следовательно, чтобы исполнитель мог выполнить команду ветвления, он должен «уметь» проверять условие – проверка условия должна быть его допустимым действием.
Рассмотрим запись конструкции ветвления на алгоритмическом языке и в виде графической схемы.
условие
да
нет
Серия команд 1
Серия команд 2
Если <условие>
то <серия команд 1>
иначе <серия команд 2>
конец ветвления
С ветвлением мы встречаемся в самых разнообразных ситуациях. Например, фрагмент инструкции, которую давал своему посланнику принц из сказки о Золушке, мог бы выглядеть так:
Примерить туфельку
Если туфелька девушке впору
то привезти невесту принца во дворец
иначе ехать дальше
конец ветвления
В математике часто приходится вычислять значение функции, которое в зависимости от значения аргумента, находится по разным формулам.
⎧ х, при х>=0
Например: y = ⎨
⎩ -x, при х<0
Алгоритм вычисления такой функции можно представить в виде следующей графической схемы:
x>=0 условие
да
нет
Ввести x
Н
Y:=x
Y:=-x
Вывести Y
КН
Часто команда ветвления используется в алгоритмах при проверке допустимости исходных данных. Например, при вычислении значения функцииY = ‾‾X , если пользователь введет значение Х < 0, необходимо вывести сообщение о неверном вводе и прервать выполнение программы.
Кроме полной формы команды ветвления, рассмотренной выше, используется сокращенная форма.
условие
Серия команд 1
да
нет
Если <условие>
то <серия команд 1>
конец ветвления
Она применяется в алгоритмах, когда в случае невыполнения условия никаких действий производить не требуется.
Пример: Если идет дождь
товзять зонт
конец ветвления
Необходимо подчеркнуть важность указателя, отмечающего конец ветвления. Он помогает избежать двусмысленностей и ошибок, разделяя команды, которые требуется выполнять в случае выполнения (невыполнения) условия, и команды, подлежащие выполнению независимо от условия, т.е. не входящие в структуру ветвления.
Может возникнуть ситуация, когда выбирать приходится не из двух, а из трех и более способов действий. Тогда применяется многократное (многовариантное) ветвление. Примером такого ветвления является фрагмент алгоритма расстановки цветных шариков на соответствующие полки:
- вынуть шарик из корзины
- Если шарик белый
- то поставить шарик на белую полку
- иначе еслишарик черный
- то поставить шарик на черную полку
- иначе поставить шарик на красную полку
- конец ветвления
- конец ветвления
Важно, что проверяемых условий всегда на одно меньше, чем способов действий. Такая задача может быть решена также с использованием команды выбора:
- вынуть шарик из корзины
- Выбор
- при шарик белый то поставить шарик на белую полку
- при шарик черный то поставить шарик на черную полку
- при шарик красный то поставить шарик на красную полку
- конец выбора
Выше отмечалось, что проверка условия должна быть допустимым действием исполнителя. Результатом проверки условия будет некоторое логическое значение: истина или ложь, т.е. в качестве условия может выступать либо логическая переменная, либо выражение, которое может принимать логическое значение. Чаще всего это сравнение. Условия могут быть составными, т.е. состоящими из нескольких простых, соединенных знаками логическихопераций.
Условие 1 и Условие 2 – такое составное условие выполняется, если одновременно выполняются оба простых условия;
Условие 1 или Условие 2 – такое составное условие выполняется, если выполняется хотя бы одно изпростых условий.
Используется также и отрицание:
не Условие – такое составное условие выполняется тогда, когда входящее в него условие не выполняется.
Фактически, здесь рассмотрены операции над логическими величинами (конъюнкция, дизъюнкция, инверсия). В качестве составных условий могут выступать и более сложные логические выражения.
В языках программирования конструкция ветвления реализуется посредством операторов языка.
В языке Бейсик для этого служит оператор условного перехода:
70
80 IF<условие>
THEN <серия команд 1 >
[ELSE<серия команд 2>]
90
Квадратные скобки указывают, что ветвь «иначе» (ЕLSE) может отсутствовать, т.е. возможно сокращенное ветвление.
Здесь оператор ветвления занимает одну логическую строку программы. Ее окончание и есть указатель окончания ветвления, т.е. строка 90 исполняется обязательно, независимо от выполнения условия.
В такой ситуации серия команд может содержать несколько последовательных операторов, разделенных двоеточием, и вся конструкция должна поместиться в одну логическую строку. Если этого сделать нельзя, приходится использовать переход:
80 IF<условие>THEN<N1 > [ELSE<N2 >],
где N1 и N2 – номера строк, с которых следует продолжать исполнение программы в случае выполнения или невыполнения условия.
В результате получится неструктурная программа, понимание логики которой, а значит и поиск ошибок, будут значительно затруднены. В последних, более совершенных версиях Бейсика сделаны шаги к преодолению этого недостатка.
В языке Паскаль для реализации конструкции ветвления используется условный оператор и оператор варианта (оба относятся к группе составных операторов).
Условный оператор записывается так:
If<условие>
then<оператор 1>
else<оператор 2>;
Здесь «оператор 1» и «оператор 2» – операторы, которые могут быть простыми, но могут быть и составными и иметь достаточно сложную структуру. В простейшем случае это может быть последовательность простых операторов, заключенных в операторные скобки.
If<условие>
then
begin
<простой оператор>
…………………….
<простой оператор >
end
else
begin
<простой оператор >
……………………….
<простой оператор >
end;
Важное правило: перед «else» знак «;» не ставится.
В качестве «оператора 1» или «оператора 2» могут вновь выступать условные операторы, тогда придем к случаю многократного, или вложенного, ветвления. Возможность использовать принцип вложенности операторов – одно из основных достоинств языка Паскаль, позволяющее реализовать структурное программирование.
Однако выбор из более чем двух способов действий позволяет сделать и оператор варианта:
Case<переменная>of
<1-е значение переменной > :<оператор 1>
<2-е значение переменной > :<оператор 2>
……………………………………..
<N-е значение переменной > :<оператор N>
else<оператор N+1>
end;
Здесь переменная должна быть обязательно переменной порядкового типа.
Для переменных порядкового типа можно перечислить все их возможные значения, и порядок их следования строго определен – для каждого значения можно указать следующее и предыдущее.
2.3. Конструкция цикла
Конструкция цикла – это форма организации действий, при которой выполнение одной и той же последовательности действий повторяется несколько раз.
Действия, выполнение которых надо повторять несколько раз, называются телом цикла. Тело цикла представляет собой серию команд. В алгоритме всегда должен присутствовать указатель, отделяющий тело цикла от основной части алгоритма.
Различают два основных типа циклов: цикл с параметром и цикл с условием.
Цикл с параметром
Он применяется, когда количество повторений известно заранее.
При этом параметр (переменная цикла) изменяется от своего начального значения до конечного с заданным шагом и определяет количество повторений.
Запись цикла с параметром на алгоритмическом языке выглядит так:
- начальноеконечноешаг
- для <имя параметра> от <значение> до <значение> шаг <изменения>
- параметрапараметрапараметра
- нц
- <тело цикла>
- кц
Если шаг изменения не указан, по умолчанию он принимает единичное значение.
Порядок исполнения алгоритма:
- параметр принимает начальное значение;
- для этого значения исполняется тело цикла;
- параметр увеличивается на величину шага;
- проверяется, осталось ли новое значение параметра меньшим или равным заданного конечного значения:
- если да – тело цикла исполняется вновь для нового значения параметра;
- если нет, т.е. значение параметра превысило конечное значение – исполнение цикла останавливается (выход из цикла).
Пример. Пусть требуется наполнить пустую200-литровую бочку с помощью 10-литрового ведра.
алг Бочка
нач
дляномер ведра от 1 до 20
нц
наполнить ведро
вылить его содержимое в бочку
кц
кон
Здесь в качестве значения параметра взят номер выливаемого ведра, его конечное значение получается из простого расчета.
Однако количество повторений рассчитать не так просто. К тому же все изменится, если, к примеру, взять 5-литровое ведро. Поэтому лучше взять в качестве параметра количество литров (объем) воды, уже находящейся в бочке.
алг Бочка
нач
для объем воды от 0 до 200 шаг 10
нц
наполнить ведро
вылить его содержимое в бочку
кц
кон
Теперь для 5-литрового ведра изменится только шаг.
Если начальное значение параметра больше конечного – шаг следует принять отрицательным. В нашем примере это ситуация выливания воды из бочки.
В языках программирования цикл с параметром реализуется следующим образом.
Бейсик
60 FOR<имя параметра> = <начальное>TO<конечное> STEP <величина>
значениезначениешага
70
80 <тело цикла>
120 NEXT [<имя параметра>]
Номера строк могут быть любыми. Здесь конкретные числа взяты для определенности.
В Бейсике параметр цикла – переменная вещественного типа. Ее начальное, конечное значения и шаг изменения могут быть любыми действительными числами. В этой ситуации не всегда можно точно знать количество повторений. Тогда о применимости цикла с параметром можно сказать – он применяется, если заранее известно количество повторений или границы изменения числового параметра.
Паскаль
For<имя параметра>:=<начальное значение>to<конечное значение>do< тело цикла >
Здесь в качестве тела цикла может выступать любой простой или составной оператор, при необходимости следует использовать операторные скобки. Если операторных скобок нет, то считается, что в тело цикла входит лишь один оператор.
В Паскале параметром может быть только переменная порядкового типа. Это не обязательно число, может быть и символ, и логическая переменная. Вещественная переменная не может выступать в качестве параметра цикла.
Шаг изменения параметра предполагается равным единице. Применительно к нашему примеру, бочку пришлось бы наполнять литровой банкой или в качестве параметра взять номер выливаемого ведра, как в первом случае.
Если начальное значение параметра превышает конечное, предусмотрен отрицательный шаг – минус единица. Тогда запись выглядит так:
For<имя параметра>:=<начальное значение>downto<конечное значение>do< тело цикла >
На каждом шаге исполнения цикла параметр изменяется на единицу.
Ограничения, накладываемые в языке Паскаль на тип параметра цикла и шаг его изменения, сужают область применения цикла с параметром, но делают работу с циклами более строгойи осмысленной.
Если вдуматься, цикл с параметром есть, по сути, сокращенная запись линейного алгоритма. Мы знаем, что надо записать определенную группу команд заданное число раз, и в принципе такую замену, хотя и нерациональную, можно было бы произвести.
Если же количество повторений заранее неизвестно, линейный алгоритм в принципе записать нельзя. Требуется иной тип цикла.
Цикл с условием
Он применяется, когда количество повторений заранее неизвестно и зависит от выполнения некоторого условия.
Пусть в нашем примере с бочкой изменятся условия: первоначально в ней есть некоторое количество воды, и неизвестно, сколько потребуется долить, т.е. тело цикла будет выполняться до тех пор, пока бочка неполная или до момента ее наполнения.
Здесь возникает вопрос, когда проверять условие – перед очередным выполнением тела цикла или после него. В зависимости от ответа различают циклы с предусловием и с постусловием.
Цикл с предусловием (цикл «пока»)
Проверка условия происходит перед очередным исполнением тела цикла.
Запись на алгоритмическом языке:
пока < условие >
нц
< тело цикла >
кц
Пока условие выполняется (соответствующее логическое выражение имеет значение «истина»), повторяется исполнение тела цикла. Как только условие перестало выполняться – прекращается исполнение цикла (выход по лжи).
Если условие изначально не выполняется, тело цикла может не быть исполнено ни разу.
Цикл с постусловием (цикл «до»)
Проверка условия происходит после очередного исполнения тела цикла, т.е. тело цикла обязательно будет исполнено хотя бы один раз.
Запись на алгоритмическом языке:
повторять
< тело цикла >
до< условие >
Исполнение тела цикла происходит, если условие не выполняется (соответствующее логическое выражение имеет значение «ложь»). Как только наступает выполнение условия, исполнение тела цикла прекращается (выход по истине).
Запись в виде графических схем такова.
Цикл с предусловием Цикл с постусловием
Условие
Тело цикла
Условие
да
нет
Тело цикла
да
нет
Пример
алг Бочка
нач
пока бочка не полная
нц
наполнить ведро
вылить его содержимое в бочку
кц
кон
алг Бочка
нач
повторять
наполнить ведро
вылить его содержимое в бочку
до бочка полная
кон
Тело цикла с условием должно содержать команды, которые влияют на выполнение условия, в противном случае цикл может оказаться бесконечным. В приведенном примере следует обратить внимание на формулировки условия и на то, что исполнение тела цикла приближает момент выполнения условия в цикле повторять – до и момент его невыполнения в цикле пока.
То же самое можно проследить и в следующем примере.
Пусть требуется сложить квадраты натуральных чисел, не превышающие заданного числа (для определенности возьмем число 45).
алг Сумма
нач
S:=0 ;n:=1
покаn*n<= 45
нц
S:= S + n*n
n:= n + 1
кц
ВывестиS
кон
алг Сумма
нач
S:=0 ;n:=1
повторять
S:=S + n*n
n:= n + 1
доn*n> 45
Вывести S
кон
Если в данный алгоритм ошибочно не включить команду n:= n + 1, это приведет к бесконечному циклу, т.к. в цикле пока условие будет выполняться всегда, а в цикле повторять – до оно никогда не будет выполнено.
Если подобную ошибку допустить в алгоритме решения другой задачисколько квадратов натуральных чисел надо сложить, чтобы их сумма не превышала 45,это приведет лишь к ошибочному ответу, но не к зацикливанию.
алг Сумма 2
нач
S:=0 ;n:=1
покаS<= 45
нц
S:= S + n*n
n:= n + 1
кц
Вывестиn - 1
кон
алг Сумма 2
нач
S:=0 ;n:=1
повторять
S:=S + n*n
n:= n + 1
доS> 45
Вывестиn - 1
кон
Цикл с предусловием является наиболее универсальным. Его можно применять для решения любых задач, предусматривающих повторение действий, ибо при определенных обстоятельствах тело цикла может не исполниться ни разу. Однако в ряде случаев цикл с постусловием более удобен. Примером такой задачи является анализ правильности ввода исходных данных, ибо прежде чем проверять исходные данные, надо их хотя бы раз ввести.
Фрагмент алгоритма таков:
повторять
ввод данных
до момента ввода правильных данных
В любом случае цикл с постусловием можно заменить циклом с предусловием, хотя не всегда это будет рационально.
Цикл с параметром также можно заменить циклом с предусловием, хотя запись станет более громоздкой и потребуется заботиться о присвоении параметру начального значения и о его изменении перед каждым исполнением тела цикла (что происходит автоматически, если используется собственно цикл с параметром).
< параметр > := < начальное значение >
пока < параметр ><=<конечное значение>
нц
< тело цикла >
< параметр > := < параметр > + < шаг >
кц
Теперь о реализации циклов с условием в языках программирования.
Пассмотрим только реализацию в языке Паскаль.
Цикл с предусловием
While< условие >do
< оператор >
Цикл с постусловием
Repeat
<оператор>
Until< условие >
Оператор, составляющий тело цикла, чаще всего составной, поэтому в цикле While необходимо использование операторных скобок. В цикле Repeat-Untilоператорные скобки не нужны, ибо тело цикла ограничивают сами служебные слова.
Цикл с условием является основным типом цикла в языке Паскаль: во-первых, потому, что это принципиально иная конструкция по сравнению с конструкцией следования, во-вторых, использование цикла с параметром в Паскале достаточно ограничено из-за того, что параметр может быть лишь переменной порядкового типа и изменяться только с единичным шагом. Это определено самой идеологией языка и является скорее достоинством, нежели недостатком.
В языке Паскаль возможна многократная вложенность циклов (как и других структур), т.е. один цикл может входить в тело другого цикла. Правило таково: цикл, начатый первым, заканчивается последним.
Заключение
Понятие алгоритм – одно из основных понятий информатики. Это фундаментальное «первоначальное» понятие, которому нельзя дать строгого определения в терминах более простых понятий. Существуют описательные определения алгоритма, каждое из которых уточняет это понятие.
Какая бы технология решения задач на компьютере ни использовалась, необходимым этапом будет алгоритмизация: проверяется соответствие полученных результатов ожидаемому в рамках построенной информационной модели задачи, а также оценивается, насколько полученный результат соотносится с реальной практикой.
На этом этапе выявляется, насколько построенная информационная модель соответствует реальности. Дело в том, что чем больше свойств объектов и явлений признано существенными и учтено, тем в большей степени модель отражает действительность. Однако учет большого числа характеристик ведет к усложнению модели, затруднениям в математическом выражении связей между характеристиками. Обычно стараются найти баланс между полнотой соответствия информационной модели реальному состоянию дел и ее сложностью в процессе уточнения модели (постепенного увеличения числа учитываемых существенных свойств).
Цель и задачи в данной работе достигнуты:
- определены содержание и характеристики основных понятий алгоритмизации как основного аспекта программирования;
- рассмотрены основные понятия алгоритма, его свойства и способы записи;
- рассмотрены основные конструкции построения алгоритмов.
Список использованных источников
- Безручко В. Т. Практикум по курсу «Информатика». Работа Windows’ 2000, Word, Excel. 2-е издание. – М.: Финансы и статистика, 2014. – 544 с.
- Информатика. Базовый курс: Учебник для вузов/ Под ред. С.В. Симоновича. – СПб.: Питер, 2014. – 640 с.
- Практикум по информатике/ А.А.Землянский, Г.А.Кретова, Ю.Р. Стратонович, Е.А. Яшкова; Под ред. А.А.Землянского. – М.: КолосС, 2014. – 384 с.
- Рудикова Л.В. MicrosoftExcel для студента. – СПб.: БХВ-Петербург, 2014. – 368 с.
- Саймон Дж. Анализ данных в Excel. – М.: Издательский дом «Вильямс», 2014. – 528 с.
- Фандрова Л.П., Шамсутдинова Т.М. Обработка табличных данных средствами электронных таблиц для анализа задач АПК: Учеб. пособие. - Уфа: БГАУ, 2014. - 90 с.
- Информатика. Базовый курс. Учебник для вузов /Под ред. Симоновича С.В. - СПб.: Питер. - 2014. - 640 с.
- Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. - М.: Нолидж. - 2014. - 576 с.
- Семашко Г.Л., Салтыков А.И. Программирование на языке Паскаль - М.: Наука, 2014. - 128 с.
- Ценообразование на услуги фитнес-клубов
- Анализ эффективности формирования портфеля ценных бумаг коммерческого банка ПАО «Московский Индустриальный банк»
- Налоговая система РФ и проблемы еe совершенствования (Сущность налоговой системы государства)
- Применение процессного подхода для оптимизации бизнес-процессов (Теоретические основы применения процессного подхода для оптимизации бизнес-процессов)
- Защита внутренней сети и сотрудников компании от атак
- Методы кодирования данных (Теоретические основы теории кодирования данных)
- Государственное финансирование спортивной отрасли на примере "Ассоциация мини-футбола России"
- Банковская система, ее элементы и важнейшие свойства (Сущность и назначение банковской системы)
- Формирование кадровой политики в современного бизнеса
- Web-представительство транспортного агентства
- Технология CORBA (Основные понятия технологии CORBA)
- Разработка регламента выполнения процесса «Управление запасами» (Выбор инструментальных внешние средств для моделирования)