Основы программирования (947332), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

1.6. Процесс выполнения программы (а) и ееотладки с помощью отладчика (б)22Часть I. Основы алгоритмизации и процедурное программированиеНа этом этапе, используя проектную документацию, в программныйпродукт вносят необходимые изменения, которые могут потребовать пере­смотра проектных решений, принятых на предшествующих этапах.1.6. Практикум. Разработка алгоритмовметодом пошаговой детализацииСоздание программы - процесс сложный, поэтому практически с любо­го этапа возможен возврат на предыдущие этапы для исправления ошибокили принятия других проектных решений. Чаще всего такого рода возвратыявляются следствием ошибок, допущенных при логическом проектированиипрограммы. Поэтому в процессе программирования необходимо особое вни­мание уделять разработке алгоритмов.Для разработки алгоритмов программ часто используют метод пошаго­вой детал^1зации [4, 9]. С использованием данного метода разработку алго­ритмов выполняют поэтапно.

На первом этапе описывают решение постав­ленной задачи, выделяя подзадачи и считая их решенными. На следующем аналогично описывают решение подзадач, формулируя уже подзадачи следу­ющего уровня. Процесс продолжают до тех пор, пока не дойдут до подзадач,алгоритмы решения которых очевидны. При этом, описывая решение каждойзадачи, желательно использовать не более одной-двух конструкций, такихкак цикл или ветвление, чтобы четче представлять структуру программы.Пример 1.3, Разработать программу, которая с заданной точностью 8 на­ходит значение аргумента х по заданному значению функции у при изве­стном значении п(х+1)п-1у=-где п>1, х> 0.При п >1 данная функция является монотонно возрастающей.

Для на­хождения значения х можно применить метод половинного деления. Сутьданного метода заключается в следующем. Вначале определяют отрезок[xj, Х2] такой, что f(X]) < у < f(x2). Затем делят его пополам х^ = (Х]+Х2)/2 иопределяют, в какой половине отрезка находится х, для чего сравнивают Г(х^)и у. Полученный отрезок опять делят пополам и так до тех пор, пока раз­ность Xj и Х2 не станет меньше заданного значения е.Для разработки алгоритма программы используем метод пошаговой де­тализации.24/. Этапы создания программного обеспеченияШаг L Определяем общую структуру программы.Программа:Ввести у, п, eps.Определить х.Вывести X, у.Конец.Шаг 2. Детализируем операцию определения х.Определить х:Определить х1 такое, что f(xl) < у.Определить х2 такое, что f(x2) > у.Определить х на интервале [х1, х2].Все.Шаг 3, Детализируем операцию определения х1. Значение х1 должнобыть подобрано так, чтобы выполнялось условие f(xl) < у.

Известно, чтоX > О, следовательно, можно взять некоторое значение х, например, х1=1, ипоследовательно уменьшая его, например в два раза, определить значениех1, удовлетворяющее данному условию.Определить х1:х1:=1цикл-пока f(xl) > ух1:=х1/2все-циклВсе.Щаг 4, Детализируем операцию определения х2. Значение х2 определя­ем аналогично х1, но исходное значение будем увеличивать в два раза.Определить х2:х2:=1цикл-пока f(x2) < ух2:=х2*2все-циклВсе.Шаг 5, Детализируем операцию определения х. Определение х выпол­няется последовательным сокращением отрезка [х1, х2].Определить х:цикл-пока x2-xl>epsСократить отрезок [х1, х2].все-циклВсе.25Часть 1.

Основы алгоритмизации и процедурное программированШаг 6, Детализируем операцию сокращения интервала определения х.Сокращение отрезка достигается делением пополам и отбрасыванием поло­вины, не удовлетворяющей условию f(x]) ^ у ^ f(x2)Сократить интервал определения х:xt:=(xl +х2)/2если f(xt) > утох2 := xtиначе х1 :=xtвсе-еслиВсе.Таким образом, за щесть шагов мы разработали весь алгоритм, которыйвыглядит следующим образом.Программа:Ввести у, п, eps.х1:=1цикл-пока f(xl) > ух1:=х1/2все-циклх2:=1цикл-пока f(x2) < ух2 := х2/2все-циклцикл-пока х2-х1 > epsxt:=(xl +х2)/2если f(xt) > утох2 := xtиначе х1 := xtвсе-есливсе-циклВывести xt, у.Конец.Таким образом, на каждом шаге решается одна достаточно простая за­дача, что существенно облегчает разработку алгоритма и является основнымдостоинством метода пошаговой детализации.При разработке алгоритма методом пошаговой детализации мы исполь­зовали псевдокод, но можно было использовать и схемы алгоритма, вкоторых решение каждой подзадачи обозначено блоком «предопределенныйпроцесс».26/.

Этапы создания программного обеспеченияЗадания для самопроверкиЗадание 1. Разработайте алгоритм программы, определяющей первые 10 чиселпоследовательности Фибоначчи, которая формируется следующим образом:Fi = р 2 = l , F n = Fn.i +Fn.2»где п > 2. Алгоритм представьте в виде схемы и запишите псевдокодом.Задание 2. Разработайте алгоритм программы, которая определяет квадратныйкорень из числа А с точностью до целой части, учитывая, что сумма первых п нечет­ных натуральных чисел равна п^:1 = 12I + 3 = 4 = 2214-3 + 5 = 9 = 321 + 3 + 5 + 7 = 16 = 42 и т.

д.Алгоритм представьте в виде схемы и запишите псевдокодом.2. ПРОСТЕЙШИЕ КОНСТРУКЦИИ ЯЗЫКАк простейшим конструкциям языка относятся способы представления скалярныхданных, конструкции выражений, оператор присваивания и операторы ввода-вывода, безкоторых не обходится ни одна программа. Однако прежде чем рассматривать эти конст­рукции, выясним, что собой представляет язык программирования и каким образомвыполняется его описание.2.1. Синтаксис и семантика языка программированияЛюбой язык, в том числе и язык программирования, подчиняется рядуправил. Их принято разделять на правила, определяющие синтаксис языка, иправила, определяющие его семантику.Синтаксис языка - совокупность правил, определяющих допустимыеконструкции (слова, предложения) языка, его форму.Семантика языка - совокупность правил, определяющих смысл синтак­сически корректных конструкций языка, его содерэюание.Языки программирования относятся к группе формальных языков, длякоторых в отличие от естественных языков однозначно определены синтак­сис и семантика.

Описание синтаксиса языка включает определение алфави­та и правил построения различных конструкций языка из символов алфави­та и более простых конструкций. Для этого обычно используют форму Бэкуса-Наура (БНФ) или синтаксические диаграммы. Описание конструкции вБНФ состоит из символов алфавита языка, названий более простых конст­рукций и двух специальных знаков:«::=» - читается как «может быть заменено на»,«I» - читается как «или».При этом символы алфавита языка, которые часто называют терминаль­ными символами или терминалами, записывают в неизменном виде. Назва­ния конструкций языка (нетерминальные символы или нетерминалы), определяемых через некоторые другие символы, при записи заключают в угловыескобки («< », « >»).Например, правила построения конструкции <Целое>, записанные вБНФ, могут выглядеть следующим образом:282.

Простейшие конструкции языка<Целое> ::= <3нак> <Целое без знака> | <Целое без знака><Целое без знака> ::= <Целое без знака> <Цифра> | <Цифра><Цифра> ::= О I 1 I 2 I 3 I 4 I 5 I 6 I 7 I 8 I 9<3нак> ::= + | Для отображения того, что конструкция <Целое без знака> может вклю­чать неограниченное количество цифр, использовано правило с левосторон­ней рекурсией. Многократное применение этого правила позволяет постро­ить целое число с любым количеством цифр.Синтаксические диаграммы отображают правила построения конструк­ций в более наглядной форме.

На такой диаграмме символы алфавита изоб­ражают блоками в овальных рамках, названия конструкций - в прямоуголь­ных, а правила построения конструкций - в виде линий со стрелками на кон­цах. При этом, если линия входит в блок, то в описываемую конструкциюдолжен входить соответствующий символ. Разветвление линии означает, чтопри построении конструкции возможны варианты.На рис. 2.1 представлена синтаксическая диаграмма, иллюстрирующаяпервые два правила описания конструкции <Целое>. Из диаграммы видно,что целое число может быть записано со знаком или без и включать произ­вольное количество цифр.Для описания синтаксических конструкций своего языка Н.

Вирт ис­пользовал именно синтаксические диаграммы, поэтому в тех случаях, когдасловесное описание синтаксиса конструкции длинно и нечетко, мы будем ис­пользовать синтаксические диаграммы.Алфавит языка программирования Borland Pas<cal 7.0 включает:• строчные, прописные буквы латинского алфавита (a..z, A..Z) и знакподчеркивания ( _ ), который также во многих случаях считается буквой;кроме того, существенно то, что строчные и прописные буквы не различают­ся: а неотличимо отА^Ь-отВ и т. д.;• цифры (0...9);• специальные знаки, состоящие из одного и двух символов:+ - * / = : << >> [ ]{ } ( ) ^ @ $ # о<= >= := (* *);• служебные слова (эти сочета­ния считаются единым целым и ихнельзя использовать в программе вдругом качестве):Цифра^"^иякЗнакWРис.

2.1. Синтаксическая диаграммаконструкции <Целое>29Часть 1. Основы алгоритмизации и процедурное программированиеabsoluteendforinlineinterfaceinterruptlabelforwardfidnctiongotomodnilnotifandexternalarraybegincaseconstfiledivdodowntoelsetypeunituntiluseswhilewithofsetshlshrimplementationorinprivatestringthenБукваБукваtoprocedureprogrampublicrecordrepeatvarxorПримечание.

Обратите внимание, что рус­ские буквы в конструкциях языка использоватьнельзя. Они допускаются только при определениистроковых и символьных данных.ЦифраИз символов алфавита в соответст­вии с правилами синтаксиса строят раз­личные конструкции. Простейшей из нихРис. 2.2. Синтаксическаяявляется конструкция <Идентификатор>.диафамма <Идентификатор>Эта конструкция используется во многихболее сложных конструкциях для обозначения имен программных объектов(полей данных, процедур, функций и т.

Характеристики

Список файлов книги