Компонентный Паскаль. Общая структура программы. Операторы цикла.

Компонентный Паскаль Общая структура программы Операторы цикла Программирование – наука основанная на трех понятиях – постановка задачи, алгоритм, программа. Каждое из перечисленных понятий имеет сложную историю образования, различные понимания, например: • постановка задачи – это описание задачи в строгой математической терминологии; • алгоритм – это описание действий, выполняя которые некий ИСПОЛНИТЕЛЬ обязательно получит требуемый результат. Обратите внимание на выделенное слово, именно так, не может получить, а обязательно получит; • программа – это запись алгоритма на строгом, однозначно понимаемом языке. Этот исполнитель должен быть способен выполнить алгоритм. И это не обязательно компьютер. В самом общем случае необходимо говорить об устройстве способном выполнять определенный, жестко заданный набор команд, но поскольку наша цель – программирование компьютера, поэтому далее исполнитель это всегда компьютер. Следовательно, научиться программировать, это значит научиться: • формулировать задачу в строгих математических терминах; • находить решение в виде последовательности действий понятных компьютеру; • записывать эту последовательность на языке программирования. Рассмотрим задачу. Дано множество чисел. Найти сумму положительных. Сформулируем алгоритм: Вариант 1: Для всех чисел из данного множества: если число положительное, то прибавляем его к сумме Это не алгоритм, т.к. по крайней мере неясно каким образом выбирать числа из заданного множества, чтобы не пропустить ни одного и не взять одно и тоже число несколько раз. Пусть, все элементы множества пронумерованы и пусть известно, сколько во множестве элементов, например – N. Тогда проблема решается легко. Исполнитель начинает перебор с элемента, имеющего нулевой номер, а для получения следующего элемента увеличивает текущий номер на 1. Вариант 2: Для Номера изменяющегося от нуля до числа N-1 с шагом 1 выполнять действие Если очередное число больше нуля то прибавлять его к сумме положительных. Т.е. для Номера изменяющегося от нуля до числа N-1 с шагом 1 выполнять действие Здесь описан процесс изменения некоторой переменной величины, которую мы назвали номером. Существенно в этой записи только то что: • переменная имеет имя (и это не обязательно слово Номер); • исходное значение переменной равно нулю; • конечное значение переменной равно N-1; • переменная изменяется с шагом 1; • на каждом шаге изменения переменной выполняется некоторое действие. На КП это будет записано так: FOR k:=0 TO N-1 BY 1 DO IF a[k]>0 THEN sum:=sum+a[k]; END; Или полная запись: sum:=0; FOR k:=0 TO N-1 DO IF a[k]>0 THEN sum:=sum+a[k]; END; END; Ключевое слово END не предусмотрено алгоритмом, оно является требованием языка. Правила языка требуют завершать сложную конструкцию таким ключевым словом. Здесь две сложных конструкции, поэтому два ключевых слова END. Одно из них закрывает условную команду, второе завершает цикл. Очевидно, что запись на строгом языке сокращает текст, делает его чтение общедоступным для большого количества людей, то есть может быть общепринятым стандартом общения для специалистов занимающихся разработкой алгоритмов. Но самое важное в языке программирования то, что он является связующим звеном между естественным языком и языком который в действительности понятен компьютеру. Это дает возможность писать специальные программы – трансляторы способные переводить программы, написанные на алгоритмических языках в тексты уже малопонятные для человека, но исполняемые компьютером. Для компьютера не существует таких понятий, как множество, массив, переменная. Он оперирует регистрами, адресами ячеек памяти и т.д. и т.п. То есть чем то очень далеким даже для того, кто неплохо владеет математическим аппаратом. Поэтому до появления языков – посредников программирование было уделом немногих, ибо требовало слишком больших усилий даже для написания несложных программ. В общем случае весь язык программирования сводится к набору небольшого количества понятий: • • величина (переменная или константа); • • команда присваивания; • • конструкция цикла; • • условная конструкция; • • процедура. Рассмотренный выше цикл с шагом, не единственная форма цикла и даже не самая сильная. Легко придумать задачу для которой цикл с шагом не даст решения. Ясно, что цикл с шагом хорош только тогда, когда программист точно знает сколько раз необходимо выполнить тело цикла. А это вполне может оказаться и не известным. Для примера вот такая задача: Арифметическая прогрессия задана начальным членом a1 и разностью d. Необходимо найти номер члена N такого, что сумма прогрессии включая N-ый превысит некое заданное число W. Это именно та ситуация в которой известно что делать: • вычислять очередной член прогрессии; • находить очередную сумму. И не известно сколько раз это делать.. Общая конструкция решения такова: sum:=a1; k:=1; WHILE sum<=W DO a1:=a1+d; sum:=sum+a1; k:=k+1; END; Данная конструкция называется циклом с условием продолжения. Это означает, что тело цикла (команды записанные между заголовком и ключевым словом END) выполняется до тех пор пока истинно условие записанное после ключевого слова WHILE (Пока). Уловие проверяется на каждом шаге цикла, причем сначала проверяется условие и лишь затем выполняются команды тела цикла. Это например, означает, что тело цикла может быть не выполнено ни разу, если в момент входа в цикл условие окажется ложным. Величина k увеличивается на 1 на каждом проходе тела цикла и фактически равна номеру суммируемого члена прогрессии. Цикл WHILE наиболее универсальная форма цикла, позволяющая смоделировать любой процесс, чего нельзя сказать о FOR (цикле с шагом). Но за эту универсальность надо платить тщательным построением условия продолжения цикла. Ошибка в построении условия может привести к так называемому зависанию, то есть бесконечному выполнению цикла. И вот тому простой пример: Листинг 7 k:=1; WHILE k<5 DO sum:=sum+k; END; В данном фрагменте некая величина k складывается с суммой на каждом шаге цикла, но цикл никогда не завершится, так как начальное значение величины k известно, но в цикле оно никак не изменяется и следовательно всегда будет меньше 5. Правильный фрагмент может выглядеть например так: k:=1; WHILE k<5 DO sum:=sum+k; k:=k+1; END; Как изменяется k конечно определяется задачей, и необязательно оно изменяется с шагом 1. Но внесенное исправление по крайней мере решает проблему зависания. Цикл выполнит несколько шагов и при k=5 прекратит свою деятельность. Цикл WHILE это цикл с условием продолжения. И в КП есть так называемый цикл с условием завершения. То есть конструкция, в которой сначала выполняется тело цикла и лишь затем проверяется условие. sum:=a1; k:=1; REPEAT a1:=a1+d; sum:=sum+a1; k:=k+1; UNTIL sum>W; Здесь просто переписаны уже известные вычисления в новой форме. Давайте проанализируем, как это работает и нет ли проблем. Работает цикл так: На каждом шаге выполняется тело цикла и лишь затем проверяется условие. Следовательно, тело цикла будет выполнено хотя бы один раз. Цикл завершает свою работу при истинном условии. Отметьте существенное различие от цикла с условием продолжения. WHILE выполняет свою работу пока условие истинно, а REPEAT UNTIL до тех пор пока условие не станет истинным. Поэтому и появилось различие в записи условия. Еще одно отличие формы записи в том, что цикл с условием завершения не нуждается в ключевом слове END. Его тело, это все команды находящиеся между ключевыми словами REPEAT и UNTIL. Есть в записи цикла REPEAT и небольшая содержательная проблема. Заметим, что и как в случае условия продолжения сумма инициализируется первым членом прогрессии, плюс к тому цикл REPEAT гарантированно посчитает еще один член прогрессии, то есть второй. Следовательно, если уже первый член прогрессии окажется больше чем W программа ошибется и завершит работу при k=2, при правильном ответе k=1. Таким образом форма цикла REPEAT существенно меняет логику и правильный вариант программы будет таков: sum:=0; k:=0; REPEAT sum:=sum+a1; a1:=a1+d; k:=k+1; UNTIL sum>W; Циклы с условием завершения и условием продолжения взаимозаменяемы и оба они годны для замены цикла с шагом. Продемонстрируем эту взаимозаменяемость примером. Вычислить факториал числа N. Форма цикла с шагом: Листинг 11 fact:=1; FOR k:=2 TO N DO fact:=fact*k; END; Форма цикла с условием продолжения: fact:=1; k:=2; WHILE k<=N DO fact:=fact*k; k:=k+1; END; Форма цикла с условием завершения: fact:=1; k:=2; REPEAT fact:=fact*k; k:=k+1; UNTIL k>N; Все написанные ранее примеры обладают одним существенным недостатком, они не являются полноценными программами, которые можно запустить и получить требуемый результат. К настоящей главе, у вас уже должно выработаться неплохое представление о том, что есть такое небольшая программа на КП и должен возникнуть вопрос, а как довести разобранные задачи до полноценной, результативной программы. Рассмотрим проблему на следующем уже решенном примере – расчета факториала: fact:=1; k:=2; WHILE k<=N DO fact:=fact*k; k:=k+1; END; Итак, что очень важное здесь отсутствует. Во-первых, по завершению работы фрагмента величина fact содержит значение факториала, но мы его не увидим, так как нет операции вывода на экран посчитанного значения, во-вторых, для работы фрагмента необходимо как-то задать исходное значение величины N, которая можно сказать является аргументом для расчетного процесса, но это тоже не сделано. Дополним фрагмент необходимыми командами: In.Open; In.Int(N); fact:=1; k:=2; WHILE k<=N DO fact:=fact*k; k:=k+1; END; StdLog.Int(fact); Команда In.Int(N) читается так: взять из входного потока одно целое значение и присвоить его переменной N. Команда StdLog.Int(fact) читается так: передать в выходной поток целое значение переменной fact. Команда In.Open открывает входной поток данных, действие без которого команда In.Int не будет иметь смысла. Далее, для того, чтобы программу на КП можно было запустить на выполнение она должна иметь имя. Это вполне естественное требование, нельзя обратиться к тому, что не имеет имени. Завершенный программный фрагмент называется процедурой и выглядит следующим образом: PROCEDURE Calculation; BEGIN In.Open; In.Int(N); fact:=1; k:=2; WHILE k<=N DO fact:=fact*k; k:=k+1; END; StdLog.Int(fact); END Calculation; Слово PROCEDURE означает, что ниже записан логически завершенный фрагмент программы, который на КП называется процедурой. Далее, после ключевого слова записывается имя процедуры и наконец между ключевыми словами BEGIN и END записывается текст процедуры. Процедура является логической единицей, но не вполне самодостаточной. Процедуры КП объединяются в модули. Это необходимо, даже в том случае, если процедура в модуле будет только лишь одна. Мы сообщили компилятору, что команды ввода/вывода находятся в модулях In и StdLog , ключевые слова ему и так известны, сейчас осталось определить переменные: N, fact, k. Точнее, определить их тип. Необходимо это вот для чего. Компилятор до запуска программы распределяет оперативную память компьютера. Для чего это нужно вопрос достаточно обширный и детально мы его рассматривать не будем, пока ограничимся следующей версией – если этого не сделать, то в процессе работы программы может случиться конфликт между различными структурами данных претендующих на одну и ту же память. Причем компилятор помочь программисту в разрешении этого конфликта не сможет, так как в процессе работы программы компилятора уже нет. Определение типа выполняется в определенном блоке, который можно создать в каждой отдельной процедуре, а можно и в модуле. Запишем окончательно работоспособный модуль: MODULE Example; IMPORT In, StdLog; PROCEDURE Calculation*; VAR N,k,fact:INTEGER; BEGIN In.Open; In.Int(N); fact:=1; k:=2; WHILE k<=N DO fact:=fact*k; k:=k+1; END; StdLog.Int(fact); END Calculation; END Example. Этот вариант уже можно запустить на выполнение и получить результат, но сначала три небольших, но очень важных замечания: Замечание о регистре символов. Для КП маленькие и большие буквы, это разные буквы. Например, переменные fact, Fact, FACT это три различных переменных. Ключевые слова в КП обязательно пишутся заглавными буквами. Поэтому, запись ключевого слова while или While будет воспринята как ошибочная. Замечание о символе «*». Заметьте, что в последней версии нашего модуля после имени процедуры появился символ звездочка. Это означает, что к данной процедуре можно получить доступ из среды BlackBox, то есть попросить среду выполнить данную процедуру и эту процедуру можно вызвать из других модулей. Блок определения переменных. В нашем примере переменные величины объявлены в теле процедуры Calculation. Это означает, что переменные известны только процедуре Calculation. Если в данном модуле будут описаны другие процедуры, то для них эти переменные окажутся недоступными. Переменные можно описать перед всеми процедурами после имени модуля и объявления требующихся модулей. Литература 1 Ключарев А.А. и др. Структуры и алгоритмы и обработки данных: Учеб. пособие / СПбГУАП.– СПб., 2003.– 172 с. 2 Белов В. В. Алгоритмы и структуры данных: Учебник / Белов В.В., Чистякова В.И. - М.:КУРС, НИЦ ИНФРА-М, 2016. - 240 с. 3 Колдаев В. Д. Структуры и алгоритмы обработки данных: Учебное пособие / В.Д. Колдаев. - М.: ИЦ РИОР: НИЦ ИНФРА-М, 2014. - 296 с. Задачи для самоконтроля №1 1. Напишите три варианта (для каждой из трех форм цикла) программного фрагмента суммирования N последовательных натуральных чисел: 1+2+3+…+N 2. Дано два целых числа a и b. Найти значение выражения ab, форма цикла на ваше усмотрение. 3. Определить номер (в натуральном ряду) четного числа, такого, что сумма всех предыдущих четных включая данное больше заданного W. Будем считать, что 2 имеет номер 1, 4 номер 2 и т.д. 4. Найти сумму квадратов натуральных чисел от 1 не превышающую заданное число W. Задачу решить в двух вариантах: циклом с условием продолжения и циклом с условием завершения. 5. Не пользуясь формулой суммы найти сумму членов геометрической прогрессии заданной начальным членом, количеством членов прогрессии и ее знаменателем. Используйте для решения цикл с шагом. 6. Найти произведение двух чисел A и B не пользуясь операцией умножения. Выбор формы цикла на ваше усмотрение. 7. Вычислить N членов ряда Фиббоначи. Ряд Фиббоначи это ряд чисел определяемый следующими условиями: a1=1; a2=1; ai=ai-1+ai-2. Выбор формы цикла на ваше усмотрение. 8. Найти остаток и частное от деления числа A на меньшее число B. Операциями нахождения остатка и деления пользоваться запрещается. Форма цикла на ваше усмотрение. 9. Найти сумму первых N – нечетных чисел. Выбор цикла на ваше усмотрение 10. Арифметическая прогрессия задана начальным членом и разностью. Геометрическая прогрессия задана начальным членом и знаменателем. Выяснить номер k при котором член геометрической прогрессии станет впервые больше члена арифметической прогрессии. Все величины – целые, положительные числа.