Метод пошаговой детализации алгоритмов

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

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

Достоинства метода пошаговой детализации:

1. Сохраняется концептуальная целостность программы: от сложного к простому.

2. Проектирование программы, кодирование, проверку и документирование можно делать параллельно.

3. В каждый момент времени (даже в начале разработки) имеется работающий вариант

программы.

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

путеводителем по программе.

 

2) Логические величины. Таблица истинности.

Логические величины: понятия, выражаемые словами: ИСТИНА, ЛОЖЬ.Следовательно, истинность высказываний выражается через логические величины

. Логическая переменная - это простое высказывание, содержащее только одну мысль. Ее символическое обозначание - латинская буква (например, A, B,C,F). Значением логической переменной могут быть только констансты ИСТИНА (1) и ЛОЖЬ (0).

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

Логические операции - логические действие.

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

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

Логическое отрицание (соответсвует частица "НЕ") - логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное – истинным.

Таблица истинности - это такая таблица, в которой показываются все выходные состояния элемента для любых комбинации входных сигналов. Иными словами, с помощью таблиц истинности можно определять истинностное значение любого высказывания для всех возможных случаев значений истинности составляющих его высказываний. Общее количество всех возможных комбинаций в таблице можно определить по формуле N=2n; где N - общее число возможных комбинаций, n - количество входных переменных. В основном таблицы истинности применяются в булевой алгебре и в цифровой электронной технике для описания работы логических схем.

 

3) Оператор цикла с предусловием, примеры.

Циклы с предусловием используются тогда, когда выполнение цикла связано с некоторым логическим условием. Оператор цикла с предусловием имеет две части: условие выполнения цикла и тело цикла.

При выполнении оператора while определенная группа операторов выполняется до тех пор, пока определенное в операторе while булево условие истинно. Если условие сразу ложно, то оператор не выполнится ни разу.

Общая форма записи следующая

while <булево выражение> do begin группа операторов end;

На русском языке это звучит примерно так:

пока выполняется это условие, делай
от начала
группа операторов
до конца;

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

При использовании цикла с предусловием надо помнить следующее:

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

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

 

Билет №9

1)Языки программирования: история, концепции и стили программирования, преодоление семантического разрыва.

Язык программирования — это способ записи программ решения различных задач на ЭВМ в понятной для компьютера форме. Процессор компьютера непосредственно понимает язык машинных команд (ЯМК). Программы на ЯМК программисты писали лишь для самых первых ламповых машин — ЭВМ первого поколения. В 1950-х гг. появляются первые средства автоматизации программирования — языки Автокоды. Переменные величины стали изображаться символическими именами. Числовые коды операций заменились на мнемонические (словесные) обозначения, которые легче запомнить. Чтобы компьютер мог исполнять программы на Автокоде, потребовался специальный переводчик — транслятор. Языки программирования высокого уровня (ЯПВУ) являются машинно-независимыми языками. Одна и та же программа на таком языке может быть выполнена на ЭВМ разных типов, оснащенных соответствующим транслятором. Форма записи программ на ЯПВУ по сравнению с Автокодом еще ближе к традиционной математической форме, к естественному языку. Первыми популярными языками высокого уровня, появившимися в 1950-х гг., были Фортран, Кобол (в США) и Алгол (в Европе). Языки Фортран и Алгол были ориентированы на научно-технические расчеты математического характера. Кобол — язык для программирования экономических задач. . В 1965 г. в Дартмутском университете был разработан язык Бейсик. По замыслу авторов это простой язык, легко изучаемый, предназначенный для программирования несложных расчетных задач. В эпоху ЭВМ третьего поколения получил большое распространение язык PL/1 {Program Language One), разработанный фирмой IBM. Значительным событием в истории языков программирования стало создание в 1971 г. языка Паскаль. Фирма Borland International, Inc (США) разработала систему программирования Турбо Паскаль для ПК. Паскаль вышел за рамки учебного предназначения и стал языком профессионального программирования. Язык программирования Си (английское название — С) создавался как инструментальный язык для разработки операционных систем, трансляторов, баз данных и других системных и прикладных программ. Дальнейшее развитие Си привело к созданию языка объектно-ориентированного программирования Си++. Модула-2 — это еще один язык, предложенный Н.Виртом, основанный на языке Паскаль и содержащий средства для создания больших программ. ЛИСП появился в 1965 г. Язык ЛИСП основан на понятии рекурсивно определенных функций, с его помощью на ЭВМ можно моделировать достаточно сложные процессы, в частности интеллектуальную деятельность людей. Язык Пролог разработан во Франции в 1972 г. также для решения проблемы «искусственного интеллекта». Пролог позволяет в формальном виде описывать различные утверждения, логику рассуждений и заставляет ЭВМ давать ответы на заданные вопросы. Реализовать тот или иной язык программирования на ЭВМ — это значит создать транслятор с этого языка для данной ЭВМ. Существуют два принципиально различных метода трансляции. Они называются соответственно компиляция и интерпретация. При компиляции в память ЭВМ загружается программа-компилятор. Она воспринимает текст программы на ЯПВУ как исходную информацию. После завершения компиляции получается программа на языке машинных команд. Затем в памяти остается только программа на ЯМК, которая выполняется, и получаются требуемые результаты. Интерпретатор в течение всего времени работы программы находится во внутренней памяти. В ОЗУ помещается и программа на ЯПВУ. Интерпретатор в последовательности выполнения алгоритма «читает» очередной оператор программы, переводит его в команды и тут же выполняет эти команды. Затем переходит к переводу и выполнению следующего оператора. При этом результаты предыдущих переводов в памяти не сохраняются. При компиляции исполнение программы разбивается на два этапа: трансляцию и выполнение. При интерпретации, поскольку трансляция и выполнение совмещены, программа на ЭВМ проходит в один этап. Однако откомпилированная программа выполняется быстрее, чем интерпретируемая.

Всякий язык программирования имеет три основные составляющие: алфавит, синтаксис и семантику.

Для описания синтаксиса языка программирования тоже нужен какой-то язык. В этом случае речь идет о метаязыке («надъязыке»), Наиболее распространенными метаязыками в литературе по программированию являются металингвистические формулы Бекуса— Наура (язык БНФ) и синтаксические диаграммы. В БНФ всякое синтаксическое понятие описывается в виде формулы, состоящей из правой и левой части, соединенных знаком ::=, смысл которого эквивалентен словам «по определению есть». Слева от знака ::= записывается имя определяемого понятия (метапеременная), которое заключается в угловые скобки < >, а в правой части записывается формула или диаграмма, определяющая все множество значений, которые может принимать метапеременная. Синтаксис языка описывается путем последовательного усложнения понятий: сначала определяются простейшие (базовые), затем все более сложные, включающие в себя предыдущие понятия в качестве составляющих. Определение, в котором некоторое понятие определяется само через себя, называется рекурсивным. Рекурсивные определения характерны для БНФ.

 

2) Оператор цикла с параметром, примеры.

Формат оператора цикла с параметром: for (выражение_1; выражение_2; выражение_3) оператор; Выражение 1 выполняется только один раз в начале цикла. Обычно оно определяет начальное значение параметра цикла (инициализирует параметр цикла). Выражение 2 — это условие выполнения цикла. Выражение 3 обычно определяет изменение параметра цикла, оператор — тело цикла, которое может быть простым или составным. В последнем случае используются фигурные скобки. Алгоритм выполнения цикла for представлен на блок-схеме на рис. 44.

После вычисления выражения 3 происходит возврат к вычислению выражения 2 — проверке условия повторения цикла.

Пример. Инициализирующая часть вынесена из оператора for:

F=l;

i=l;

for(;i<=N;i++) F=F*i

 

Оператор continue. Если выполнение очередного шага цикла требуется завершить до того, как будет достигнут конец тела цикла, используется оператор continue. Следующий фрагмент программы обеспечивает вывод на экран всех четных чисел в диапазоне от 1 до 100.

Пример:

for(i=l;i<=100;i++)

{if(i%2) continue; cout«"\t"«i;}

Оператор goto. Одна из ситуаций, в которых использование goto является оправданным — это необходимость «досрочного» выхода из вложенного цикла. Вот пример такой ситуации:

for(...)

{ while (...)

{ for(...)

{... goto exit ...}

}

}

exit: cout«"Bbixofl из цикла";

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

 

3) Синтаксис основных операторов Pascal: оператор присваивания. Правила использования. Ввод / вывод информации. Форматы вывода.

Арифметический оператор присваивания имеет структуру, представленную на рис. 17.

 

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

 

 

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

Read(<список ввода>)

где <список ввода> — это последовательность имен переменных, разделенных запятыми. Если в программе имеется несколько операторов Read, то данные для них вводятся потоком, т.е. после считывания значений переменных для одного оператора Read данные для следующего оператора читаются из той же строки на экране, что и для предыдущего до окончания строки, затем происходит переход на следующую строку.

Другой вариант оператора ввода с клавиатуры имеет вид:

ReadLn(<список ввода>)

Здесь слово ReadLn означает read line — читать строку. Этот оператор отличается от Read только тем, что после считывания последнего в списке значения для одного оператора ReadLn данные для следующего оператора будут считываться с начала новой строки.

Оператор вывода на экран (обращение к стандартной процедуре вывода) имеет следующий формат:

Write(<список вывода>)

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

Второй вариант процедуры вывода на экран:

WriteLn(<список вывода>)

Слово WriteLn — write line — означает писать строку. Его действие отличается от оператора Write тем, что после вывода последнего в списке значения происходит перевод курсора к началу следующей строки. Оператор WriteLn, записанный без параметров, вызывает перевод строки.

В списке вывода могут присутствовать указатели форматов вывода (форматы). Формат определяет представление выводимого значения на экране. Он отделяется от соответствующего ему элемента двоеточием. Если указатель формата отсутствует, то машина выводит значение по определенному правилу, предусмотренному по умолчанию.

Билет №10

1) Языки программирования. Классификация языков программирования. Понятие уровня языка программирования. Системы программирования.

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

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

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

С точки зрения принципов программирования языки программирования можно разбить на 3 группы:

Процедурные языки программирования

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

Логические языки программирования

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

Функциональные языки программирования

Функциональное программирование основывается на использование списков и функций. Переменные могут отсутствовать вообще.

Примером процедурного языка является язык программирования Паскаль. Язык Пролог является логическим языком программирования, а язык Лисп есть функциональный язык программирования.

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

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

По этому критерию можно выделить следующие уровни языков программирования:

· машинные;

· машинно-оpиентиpованные (ассемблеpы);

· машинно-независимые (языки высокого уровня).

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

Языки высокого уровня делятся на:

· процедурные (алгоритмические) (Basic, Pascal, C и др.), которые предназначены для однозначного описания алгоритмов; для решения задачи процедурные языки требуют в той или иной форме явно записать процедуру ее решения;

· логические (Prolog, Lisp и др.), которые ориентированы не на разработку алгоритма решения задачи, а на систематическое и формализованное описание задачи с тем, чтобы решение следовало из составленного описания;

· объектно-ориентированные (ObjectPascal, C++, Java и др.), в основе которых лежит понятие объекта, сочетающего в себе данные и действия над нами. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути описывает часть мира, относящуюся к этой задаче. Описание действительности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур.

Система программирования — это система для разработки новых программ на конкретном языке программирования.

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

· компилятор или интерпретатор;

· интегрированная среда разработки;

· средства создания и редактирования текстов программ;

· обширные библиотеки стандартных программ и функций;

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

· "дружественная" к пользователю диалоговая среда;

· многооконный режим работы;

· мощные графические библиотеки; утилиты для работы с библиотеками

· встроенный ассемблер;

· встроенная справочная служба;

· другие специфические особенности.

Популярные системы программирования — TurboBasic, QuickBasic, TurboPascal, Turbo C.

2) Оператор выбора, примеры.

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

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

Например, оператор выбора

case X of
'=' : K:=0
|'*', ' + ' : K:=1
|'-' : K:=2
else K:=3
end

равносиленоператору

if X = ' = ' then K := 0
elsif (X = '*') or (X = '+') then K := 1
elsif X = '-' then K := 2
else K:=3
end.

Используя оператор выбора, можно построить следующую программу печати названия дня недели по его номеру

module ПечатьДня;
var Номер : integer;
begin
read (Номер);
if (Номер < 1) or (Номер > 7)
then write ('Ошибка в номере!')
else
case Номер of
1: write ('ПОНЕДЕЛЬНИК')
| 2: write ('ВТОРНИК')
| 3: write ('СРЕДА')
| 4: write ('ЧЕТВЕРГ')
| 5: write ('ПЯТНИЦА')
| 6: write ('СУББОТА')
| 7: write ('ВОСКРЕСЕНЬЕ')
end
end ПечатьДня.

Это же вычисление можно осуществить следующим образом:

module ПечатьДня1;
var Номер : integer;
begin
read (Номер);
case Номер of
1: write ('ПОНЕДЕЛЬНИК');
| 2: write ('ВТОРНИК')
| 3: write ('СРЕДА')
| 4: write ('ЧЕТВЕРГ')
| 5: write ('ПЯТНИЦА')
| 6: write ('СУББОТА')
| 7: write ('ВОСКРЕСЕНЬЕ')
else write ('Ошибка в номере!')
end
end ПечатьДня1.

3) Массивы статические и динамические. Работа с массивами.

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

Динамическим называется массив, размер которого может меняться во время исполнения программы. Язык программирования, поддерживающий динамические массивы, должен предоставлять возможность для изменения размера массива. Динамические массивы делают работу с данными более гибкой, так как не требуют предварительного определения хранимых объёмов данных, а позволяют регулировать размер массива в соответствии с реальными потребностями. Обычные (не динамические) массивы называют ещё фиксированными.