Какие характеристики присущи для алгоритмических языков
Перейти к содержимому

Какие характеристики присущи для алгоритмических языков

  • автор:

Какие характеристики присущи для алгоритмических языков

Главное меню

Соглашение

Регистрация

Английский язык

Астрономия

Белорусский язык

Информатика

Итальянский язык

Краеведение

Литература

Математика

Немецкий язык

Обществознание

Окружающий мир

Русский язык

Технология

Физкультура

Для учителей

Дошкольникам

VIP — доступ

Автор: Кеся Наталья Петровна | ID: 8383 | Дата: 31.5.2016

Помещать страницу в закладки могут только зарегистрированные пользователи
Зарегистрироваться

Получение сертификата
о прохождении теста

Характеристика алгоритмических языков

История развития языков программирования, их особенности и назначение. Универсальный язык программирования COBOL. Развитие средств программирования. Универсальный код символических инструкций BASIC и сущность алгоритмического языка программирования.

Рубрика Программирование, компьютеры и кибернетика
Вид реферат
Язык русский
Дата добавления 11.01.2010
Размер файла 46,7 K
  • посмотреть текст работы
  • скачать работу можно здесь
  • полная информация о работе
  • весь список подобных работ

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Содержание

1. История развития языков программирования

1.1 Универсальный язык программирования COBOL

1.2 Алгоритмический язык программирования Алгол

1.3 Универсальный код символических инструкций BASIC»а

1.4 Алгоритмический язык Паскаль

2. Развитие средств программирования

Введение

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

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

Язык программирования — это совокупность набора символов (алфавит) системы, правил образования (синтаксис) и истолкования конструкций из символов (семантика) для задания алгоритмов с использованием символов естественного языка.

Именно для удобного решения задач с помощью ЭВМ искусственно и создавались языки программирования. Естественным же языком, который «понимает» компьютер, является машинный.

Машинный язык — это такой язык, который компьютер воспринимает непосредственно, то есть это язык машинных команд данной модели компьютера. А мы уже знаем, что ЭВМ «понимают» только язык двоичных знаков: нулей и единиц.

1. История развития языков программирования

С 1954 годов группа инженеров всем известной (теперь) компании IBM под руководством Джона Бекуса занималась созданием компилятора для Fortran. Эти работы велись более 2-х лет и, в конце концов, привели к созданию нового языка. Fortran — это сокращение от двух английских слов FORmula TRANslator — что переводится как «транслятор формул». Как видно из названия, первоначально язык создавался с целью использования при математических расчетах. Он предназначался для написания программ, используемых при решении прикладных технических задач. Основу языка составляли арифметические операторы, соответствующие по своему синтаксису традиционной записи математических выражений. В дополнение к этому в языке имелись средства разбиения сложных алгоритмов на более простые за счет явного определения подпрограмм (SUBROUTINE) и функций (FUNCTION). Описания данных в Fortran были ориентированы на представление главным образом числовой информации, поэтому и типы данных были просты: это целые и действительные числа, а также массивы из таких чисел. Однако программирование на Фортране представляло собой задачу непростую. К примеру, оператор DO 150 I=1,10 определяет начало цикла выполнения команд, идущих непосредственно за ним вплоть до строки с отметкой 150, причем параметр I при каждом новом начале цикла увеличивается на 1, и так до 10. А если вместо запятой между 1 и 10 поставить точку, то вместо цикла мы получим присвоение переменной DO150I значения 1.10. Но поскольку Fortran обладает хорошо развитым математическим аппаратом, и под него за время его существования было написано множество удобных и полезных библиотек, он до сих пор иногда используется при программировании сложных вычислений. Первая версия была предназначена специально для компьютера IBM-704, который работал на лампах (!). Позднее появились более проработанные версии: Фортран II позволял присоединять куски кода на ассемблере, Фортран III и Фортран IV, который вышел в свет в 1962 году, а также Фортран V, который умел работать с комплексными числами. Большим неудобством было то, что на разных машинах стояли Fortran»ы разных версий и между ними не было никакой совместимости, поэтому в 1966 году решено было принять единый стандарт. Следующая стандартизация была проведена в 1977, и версия стандарта Fortran77 стала особенно популярна. Стоит заметить, что это был первый пример коммерчески успешного языка. Fortran не умер и сегодня, как думают многие, хотя область его применения остается достаточно специфической. Появились даже пакеты Visual Fortran, позволяющие писать программы с графическим интерфейсом пользователя под среду Windows. К тому же Fortran до сих пор продолжают изучать при подготовке по некоторым физико-математическим специальностям во многих университетах, где он остается профилирующим языком программирования. Но Fortran приносил радость и утешение лишь ученым, которые решали с его помощью свои специфические научные и инженерные задачи.

1.1 Универсальный язык программирования COBOL

ЭВМ между тем развивались, и становилось понятным, что с их помощью можно решать самые разнообразные проблемы, зачастую не связанные с научными приложениями. Поэтому постепенно разрабатывались и компиляторы других языков программирования. Так в конце 1959 года в США группа разработчиков представила совершенно новый универсальный язык программирования COBOL — это аббревиатура от Common Business-Oriented Language — универсальный язык, ориентированный на задачи бизнеса. В Коболе, в отличие от большинства других языков, все данные описываются в отдельной секции, которая не совпадает с секцией команд. Это позволяет использовать одни и те же описания данных в различных программах. COBOL был аппаратно независим, и это также способствовало его потрясающей популярности в 60-х — 70-х годах, особенно после выхода в 1962 году его новой версии. Особенно эффективно программы, написанные на COBOL»е, производят простые арифметические операции с большими массивами данных, что довольно часто приходится делать в бухгалтерских расчетах. В нашей стране этот язык тоже достаточно широко использовался, причем он, один из немногих, был переведен на русский язык.

1.2 Алгоритмический язык программирования Алгол

Языков программирования было все еще мало, да и те, что были, не всегда устраивали привередливых разработчиков. Поэтому ряд ведущих программистов в Цюрихе представили в 1958 году свое новое детище — Алгол (сокращение от ALGOrithmic Language — алгоритмический язык программирования). Первая версия языка так и называлась — Алгол 58, а позднее, в 60 году, уже в Париже, был принят стандарт Алгол 60, который и стал основным на долгие годы, и хотя несколько раз вносились новые поправки и дополнения, это название оставалось неизменным до 1968 года. Язык приняли неоднозначно, как удачно заметила Грейс Хоппер — один из крупнейших специалистов по языкам высокого уровня (если не сказать «крестная мать» языков программирования) — «Алгол похож на большую поэму: простой и ясный с точки зрения математики, но отнюдь не практичный». В США Алгол не получил широкого распространения, зато европейцы сразу приняли Алгол. Он дал возможность европейской компьютерной индустрии обрести независимость от американской технологии и распространился от Великобритании до Советского Союза. В начале 80-х множество советских программистов работали на Алголе-60. Но основная заслуга этого языка в другом — он заложил базу для дальнейшего развития программистской мысли, и многие языки программирования, разработанные впоследствии и получившие широкое распространение как в кругу профессионалов, так и среди любителей, содержат многие идеи и решения, взятые из Алгола. В первую очередь, это создание специальной нотации для определения синтаксиса алгоритмических языков (нотация Бэкуса-Наура). Во-вторых, доведение до логического завершения самой концепции операторных алгоритмических языков с заранее фиксированными типами данных и блочной структурой. Из дополнительных нововведений можно выделить возможность разработки отдельных модулей проекта независимо друг от друга, а также реализацию вызовов фрагментов кода программы, способов передачи параметров между процедурами и функциями. Достаточно сказать, что именно в Алголе появились понятия блока и рекурсивного вызова функции.

1.3 Универсальный код символических инструкций BASIC

На заре развития вычислительной техники программисты были чем-то вроде обособленной секты, неохотно пускающей в свои ряды новичков. В основном этому способствовали техническое несовершенство компьютеров и малое их количество. Но среди программистов были и те, которые считали необходимым сделать программирование такой же простой и обыденной учебной дисциплиной, как математика. Отцы-основатели BASIC»а (расшифровывается как Basic Beginner»s All-purpose Symbolic Instruction Code — универсальный код символических инструкций для начинающих) — два ярких представителя программистов старшего поколения, сотрудники математического факультета Дармутского колледжа Томас Курц и Джон Кемени. Курц имел степень доктора по математической статистике. Впервые с компьютерами он познакомился в 1951 году в Калифорнийском университете. Кемени был на два года младше Курца. С компьютерами он был, что называется, «на ты». Еще во время учебы в Принстоне, он ездил в 1945 году в Лос-Аламос, где принимал участие в работе над особо секретным «Манхэттенским проектом» по созданию атомной бомбы. Наставником Кемени был сам Джон фон Нейман, чьи идеи в области компьютерных вычислений оказали серьезное влияние на все дальнейшие разработки в этом направлении. После войны Кемени работал ассистентом у Альберта Эйнштейна в Принстонском институте перспективных исследований, одновременно заканчивая докторантуру. Так как получить место преподавателя математики не удалось, он преподавал логику. В 1953 году ему предложили возглавить математический факультет в Дартмутском колледже. В то время ему было всего 27 лет. Когда Кемени и Курц только начинали совместное сотрудничество, Дармутский колледж представлял собой лишь небольшое учебное заведение гуманитарного профиля, которое не имело своего компьютера. Однако уже через десять лет колледж не только получил великолепный вычислительный центр, но и право называться родиной языка Бейсик, оказавшего огромное влияние на программирование. В первое время Кемени и Курц были вынуждены работать со своими математическими программами за 215 км от Дармутского колледжа. Ближайший доступный им вычислительный центр находился в Массачусетском технологическом институте. Это был новейший компьютер IBM-704, который имел феноменальный по тем временам объем памяти 8192 слова по 365 разрядов каждое. Но, даже проделав долгий путь, Курц и Кемени не могли самостоятельно работать на машине, из-за существовавшей тогда системы пакетной обработки (batch processing). Так как компьютеры были немногочисленны и страшно дороги, доступ к ним имели только избранные. Программисту требовалось подготовить задание на перфокартах и передать его в вычислительный центр оператору. Он вводил карты в машину в большом пакете, который содержал сотни программ, принадлежащих различным пользователям. Потом происходило ожидание, в течение нескольких дней. Причем не всегда данные, выданные машиной, оправдывали эти ожидания. Малейшей описки было достаточно, чтобы машина прекратила выполнение программы. Исправив ошибку, программист должен был заново отправить программу оператору и опять ждать результатов. Даже хорошие программисты тратили много времени на исправления ошибок в своей программе. Для Курца, а именно он отвозил программы в МТИ, это оборачивалось бесконечными поездками из Дартмута в Бостон и обратно. Но проблемы не ограничивались лишь неудобствами пакетной обработки. Помимо этого первые программы для машины IBM-704 приходилось писать на языке ассемблера. И если программа начинала вести себя «странно», то единственным способом исправления ошибки было изучение дампа памяти — длинной бумажной ленты, содержащей числовые коды. Свое программистское мастерство Кемени и Курц оттачивали, изучая язык ассемблера и разбираясь с бесконечными дампами, лелея надежду об установке компьютера в Дартмуте. Не представляли они себе лишь того, как научить программированию коллег и студентов, ведь сам процесс программирования был чрезвычайно сложным. К началу 60-х годов Кемени и Курц добились некоторых успехов. Вначале Дармутский колледж получил собственный маленький компьютер LGP-30 с объемом памяти вдвое меньше, чем у IBM-704. Курц возглавил новоиспеченный вычислительный центр, и на протяжении нескольких лет два молодых профессора занимались разработкой простых языков, предназначенных для работы на машине LGP-30. Один студент, не занимавшийся до этого программированием, разработал язык «ДАРТ». Успехи студента подтвердили убеждение Курца и Кемени — работа с компьютером вполне по силам студентам. Наконец настала пора выдвинуть идею, которую они вынашивали многие годы. Их предложение было очень смелым: обучать азам программирования всех студентов, независимо от специальностей, будь то гуманитарные или естественные науки. Поставленная цель уже сама по себе была весьма необычной, но намерения Кемени и Курца этим не ограничивались. В отличие от своих коллег, которых вполне устраивала методика обучения студентов программированию путем чтения лекций, Кемени хотел, чтобы студенты работали с машиной «вживую», создавая для нее реальные программы. Но студентов много, а компьютер только один, и, хотя студентам не приходилось путешествовать в другой город, утомительность работы с пакетной обработкой несла с собой разочарования. Будущих инженеров и математиков необходимо было заставить смириться с многочасовым и даже многодневным ожиданием результатов. Перспектива пакетной обработки создавала определенные трудности, но они были не такими пугающими, как сам процесс обучения студентов языкам программирования. Но никакими препятствиями невозможно было остановить пытливые умы «дармутской команды». Для начала они попытались устранить неудобства пакетного режима, и решили использовать систему разделения времени (time sharing), предложенную МТИ в конце 50-х годов. Система разделения времени предполагала подключение к главному процессору (mainframe) нескольких терминалов с алфавитно-цифровой клавиатурой. Специальные инструкции позволяли процессору по очереди подключаться к каждому терминалу, выполняя некоторую часть операций в течение определенного временного отрезка — несколько миллисекунд. Так как используемый процессор предполагался достаточно мощным, у каждого программиста создавалось впечатление, что машина работает только с ним. Следующая их идея была в создании языка программирования, который бы подходил для обучения азам программирования, то есть был бы легок для освоения студентами. Воображение легко рисовало язык, состоящий из английских слов, понятных и программисту, и компьютеру. Операторы нового языка должны были обладать сходством с операторами языка Фортран для возможности легкого перехода на новый уровень программирования. Некоторые идеи Кемени и Курца отличались от существовавших тогда «принципов». Например, введение в язык оператора INPUT, позволяющего вести некое интерактивное взаимодействие. Это позволяло изменять программу в процессе ее работы. Кроме того, язык, разработанный Кемени и Курцом, не предусматривал разделения чисел на целые и вещественные, как в языке Фортран. Бейсик оказался универсальным языком в отличие от, например, COBOL»а. А его простота позволяла использовать преимущества ЭВМ как математикам и инженерам, так и филологам и социологам. Летом 1963 года Кемени начал разрабатывать первую версию компилятора для языка Бейсик. Осенью того же года студенты приступили к проектированию и кодированию операционной системы для машин, на которых Кемени и Курц планировали реализовать свои идеи. Это были машины General Electric-225 и Datanet-30. В феврале 1964 года оборудование было доставлено в колледж, и работа закипела с удвоенной силой. Наконец, 1 мая 1964 года в 4 часа утра в полуподвале здания колледжа Кемени и его коллеги начали набирать программы, каждый на своем терминале. Наконец-то все заработало! Одновременно родились язык Бейсик и система разделения времени. Но это было только начало. Долгое время BASIC не имел компилятора или интерпретатора, который бы позволял создавать полноценные исполняемые exe-файлы. И лишь в конце 1975 году был создан первый его интерпретатор. Он был создан двумя программистами-любителями — Диком Уипплом и Джоном Арнольдом. В том же 1975 году фирма Micro Instrumentation and Telemetry Systems выпустила свою версию языка BASIC. Ее создатели — кто бы вы думали? — никому не известные программист фирмы «Хониуэл» (Honeywell) и студент младших курсов Гарвардского университета Пол Аллен, а также его нерадивый приятель Билл Гейтс. Одно время популярность BASIC»а была столь велика, что PC выпускались с его интерпретатором, прошитым прямо в ПЗУ компьютера. Самым популярным стал М-Бейсик, первый коммерческий успех молодой компании Microsoft Corporation. Но, несмотря на все свои достоинства, и он скоро стал сдавать свои позиции, уступая их объектно-ориентированным языкам программирования. Не помогли даже пересмотры стандарта языка и исключение вечного камня преткновения — оператора безусловного перехода GOTO, который запутывал программу, делая из нее нечто похожее на блюдо спагетти. К слову сказать, Microsoft до сих пор продвигает своего первенца — теперь это уже хорошо разросшийся Visual Basic — целый пакет визуального программирования, который вряд ли кто-нибудь обвинит в «объектной неориентированности», и его аналог для программирования в Internet — VBScript. Несмотря на практически полностью измененный интерфейс, этот язык и сейчас остается простым в изучении и отлично подходит для написания небольших, нетребовательных к ресурсам программ. Еще один очень интересный пример языка, сошедшего с пути исторического развития, о котором сегодня помнят разве что специалисты, — PL/1. Все началось с того, что уже упоминавшаяся ранее фирма IBM в 1961 году решила начать разработку новой ЭВМ. Это должна была быть совершенно новая машина, одинаково хорошо обрабатывающая большие массивы данных и обсчитывающая сложные математические задачи; проект получил название «Система-360». Вместе с новой машиной разрабатывался и язык: он совмещал особенности трех лидеров данного сектора рынка — Фортрана, Кобола и Алгола. Главой проекта стал Джорж Рэдин. Менее чем за год все необходимые работы были проведены, и появился первый компилятор. Свое название язык получил как аббревиатуру от Programming Language One PL/1. Возникает резонный вопрос: почему же мы сегодня ничего не знаем об PL/1, раз он такой хороший и так много всего в себе совмещает? Оказалось, что разработчики далеко не всегда брали от его «родителей» все самое лучшее, как следствие, язык получился перегруженным возможностями и концепциями. Но вернемся к началу 60-х годов. Все основные языки программирования все еще можно было пересчитать по пальцам, но вскоре их число начало резко возрастать. Поэтому были предприняты попытки создать универсальный язык программирования, но ни одна из этих попыток не увенчалась успехом. Среди десятка наиболее распространенных на тот период времени языков программирования каждый был ориентирован на решение определенных задач. Бейсик употреблялся для написания простых программ. Фортран — с его четко определенными правилами выполнения арифметических операций — являлся классическим языком программирования для решения математических и физических задач. Язык программирования COBOL был задуман как основной язык для массовой обработки данных в сферах управления и бизнеса. Другие языки программирования были также специализированы. Еще один заслуживающий внимания язык программирования — Алгол — предназначался для записи алгоритмов, которые строятся в виде последовательности процедур, применяемых для решения поставленной задачи. Программисты далеко неоднозначно приняли Алгол, широкого одобрения он не получил. Но все же влияние Алгола на развитие других языков программирования оказалось значительным. Среди языков, целью создания которых было улучшение Алгола, следует особо отметить.

1.4 Алгоритмический язык Паскаль

Паскаль, разработанный в конце 60-х годов швейцарским ученым Никлаусом Виртом. Pascal был назван в честь французского философа и математика XVII века Блеза Паскаля. Как известно, история повторяется, и вся новизна лишь в том, что на каждом новом витке — она делает это на более высоком уровне. Мы уже отмечали, что BASIC появился как побочный продукт преподавательской деятельности у Кемени и Курца, когда они пытались обучать студентов программированию. Нечто похожее произошло и с Паскалем. Некоторое время Никлаус Вирт был профессором информатики в Федеральном техническом университете в Швейцарии и нуждался в языке, с помощью которого относительно легко можно было бы обучать студентов навыкам программирования на хорошем уровне. Базовая концепция Паскаля была разработана Виртом примерно в 1970 году, и Паскаль очень быстро начал повсеместно распространяться, прежде всего, благодаря легкости в изучении и наглядности написанных на нем программ. Язык Паскаль требовал от программиста определения всех переменных в отдельной секции в начале программы. Так как эти определения задавались явным образом, то в программах появлялось сравнительно немного ошибок, и их было проще понять и исправить разработчику. Это сделало Паскаль популярным при создании больших программ. В 1962 году он был объявлен официальным языком программирования для учащихся средних школ, которые намерены специализироваться в области вычислительной техники и программирования в американских университетах. В то же время, стандартный Паскаль обладал рядом существенных недостатков. Поэтому Вирт продолжил развивать свое детище, так через девять лет, в 1979 году, появилась Модула-2, прежде всего от Паскаля она отличалась тем, что давала возможность использовать модульное программирование, а значит, с ее помощью уже можно было создавать достаточно большие проекты. К середине 70-х годов назрела необходимость разработать международный стандарт на Паскаль. В результате, в 1982 году появился стандарт ИСО 7185. Но Вирт не останавливался на достигнутом, и немного позднее появились Ада и Оберон, которые позволяли использовать типы и объекты, что уже давало кардинально новые возможности для разработчиков. Язык Ада был создан фактически по заказу Министерства обороны США и, соответственно, при его активной поддержке. Был проведен конкурс среди разработчиков, и его выиграла некая фирма Honeywell в лице ее подразделения Cii-Bull с руководителем Ж. Ишбиа. Язык был назван в честь Августы Ады Лайвейс — дочери английского поэта Дж. Байрона, которая считается первой программисткой. Окончательная версия спецификаций языка Ада появилась в феврале 1983 году, она и стала основной. Ада до сих пор считается современным языком с традиционной структурой управления, возможностями определения типов и подпрограмм. Удовлетворяет язык и требованиям модульности. В дополнение к классическим свойствам язык обеспечивает программирование задач реального времени, а также возможности моделирования параллельного решения задач и обработку прерываний. Поскольку Ада морфологически произошла от Pascal, у них есть очень много общего, хотя наблюдаются и некоторые аналогии с Модулой. С самого начала Ада предназначалась для разработки больших программных пакетов. Учитывая то, какую серьезную (моральную и не только) поддержку предоставляли правительство и Министерство обороны США, неудивительно, что язык очень быстро развивался и без особых проблем распространялся. Здесь нужно заметить, что стандартный Паскаль был действительно очень простым языком. В то же время в сознании большинства людей (особенно молодого поколения, тех, кому еще нет 30), Паскаль обычно ассоциируется с Turbo Pascal от фирмы Borland — это не верно! Ведь Turbo Pascal включает в себя многие положительные качества как Модулы, так и Oberon»a, и является гораздо более сложным и мощным языком, чем Паскаль Вирта. Судите сами: он позволяет использовать и модули, и типы, и даже объекты, давая всю мощь объектно-ориентированного программирования в руки разработчика. Как же он возник? Никлаус Вирт здесь совсем не при чем, а при чем — Андерс Хейлсберг, которого и следует считать отцом-создателем Турбо Паскаля, вскоре вытеснившего с рынка все другие спецификации. Это победоносное шествие началось в 1984 году с появлением версии Turbo Pascal 2.0, ее распространение шло стремительными темпами. Версии 3.0, 4.0 и 5.0 выходили соответственно в 1985 и 1988 годах (последние две). В них появилось несколько революционных нововведений: возможность разбивать программу на несколько файлов (модулей), интерфейс взаимодействия с MS-DOS и встроенный отладчик. Отладчик (debugger) — это очень полезное средство, позволяющее в период выполнения программы просматривать содержимое регистров процессора, текущие значения переменных и последовательность выполнения программы. От версии к версии оптимизировалась работа компилятора, который генерировал исполняемый код на основе текста программы. Даже достаточно простые программы, перенесенные с других языков программирования, не использующие всех возможностей, которые давал Паскаль, после компиляции начинали работать существенно быстрее. Так, основной из причин, по которой автор этих строк еще очень давно решил отказаться от Бейсика и использовать Паскаль, — явилась наглядная демонстрация скорости работы компилятора Turbo Pascal 2.0. Компиляция происходила в полтора раза быстрее, ехе`шник получался во много раз меньше (несколько килобайт для простенького приложения против 40-50 у Бейсика), а скорость выполнения полученного кода просто впечатляла. Сейчас, когда машины оснащаются сотнями мегабайт оперативной памяти и быстродействующими процессорами, мало кто обращает внимание на такие, казалось бы, мелочи, а тогда, при работе на 8088 процессоре со всего 640 кб оперативной памяти, это было очень важно. Последующее развитие Pascal привело к появлению таких библиотек, как Turbo Vision, с использованием которой написан, наверное, всем известный, Dos Navigator, а также языка Object Pascal, который впоследствии стал основой для создания Delphi. Delphi — компилятор языка Object Pascal. Delphi 1 был первым инструментарием разработки Windows-приложений, объединившим в себе оптимизирующий компилятор, визуальную среду программирования и мощные возможности работы с базами данных. Годом позже Delphi 2 предложил все то же, но на новом уровне современной 32-битной операционной системы Windows 95 и Windows NT. Кроме того, Delphi 2 предоставил программисту 32-битовый компилятор, создававший более быстрые и эффективные приложения, мощные библиотеки объектов. Продолжительная работа команды разработчиков Delphi привела к появлению в третьей версии продукта расширенного набора инструментов для создания приложений, возможности использования технологий COM для разработки приложений WWW и многих других современных технологий программирования. Современный Delphi 6 является очередным шагом в эволюции компиляторов Паскаля, первый, как вы помните, был сделан более 16 лет назад Андерсом Хейлсбергом. Пожалуй, мало найдется языков, которые бы жили так долго, при этом оставаясь актуальными. Действительно, Delphi позволяет даже самому неискушенному в программировании человеку после сравнительно небольшого времени, потраченного на его изучение, создавать профессионально выглядящие программные продукты с графическим интерфейсом пользователя в стиле Windows. Особенно удобно на Delphi работать с базами данных. Естественно, эта легкость работы с Delphi оборачивается некоторыми минусами языка. Основной недостаток Delphi — скорость работы, она очень и очень невысока. Да и генерируемый компилятором код получается увесистым и неуклюжим. Так, создание пустого окна даст ехе-файл размером почти в полмегабайта, на С++ — такое же займет 15-30 килобайт, в зависимости от ваших стараний (или 1 Кб при совсем творческом подходе к проблеме). Тем не менее, для некоторых сфер применения Delphi является идеальным решением, поэтому сейчас он достаточно популярен.

Существуют два способа трансляции:

1. ИНТЕРПРЕТАЦИЯ (Interpretation) — метод выполнения в ЭВМ программы, заданной на языке программирования, при котором инструкция исходной программы переводится и сразу выполняется.

2. КОМПИЛЯЦИЯ (Compile — собирать) — метод выполнения в ЭВМ программы, но не сразу, а лишь тогда, когда собран перевод всего текста программы.

Разницу между компиляцией и интерпретацией можно выяснить с помощью аналогии. Фармацевты в аптеке приготовляют микстуру по старинному рецепту, написанному на латыни. Есть два пути: можно сначала перевести (скомпилировать) рецепт на родной язык и лишь затем готовить лекарство на родном языке. А можно, по мере чтения перевода рецепта, сразу готовить лекарство, но не записывать сам текст перевода (т.е. только интерпретировать). В последнем случае мы не получим текста рецепта на родном языке. А можно, по мере чтения перевода рецепта, сразу готовить лекарство, но не записывать сам текст перевода (т.е. только интерпретировать). В последнем случае мы не получим текста рецепта на родном языке, а сразу получим микстуру, правда, если лекарство нужно готовить несколько раз, рецепт придется переводить многократно. Интерпретация используется в простых языках, где требуется несложная трансляция (Бейсик), или там, где компиляция слишком сложна или даже невозможна (язык ЛИСП). Часто используют оба эти способа совместно: интерпретатор — для отладки и компилятор — для трансляции отлаженной программы. Работа с программой, написанной на алгоритмическом языке, очень упрощается за счет относительной простоты написания программы, удобной читаемости, возможности ее подкорректировать. Однако при этом всплывают и недостатки: требуется дополнительное время на трансляцию и дополнительная память для размещения транслятора.

Итак, в 1955 году увидел свет первый алгоритмический язык Фортран. Он использовался для решения научно-технических и инженерных задач. Слово «Фортран» образовано от начальных слогов английских слов — formula translator (переводчик формул). Он был разработан сотрудниками фирмы IBM под руководством Джона Бэкуса. Основным назначением этого языка является программирование численных расчетов на ЭВМ.

Как и многие естественные языки (украинский, русский, английский и т.д.), Фортан (и другие языки) имеет много «диалектов» (их называют версиями), различающихся правилами записи некоторых команд, но по сути одинаковых. За прошедшие годы было много новых версий языка Фортан. Он все время менялся и развивался. Одна из последних версий — Фортран-77. Благодаря простоте и тому, что этим языком написаны большие библиотеки программ, Фортран и в наши дни является одним из самых распространенных в мире языков программирования.

Затем в 1960 г. появился Алгол (Algoritmic language — алгоритмический язык), также ориентированный на научное применение, в него было введено множество новых понятий, подхваченных позднейшими языками, например, понятие блочной структуры. Также при поддержке фирмы IBM появился язык Кобол (Cobol — сокращенное от английских слов Comnon business oriented language — общепринятый деловой ориентированный язык). Он был ориентирован на решение экономических задач, а точнее — на обработку информации.

Язык Бейсик (Basic — beginners all-parpouse sumbolic instraction code, что в переводе с английского означает «многоцелевой язык символических инструкций для начинающих») был разработан профессорами Дартмутского колледжа (СИГА) Т.Куртцем и Дж. Кемени в 1965 году для обучения студентов, незнакомых с вычислительной техникой. Этот язык, напоминающий Фортран, но более простой, быстро стал очень популярным. Особенно его популярность повысилась благодаря «взрыву микроинформатики» — появлению персональных микрокомпьютеров, где Бейсик стал основным языком программирования. Достоинствами Бейсика являются удобные средства ввода, отладки и испытания программ, а также возможность доступа ко всем основным ресурсам компьютера. Его отличает простота конструкций и возможность осуществления диалогового режима работы с ЭВМ. Вместе с тем Бейсик имеет и ряд недостатков. Это прежде всего отсутствие явных ограничений на составление запутанных программ (этот недостаток присущ и Фортрану). Его оператор Goto при бездумном применении сильно запутывает программу и порой делает ее совсем непонятной с точки зрения логики выполнения. Кроме того, программы на языке Бейсик обычно выполняются относительно медленно, поскольку ЭВМ применяют, как правило, не компиляторы, а интерпретаторы языка. Но последние диалекты языка Бейсик все больше устраняют перечисленные недостатки и приближают его к языку Паскаль и другим процедурным языкам (т.е. основанным па понятиях алгоритмов, программ, инструкции). С его помощью можно решать достаточно сложные задачи. Например, так называемая версия расширенного Бейсика, имеющая матричные операции, позволяет с помощью одного оператора преобразовывать большие таблицы (матрицы). Есть версии Бейсика, работающие в режиме компиляции, что значительно ускоряет прогон программ, написанных на этом языке.

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

В 1967-1968 гг. появился язык PL/1 (Programming language — универсальный программно-ориентированный). Он также был создан на фирме IBM, но уже в качестве универсального языка программирования. Этот язык, как языки программирования СИ, Ада и Паскаль, может использоваться как для научных задач, так и для задач управления. Он очень мощный, но и очень сложный, используется лишь в высших учебных заведениях и научно-исследовательских центрах.

В 1970 г. профессор Никлаус Вирт создал в Цюрихском политехническом университете язык Паскаль (Pascal). Создатель языка назвал его в честь Блеза Паскаля первого конструктора устройства, которое теперь относится к классу цифровых вычислительных машин. Он создавался как язык, который, с одной стороны, был бы хорошо приспособлен для обучения программированию, а с другой — давал бы возможность эффективно решать самые разнообразные задачи на современных ЭВМ. При создании этого языка Вирт большое внимание уделял хорошему стилю программирования (так называемое структурное программирование), благодаря которому конструкции Паскаля позволяют писать надежные, легко проверяемые программы с ясной и четкой структурой. Работая в среде данных языков, компьютер решает задачу, а программист лишь ее формулирует. ЭВМ пробегает все рабочее пространство в поисках решения специальным способом, но зато полностью исчерпывающим (возможен обратный ход). Существует огромное множество специализированных языков, позволяющих эффективно решать задачи в некоторых областях: моделирования (языки Симула, Симкрит и GPSS), управления аппаратурой (ФОРТ), для написания системных программ (СИ), написания баз данных (Кодасил), обучения программированию (Лого, Робик, алгоритмический язык А.П.Ершова) и другие. Но в целом эволюция машинных языков происходит в направлении естественного языка — идеальное решение, состоящее в том, что пользователю надо будет только сформулировать задачу на естественном языке, а все остальное сделает компьютер. Конечно, в настоящее время это всего лишь мечта, но тем не менее языки последних поколений более близки к языку человеческих рассуждений.

2. Развитие средств программирования

Основные особенности развития программирования в период машин второго поколения обусловлены расширением областей применения ЦВМ и усложнением их структуры. Расширение областей применения — одна из важнейших причин разработки большого количества алгоритмических языков. По состоянию на 1967г. во всем мире использовалось около 1000 алгоритмических языков, включая специализированные языки и языки, ориентированные на запись широкого класса алгоритмов, т. е. универсальные применительно к данной достаточно широкой области применения (вычислительные задачи, обработка экономической информации, информационно-логические задачи, управление в реальном масштабе времени). В то же время, начиная с середины 50-х годов, предпринимались попытки создания единого универсального алгоритмического языка. Широкий международный характер приняли работы по созданию и совершенствованию языка АЛГОЛ, ориентированного на применение в научно-технических расчетах. Первый вариант языка АЛГОЛ был разработан группой ученых из ФРГ и Швейцарии и в 1957 г. одобрен Германским техническим обществом. Цель разработки заключалась в создании универсального международного языка, который был бы пригоден для всех выпускаемых моделей универсальных ЦВМ. В переработке первого варианта АЛГОЛА участвовали ученые ряда стран, собравшиеся в январе 1960 г. на Объединенную конференцию в Париже. Представители США, Великобритании, Франции, ФРГ, Швейцарии и Дании одобрили переработанный вариант АЛГОЛА (АЛГОЛ-60) и рекомендовали его для применения в качестве универсального языка. «Не будет преувеличением утверждать,— писал в 1965 г. М. Р. Шура-Бура,— что появление пять лет назад сообщения об АЛГОЛ-60 стало важной вехой в развитии языков программирования… АЛГОЛ-60, как язык для описания алгоритмов численного анализа, сконцентрировал в себе значительную часть наиболее удачных сторон ранее известных языков программирования, предназначенных для тех же целей».Недостатком АЛГОЛА-60 явилось отсутствие в языке каких-либо канонизированных средств для задания ввода и вывода информации, что существенно затрудняло разработку трансляторов. Поэтому ряд зарубежных фирм, выпускающих универсальные ЦВМ, предпочли ориентироваться на собственные разработки. В 1957 г. группа специалистов фирмы «ИБМ» под руководством Дж. Бакуса закончила разработку языка ФОРТРАН. Целью работ, проводившихся в течение трех лет (1954—1957 гг.), было создание алгоритмического языка, ориентированного на задачи численного анализа и транслятора с этого языка на язык команд машины ИБМ-704. По сравнению с АЛГОЛОМ язык ФОРТРАН более ориентирован на машину и конкретные способы трансляции, что и послужило одной из причин его широкого распространения в США и других странах.Очень широкое распространение получил также язык «КОБОЛ», разработанный в США в 1958—1960 гг. и ориентированный на описание алгоритмов экономических задач. Поскольку научно-технические и экономико-статистические задачи составляют значительное большинство всех задач, решаемых с помощьюЦВМ, языки КОБОЛ, АЛГОЛ и ФОРТРАН получили весьма широкое распространение в 60-х годах. Трансляторы с этих трех языков, как правило, входят в набор средств математического обеспечения, которыми оснащаются выпускаемые за рубежом универсальные ЦВМ. В СССР сравнительно широкое применение получил язык АЛГОЛ, который «положен в основу различных систем автоматизации программирования, содержащих в своем составе трансляторы для конкретных машин». Наряду с языками АЛГОЛ, КОБОЛ и ФОРТРАН в СССР и за рубежом в первой половине 60-х годов были разработаны и получили практическое применение другие специализированные и обобщенные алгоритмические языки, среди которых необходимо отметить языки, созданные для описания алгоритмов решения неарифметических задач (ИПЛ, ЛИСП, КОМИТ и др.) и языки для управления в реальном масштабе времени.В 1963 г. в США была начата работа по созданию алгоритмического языка, сочетающего наиболее ценные свойства языков для записи алгоритмов численного анализа (ФОРТРАН и АЛГОЛ), обработки экономической информации (КОБОЛ) и информационно-логических задач (ИПЛ). Результатом исследований, проведенных комитетом из специалистов фирмы «ИБМ» и ассоциации «ШЕАР», явилась разработка языка ПЛ-1. В настоящее время ПЛ-1 является одним из наиболее мощных средств программирования.Рассмотрение обстоятельств создания алгоритмических языков позволяет наметить некоторую общую схему их развития. В целом развитие языков связано с расширением областей применения ЦВМ. Тенденция к созданию единого универсального языка приводит к разработке одного или нескольких языков, пригодных для описания значительного большинства задач, решаемых в данный момент времени средствами цифровой вычислительной техники. Именно такими соображениями руководствовались создатели АЛГОЛА и ФОРТРАНА, начавшие разработку данных языков в то время, когда научно-технические задачи составляли абсолютное большинство задач, решаемых на ЦВМ.В последующие годы область применения электронных ЦВМ существенно расширилась, прежде всего за счет задач, связанных с обработкой больших объемов информации. Наряду с этим произошло существенное усложнение структуры ЦВМ, прежде всего в результате применения различных форм мультипрограммной работы. Новым шагом на пути создания универсального языка явилась разработка ПЛ-1, приспособленного для описания алгоритмов решения подавляющего большинства задач (по состоянию на середину 60-х годов) и учитывающего архитектурные особенности наиболее распространенной серии вычислительных машин (ИБМ-360). Однако процесс расширения областей применения ЦВМ, естественно, не закончился в середине 60-х годов. В настоящее время, например, интенсивно развиваются такие направления, как обработка графоаналитической информации и машинное проектирование. Новые области применения неизбежно вызывают появление новых алгоритмических языков и соответственно тенденции к их обобщению на более высоком уровне. Поэтому в дальнейшем можно ожидать новых разработок в области универсального алгоритмического языка, например за счет усовершенствования ПЛ-1.Разработка алгоритмических языков имела существенное значение для формирования в 60-х годах нового подхода к разработке универсальных ЦВМ. Как отмечает А. Оплер, в первой половине 60-х годов «произошла техническая революция, в результате которой средства математического обеспечения превратились из полезного вспомогательного средства при программировании и эксплуатации вычислительных машин в равноправного партнера аппаратуры с точки зрения их значения для вычислительной техники». При этом подход к разработке вычислительных машин претерпел существенную эволюцию: вместо независимой разработки аппаратуры и некоторых средств математического обеспечения стала разрабатываться система, состоящая из совокупности аппаратурных средств и средств программирования. На протяжении 60-х годов сложилась современная система средств математического обеспечения, которой, как правило, оснащаются выпускаемые универсальные ЦВМ и от которой в решающей степени зависят возможности их практического применения. В состав системы средств математического обеспечения, как правило, входят:а) одна или несколько операционных систем, обеспечивающих работу машины в том или ином режиме и содержащих такие программные средства, как управляющие программы (управление потоком заданий, управление процессом решения задач, управление обменом данными между запоминающими устройствами и т. п.), трансляторы с наиболее распространенных алгоритмических языков и сервисные программы (текущая модификация данных: сортировка, объединение, редактирование и т. п.);б) набор программ технического обслуживания машины (наладочные, проверочные, диагностические тесты);в) пакеты прикладных программ (для решения типовых научных, экономических, инженерных, информационно-поисковых и других задач).При этом сравнительно часто для записи программ, входящих в состав операционной системы, используется символический вариант языка данной машины, расширенный за счет введения в него некоторых команд и операторов (автокод). Таким образом создается двухступенчатая структура трансляции: с обобщенного алгоритмического языка на автокод и с автокода на язык машины. Применение автокодов обусловлено как неудобством (громоздкостью) машинных языков для описания операционных систем, так и непригодностью для данной цели таких языков, какАЛГОЛ. КОБОЛ и ФОРТРАН. Попытка упростить трансляцию была предпринята при создании языка ПЛ-1, который может быть использован как для описания алгоритмов решаемых задач, так и для описания операционных систем.

Заключение

В 1955 г. появился первый язык высокого уровня. Программы, написанные на таком языке, представляли собой набор уже не отдельных машинных команд, а более крупных элементов, называемых операторами данного языка. На языке высокого уровня исходная программа состояла из последовательности операторов.

Именно такие языки и ориентированы на описание алгоритмов. Поэтому их еще называют алгоритмическими языками.

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

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

Литература

1. “Язык программирования Си.” Б.В. Керниган, Д. Ритчи, А. Фьюэр. Русский перевод: Москва: Финансы и Статистика. 1985 г.;

2. “Основы автоматизации” ч.1, Золотарев В.В., 1978 г.;

3. “Языки программирования” кн.5, Ваулин А.С., 1993 г.;

4. “Языки программирования: разработка и реализация”, П. Терренс, 1979 г.

5. “Алгоритмические языки реального времени”, Янг С., 1985 г.

6. Можаров Р.В., Можарова Н.Р., Евтеев В.В., Кузьменко О.А., Шевченко М.О. Программное обеспечение персональных компьютеров//Учебное пособие для вузов. — М.: Финстатинформ, 1999.

7. В.И. Пономарёва. Практикум по программированию в среде Turbo Pascal. Симферополь, Таврида, 1998, 256

Программирование. Стандартные алгоритмы

Термин «алгоритм», впервые употребленный в современном значении. Лейбницем (1646–1716), является латинизированной формой имени великого персидского математика Мухаммеда бен Муссы аль-Хорезми (ок. 783 – ок. 850). Его книга «Об индийском счете» в XII в. была переведена на латинский язык и пользовалась широкой популярностью не одно столетие. Имя автора европейцы произносили как Алгоритми (Algorithmi), и со временем так стали называть в Европе всю систему десятичной арифметики.

Научное определение алгоритма дал А. Чёрч в 1930 году. В наше время понятие алгоритма является одним из основополагающих понятий вычислительной математики и информатики.

Алгоритм — это точное и полное описание последовательности действий над заданными объектами, позволяющее получить конечный результат.

Можно сказать, что алгоритм решения какой-либо задачи — это последовательность шагов реализации (или нахождения) этого решения, а процесс построения алгоритма (алгоритмизация) — разложение задачи на элементарные действия или операции.

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

Определение алгоритма для применения в области информатики нуждается в некотором уточнении. Во-первых, решение задач в информатике всегда связано с преобразованием информации, а значит, исходными данными и результатом работы алгоритма должна быть информация. Это может быть представлено в виде схемы.

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

Основные требования, предъявляемые к алгоритмам:

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

Определенность (детерминированность; лат. determinate — определенность, точность): шаги (операции) алгоритма должны допускать однозначную трактовку и быть понятными для исполнителя алгоритма. Это свойство указывает на то, что любое действие в алгоритме должно быть строго определено и описано для каждого случая.

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

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

Конечность: количество шагов алгоритма должно быть конечным.

Эффективность: количество шагов и сами шаги алгоритма должны быть такими, чтобы решение могло быть найдено за конечное и, более того, приемлемое время.

Для оценки и сравнения алгоритмов существует много критериев. Чаще всего анализ алгоритма (или, как говорят, анализ сложности алгоритма) состоит в оценке временных затрат на решение задачи в зависимости от объема исходных данных. Используются также термины «временная сложность», «трудоемкость» алгоритма. Фактически эта оценка сводится к подсчету количества основных операций в алгоритме, поскольку каждая из них выполняется за заранее известное конечное время. Кроме временной сложности, должна оцениваться также емкостная сложность, т. е. увеличение затрат памяти в зависимости от размера исходных данных. Оценка сложности дает количественный критерий для сравнения алгоритмов, предназначенных для решения одной и той же задачи. Оптимальным (наилучшим) считается алгоритм, который невозможно значительно улучшить в плане временных и емкостных затрат.

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

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

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

  1. следование — образуется из последовательности действий, следующих одно за другим;
  2. ветвление (развилка) — обеспечивает в зависимости от результатов проверки условия (ДА или НЕТ) выбор одного из альтернативных путей алгоритма;
  3. цикл — обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.

Для описания алгоритмов наиболее распространены следующие методы (языки):

Обычный язык. Изложение алгоритма ведется на обычном языке с разделением на последовательные шаги.

Блок-схемы. Графическое изображение алгоритма с помощью специальных значков-блоков.

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

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

Словесный способ (запись на обычном языке) не имеет широкого распространения, т. к. таких описаний есть ряд недостатков:

  • строго не формализуемы;
  • достаточно многословны;
  • могут допускать неоднозначность толкования отдельных предписаний;
  • сложные задачи с анализом условий, с повторяющимися действиями трудно представляются в словесной или словесно-формульной форме.

Графический способ представления информации является более наглядным и компактным по сравнению со словесным. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление алгоритма называется блок-схемой. Определенному типу действия (ввод/вывод данных, проверка условия, вычисление выражения, начало и конец алгоритма и т. п.) соответствует определенная геометрическая фигура — блочный символ. Блоки соединяются между собой линиями переходов, которые определяют очередность выполнения действий.

Название символа Графическое изображение Комментарии
Пуск/Останов (блоки начала и конца алгоритма) Указание на начало или конец алгоритма
Ввод/Вывод данных (блоки ввода, вывода Организация ввода/вывода в общем виде
Процесс (операторные блоки) Выполнение вычислительного действия или последовательности действий (можно объединять в один блок), которые изменяют значение, форму представления или размещение данных
Условие (условный блок) Выбор направления выполнения алгоритма. Если условие, записанное внутри ромба, выполняется, то управление передается по стрелке «да», в противном случае — по стрелке «нет». Таким образом, реализуется процесс изменения последовательности вычислений в зависимости от выполнения условия
Начало цикла с параметром Используется для организации циклических конструкций с известным количеством итераций (повторений) и известным шагом изменения параметра цикла. Внутри блока для параметра цикла указываются через запятую его начальное значение, конечное значение и шаг изменения. Цикл, для которого неизвестно количество повторений, записывается с помощью условного и операторных блоков
Предопределенный процесс Используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращения к библиотечным подпрограммам
Печать сообщений (документ) Вывод результатов на печать

При составлении блок-схемы необходимо проверять выполнение следующих условий:

  1. из каждого прямоугольника и параллелограмма (кроме конца алгоритма) должна выходить только одна стрелка;
  2. в каждый прямоугольник и параллелограмм (кроме начала алгоритма) должна входить хотя бы одна стрелка;
  3. в каждый ромб должна входить хотя бы одна стрелка, а выходить из него — две стрелки, помеченные словами «ДА» и «НЕТ».

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

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

алг — заголовок алгоритма нц — начало цикла знач
нач — начало алгоритма кц — конец цикла и
кон — конец алгоритма дано или
арг — аргумент надо не
рез — результат если да
цел — целый то нет
сим — символьный иначе при
лит — литерный всё выбор
лог — логический пока утв
вещ — вещественный для ввод
таб — таблица от вывод
длин — длина до

Общий вид записи алгоритма на псевдокоде:

алг — название алгоритма (аргументы и результаты)

дано — условие применимости алгоритма

надо — цель выполнения алгоритма

нач — описание промежуточных величин

последовательность команд (тело алгоритма)

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

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

Команды учебного языка:

1. Оператор присваивания, который обозначается «:=» и служит для вычисления выражений, стоящих справа, и присваивания их значений переменным, указанным в левой части. Например, если переменная а имела значение 5, то после выполнения оператора присваивания а := а + 1, значение переменной а изменится на 6.

2. Операторы ввода/вывода:

ввод (список имен переменных)

вывод (список вывода)

Список вывода может содержать комментарии, которые заключаются в кавычки.

3. Оператор ветвления (с использованием команды если. то… иначе…всё; выбор);

4. Операторы цикла (с использованием команд для, пока, до).

Запись алгоритма на псевдокоде:

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

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

Для решения одной и той же задачи можно предложить несколько алгоритмов. Алгоритмы составляются с ориентацией на определенного исполнителя алгоритма. У каждого исполнителя имеется свой конечный набор команд, которые для него понятны и исполняемы. Этот набор называется системой команд исполнителя. Пользуясь системой команд, исполнитель может выполнить алгоритм формально, не вникая в содержание поставленной задачи. От исполнителя требуется только строгое выполнение последовательности действий, предусмотренной алгоритмом. Таким образом, в общем случае алгоритм претерпевает изменения по стадиям:

  • первая стадия — алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает;
  • вторая стадия — алгоритм должен быть представлен в форме, понятной исполнителю алгоритма (вторая стадия может отсутствовать, если исполнять алгоритм будет сам разработчик).

Примеры решения задач

Пример 1. Исполнитель Утроитель может выполнить только две команды, которым присвоены номера:

Первая команда уменьшает число на 1, вторая — увеличивает его втрое.

Написать набор команд (не более пяти) получения из числа 3 числа 16. В ответе указать только номера команд.

Ответ: 13311

Пример 2. Имеется Исполнитель алгоритма, который может передвигаться по числовой оси.

Система команд Исполнителя алгоритма:

1. «Вперед N» (Исполнитель алгоритма делает шаг вперед на N единиц).

2. «Назад M» (Исполнитель алгоритма делает шаг назад на M единиц).

Переменные N и M могут принимать любые целые положительные значения. Известно, что Исполнитель алгоритма выполнил программу из 50 команд, в которой команд «Назад 2» на 12 больше, чем команд «Вперед 3». Других команд в программе не было. Какой одной командой можно заменить эту программу, чтобы Исполнитель алгоритма оказался в той же точке, что и после выполнения программы?

1. Найдем, сколько было команд «Вперед», а сколько «Назад». Учитывая, что общее количество команд равно 50 и что команд «Назад» на 12 больше, чем команд «Вперед». Получим уравнение: x + (x + 12) = 50, где x — количество команд «Вперед». Тогда общее количество команд «Вперед»: x = 19, а количество команд «Назад»: 19 + 12 = 31.

2. Будем вести отсчет от начала числовой оси. Выполнив 19 раз команду «Вперед 3», Исполнитель алгоритма оказался бы на отметке числовой оси 57 (19 * 3 = 57). После выполнения 31 раз команды «Назад 2» (31 * 2 = 62) он оказался бы на отметке –5 (57 – 62 = –5).

3. Все эти команды можно заменить одной — «Назад 5».

Ответ: команда«Назад 5».

Пример 3. Черепашка является исполнителем для создания графических объектов на рабочем поле. При движении Черепашка оставляет след в виде линии. Черепашка может исполнять следующие команды:

Название команды Параметр Действия исполнителя
вп Число шагов Продвигается в направлении головы на указанное число шагов
нд Число шагов Продвигается в направлении, противоположном направлению головы на указанное число шагов
пр Число градусов Поворачивается направо относительно направления, заданного головой черепашки
лв Число градусов Поворачивается налево относительно направления, заданного головой черепашки

Для записи повторяющихся действий (цикла) используется команда Повтори. В этой команде два параметра: первый задает количество повторений (итераций), а второй — список команд которые должны повторяться (тело цикла); список заключается в квадратные скобки.

Записать для исполнителя Черепашка алгоритмы:

а) построения квадрата со стороной 100;

б) построения правильного шестиугольника со стороной 50.

в) построения изображения цифры 4, если голова Черепашки смотрит на север.

Ответ: а) Повтори 4 [вп 100 пр 90]; б) Повтори 6 [вп 50 пр 360/6]; в) вп 100; повтори [лв 135 вп 50].

Пример 4. Два игрока играют в следующую игру (это вариант восточной игры). Перед ними лежат три кучки камней, в первой из которых 2, во второй — 3, в третьей — 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в одной из кучек, или добавляет по два камня в каждую из них. Выигрывает игрок, после хода которого либо в одной из кучек становится не менее 15 камней, либо общее число камней в трех кучках становится не менее 25. Кто выиграет при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ следует обосновать.

Решение. Удобнее всего составить таблицу возможных ходов обоих игроков. Заметим, что в каждом случае возможны всего четыре варианта хода. В таблице курсивом выделены случаи, которые сразу же приносят поражение игроку, делающему этот ход (например, когда камней в какой-либо кучке становится больше или равно 8, другой игрок непременно выигрывает следующим ходом, удваивая количество камней в этой кучке). Из таблицы видно, что при безошибочной игре обоих игроков первый всегда выиграет, если первым ходом сделает 4, 5, 6. У второго игрока в этом случае все ходы проигрышные.

1-й ход 2-й ход
Начало 1-й игрок 2-й игрок 1-й игрок 2-й игрок
2,3,4 4,3,4 8,3,4 выигрыш
4,6,4 8,6,4 выигрыш
4,12,4 выигрыш
4,6,8 выигрыш
6,8,6 выигрыш
4,3,8 выигрыш
6,5,6 12,5,6 выигрыш
6,10,6 выигрыш
6,5,12 выигрыш
8,7,8 выигрыш
2,6,4 4,6,4 8,6,4 выигрыш
4,12,4 выигрыш
4,6,8 выигрыш
6,8,6 выигрыш
2,12,4 выигрыш
2,6,8 выигрыш
4,8,6 выигрыш
2,3,8 выигрыш
4,5,6 8,5,6 выигрыш
4,10,6 выигрыш
4,5,12 выигрыш
6,7,8 выигрыш

Пример 5. Записано 7 строк, каждая из которых имеет свой номер. В нулевой строке после номера записана цифра 001. Каждая последующая строка содержит два повторения предыдущей строки и добавленной в конец большой буквы латинского алфавита (первая строка — A, вторая строка — B и т. д.). Ниже приведены первые три строкиєтой записи (в скобках указан номер строки):

Какой символ находится в последней строке на 250-м месте (считая слева направо)?

Примечание. Первые семь букв латинского алфавита: A, B, C, D, E, F, G.

Решение. Найдем длину каждой строки. Длина каждой следующей строки в два раза больше длины предыдущей плюс один символ, длина строк составит:

(6) 127*2+1=255 символов.

Так как задано 7 строк, а нумерация начинается с нулевой строки, последняя строка имеет номер 6 и содержит 255 символов. Последний символ в строке — F. Предпоследний элемент — E, далее идут символы D, C, B, A, 1 (по правилу формирования строк). Таким образом, 250-й символ — это 1.

Пример 6. Имеется фрагмент алгоритма, записанный на учебном алгоритмическом языке:

n := Длина(а)

b := Извлечь(а, k)

нц для i от 7 до n – 1

с := Извлечь(а, i)

b := Склеить(b, с)

Здесь переменные а, b, с — строкового типа; переменные n, i — целые.

В алгоритме используются следующие функции:

Длина(х) — возвращает количество символов в строке х. Имеет тип «целое».

Извлечь(х, i) — возвращает i-й символ слева в строке х. Имеет строковый тип.

Склеить(х, у) — возвращает строку, в которой находятся все символы строки х, а затем все символы строки у. Имеет строковый тип.

Какое значение примет переменная b после выполнения этого фрагмента алгоритма, если переменная а имела значение «ВОСКРЕСЕНЬЕ»?

Решение. Находим общее число символов в строке а, получим, что n = 11.

Выполняя команду b := Извлечь(а, k) при k = 2, получим, что b примет значение «О«.

В цикле последовательно, начиная с 7-го символа строки а и заканчивая предпоследним (n – 1), извлекаем символ из строки а и присоединяем к строке b.

В результате получим слово «ОСЕНЬ» (символы с номерами 2 + 7 + 8 + 9 + 10).

Ответ: «ОСЕНЬ«

Пример 7. Леонардо из Пизы, известный как Фибоначчи, был первым из великих математиков Европы позднего Средневековья. Числовой ряд, который называется его именем, получился в результате решения задачи о кроликах, которую Фибоначчи изложил в своей «Книге Абака», написанной в 1202 году. Он выглядит так:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.

В этом ряду каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Составить словесный алгоритм и блок-схему проверки принадлежности введенного числа n ряду Фибоначчи.

Решение. Словесный алгоритм:

  1. Ввести число n.
  2. Установить значение первых трех чисел Фибоначчи: 1, 1, 2 (сумма двух предыдущих чисел).
  3. Пока введенное число n больше очередного числа Фибоначчи, взять два последних числа Фибоначчи и получить из них новое число Фибоначчи.
  4. Если число Фибоначчи равно введенному n или было введено число n = 1, значит, что было введено число Фибоначчи, в противном случае — введенное число не является числом Фибоначчи.

Приведенный словесный алгоритм в пункте 1, 2 содержит начальные установки, в пункте 3 — цикл с условием, а пункт 4 — это вывод результата работы алгоритма.

F — текущее число ряда Фибоначчи;

F1 и F2 — два предыдущих числа ряда Фибоначчи для числа F;

n — число, для которого требуется определить, является ли оно числом из ряда Фибоначчи.

Использование основных алгоритмических конструкций: следование, ветвление, цикл

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

Базовая структура СЛЕДОВАНИЕ указывает на то, что управление передается последовательно от одного действия к другому.

Учебный алгоритмический язык Язык блок-схем
действие 1
действие 2

действие n

Использование исключительно этой структуры возможно лишь для достаточно простых задач, ход решения которых не меняется в зависимости от конкретных исходных данных и состоит в последовательном выполнении определенных операций.

В качестве примера рассмотрим решение простой задачи.

Пример. Найти y(x) = x2 + 3x + 5, используя только операции умножения и сложения.

Решение. На рис. приводятся два алгоритма, реализующие решение поставленной задачи.

Порядок вычисления y(x) в первом случае — обычный, а во втором — (x + 3) x + 5. Обе формулы эквивалентны, но в первом случае для вычисления необходимо 2 умножения, 2 сложения и 3 переменных (x, y, z), а во втором используются 1 умножение, 2 сложения и 2 переменные (x, y).

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

Обратите внимание, как в блоке следования используется оператор присваивания.

Операция присваивания — важнейшая операция во всех языках программирования. С помощью присваивания переменные получают новые значения: в левой части инструкции ставится идентификатор величины, а в правой части — выражение, значение которого можно определить.

В операторах присваивания используется либо привычный знак равенства, либо сочетание двоеточия и знака равенства «:=». Поскольку знак присваивания — это не знак равенства, возможны записи вида Х := Х + 1 или А := А – В. Нужно учитывать, что оператор присваивания будет выполняться только в том случае, если значения всех переменных правой части уже определены.

Базовая структура ВЕТВЛЕНИЕ (РАЗВИЛКА) используется в случае, когда выполнение программы может измениться в зависимости от результата проверки условия и пойти двумя разными (альтернативными) путями. Другими словами, условие является некоторым высказыванием (предикатом) и может быть истинным или ложным (принимать значение TRUE или FALSE). Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.

Различают две структуры этого типа — полную и неполную. В случае полной структуры, если условие выполняется (является истинным), вслед за ним выполняется действие 1, иначе — действие 2. В случае неполной структуры, если условие выполняется (является истинным), то вслед за ним выполняется действие 1, иначе ничего не происходит.

Важную роль в операторах ветвления играют содержащиеся в них условия. В простейшем случае условиями служат отношения между величинами. Условия с одним отношением называют простыми условными выражениями, или простыми условиями. В некоторых задачах необходимы более сложные условия, состоящие из нескольких простых, например условие А < X < С, т. е. Х < А и (Х >C) (возможна запись (Х < А) and (Х >C)). Объединение нескольких простых условий в одно образует составное условное выражение, или составное условие. Составные условия образуются с помощью логических операторов not (отрицание), and (логическое И), or (логическое ИЛИ), хоr (исключающее ИЛИ).

Структура ВЕТВЛЕНИЕ существует в четырех основных вариантах:

если — то (неполная структура);

если — то — иначе (полная структура);

выбор (неполный);

выбор — иначе (полный).

если условие

то действие 1

если условие

то действие 1

иначедействие 2

при условие 1: действие 1

при условии 2: действие 2

при условие N: действие N

при условие 1: действие 1

при условие 2: действие 2

при условие N: действие N + 1

иначе действия N + 1

В качестве простого примера рассмотрим нахождение модуля числа y(x) = |x|. Решение приведено на рис. для случаев полной (а) и неполной (б) структур ветвления.

Базовая структура ЦИКЛ служит для записи алгоритмов, в которых некоторая часть алгоритма (тело цикла) должна повторяться несколько раз. Количество повторений цикла может определяться разными способами, в зависимости от которых различают три вида циклов.

1. Цикл с предусловием, или цикл «пока». При реализации этого цикла сначала проверяется условие его выполнения. Пока оно выполняется, будут происходить повторения тела цикла. Отсюда и другое его название — цикл «пока». Если условие не выполняется при первой проверке, то тело цикла не будет выполняться вообще. После выхода из цикла управление передается следующей структуре. Для того чтобы избежать зацикливания, т. е. бесконечного цикла, в теле цикла обязательно должны изменяться параметры, записанные в условии.

пока условие

тело цикла (последовательность действий)

2. Цикл с параметром. Этот вид цикла удобно использовать в тех случаях, когда заранее извесно количество повторений цикла. Вводится понятие счетчика цикла, который по умолчанию считается равным либо 1, либо –1. В некоторых случаях изменение счетчика цикла (приращение) указывают явно. Для организации цикла необходимо задать верхнюю и нижнюю границы изменения счетчика цикла. В зависимости от значения верхней и нижней границы определяется шаг цикла (1 или −1), т. е. значение счетчика цикла.

для i от i1 до i2

тело цикла (последовательность действий)

3. Цикл с постусловием, или цикл «до». При реализации этого цикла условие завершение цикла проверяется после тела цикла. В этом случае тело цикла всегда выполняется хотя бы один раз. Цикл будет выполняться до выполнения условия, отсюда и другое название — цикл «до». А пока условие не выполнено, будет повторяться тело цикла (выполнение условия, таким образом, является условием окончания цикла). В этом случае, как и в цикле «пока», необходимо предусмотреть в теле цикла изменение параметров условия цикла.

тело цикла (последовательность действий)

до условие

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

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

Алгоритм, в состав которого входит итерационный цикл, называется итерационным алгоритмом. Итерационные алгоритмы используются при реализации итерационных численных методов. В итерационных алгоритмах необходимо обеспечить обязательное условие выхода из цикла (сходимость итерационного процесса). В противном случае произойдет зацикливание алгоритма, т. е. не будет выполняться основное свойство алгоритма — результативность.

Пример. Вычислить сумму знакопеременного ряда $S=x-/+/-/+. $ с заданной точностью $ε$.

Для данной знакочередующейся бесконечной суммы требуемая точность будет достигнута, когда очередное слагаемое станет по абсолютной величине меньше $ε$.

Решение. Запишем блок-схему алгоритма, где будем использовать следующие обозначения:

$S$ — частичная сумма ряда (стартовое значение равно 0);

$ε$ — точность вычисления;

$i$ — номер очередного слагаемого;

$m$ — значение очередного слагаемого;

$p$ — числитель очередного слагаемого.

На псевдокоде алгоритм можно записать следующим образом:

Примечание. Следует отметить, что ряд будет сходящимся только при выполнении условия 0 < х < 1.

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

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

Пример. Вычислить сумму элементов для заданной матрицы (таблицы из 5 строк и 3 столбцов) А(5,3).

Решение. Алгоритм решения задачи на псевдокоде:

Основная часть блок-схемы нахождения суммы элементов матрицы будет иметь следующий вид:

Здесь порядок выполнения вложенных циклов следующий: счетчик внутреннего цикла изменяется быстрее, т. е. для i = 1(внешний цикл), j пробегает значения 1, 2, 3 (внутренний цикл); далее i = 2, j опять пробегает значения 1, 2, 3 и т. д.

Примеры решения задач

Пример 1. Дан фрагмент блок-схемы некоторого алгоритма.

Определить значение переменной А после выполнения фрагмента алгоритма.

Какие исправления нужно внести, чтобы изменение значения переменной А происходило в обратном порядке?

Как записать исходный алгоритм с помощью двух других видов цикла?

Решение. Если представить пошаговое выполнение алгоритма в виде таблицы, получим:

Начальные установки: A = 100000; N = 2
1-я итерация A = 10000; N = 4
2-я итерация A = 1000; N = 6
3-я итерация A = 100; N = 8
4-я итерация A = 10; N = 10
5-я итерация, выполнилось условие выхода: N > 10 Ответ: А = 1; N = 12

Таблица обратного хода изменения значения А будет иметь такой вид:

Начальные установки: A = 1; N = 2
1-я итерация A = 10; N = 4
2-я итерация A = 100; N = 6
3-я итерация A = 1000; N = 8
4-я итерация A = 10000; N = 10
5-я итерация, выполнилось условие выхода: N > 10 А = 100000; N = 12

Блок-схема алгоритма примет такой вид:

В алгоритме нужно изменить начальное значение А и операцию деления заменить операцией умножения. Счетчик N в данном случае изменять не нужно.

В приведенной в условии блок-схеме используется цикл с предусловием. Для цикла с параметром блок-схема алгоритма будет иметь такой вид:

Понятно, что цикл должен выполниться пять раз. В заголовке цикла необходимо указать начальное и конечное значение счетчика цикла N (приращение по умолчанию равно 1).

Для цикла с постусловием блок-схема исходного алгоритма имеет такой вид:

В данной схеме условие завершения цикла находится после тела цикла. Цикл, в отличие от цикла с предусловием, выполняется, пока значение условия ложно.

Пример 2. Сколько раз выполнится тело цикла в программе?

нц пока (div(Q, 5) = div(P, 7))

Примечание. Результат функции div(X, Y) — целая часть от деления X на Y.

Решение. Рассмотрим пошаговое выполнение алгоритма, оформив его в виде таблицы.

Начальные установки Q := 27; P := 36
Проверка выполнения условия div(27, 5) = 5;
div(36, 7) = 5;
5 = 5
1-я итерация; выполнение тела цикла Q := 29; P := 39
Проверка выполнения условия div(29, 5) = 5;
div(39, 7) = 5;
5 = 5
2-я итерация; выполнение тела цикла Q := 31; P := 42
Проверка выполнения условия div(31, 5) = 6;
div(42, 7) = 6;
6 = 6
3-я итерация; выполнение тела цикла Q := 33; P := 45
Проверка выполнения условия div(33, 5) = 6;
div(45, 7) = 6
6 = 6
4-я итерация; выполнение тела цикла Q := 35; P := 48
Проверка выполнения условия. Условие не выполняется, цикл завершает работу div(35, 5) = 7;
div(48, 7) = 6;
7 ≠ 6

Ответ: цикл выполнится 4 раза.

Использование переменных. Объявление переменной (тип, имя, значение). Локальные и глобальные переменные

Величины служат для описания объектов и процессов в материальном мире. Каждая величина имеет некоторые характеристики. В программировании понятие величины несколько отличается от понятия величины в естественных науках — оно является более формальным. Величиной называют объект — переменную, с которым связывается определенное множество значений. Такому объекту присваивается имя — идентификатор. Понятие переменной в программировании сходно с понятием переменной в математике. Например, в алгебраическом равенстве C = F + 2B – 5 значение переменной С зависит от значений переменных F и B, указанных в правой части равенства. Например, при F = 2 и B = 6, С = 9. Такое же равенство можно записать в программе, например на языке программирования Бейсик: C = F + 2*B – 5. В терминах языка программирования C, F и B — это идентификаторы (имена) переменных.

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

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

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

  • идентификатором;
  • типом;
  • значением.

Каждая переменная имеет свой идентификатор, т. е. свое уникальное имя. Имя переменной показывает, в каком месте памяти компьютера она хранится, значение переменной считывается из указанного ее именем места в памяти. Двух переменных с одним именем в одном программном модуле (блоке) быть не должно. Примерами идентификаторов величин могут быть, например, следующие последовательности символов: a1, SUMMA, X_1, Y_1, My_program.

Во многих языках программирования существуют некоторые ограничения на задания имен переменных. Имена составляются из букв и цифр; первой литерой должна быть буква. Знак подчеркивания «_» считается буквой, его удобно использовать, чтобы улучшить восприятие длинных имен переменных. Разумно давать переменным логически осмысленные имена, в соответствии с их назначением. Нельзя использовать в качестве имен зарезервированные (служебные) слова языка программирования.

Тип переменной — это диапазон (набор) всех значений, которые может принимать данная переменная. Тип переменной определяет, какие операции для нее допустимы. Другими словами, тип переменной — это характеристика, которая для величины определяет:

  • необходимый размер памяти;
  • диапазон значений, которые может принимать величина;
  • возможные операции над величиной (подразумеваются действия относительно использования величин в выражениях);
  • формы представления величин (или формат представления величин).

Стандартные типы — это числовые, литерные и логические типы.

Числовой тип, к которому относятся целые и вещественные величины, позволяет оперировать с числами. Целые числа, которые в учебном алгоритмическом языке составляют тип цел, сверху ограничены положительным числом Nmax, а снизу — отрицательным числом Nmin. Значения Nmax и Nmin определяются объемом ячеек памяти, в которые записываются целые числа. Обычно для целых чисел выделяется два байта памяти, соответственно границы диапазона равны [Nmin = –32768 и Nmax = 32767]. Считается, что все операции с величинами типа цел выполняются по обычным правилам арифметики, за одним исключением: возможны две операции деления div и mod.

Операция div обозначает целочисленное деление. При делении с точностью до целых чисел получается два результата — частное и остаток. Знак результата берется по обычным правилам, а полученный остаток игнорируется. Например:

Операция mod определяет остаток при делении двух целых чисел.

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

К другому числовому типу относятся вещественные (вещ) величины. Значения вещественных величин могут изображаться в форме с фиксированной запятой (например, 0,3333; 2,0; –4,567 и т. д.) и с плавающей запятой (например, 7,0*10 2 , 5,173*10 –3 и т. д.).

В отличие от целых чисел, действия с вещественными числами могут быть неточными — это связано с ошибками округлений. Объем памяти, который предоставляется для хранения значений вещественной переменной, — от 4 до 10 байтов (в зависимости от выбранного формата числа). Над числовыми величинами можно выполнять как арифметические операции, так и операции сравнения (>, =,

Литерный тип, включающий символы и строки, дает возможность работать с текстом. Литерные величины — это произвольные последовательности символов: букв, цифр, знаков препинания, пробела и других специальных знаков (возможными символами могут быть символы таблицы ASCII). Литерные величины обычно заключаются в кавычки: «а», «В», «СТРОКА», «1_2_3». В учебном алгоритмическом языке литерные величины обозначаются как лит. В других языках программирования (например, в Паскале) различают символьный (char) и строковый (string) типы. Величины символьного типа состоят из одного символа и занимают в памяти всего 1 байт. Величины строкового типа представляют собой различные последовательности символов, которые предусмотрены кодовой страницей, установленной в компьютере. Длина строки может составлять от 0 до 255 символов. Над всеми литерными величинами возможны операции сравнения. С помощью отношений типа «a» < "b", "b" < "c", "c" < "d". выполняется упорядочение литерных величин (сортировка по возрастанию или убыванию).

Еще одной операцией, характерной для символьных и строковых величин, является операция конкатенации (слияния): «a» + «b» = «ab».

Логический тип позволяет определять логические переменные, которые могут принимать только два значения: истина (true) или ложь (false). Для представления логической величины достаточно одного бита, однако, поскольку место в памяти выделяется по байтам, логической величине отводится минимальная «порция» памяти — один байт. Над логическими величинами можно выполнять все стандартные логические операции.

Значение — это непосредственно то, чему равна переменная в конкретный момент времени. Это может быть число, символ, текст и т. д. Значение переменной в программе можно задать двумя способами: присваиванием и с помощью процедуры ввода.

Оператор присваивания

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

В операторах присваивания используется либо обычный знак равенства, либо сочетание двоеточия и знака равенства «:=». Поскольку знак присваивания — это не знак равенства, возможны записи вида Х := Х + 1 или А := А – В. Нужно учитывать, что оператор присваивания будет выполняться только в том случае, если значения всех переменных в правой части уже определены и выполняется соответствие типов для правой и левой части оператора присваивания. Например, С := А > B выполнится только в том случае, если для переменной С определен булевский (логический) тип. Операция присваивания может быть применена к большинству типов величин. Однако для каждого из типов предусмотрен свой набор операций.

Локальные, глобальные и общие переменные

Каждая переменная характеризуется областью действия или областью видимости. По зоне видимости в языках программирования различают локальные и глобальные переменные. Первые доступны только конкретному подалгоритму (вспомогательному алгоритму, подпрограмме, модулю), вторые — всему алгоритму (программе). С распространением модульного и объектного программирования появились еще и общие переменные, доступные для определенных уровней иерархии подпрограмм.

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

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

Примеры решения задач

Пример 1. Значения заданных переменных А, В перераспределить таким образом, чтобы А и В поменялись значениями.

Решение. Возможны два варианта решения:

С использованием промежуточной переменной С Без использования дополнительной переменной
C := A;
A := B;
B := C
A := A + B;
B := A – B;
A := A – B

Пример 2. Определить значение переменной A после выполнения фрагмента алгоритма:

Решение. Оформим решение в виде таблицы.

A B D Условие
2 –2 10 да
–4 –2 12 да
8 –2 14 да
–16 –2 16 да
32 –2 18 да
–64 –2 20 да
128 –2 22 нет — окончание цикла

Ответ: А = 128.

Пример 3. Определить значение переменной S:

нц пока A + B < 10

A := A + 1; B := B + A

Решение. Оформим решение в виде таблицы.

A B A + B S
–1 1 0
0 1 1
1 2 3
2 4 6
3 7 10 — условие выхода из цикла 21

Ответ: S = 21.

Пример 4. Записать последовательность операций присваивания (:=), которая позволит определить номера подъезда и этажа по номеру N квартиры девятиэтажного дома, считая, что на каждом этаже по 4 квартиры, а нумерация квартир начинается с первого подъезда.

Х := (N – 1) div 36 + 1

Y := (N – 1) div 4 + 1

Например, для квартиры с номером 150 получим:

Х = (150 – 1) div 36 + 1 = 4 + 1 = 5;

N = 150 – (5 – 1) * 36 = 6;

Y = (6 – 1) div 4 + 1 = 2.

Ответ: квартира с номером 150 находится в пятом подъезде, на втором этаже.

Работа с массивами (заполнение, считывание, поиск, сортировка, массовые операции и др.)

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

  1. объединением однородных элементов данных;
  2. объединением разнородных элементов данных.

В первом случае примером могут служить массивы, а во втором — записи.

Информацию удобно представлять в виде таблиц. Наиболее привычными являются прямоугольные таблицы, т. е. таблицы, состоящие из строк и столбцов. В том числе таблицы, состоящие из единственной строки или единственного столбца, — линейные таблицы, имеющие одно «измерение».

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

Массив — это упорядоченный набор данных, имеющий одно имя и состоящий из фиксированного числа однотипных элементов.

Каждый элемент массива снабжен индексом. Индекс — это порядковый номер элемента, определяющий его положение в массиве. Таким образом, элементы массива идентифицируются с помощью имени массива и с помощью своих индексов.

Количество элементов массива называется размерностью массива.

Итак, массив характеризуется:

  • размерностью;
  • базовым типом элементов;
  • типом индекса (может быть только порядковым типом);
  • множеством значений для индекса.

Массив может быть одномерным (вектор) и многомерным (матрица).

Одномерный массив содержит одно измерение; каждый элемент массива обозначается идентификатором (именем) массива с индексом. Многомерный массив содержит n-е количество измерений; каждый элемент массива обозначается идентификатором массива для n индексов.

Существует несколько способов заполнения массива данными:

  1. непосредственное присваивание значений элементам;
  2. заполнение массива произвольными элементами, случайными числами;
  3. ввод значений элементов с клавиатуры или чтение из файла.

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

Примечание. Строковый тип данных напоминает одномерный массив, в котором элементами являются символы. К примеру, строку «МАМА КУПИЛА ХЛЕБ» можно рассматривать как одномерный массив из 16 символов (включая пробелы). Эту строку можно обозначить идентификатором (например, Novost) и пронумеровать все символы, считая их элементами массива: Novost (l) = «М», . Novost (16) = «Б».

Однако для работы с символьной информацией более гибким инструментом является не одномерный массив, а строка (string). Это связано с тем, что количество символов в строке, в отличие от массива, не фиксировано. Благодаря этому к строке можно без ограничений применять стандартные операции и функции, предназначенные для работы с текстом.

Задачи, связанные с обработкой массивов, как и все задачи вообще, условно можно разделить на два вида:

  1. стандартные задачи;
  2. задачи, решение которых требует знания вспомогательных алгоритмов, специальных методов и приемов.

Очевидно, что без умения решать задачи первых двух видов невозможно решать нестандартные задачи.

Стандартные задачи обработки массивов

Пример 1. В массиве А каждый элемент равен 0 или 1. Заменить все нули единицами и наоборот.

Решение. Достаточно одного оператора присваивания в теле цикла:

Пример 2. В массиве каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все 0, затем все 1 и, наконец, все 2. Дополнительный массив не использовать.

Решение. Можно не переставлять элементы массива, а подсчитать количество 0, 1, 2 и заново заполнить массив требуемым образом.

Пример 3. Даны два n-элементных массива Х и Y одного типа. Поменять местами все Xi и Yi, (i = 1. n), не используя промежуточные величины.

Решение. Обмен можно выполнить в цикле для всех i от 1 до n с помощью серии из трех операторов присваивания:

Пример 4. Записать алгоритм нахождения максимального элемента массива А(n) и его номера.

Решение. На псевдокоде требуемый алгоритм запишется следующим образом:

Примечание. Если таких элементов несколько, будет найден номер последнего.

Пример 5. Найти сумму элементов одномерного массива А(n).

Решение. На псевдокоде алгоритм нахождения суммы запишется следующим образом:

Примечание. Для нахождения суммы положительных элементов массива вместо оператора

S := S + A[i] необходимо записать:

если A[i] > 0

то S := S + A[i]

Пример 6. Записать алгоритм вычисления произведения элементов столбцов заданной вещественной двумерной матрицы A(n, m).

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 7. Подсчитать количество элементов для заданной целочисленной матрицы A(n, m), равных ее максимальному элементу.

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 8. Запиcать алгоритм обмена элементами строк с номерами P и Q в заданной вещественной матрице A(n, m).

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 9. Включить заданное число D в одномерный упорядоченный по возрастанию массив F(n) с сохранением упорядоченности.

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 10. Сформировать новый массив B из элементов целочисленного массива A(n), для которых выполняется условие D < Ai < C.

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 11. Найти в заданном целочисленном массиве А(m) хотя бы одну пару элементов, совпадающих по значению.

Решение. На псевдокоде алгоритм запишется следующим образом:

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

  1. элемент найден;
  2. весь массив просмотрен — элемент не найден.

В упорядоченном массиве поиск можно значительно ускорить, применяя метод половинного деления, или бинарный поиск. Его идея заключается в следующем. Пусть фиксированный массив упорядочен по неубыванию (ai ≤ ai + 1). Случайно выбранный элемент am (обычно берут средний элемент) сравнивают с элементом поиска х. Если он меньше х, то искомый элемент может быть среди элементов am + i, . аn, т. е. в правой половине массива. Если он больше х — то среди элементов левой части массива. Если же он равен х, то поиск успешно заканчивается.

К стандартным задачам относятся задачи сортировки массива. Сортировка массива — это перерасположение элементов массива в заданном порядке. Основная цель сортировки — облегчить последующий поиск. Методы условно разделяют по главной идее алгоритма, а реализуются они целым семейством алгоритмов.

К простым методам сортировки относят:

  • сортировку с помощью обмена (метод пузырька);
  • сортировку с помощью прямого включения;
  • сортировку с помощью выбора.

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

Алгоритм сортировки массива A(n) по возрастанию на псевдокоде:

Сортировка с помощью прямого включения (вставки). На каждом шаге этого метода массив разделен на две части: левую, уже отсортированную, и правую, еще не отсортированную. Первый элемент правой части вставляется в левую часть массива так, чтобы левая часть осталась отсортированной. В результате отсортированная часть увеличивается на один элемент, а неотсортированная — на один элемент уменьшается. Таким образом, на каждом шаге алгоритма сортировки вставками приходится выполнять две операции: поиск позиции для вставки элемента и собственно его вставку с последующим сдвигом на одну позицию вправо от элементов отсортированной части. Этот сдвиг «стирает» первый элемент неотсортированной части. Сначала отсортированным подмассивом считаем первый элемент, а остальная часть массива относится к неотсортированной части. Поскольку операции сравнения и перемещения чередуются друг с другом, этот способ сортировки часто называют просеиванием или погружением.

Сортировка с помощью прямого выбора. При сортировке этим методом сначала выбирается наименьший (наибольший) элемент массива и меняется местами с первым. Затем выбирается наименьший (наибольший) среди оставшихся (n – 1) элементов и меняется местами со вторым и т. д. до тех пор, пока не останется один наибольший (наименьший) элемент. Сортировка осуществляется с помощью двух вложенных циклов.

Приведенные алгоритмы сортировки не требуют дополнительной оперативной памяти. Время выполнения алгоритмов сортировки пропорционально количеству операций сравнения и перестановки элементов. Сортировка массива из $n$ элементов методом выбора главного элемента требует выполнения $/$ операций сравнения и n операций обмена элементами. Метод сортировки вставками требует $/$ операций сравнения и столько же операций обмена, а метод пузырьковой сортировки — $/$ операций сравнения и столько же операций обмена. Таким образом, из трех рассмотренных методов сортировки массива методы вставки и выбора приблизительно эквивалентны, а обменная сортировка — медленнее. Кроме того, что в методе вставки исходные элементы могут поступать последовательно, а в методе выбора они должны быть в наличии до начала сортировки.

Примеры решения задач

Пример 1. Одномерный массив, содержащий десять элементов, заполняется по следующему закону: A[1] = 1; A[2] = X; A[i] = 2 * X * A[i – 1] – A[i – 2], где i = 3, 4, . 10. Каким будет значение A[5] при X = 1?

Решение. Представим значения первых пяти элементов массива А, полученные по заданному закону при Х = 1:

A[3] = 2 * Х * A[2] – A[1] = 2 * 1 * 1 – 1 = 1;

A[4] = 2 * Х * A[3] – A[2] = 2 * 1 * 1 – 1 = 1;

A[5] = 2 * Х * A[4] – A[3] = 2 * 1 * 1 – 1 = 1.

Таким образом, значение A[5] при Х = 1 будет равно 1.

Пример 2. Задан двумерный массив А(n, n). Определить, что вычисляет приведенный фрагмент алгоритма:

Решение. В данном алгоритме переменной S присваивается значение 0. Затем в структуре циклов по переменным i и j каждый из элементов массива Аij сравнивается с нулем (А[i, j] > 0) и если элементы Аij положительны, то квадраты А[i, j]^2 положительных элементов Аij увеличивают значение суммы S (S := S + A[i, j]^2).

Ответ: фрагмент алгоритма вычисляет сумму квадратов положительных элементов массива.

Пример 3. Задан фрагмент алгоритма, использующий двумерный массив (таблицу) М(n, n), два одномерных массива A(n), B(n) и переменную X. Определить назначение массивов А и В и переменной.

Решение. Представим фрагмент алгоритма словесно.

  1. Переменной X присвоить значение 0.
  2. Переменной i присвоить значение 1.
  3. Если i ≤ n, то перейти к следующему пункту; в противном случае — конец фрагмента алгоритма.
  4. Элементу одномерного массива А с индексом i присвоить значение элемента двумерного массива М, находящегося в i-й строке и первом столбце.
  5. Элементу одномерного массива В с индексом i присвоить значение 1.
  6. Переменной j присвоить значение 1.
  7. Если j ≤ n, то перейти к следующему пункту; в противном случае — к п. 13.
  8. Если М[i, j] < A[i], то перейти к следующему пункту; иначе — к п. 11.
  9. Элементу A[i] присвоить значение элемента массива М, находящегося в i-й строке и j-м столбце.
  10. Элементу В[i] присвоить значение переменной j.
  11. Переменной Х присвоить значение суммы X + M[i, j].
  12. Переменной j присвоить значение суммы j + 1 и вернуться к п. 7.
  13. Переменной i присвоить значение суммы i + 1 и вернуться к п. 3.

Таким образом, анализ алгоритма показывает, что переменная X накапливала сумму всех элементов массива М; массив А — минимальные элементы соответствующих строк массива М; массив В — индексы (порядковые номера столбцов) минимальных элементов в соответствующих строках массива М.

Пример 4. Составить алгоритм определения наличия среди элементов главной диагонали заданной целочисленной матрицы A(n, m) хотя бы одного положительного нечетного элемента.

Решение. Для всех элементов Аij главной диагонали выполняется условие i = j. Определение наличия нечетных элементов выполняется с помощью операции mod (остаток от целочисленного деления), при этом, если результат mod равен 1, — число нечетное.

Структурирование задачи при ее решении для использования вспомогательного алгоритма. Вспомогательные алгоритмы: процедуры и функции

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

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

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

Если вспомогательный алгоритм в процессе работы программы выполняется многократно, отличаясь только параметрами, то обычно прибегают к оформлению вспомогательного алгоритма в виде подпрограммы — алгоритма-процедуры, или алгоритма-функции.

Подпрограмма — это именованный, логически законченный алгоритм, который оформляется специальным образом и может многократно использоваться при решении более общей задачи.

Описание подпрограмм можно сравнить с записываемой в математике формулой «в общем виде», в которую при расчетах подставляются конкретные значения. Далеко не каждую задачу можно свести к единственной формуле, но всегда можно записать алгоритм ее решения, а значит, подпрограмма — это инструкция по решению некоторой задачи. Как и формулу, подпрограмму можно использовать для обработки различных данных, передаваемых из главной программы или других подпрограмм.

В языках программирования подпрограмма является частью основной программы, ее описание располагается в описательной части программы. Структура подпрограммы такая же, как и основной программы; различие заключается лишь в оформлении заголовка подпрограммы. Заголовок подпрограммы состоит из служебного слова — идентификатора подпрограммы (имени подалгоритма) — и списка формальных параметров (список параметров не обязателен, допускаются подпрограммы без параметров). При вызове процедуры из текста программы вместо формальных параметров подставляются фактические параметры, при этом соблюдаются следующие правила:

  • количество формальных и фактических параметров должно совпадать, причем соответствие между параметрами команды вызова и формальными параметрами процедуры устанавливается по порядку следования: первый фактический параметр соответствует первой переменной, записанной в заголовке подпрограммы, второй фактический параметр — второй переменной и т. д.;
  • типы соответствующих параметров команды вызова и заголовка подпрограммы должны совпадать.

Команда вызова подпрограммы выполняется в три этапа:

  1. вычисление фактических аргументов;
  2. исполнение алгоритма подпрограммы;
  3. присвоение полученных значений результатов алгоритма-подпрограммы соответствующим фактическим переменным.

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

Различают два вида подпрограмм — процедуры и функции. Имея один и тот же смысл и аналогичную структуру, процедуры и функции различаются назначением и способом их использования. Основное отличие функций от процедур заключается в том, что результатом выполнения функции является некоторое единственное значение. Функция — это алгоритмически вычисляемое выражение, которое присваивается идентификатору функции.

Подпрограммы бывают двух видов: стандартные и пользовательские. Стандартные, или встроенные, подпрограммы входят в состав языка программирования. Эти подпрограммы определенным образом организованы в специальные библиотеки. С помощью встроенных процедур и функций выполняются операции ввода/вывода, работа с файлами, обработка символьной информации, вычисление различных математических функций и т. п.

Подпрограммы, которые написаны пользователем, называются пользовательскими.

Технология программирования

Чтение короткой (30±50 строк) простой программы на алгоритмическом языке (языке программирования)

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

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

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

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

При чтении программы необходимо сначала определить, к какому виду она относится. Условно программы можно разделить на два вида: простая программа без использования подпрограмм (кроме стандартных процедур ввода\вывода) и программа, использующая подпрограммы (подалгоритмы). Такая программа может включать в свою структуру как стандартные подпрограммы, так и подпрограммы, написанные пользователем.

Для чтения простой программы необходимо выяснить:

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

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

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

Примеры чтения программ на языках Pascal, QBASIC

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

Пример 1. Дана программа на двух языках программирования. Определить, какую задачу она решает.

Решение. Проанализируем тексты программы:

  1. формируется тело программы и описываются переменные;
  2. вводятся натуральные числа М и N, причем проверяется условие корректности ввода: числа должны быть положительные. Если введенные значения не удовлетворяют условию, то ввод повторяют, пока условие не будет выполнено;
  3. выбирается наименьшее значение из М и N, результат записывается в K;
  4. NOD присваивается значение 1;
  5. в цикле от двух до K генерируется число I;
  6. тело цикла — в условном операторе проверяется, является ли значение переменной I одновременно делителем М и N. Если условие выполняется, то текущее значение I сохраняется в переменной NOD; если условие не выполняется, NOD не изменит своего значения;
  7. после перебора всех значений I в NOD или запишется наибольший делитель двух чисел М и N, или останется значение 1;
  8. последний оператор программы служит для вывода результата работы программы — значения переменной NOD.

Переменные, используемые в программе:

N, М — исследуемые числа;

I — переменная цикла;

NOD — наибольший общий делитель;

К — наименьшее из М и N.

Ответ: данная программа позволяет определить для двух чисел М и N их наибольший общий делитель NOD.

Примечание. Эту же задачу можно решить, используя алгоритм Евклида.

Пример 2. Дана программа на двух языках программирования. Определить, какую задачу она решает.

  • ООО «Экзамер», 2024
  • Написать нам
  • Юридические документы

Обработка алгоритмов. Робот, Чертёжник, Редактор

Термин «алгоритм», впервые употребленный в современном значении. Лейбницем (1646–1716), является латинизированной формой имени великого персидского математика Мухаммеда бен Муссы аль-Хорезми (ок. 783 – ок. 850). Его книга «Об индийском счете» в XII в. была переведена на латинский язык и пользовалась широкой популярностью не одно столетие. Имя автора европейцы произносили как Алгоритми (Algorithmi), и со временем так стали называть в Европе всю систему десятичной арифметики.

Научное определение алгоритма дал А. Чёрч в 1930 году. В наше время понятие алгоритма является одним из основополагающих понятий вычислительной математики и информатики.

Алгоритм — это точное и полное описание последовательности действий над заданными объектами, позволяющее получить конечный результат.

Можно сказать, что алгоритм решения какой-либо задачи — это последовательность шагов реализации (или нахождения) этого решения, а процесс построения алгоритма (алгоритмизация) — разложение задачи на элементарные действия или операции.

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

Определение алгоритма для применения в области информатики нуждается в некотором уточнении. Во-первых, решение задач в информатике всегда связано с преобразованием информации, а значит, исходными данными и результатом работы алгоритма должна быть информация. Это может быть представлено в виде схемы.

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

Основные требования, предъявляемые к алгоритмам:

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

Определенность (детерминированность; лат. determinate — определенность, точность): шаги (операции) алгоритма должны допускать однозначную трактовку и быть понятными для исполнителя алгоритма. Это свойство указывает на то, что любое действие в алгоритме должно быть строго определено и описано для каждого случая.

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

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

Конечность: количество шагов алгоритма должно быть конечным.

Эффективность: количество шагов и сами шаги алгоритма должны быть такими, чтобы решение могло быть найдено за конечное и, более того, приемлемое время.

Для оценки и сравнения алгоритмов существует много критериев. Чаще всего анализ алгоритма (или, как говорят, анализ сложности алгоритма) состоит в оценке временных затрат на решение задачи в зависимости от объема исходных данных. Используются также термины «временная сложность», «трудоемкость» алгоритма. Фактически эта оценка сводится к подсчету количества основных операций в алгоритме, поскольку каждая из них выполняется за заранее известное конечное время. Кроме временной сложности, должна оцениваться также емкостная сложность, т. е. увеличение затрат памяти в зависимости от размера исходных данных. Оценка сложности дает количественный критерий для сравнения алгоритмов, предназначенных для решения одной и той же задачи. Оптимальным (наилучшим) считается алгоритм, который невозможно значительно улучшить в плане временных и емкостных затрат.

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

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

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

  1. следование — образуется из последовательности действий, следующих одно за другим;
  2. ветвление (развилка) — обеспечивает в зависимости от результатов проверки условия (ДА или НЕТ) выбор одного из альтернативных путей алгоритма;
  3. цикл — обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.

Для описания алгоритмов наиболее распространены следующие методы (языки):

Обычный язык. Изложение алгоритма ведется на обычном языке с разделением на последовательные шаги.

Блок-схемы. Графическое изображение алгоритма с помощью специальных значков-блоков.

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

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

Словесный способ (запись на обычном языке) не имеет широкого распространения, т. к. таких описаний есть ряд недостатков:

  • строго не формализуемы;
  • достаточно многословны;
  • могут допускать неоднозначность толкования отдельных предписаний;
  • сложные задачи с анализом условий, с повторяющимися действиями трудно представляются в словесной или словесно-формульной форме.

Графический способ представления информации является более наглядным и компактным по сравнению со словесным. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление алгоритма называется блок-схемой. Определенному типу действия (ввод/вывод данных, проверка условия, вычисление выражения, начало и конец алгоритма и т. п.) соответствует определенная геометрическая фигура — блочный символ. Блоки соединяются между собой линиями переходов, которые определяют очередность выполнения действий.

Название символа Графическое изображение Комментарии
Пуск/Останов (блоки начала и конца алгоритма) Указание на начало или конец алгоритма
Ввод/Вывод данных (блоки ввода, вывода Организация ввода/вывода в общем виде
Процесс (операторные блоки) Выполнение вычислительного действия или последовательности действий (можно объединять в один блок), которые изменяют значение, форму представления или размещение данных
Условие (условный блок) Выбор направления выполнения алгоритма. Если условие, записанное внутри ромба, выполняется, то управление передается по стрелке «да», в противном случае — по стрелке «нет». Таким образом, реализуется процесс изменения последовательности вычислений в зависимости от выполнения условия
Начало цикла с параметром Используется для организации циклических конструкций с известным количеством итераций (повторений) и известным шагом изменения параметра цикла. Внутри блока для параметра цикла указываются через запятую его начальное значение, конечное значение и шаг изменения. Цикл, для которого неизвестно количество повторений, записывается с помощью условного и операторных блоков
Предопределенный процесс Используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращения к библиотечным подпрограммам
Печать сообщений (документ) Вывод результатов на печать

При составлении блок-схемы необходимо проверять выполнение следующих условий:

  1. из каждого прямоугольника и параллелограмма (кроме конца алгоритма) должна выходить только одна стрелка;
  2. в каждый прямоугольник и параллелограмм (кроме начала алгоритма) должна входить хотя бы одна стрелка;
  3. в каждый ромб должна входить хотя бы одна стрелка, а выходить из него — две стрелки, помеченные словами «ДА» и «НЕТ».

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

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

алг — заголовок алгоритма нц — начало цикла знач
нач — начало алгоритма кц — конец цикла и
кон — конец алгоритма дано или
арг — аргумент надо не
рез — результат если да
цел — целый то нет
сим — символьный иначе при
лит — литерный всё выбор
лог — логический пока утв
вещ — вещественный для ввод
таб — таблица от вывод
длин — длина до

Общий вид записи алгоритма на псевдокоде:

алг — название алгоритма (аргументы и результаты)

дано — условие применимости алгоритма

надо — цель выполнения алгоритма

нач — описание промежуточных величин

последовательность команд (тело алгоритма)

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

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

Команды учебного языка:

1. Оператор присваивания, который обозначается «:=» и служит для вычисления выражений, стоящих справа, и присваивания их значений переменным, указанным в левой части. Например, если переменная а имела значение 5, то после выполнения оператора присваивания а := а + 1, значение переменной а изменится на 6.

2. Операторы ввода/вывода:

ввод (список имен переменных)

вывод (список вывода)

Список вывода может содержать комментарии, которые заключаются в кавычки.

3. Оператор ветвления (с использованием команды если. то… иначе…всё; выбор);

4. Операторы цикла (с использованием команд для, пока, до).

Запись алгоритма на псевдокоде:

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

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

Для решения одной и той же задачи можно предложить несколько алгоритмов. Алгоритмы составляются с ориентацией на определенного исполнителя алгоритма. У каждого исполнителя имеется свой конечный набор команд, которые для него понятны и исполняемы. Этот набор называется системой команд исполнителя. Пользуясь системой команд, исполнитель может выполнить алгоритм формально, не вникая в содержание поставленной задачи. От исполнителя требуется только строгое выполнение последовательности действий, предусмотренной алгоритмом. Таким образом, в общем случае алгоритм претерпевает изменения по стадиям:

  • первая стадия — алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает;
  • вторая стадия — алгоритм должен быть представлен в форме, понятной исполнителю алгоритма (вторая стадия может отсутствовать, если исполнять алгоритм будет сам разработчик).

Примеры решения задач

Пример 1. Исполнитель Утроитель может выполнить только две команды, которым присвоены номера:

Первая команда уменьшает число на 1, вторая — увеличивает его втрое.

Написать набор команд (не более пяти) получения из числа 3 числа 16. В ответе указать только номера команд.

Ответ: 13311

Пример 2. Имеется Исполнитель алгоритма, который может передвигаться по числовой оси.

Система команд Исполнителя алгоритма:

1. «Вперед N» (Исполнитель алгоритма делает шаг вперед на N единиц).

2. «Назад M» (Исполнитель алгоритма делает шаг назад на M единиц).

Переменные N и M могут принимать любые целые положительные значения. Известно, что Исполнитель алгоритма выполнил программу из 50 команд, в которой команд «Назад 2» на 12 больше, чем команд «Вперед 3». Других команд в программе не было. Какой одной командой можно заменить эту программу, чтобы Исполнитель алгоритма оказался в той же точке, что и после выполнения программы?

1. Найдем, сколько было команд «Вперед», а сколько «Назад». Учитывая, что общее количество команд равно 50 и что команд «Назад» на 12 больше, чем команд «Вперед». Получим уравнение: x + (x + 12) = 50, где x — количество команд «Вперед». Тогда общее количество команд «Вперед»: x = 19, а количество команд «Назад»: 19 + 12 = 31.

2. Будем вести отсчет от начала числовой оси. Выполнив 19 раз команду «Вперед 3», Исполнитель алгоритма оказался бы на отметке числовой оси 57 (19 * 3 = 57). После выполнения 31 раз команды «Назад 2» (31 * 2 = 62) он оказался бы на отметке –5 (57 – 62 = –5).

3. Все эти команды можно заменить одной — «Назад 5».

Ответ: команда«Назад 5».

Пример 3. Черепашка является исполнителем для создания графических объектов на рабочем поле. При движении Черепашка оставляет след в виде линии. Черепашка может исполнять следующие команды:

Название команды Параметр Действия исполнителя
вп Число шагов Продвигается в направлении головы на указанное число шагов
нд Число шагов Продвигается в направлении, противоположном направлению головы на указанное число шагов
пр Число градусов Поворачивается направо относительно направления, заданного головой черепашки
лв Число градусов Поворачивается налево относительно направления, заданного головой черепашки

Для записи повторяющихся действий (цикла) используется команда Повтори. В этой команде два параметра: первый задает количество повторений (итераций), а второй — список команд которые должны повторяться (тело цикла); список заключается в квадратные скобки.

Записать для исполнителя Черепашка алгоритмы:

а) построения квадрата со стороной 100;

б) построения правильного шестиугольника со стороной 50.

в) построения изображения цифры 4, если голова Черепашки смотрит на север.

Ответ: а) Повтори 4 [вп 100 пр 90]; б) Повтори 6 [вп 50 пр 360/6]; в) вп 100; повтори [лв 135 вп 50].

Пример 4. Два игрока играют в следующую игру (это вариант восточной игры). Перед ними лежат три кучки камней, в первой из которых 2, во второй — 3, в третьей — 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в одной из кучек, или добавляет по два камня в каждую из них. Выигрывает игрок, после хода которого либо в одной из кучек становится не менее 15 камней, либо общее число камней в трех кучках становится не менее 25. Кто выиграет при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ следует обосновать.

Решение. Удобнее всего составить таблицу возможных ходов обоих игроков. Заметим, что в каждом случае возможны всего четыре варианта хода. В таблице курсивом выделены случаи, которые сразу же приносят поражение игроку, делающему этот ход (например, когда камней в какой-либо кучке становится больше или равно 8, другой игрок непременно выигрывает следующим ходом, удваивая количество камней в этой кучке). Из таблицы видно, что при безошибочной игре обоих игроков первый всегда выиграет, если первым ходом сделает 4, 5, 6. У второго игрока в этом случае все ходы проигрышные.

1-й ход 2-й ход
Начало 1-й игрок 2-й игрок 1-й игрок 2-й игрок
2,3,4 4,3,4 8,3,4 выигрыш
4,6,4 8,6,4 выигрыш
4,12,4 выигрыш
4,6,8 выигрыш
6,8,6 выигрыш
4,3,8 выигрыш
6,5,6 12,5,6 выигрыш
6,10,6 выигрыш
6,5,12 выигрыш
8,7,8 выигрыш
2,6,4 4,6,4 8,6,4 выигрыш
4,12,4 выигрыш
4,6,8 выигрыш
6,8,6 выигрыш
2,12,4 выигрыш
2,6,8 выигрыш
4,8,6 выигрыш
2,3,8 выигрыш
4,5,6 8,5,6 выигрыш
4,10,6 выигрыш
4,5,12 выигрыш
6,7,8 выигрыш

Пример 5. Записано 7 строк, каждая из которых имеет свой номер. В нулевой строке после номера записана цифра 001. Каждая последующая строка содержит два повторения предыдущей строки и добавленной в конец большой буквы латинского алфавита (первая строка — A, вторая строка — B и т. д.). Ниже приведены первые три строкиєтой записи (в скобках указан номер строки):

Какой символ находится в последней строке на 250-м месте (считая слева направо)?

Примечание. Первые семь букв латинского алфавита: A, B, C, D, E, F, G.

Решение. Найдем длину каждой строки. Длина каждой следующей строки в два раза больше длины предыдущей плюс один символ, длина строк составит:

(6) 1272+1=255 символов.

Так как задано 7 строк, а нумерация начинается с нулевой строки, последняя строка имеет номер 6 и содержит 255 символов. Последний символ в строке — F. Предпоследний элемент — E, далее идут символы D, C, B, A, 1 (по правилу формирования строк). Таким образом, 250-й символ — это 1.

Пример 6. Имеется фрагмент алгоритма, записанный на учебном алгоритмическом языке:

n := Длина(а)

b := Извлечь(а, k)

нц для i от 7 до n – 1

с := Извлечь(а, i)

b := Склеить(b, с)

Здесь переменные а, b, с — строкового типа; переменные n, i — целые.

В алгоритме используются следующие функции:

Длина(х) — возвращает количество символов в строке х. Имеет тип «целое».

Извлечь(х, i) — возвращает i-й символ слева в строке х. Имеет строковый тип.

Склеить(х, у) — возвращает строку, в которой находятся все символы строки х, а затем все символы строки у. Имеет строковый тип.

Какое значение примет переменная b после выполнения этого фрагмента алгоритма, если переменная а имела значение «ВОСКРЕСЕНЬЕ»?

Решение. Находим общее число символов в строке а, получим, что n = 11.

Выполняя команду b := Извлечь(а, k) при k = 2, получим, что b примет значение «О«.

В цикле последовательно, начиная с 7-го символа строки а и заканчивая предпоследним (n – 1), извлекаем символ из строки а и присоединяем к строке b.

В результате получим слово «ОСЕНЬ» (символы с номерами 2 + 7 + 8 + 9 + 10).

Ответ: «ОСЕНЬ«

Пример 7. Леонардо из Пизы, известный как Фибоначчи, был первым из великих математиков Европы позднего Средневековья. Числовой ряд, который называется его именем, получился в результате решения задачи о кроликах, которую Фибоначчи изложил в своей «Книге Абака», написанной в 1202 году. Он выглядит так:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.

В этом ряду каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Составить словесный алгоритм и блок-схему проверки принадлежности введенного числа n ряду Фибоначчи.

Решение. Словесный алгоритм:

  1. Ввести число n.
  2. Установить значение первых трех чисел Фибоначчи: 1, 1, 2 (сумма двух предыдущих чисел).
  3. Пока введенное число n больше очередного числа Фибоначчи, взять два последних числа Фибоначчи и получить из них новое число Фибоначчи.
  4. Если число Фибоначчи равно введенному n или было введено число n = 1, значит, что было введено число Фибоначчи, в противном случае — введенное число не является числом Фибоначчи.

Приведенный словесный алгоритм в пункте 1, 2 содержит начальные установки, в пункте 3 — цикл с условием, а пункт 4 — это вывод результата работы алгоритма.

F — текущее число ряда Фибоначчи;

F1 и F2 — два предыдущих числа ряда Фибоначчи для числа F;

n — число, для которого требуется определить, является ли оно числом из ряда Фибоначчи.

Использование основных алгоритмических конструкций: следование, ветвление, цикл

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

Базовая структура СЛЕДОВАНИЕ указывает на то, что управление передается последовательно от одного действия к другому.

Учебный алгоритмический язык Язык блок-схем
действие 1
действие 2

действие n

Использование исключительно этой структуры возможно лишь для достаточно простых задач, ход решения которых не меняется в зависимости от конкретных исходных данных и состоит в последовательном выполнении определенных операций.

В качестве примера рассмотрим решение простой задачи.

Пример. Найти y(x) = x2 + 3x + 5, используя только операции умножения и сложения.

Решение. На рис. приводятся два алгоритма, реализующие решение поставленной задачи.

Порядок вычисления y(x) в первом случае — обычный, а во втором — (x + 3) x + 5. Обе формулы эквивалентны, но в первом случае для вычисления необходимо 2 умножения, 2 сложения и 3 переменных (x, y, z), а во втором используются 1 умножение, 2 сложения и 2 переменные (x, y).

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

Обратите внимание, как в блоке следования используется оператор присваивания.

Операция присваивания — важнейшая операция во всех языках программирования. С помощью присваивания переменные получают новые значения: в левой части инструкции ставится идентификатор величины, а в правой части — выражение, значение которого можно определить.

В операторах присваивания используется либо привычный знак равенства, либо сочетание двоеточия и знака равенства «:=». Поскольку знак присваивания — это не знак равенства, возможны записи вида Х := Х + 1 или А := А – В. Нужно учитывать, что оператор присваивания будет выполняться только в том случае, если значения всех переменных правой части уже определены.

Базовая структура ВЕТВЛЕНИЕ (РАЗВИЛКА) используется в случае, когда выполнение программы может измениться в зависимости от результата проверки условия и пойти двумя разными (альтернативными) путями. Другими словами, условие является некоторым высказыванием (предикатом) и может быть истинным или ложным (принимать значение TRUE или FALSE). Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.

Различают две структуры этого типа — полную и неполную. В случае полной структуры, если условие выполняется (является истинным), вслед за ним выполняется действие 1, иначе — действие 2. В случае неполной структуры, если условие выполняется (является истинным), то вслед за ним выполняется действие 1, иначе ничего не происходит.

Важную роль в операторах ветвления играют содержащиеся в них условия. В простейшем случае условиями служат отношения между величинами. Условия с одним отношением называют простыми условными выражениями, или простыми условиями. В некоторых задачах необходимы более сложные условия, состоящие из нескольких простых, например условие А C) (возможна запись (Х C)). Объединение нескольких простых условий в одно образует составное условное выражение, или составное условие. Составные условия образуются с помощью логических операторов not (отрицание), and (логическое И), or (логическое ИЛИ), хоr (исключающее ИЛИ).

Структура ВЕТВЛЕНИЕ существует в четырех основных вариантах:

если — то (неполная структура);

если — то — иначе (полная структура);

выбор (неполный);

выбор — иначе (полный).

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *