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

Обновлено: 07.07.2024

Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.

§ 9. Структурное программирование

Информатика. 11 класса. Босова Л.Л. Оглавление

На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма.

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

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

Фундаментом структурного программирования является теорема о структурировании.

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

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

9.1. Общее представление о структурном программировании

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

Одна из таких технологий — структурное программирование — была разработана ещё в начале 70-х годов прошлого века и связана с именем выдающегося нидерландского ученого Эдсгера Дейкстры (1930-2002).

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

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

1. Любая программа строится из трёх базовых управляющих конструкций: последовательность, ветвление, цикл.
2. В программе базовые управляющие конструкции могут быть вложены друг в друга произвольным образом.
3. Повторяющиеся фрагменты программы можно оформить в виде подпрограмм (процедур и функций). В виде подпрограмм можно оформить логически целостные фрагменты программы, даже если они не повторяются.
4. Все перечисленные конструкции должны иметь один вход и один выход.
5. Разработка программы ведётся пошагово, методом «сверху вниз».

О методе разработки алгоритма «сверху вниз» вы получили представление в курсе информатики основной школы. Напомним его ключевые моменты на примере разработки некоторой программы.

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

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

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

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

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

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

9.2. Вспомогательный алгоритм

Пример 1. Применим метод «сверху вниз» для разработки алгоритма нахождения периметра треугольника, заданного координатами своих вершин.

Пусть ХА, ХВ, YA, YB, ХС, YC — координаты вершин треугольника ABC. Его периметр — сумма длин отрезков АВ, ВС и АС.

Из курса геометрии вам известна формула для вычисления длины отрезка АВ по координатам его концов (рис. 2.11):

Рис. 2.11. Отрезок АВ

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

На рисунке 2.12 представлены:

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

При вызове вспомогательного алгоритма указываются его параметры (входные данные и результаты). Параметрами вспомогательного алгоритма Отрезок являются величины XI, Y1, Х2, Y2, D. Это формальные параметры, они используются при описании алгоритма. При конкретном обращении к вспомогательному алгоритму формальные параметры заменяются фактическими параметрами, т. е. именно теми величинами, для которых будет исполнен вспомогательный алгоритм. Типы, количество и порядок следования формальных и фактических параметров должны совпадать.

Рис. 2.12. Алгоритм вычисления периметра треугольника и вспомогательный алгоритм Отрезок

Команда вызова вспомогательного алгоритма исполняется следующим образом:

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

Каким будет результат работы алгоритма при следующих исходных данных: ХА = 1, ХВ = 2, ХС = 3, YA = 1, YВ = 3, YC = 1.

9.3. Рекурсивные алгоритмы

Алгоритм называется рекурсивным, если на каком-либо шаге он прямо или косвенно обращается сам к себе.

Иначе это можно записать так:

В определении факториала через рекурсию имеется условие n ≤ 1, при достижении которого вызов рекурсии прекращается.

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

Пример 3. Определим функцию S(n), вычисляющую сумму цифр в заданном натуральном числе n:

Самостоятельно определите функцию К(n), которая возвращает количество цифр заданного натурального числа n.

Пример 4. Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

Требуется выяснить, чему равно значение функции F(7). По условию, F(1) = F(2) = 1.

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

Пример 5. Исполнитель Плюс имеет следующую систему команд:

1) прибавь 1;
2) прибавь 2;
3) прибавь 4.

С помощью первой из них исполнитель увеличивает число на экране на 1, с помощью второй — на 2, с помощью третьей — на 4. Программа для исполнителя Плюс — это последовательность команд. Выясним, сколько разных программ, преобразующих число 20 в число 30, можно составить для этого исполнителя.

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

Число, меньшее 20, при заданных начальных условиях и системе команд исполнителя Плюс получить невозможно. Следовательно, при n < 20 К(n) = 0.

Для начального числа 20 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды. Можем записать: К(n) = 1 при n = 20.

Запишем все соотношения, определяющие функцию К(n):

К(n) = 0 при n < 20;

К(n) — 1 при n = 20;

Заполним по этой формуле таблицу для всех значений n от 20 до 30:

Итак, существует 169 различных программ, с помощью которых исполнитель Плюс может преобразовать число 20 в 30.

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

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

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

3. Примером рекурсивной структуры является замечательное стихотворение Р. Бернса «Дом, который построил Джек» в переводе С. Маршака.

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

9.4. Запись вспомогательных алгоритмов на языке Pascal

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

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

Описание процедуры имеет вид:

procedure <имя_процедуры>(<описание параметров-значений>; var: <описание параметров-переменных>);

begin

end;

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

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

Выполните программу на компьютере.

Подумайте, каким образом можно модифицировать программу, чтобы вычислять с её помощью периметр n-угольника. Каким образом при решении этой задачи можно использовать массивы?

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

Описание функции имеет вид:

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

<имя_функции> := <результат>;

Для вызова функции достаточно указать её имя со списком фактических параметров в любом выражении, в условиях (после слов if, while, until) или в операторе write главной программы.

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

Выполните программу на компьютере.

На основе этой программы напишите функцию, вычисляющую площадь треугольника по целочисленным координатам его вершин. Используйте эту функцию для вычисления площади n-угольника.

САМОЕ ГЛАВНОЕ

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

1) любая программа строится из трёх базовых управляющих конструкций: последовательность, ветвление, цикл;
2) в программе базовые управляющие конструкции могут быть вложены друг в друга произвольным образом;
3) повторяющиеся фрагменты программы можно оформить в виде подпрограмм (процедур и функций). В виде подпрограмм можно оформить логически целостные фрагменты программы, даже если они не повторяются;
4) все перечисленные конструкции должны иметь один вход и один выход;
5) разработка программы ведётся пошагово, методом «сверху вниз».

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

Алгоритм называется рекурсивным, если на каком-либо шаге он прямо или косвенно обращается сам к себе.

Вопросы и задания

1. В чём заключается сущность структурного программирования? Какие преимущества обеспечивает эта технология?

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

3. Вспомните, в чём состоит суть метода последовательного построения (уточнения) алгоритма. Как он называется иначе?

4. Опишите основные шаги разработки программы методом «сверху вниз».

5. Дан прямоугольный параллелепипед, длины рёбер которого равны а, b и с.

Требуется определить периметр треугольника, образованного диагоналями его граней. Какой алгоритм целесообразно использовать при решении этой задачи в качестве вспомогательного?

6. Какой вспомогательный алгоритм называется рекурсивным? Что такое граничное условие и каково его назначение в рекурсивном алгоритме?

7. Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

Требуется выяснить, чему равно значение функции F(10).

8. Исполнитель Калькулятор имеет следующую систему команд:

1) прибавь 1;
2) умножь на 2.

С помощью первой из них исполнитель увеличивает число на экране на 2, с помощью второй — в 2 раза.

1) Выясните, сколько разных программ, преобразующих число 1 в число 20, можно составить для этого исполнителя.
2) Сколько среди них таких программ, у которых в качестве промежуточного результата обязательно получается число 15?
3) Сколько среди них таких программ, у которых в качестве промежуточного результата никогда не получается число 12?

9. Попробуйте найти рекурсивные синтаксические структуры:

1) в поэме А. Блока «Двенадцать»;
2) в стихотворении М. Лермонтова «Сон»;
3) в романе М. Булгакова «Мастер и Маргарита»;
4) в фольклоре.

10. Найдите информацию о таких геометрических фракталах, как Снежинка Коха, Т-квадрат, Н-фрактал, кривая Леви, Драконова ломаная.

11. Напишите программу вычисления значения функции F(n), рассмотренной в примере 4 этого параграфа. Вычислите с её помощью значение функции F(7).

12. Напишите программу вычисления

13. Дана программа:

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

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

Дополнительные материалы к главе смотрите в авторской мастерской.

Задан фрагмент алгоритма:1. если a<b, то с=b-a, иначе c=2*(a-b)2. d=03. пока c>a выполнить действия d=d+1, с=с-1В результате выполнения данного алгоритма с начальными значениями a=8, b=3, переменные c и d примут значения c=8, d=2

При выполнении подпрограммы Алг пр1 (аргцел X, резцел F)Начесли X <= 1 то F := 1 иначе F := F (X – 2) – 4 всеконс параметрами (3, А) значение переменной А будет равно– 3

При выполнении подпрограммы Алг пр1 (аргцел X, резцел F)Начесли X <= 1 то F := 1 иначе F := F (X – 2) + 3 всеконс параметрами (3, А) значение переменной А будет равно4

При выполнении подпрограммы Алг пр1 (аргцел X, резцел F)Начесли X <= 1 то F := 2 иначе F := F (X – 2) + 3 всеконс параметрами (2, А) значение переменной А будет равно5

При выполнении подпрограммы Алг пр1 (аргцел X, резцел F)Начесли X < 1 то F := 2 иначе F := F (X – 2) + 3 всеконс параметрами (1, А) значение переменной А будет равно5

При выполнении подпрограммы Алг пр1 (аргцел X, резцел F)Начесли X <= 1 то F := 2 иначе F := F (X – 1) + 3 всеконс параметрами (2, А) значение переменной А будет равно5

Оператор, имеющий формат записи IF < выражение > Then < оператор > Else< операторы >называется ______________ оператором. условным

Оператор, заставляющий выполняться входящие в его состав (так называемые внутренние операторы) называется оператором… цикла

Элементами оператора ветвления являются…а) условие б) переход по условию в) интерпретация г) повторение(а, б)

Элементами оператора ветвления являются…а) интерпретация б) повторение в) условие г) переход по условию (в, г)

Понятие о структурном программировании

1. При проектировании программного обеспечения используются подходы: а) «сверху-вниз»б) «снизу-вверх» в) «слева-направо» г) «справа-налево» (а,б)

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

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

Правила композиции, используемые при структурном подходе к составлению алгоритмов: а) альтернативный выбор б) цикл с) подпрограмма д) метки (а,б,с)

Процедура ABCD Процедура ABCD;НАЧАТЬ||писать ('ВВЕДИТЕ ЗНАЧЕНИЕ A, B, C, D');||ЧИТАТЬ (A, B, C, D);||ЕСЛИ A=B ТО

ЕСЛИ C<D ТОX:=1

ИНАЧЕX:=2||ИНАЧЕ X:=3КОНЕЦ реализует алгебраическое выражение вида… Данная блок-схема программы … производит сложение 9 подряд идущих натуральных чисел начиная с введенного и выводит результат Структурное программирование по-другому называют программированием без… GOTO Дан массив целых чисел , где i=1,2,3,…,M. Пусть M равно 15. Программа вычисляет произведение сумм некоторых элементов этого массива. В программе введены следующие константы: G=1; W=12; T=8; L=15.ПРОГРАММА 15; ФУНКЦИЯ SUMMA(I1,I2); НАЧАТЬ ФУНКЦИЮ ||S:=0; ||НЦ ДЛЯ I:=I1 ДО I2 |S:=S + A[I] ||КЦ; ||SUMMA:=S КОНЕЦ ФУНКЦИИ;НАЧАТЬ ПРОГРАММУ||ПИСАТЬ ('ВВЕДИТЕ ЗНАЧЕНИЯ МАССИВА A:' );||НЦ ДЛЯ J:=1 ДО M|ЧИТАТЬ (A[J]);||КЦ;||P:=SUMMA (G, W)*SUMMA(T, L);||ПИСАТЬ ('ПРОИЗВЕДЕНИЕ РАВНО:', P:6)КОНЕЦ ПРОГРАММЫ.Работу программы описывает следующее алгебраическое выражение : Процедура KLMNПРОЦЕДУРА KLMN;НАЧАТЬ ПРОЦЕДУРУ||ПИСАТЬ('ВВЕДИТЕ ЗНАЧЕНИЕ K, L, M, N');||ЧИТАТЬ (K, L, M, N);||ЕСЛИ K=L ТО

ЕСЛИ M<N ТОX:=1

ИНАЧЕX:=2|КОНЕЦ ЕСЛИ||ИНАЧЕ X:=3||КОНЕЦ ЕСЛИКОНЕЦ ПРОЦЕДУРЫ;реализует следующее алгебраическое выражение … Программирование, основанное на модульной структуре программного продукта и типовых управляющих структурах алгоритмов называется… структурным Основной целью структурного программирования является… организация программного обеспечения с минимальными взаимосвязями между его модулями Основой метода структурного программирования являются…а) принцип модульности разработки сложных программ б) использование композиции трех базовых элементов – линейной, ветвления и циклической структур в) использование композиции двух базовых элементов – ветвления и циклической структур д) использование большого количества подпрограмм (а, б) Основой метода структурного программирования являются…а) использование композиции двух базовых элементов – ветвления и циклической структур б) использование большого количества подпрограмм в) принцип модульности разработки сложных программ д) использование композиции трех базовых элементов – линейной, ветвления и циклической структур (в, д)

Объектно-ориентированное программирование

К концепции ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАМИРОВАНИЯ НЕ относится параллелизм

Базовыми понятиями ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАМИРОВАНИЯ являются а) объект б) класс в) структура г) функция(а,б)

Объект связан с классом в терминах ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАМИРОВАНИЯ в следующей нотации класс является описанием объекта

Суть понятия полиморфизм заключается в том, что в зависимости от типа объекта одно и то же имя метода может соответствовать различным действиям

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

объект скрывает в себе детали, несущественные для его использования

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

Объектно-ориентированный подход к программированию использует следующие базовые понятия…а) объект б) свойство в) метод обработки г) событие д) класс объектов е) инструкции ж) данные з) модель (а, б, в, г, д)

В основе объектно-ориентированного подхода к программированию лежит метод… нисходящего проектирования

В основе абстракции объектно-ориентированного подхода лежит понятие… иерархии

Уменьшение объема кода программ связано с использованием ______________ программирования. объектно-ориентированного

Сетевые технологии обработки данных

Сервер сети – это компьютер… предоставляющий доступ к ресурсам

Волоконно-оптические линии связи используются в следующих сетях. FDDI

Линией связи с минимальной задержкой является. волоконно-оптическая линия связи

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

Усредненная геометрическая схема соединений узлов сети, называется ______________ сетитопологией

Сетевым протоколом является. набор правил

Сеть Internet базируется на протоколах. TCP/IP

Протокол FTP предназначен для. передачи файлов

Сетевые стандарты

Протокол POP3 работает на _________ уровне. прикладном

На сетевом уровне. определяется адресация в системе передачи данных

К понятиям физического уровня относится. v.24

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

Не инкапсулируется пакет __________ уровня: канального

Разработчиками стандартов для локальных вычислительных сетей является. IEEE 802

Стандартом верхнего уровня и администрирования является. 802.1

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

Стандарт - маркерная шина, это. 802.4

Внутреннее представление информации

Дискретно

Сигнал называется дискретным, если он

Может принимать лишь конечное число значений в конечное число моментов времени

3. Выберите наиболее точное продолжение фразы. Информатика – это наука, изучающая…

Способы представления, хранения, обработки и передачи информации

4. Процессы получения, хранения и преобразования информации называются…

Информационными процессами

Перекодировкой

Кодировщиком называется

Информация по способу ее восприятия человеком подразделяется на

- Учитель,- проговорил Сунь У-кун.- Я человек простой и вашего городского языка не понимаю. Что значат подпорки к стене?

- Когда люди начинают строить дом и хотят сделать его прочным и крепким, то между стенами они ставят подпорки. Но проходит время, и здание рушится, а это значит, что подпорки сгнили.

У Чэн-энь. "Путешествие на Запад", глава 2

Общая характеристика структурного программирования

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

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

Начнем с того, что обратимся к истории.

В теории схем программ было замечено, что некоторые случаи блок-схем легче поддаются анализу [ 16 ] . Поэтому естественно было выделить такой класс блок-схем, что и сделали итальянские ученые С. Бем и К. Джакопини в 1966 г. Они доказали, что любую блок-схему можно привести к структурированному виду, использовав несколько дополнительных булевых переменных. Э. Дейкстра подчеркнул, что программы в таком виде, как правило, являются легче понимаемыми и модифицируемыми, так как каждый блок имеет один вход и один выход .

В качестве методики структурного программирования Э. Дейкстра предложил пользоваться лишь конструкциями цикла и условного оператора, изгоняя go to как концептуально противоречащее этому стилю

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

К несчастью, оператор go to формально совместим с другими конструкциями традиционных (тогда говорили - универсальных) алгоритмических языков. Но реально он плохо взаимодействует с ними. Значит, он плох сам по себе.

Структурное программирование основано главным образом на теоретическом аппарате теории рекурсивных функций. Программа рассматривается как частично-рекурсивный оператор [ 21 ] над библиотечными подпрограммами и исходными операциями. Структурное программирование базируется также на теории доказательств, прежде всего на естественном выводе. Структура программы соответствует структуре простейшего математического рассуждения, не использующего сложных лемм и абстрактных понятий 2 На самом деле традиционным вычислительным программам соответствует не классическая, а интуиционистская логика, но структура доказательств и большинство правил вывода в них совпадают. .

Средства структурного программирования в первую очередь включаются во все языки программирования традиционного типа и во многие нетрадиционные языки. Они занимают основное место в учебных курсах программирования и в теоретических работах (например, [ 1 ] , [ 4 ] , [ 9 ] ).

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

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

действия и условия локальны.

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

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

Для структурного стиля программирования требуется следующее. Задача разбивается на подзадачи, и таким образом выстраивается дерево вложенности подзадач. Информационное пространство структурируется в точном соответствии с деревом вложенности: для каждой подзадачи оно состоит из ее локальных объектов, определяемых вместе с подзадачей и для нее, и так называемых глобальных объектов, определяемых как информационное пространство непосредственно объемлющей подзадачи. Таким образом, информационное пространство всей задачи (подзадачи самого верхнего уровня) расширяется по мере перехода к подзадачам за счет их локальных объектов. Для различных дочерних подзадач одной подзадачи оно имеет общую часть - информационное пространство родительской подзадачи 3 В этой системе требований без труда распознается так называемая блочная структура языков программирования, появившаяся еще в Algol 60 и ставшая в настоящее время фактическим стандартом. .

К структурным операторам добавляются либо циклы , либо рекурсии .

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

Призраки. Часто даже сама программа не может быть объяснена через понятия, которые используются внутри нее. Еще чаще это происходит для ее связей с внешним миром. Понимание программы возможно лишь после сопоставления реальных внутрипрограммных объектов с идеальными внепрограммными. Эти идеальные внепрограммные объекты ( призраки ) часто не просто не нужны, но даже вредны для исполнения программы 4 Кстати, программистам стоит почаще вспоминать, что, с точки зрения пользователя или заказчика, их внутрипрограммные объекты как раз являются такими же призраками , которые не имеют никакого отношения к реальной действительности. Так что при переходе от уровня рассмотрения программы самой по себе к уровню программы как части архитектуры реальной человеко-машинной системы идеальные и реальные объекты порою меняются местами. .

Первым обратил внимание на необходимость введения призраков для логического и концептуального анализа программ Г. С. Цейтин в 1971 г. В Америке это "независимо" открыли заново в 1979 г., хотя упомянутая статья Цейтина была опубликована на английском языке в общедоступном издании. Даже название сущностям было дано то же самое. Этому важнейшему и традиционно игнорируемому понятию посвящена отдельная лекция в курсе "Основания программирования" [ 21 ] .

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

Для структурного программирования весьма важно требование:

Все структуры подчиняются структуре информационного пространства.

Это общее требование конкретизируется в следующие.

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

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

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

(1)Способ записи программ, допускающий их непосредственное выполнение на ЭВМ. называется

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

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

●машинным языком программирования

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

(1)На этапе отладки программы

строится математическая модель решаемой задачи

определяется состав входных данных

выполняется анализ физических характеристик

●проверяется корректность работы программы

(1)Типы входных и выходных данных определяются на этапе.

тестирования и отладки

(1)Если задан тип данных, то известной является информация о

●диапазоне возможных значений

количестве обращений к данным

(1)Какая информация известна, если задан тип данных?

●диапазон возможных значений

количество обращений к данным

количество записей данных

(1)Вид хранимой информации определяет.

связи между данными

вложенность структур данных

●тип соответствующего поля данных

устойчивость структур данных

(1)Целочисленный тип является типом данных

(1)Понятием «переменная» в традиционных языках программирования называется…

любое законченное минимальное смысловое выражение на языке программирования

●именованная область памяти, в которой хранится некоторое значение

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

служебное слово на языке программирования

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

тестированием «черного ящика»

определением белого шума

тестированием «белого ящика»

(1)Тестирование, при котором разработчик теста имеет доступ к исходному коду программы, называется .

тестированием «черного ящика»

определением белого шума

тестированием «белого ящика»

(1)Тестирование, при котором выявляется, что сделанные изменения не повлияли на функциональность предыдущей версии, называется …

тестированием «черного ящика»

тестированием «белого ящика»

(1)Пошаговая детализация постановки задачи, начиная с наиболее общей проблемы, характеризует

метод проектирования «от частного к общему»

●метод последовательной декомпозиции сверху-вниз

поиск логической взаимосвязи

(1)Основной целью структурного программирования является.

●организация программного обеспечения с минимальными взаимосвязями между его модулями

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

решение задач, для которых нет явного алгоритма решения

исключение использования подпрограмм

(1)Основой метода структурного программирования являются.

а) использование композиции двух базовых элементов - ветвления и циклической структур

б) использование большого количества подпрограмм

в) принцип модульности разработки сложных программ

д) использование композиции трех базовых элементов -линейной, ветвления и циклической структур

(1)Модульная структура программы отражает одну из особенностей ___________программирования

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

(1)Правила композиции, используемые при структурном подходе к составлению алгоритмов:

а) альтернативный выбор

(1)Структурное программирование по-другому называют программированием без.

(1)Укажите структуры, которые не допускается использовать в программе при структурном программировании

Последовательное выполнение двух и более операций

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

(1)Уменьшение объема кода программ связано с использованием программирования.

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

(1)В основе объектно-ориентированного подхода к программированию лежит метод…

ветвей и границ

(1)К концепции объектно-ориентированного программирования НЕ относится

(1)Понятие «Наследование» характеризует

сокрытие информации и комбинирование данных и методов внутри объекта

●способность объекта сохранять свойства и методы класса-родителя

возможность задания различных действий в методе с одним именем

(1)В основе абстракции объектно-ориентированного подхода лежит понятие.

(1)Понятие «иерархия классов» присуще методологии _____________ программирования

(1)Объектно-ориентированный подход к программированию использует следующие базовые понятия.

е) метод обработки

з) класс объектов

(1)Объектно-ориентированный подход к программированию использует следующие базовые понятия.

е) метод обработки

з) класс объектов

(1)Базовыми понятиями объектно-ориентированного программирования являются

(1)Объект связан с классом в терминах объектно-ориентированного программирования в следующей нотации

объект не является наследником класса

объект и класс связаны через общие функции

совокупность классов образует объект

●класс является описанием объекта

(1)Объект связан с классом в терминах объектно-ориентированного программирования в следующей нотации

совокупность классов образует объект

●класс является описанием объекта

объект и класс не связанные понятия

объект не является наследником класса

(1)Объектно-ориентированными языками являются.

(1)Обьектно-ориентированным языком, в котором имеется возможность множественного наследования, является.

(1)Интегрированная система программирования включает компонент для перевода исходного текста программы в машинный код, который называется .

(1)Интегрированная система программирования включает компонент для создания исходного текста программы, который называется .

(1) Рекурсия использует.

удаление подпрограммой самой себя

заражение подпрограммой самой себя

●обращение подпрограммы к самой себе

размножение подпрограммой самой себя

(1)Какая структура данных больше подходит для реализации рекурсии

(1)Какой алгоритм сортировки массива относится к рекурсивным:

сортировка методом пузырька

сортировка простыми вставками

На рис. в виде дерева рекурсии представлен фрагмент алгоритма F(5)

поиска простых чисел

●вычисления чисел Фибоначчи

задачи о ближайших точках

f(xl xn .0) = a(xl xn). f(xl xn.y+1) = h(xl xn ,y, f(xl xn0)) определяет

набор переменных, начинающихся с одной буквы

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

●последовательность фиксированного числа однотипных переменных, имеющих общее имя

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

(1)Массив относится к __________ типам данных

(1)Массив относится к.

●составным (конструируемым) типам

(1)Элементы массива упорядочены.

по возрастанию значений элементов

по частотным характеристикам

●по возрастанию индексов элементов

(1)Верным является высказывание, утверждающее…

элементы массива автоматически упорядочиваются по возрастанию

к элементу массива невозможно получить доступ по номеру

элементы массива могут иметь разные типы

●доступ к элементу массива осуществляется по имени массива и номеру элемента

(1)Задан одномерный массив X1. Х2 XN. Фрагмент алгоритма

количество нулевых элементов

количество положительных элементов

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

номер первого нулевого элемента

(1)Задан массив А[1..4], состоящий из строк А = («2000», «836», «102», «21»). После сортировки по убыванию элементы массива будут расположены в следующем порядке

«836», «21», «2000», «102»

«2000», «836», «102», «21»

«21», «102», «836», «2000»

(1)Задан массив А[1..4], состоящий из строк А = («2000», «836», «102», «21»). После сортировки по возрастанию элементы массива будут расположены в следующем порядке

«2000», «836», «102», «21»

«21», «102», «836», «2000»

«21», «2000», «102», «836»

(1)Если элементы массива D[1..5] равны соответственно 4, 1, 5, 3, 2, то значение выражения

D[ D[4] – D[5] ] равно

(1)Ветвление обязательно должно содержать .

оператор, выполняемый в случае истинности условия и оператор, выполняемый в случае ложности условия

●условие и оператор, выполняемый в случае истинности условия

оператор, выполняемый в случае ложности условия

(1)Элементами оператора ветвления являются.

б) переход по условию

(1)Оператор ветвления на блок схеме отображается в виде