Развилка

1. Задачи на ветвление

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

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

Признаком разветвляющегося алгоритма является наличие операций проверки условия.

Условие – это выражение логического типа. Оно может включать в себя константы, имена переменных, арифметические операции, операции отношения, логические операции, скобки. Условие может быть истинным или ложным, то есть принимать одно из двух значений: ИСТИНА или ЛОЖЬ.

Различают два вида условий: простые и составные.

Простым условием называется выражение, составленное из двух арифметических выражений или двух текстовых величин, связанных одним из знаков: <, , >, ³, =, ¹. Такое условие часто называют операцией отношения.

Составными условиями называются условия, состоящие из нескольких простых и соединенные знаками логических операций И, ИЛИ, НЕ.

ПРИМЕРЫ составных условий.

(A > 5) И (B < 2)

(X = Y) ИЛИ (50 £ C – 1)

НЕ («собака» = «конура») И («кошка» = D)

Составное условие вида «X И Y» истинно тогда и только тогда, когда истинны оба условия X и Y, в остальных случаях – ложно.

Составное условие вида «X ИЛИ Y» истинно тогда, когда истинно хотя бы одно условие X или Y.

Условие вида «НЕ X» истинно, если X ложно, и наоборот.

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

Если выходов два, то они обозначаются ДА и НЕТ. Если условие истинно, то вычислительный процесс «идет» по ветви ДА; если ложно – по ветви НЕТ.

Если выходов три (это чаще всего бывает, когда в условии переменная или выражение сравниваются с нулем), то они обозначаются: > 0, < 0, =0.

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

Пример 1. Вычислить значение функции

1. Ввести x. 2. Если x –12, то y: =–x2 3. Если x< 0, то y: =x4 4. y: = x–2 5. Вывести y 6. Конец

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

Циклы

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

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

Цикл с предусловием (цикл-пока)

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

Блок-схема цикла с предусловием

Цикл с постусловием (цикл-до)

Цикл с постусловием начинается с выполнения тела цикла и лишь затем проверяется условие. Тело цикла обязательно выполнится хотя бы один раз. Если условие ложно, то повторяется выполнение тела цикла, если истинно – то осуществляется выход из цикла. Поэтому данное условие называют условием прекращения цикла. Чтобы не было зацикливания, в теле цикла необходимо изменять значение параметра цикла так, чтобы за конечное количество «шагов» условие стало истинным.

Блок-схема цикла с постусловием

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

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

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

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

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

В начале 50-х годов появился первый язык ассемблера. К концу 50-х годов начали появляться языки программирования более высокого уровня, такие как Lisp, Fortran, ALGOL. В них уже не было точного соответствия между языковыми конструкциями и машинными командами. Преобразование строк исходного кода в последовательности двоичных команд осуществлялось компилятором. Со временем их число пополнилось языками PL /1, Pascal, C, C++, Java. Все они менее эффективно используют аппаратуру по сравнению с языками ассемблера, но позволяет быстрее создавать приложения. В результате им удалось практически полностью вытеснить языки ассемблера при создании крупных приложении.

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

1. неструктурный;

2. структурный;

3. объектно-ориентированный;

4. логический;

5. функциональный.

Неструктурное программирование допускает использование в явном виде команды безусловного перехода (в большинстве языков GOTO). Типичные представители неструктурных языков - ранние версии Бейсика и Фортрана. Данный стиль вызван особенностями выполнения машиной программы в кодах и унаследован от программ на языке ассемблера, поскольку там команда перехода является обязательной. Однако в языках высокого уровня наличие команды перехода влечет за собой массу серьезных недостатков: программа превращается в " спагетти" с бесконечными переходами вверх-вниз, ее очень трудно сопровождать и модифицировать. Фактически неструктурный стиль программирования не позволяет разрабатывать большие проекты. Ранее широко практиковавшееся первоначальное обучение программированию на базе неструктурного языка (обычно Бейсика) приводило к огромным трудностям при переходе на более современные стили.

Структурное программирование – процесс разработки алгоритмов с помощью блок-схем.

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

Структурный стиль был разработан в середине 60-х - начале 70-х гг. В его основе лежат две идеи: задача разбивается на большое число мелких подзадач, каждая из которых решается своей процедурой или функцией (декомпозиция задачи). При этом проектирование программы идет по принципу сверху вниз: сначала определяются необходимые для решения программы модули, их входы и выходы, а затем уже эти модули разрабатываются. Такой подход вместе с локальными именами переменных позволяет разрабатывать проект силами большого числа программистов. Как доказал Э. Дейкстра, любой алгоритм можно реализовать, используя лишь три управляющие конструкции: последовательное выполнение, ветвление и цикл. Данное обстоятельство позволяет при наличии соответствующих операторов исключить из языка команду безусловного перехода GOTO.

Принципы структурного программирования были реализованы в языке Алгол, но наибольшую популярность завоевал язык Паскаль, созданный в 1970 швейцарским ученым Н. Виртом. Паскаль получил широчайшее распространение и может считаться образцовым языком программирования, наиболее популярным и сейчас (например, в версии Delphi фирмы Imprise).

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

БРАТЬЯ ИМЕЮТ ОДНОГО ОТЦА

ДЖОН - ОТЕЦ ДЖЕКА

МАЙК - БРАТ ДЖЕКА

то система логического программирования должна сделать вывод:

ДЖОН - ОТЕЦ МАЙКА.

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