Практикум по Visual Basic for Applications. 3 Глава Алгоритмы и программы Понятие алгоритма
 Скачать 1.74 Mb.
|
|
Программирование, практикум по Visual Basic for Applications. 3 Глава 1. Алгоритмы и программы 1.1. Понятие алгоритма Алгоритм. Фундаментальной концепцией информатики является понятие алгоритма. Алгоритм – это конечная последовательность инструкций (дейст- вий, предписаний), предназначенных для решения поставленной задачи. Инст- рукции должны быть точными: два исполнителя одного и того же алгоритма должны прийти к одному и тому же результату. Совокупность всех исходных данных, к которым алгоритм применим, на- зывается областью применимости алгоритма. Каждый алгоритм задает функцию, относящую каждому элементу области применимости соответствую- щий результат, т.е. область применимости совпадает с областью определения этой функции. Говорят тогда, что алгоритм вычисляет эту функцию. Функция, которая вычисляется некоторым алгоритмом, называется вычислимой. Множе- ство значений вычислимой функции, определенной на N (натуральный ряд), образует перечислимое множество (значения функции перечисляются алго- ритмом). Область применимости и область результатов любого алгоритма – пе- речислимые множества. Не всякая математическая задача может быть решена с помощью алго- ритма. Это связано с невычислимостью (неперечислимостью) некоторых об- ластей, на которых определены решения этих задач. Например, существуют пе- речислимые подмножества натурального ряда с неперечислимым дополнением. Задачи, не решаемые с помощью алгоритма, называют алгоритмически нераз- решимыми. К числу таких задач относятся, например, проблема распознавания эквивалентности (равенства) слов (существуют конечный алфавит, конечный набор правил составления и преобразования слов в этом алфавите, но нельзя построить алгоритм, который по двум произвольным словам этого алфавита всегда определит, преобразуются они или нет к одному и тому же слову). Дру- гая известная алгоритмически неразрешимая задача – проблема остановки – не существует алгоритма, отвечающего на вопрос: остановится или нет некоторая программа, запущенная на некотором наборе начальных данных (не распозна- ется наличие в программах бесконечных циклов). Проблема самоприменимо- сти также неразрешима (нельзя с помощью алгоритма распознать для машины, преобразующей слова, распознает она или нет шифр самой себя). Задачи, ре- шаемые алгоритмами, относятся к области исследований конструктивной ма- тематики. Средства записи алгоритмов. Записать алгоритм можно на естествен- ном языке, в виде схемы, на каком-либо (специальном) языке программирова- ния, к числу которых относятся и языки машинных команд, ассемблеры, авто- коды. Одним из популярных схемных средств представления алгоритмов явля- ются блок-схемы. 4 Блок-схема – это диаграмма специального вида, на которой фигуры обо- значают операторы (действия алгоритма), а стрелки – последовательность ис- полнения операторов. Основные алгоритмические структуры (операторы) – конструкции, с по- мощью которых можно записать алгоритм, - это: присваивание, условный опе- ратор, оператор цикла и последовательность операторов. В различных языках программирования эти конструкции могут изображаться по-разному (иметь разный синтаксис), но отличия, как правило, несущественны. 1.2. Основные алгоритмические конструкции 1.2.1. Последовательность Последовательность операторов означает последовательное их исполне- ние друг за другом. На блок-схемах эта конструкция изображается стрелкой . В языках программирования последовательно выполняемые операторы отде- ляются друг от друга символом «;» или (как в VBA) символом конца строки (каждый оператор начинается с новой строки) или двоеточием. 1.2.2. Присваивание Обычный синтаксис оператора присваивания: <переменная> <знак присваивания> <выражение>, где <знак присваивания> может иметь вид « » или «» (как, например, в VBA). Выполняется присваивание так: вычисляется выражение в правой части этого оператора и полученное значение присваивается переменной левой части (переменная получает это значение, «стирая» предыдущее). Например, после- довательность операторов присваивания (в языке VBA): а = 4 + 7 а = а + 2 в = 2 а = в*3 + а исполняется так: вычисляется 4+7, результат 11 присваивается переменной а. Прежнее значение а стирается, новое значение а есть 11. Во второй строке к этому значению прибавляется 2, результат выражения есть 13 (11+2=13). Это значение присваивается переменной а, теперь уже значение а есть 13. В треть- ей строке в получает значение 2. Наконец, в четвертой строке снова пересчи- тывается значение переменной а: вычисляется выражение в*3+а (вместо в и а подставляются их значения 13 и 2), результат 2*3 + 13 = 19 присваивается пе- ременной а (говорят, 19 «заносится» в переменную а или «запоминается» в а). Результат выполнения всей последовательности: а=19, в=2. Присваивание можно трактовать как запоминание (сохранение) вычис- ляемых в ходе исполнения алгоритма значений для последующего их использо- вания. Сохраняясь в переменной, значение приобретает имя, например, в пре- 5 дыдущем примере далее в алгоритме вместо числа 19 можно использовать его (временное) имя a, вместо числа 2 – имя в. Обратную операцию – извлечение значения из переменной называют разыменованием. На блок-схеме присваивание представляется прямоугольником со входом и выходом. Внутри прямоугольника записывается сам оператор. Например, а = в*3+а выглядит так: а = в*3 + а Вся последовательность предыдущего примера изображается так: а = 4+7 а = а+2 в = 2 а=в*3+а 1.2.3. Условный оператор (ветвление) Эта алгоритмическая структура представляет разветвление алгоритма в зависимости от значения (истинности или ложности) некоторого условия. В общем виде конструкция выглядит так: <если> <условие> <то> <действия1> <иначе> <действия2>, и читается как «если условие истинно, то выполнить действия1, иначе (если ус- ловие ложно), выполнить действия2». Слова «если», «то», «иначе» в разных языках могут иметь разный синтаксис, но в большинстве языков это «if», «then», «else». В VBA синтаксис условного оператора: If <условие> Then <действия1> Else <действия2> End If 6 Условный оператор может быть неполным, без ветки <иначе> <дейст- вия2>. Тогда, если условие ложно, управление передается следующему в общей последовательности оператору. На блок-схемах эти два случая изображаются так: условие + действия1 действия2 - условие + действия1 - Здесь знаки «+» и «-» обозначают «да» (условие выполняется) и «нет» (условие не выполняется). Например, вычисление y, заданного формулой: 2 y x при x 0, можно представить следующей блок-схемой: x 1, при x 0 x<0 + - y = x*x y = x+1 На языке программирования VBA эта конструкция выглядит так: If x<0 Then y=x*x Else y=x+1 End If Обратите внимание, что операторы после Then (ветка «+») и Else (ветка «-») начинаются с новой строки, а сам условный оператор заканчивается фра- зой End If – признаком конца конструкции ветвления. Пример использования неполного условного оператора: суммируются числа, вводимые с клавиатуры; если число отрицательное, оно прежде заменя- ется единицей. Пусть переменная а хранит значение введенного числа, а пере- 7 менная S хранит сумму введенных чисел. Фрагмент блок-схемы решения такой задачи: a<0 a = 1 S=S+a На языке программирования VBA эта конструкция выглядит так: If a<0 Then a=1 End If S=S+a Каждая из ветвей условного оператора может содержать произвольное количество операторов, среди которых могут быть снова ветвления (вложенные «если»). Например, следующая программа: x=10 If x>5 Then x=x-5 If x>7 Then x=x+4 y=x Else x=x*x-1 y=x+8 End If Else x=x-4 y=1 End If выполняется так: переменная x получает в результате присваивания значение 10. Затем проверяется условие x>5? В данном случае оно выполняется, поэтому исполняются операторы после Then: вначале x получает новое значение 5, за- тем проверяется (вложенное) условие x>7? Оно ложно, тогда последовательно исполняются операторы, идущие после Else: x=x*x-1 и y=x+8, результат x=24, y=32. На этом внутренний «If» заканчивается, ветка «Else» внешне- 8 го «If» не исполняется, общий результат остается тем же: x=24, y=32. Если же изменить начальное присваивание, например, вместо x=10 записать x=2, то исполнение программы будет идти по другой ветке, соответствующей внешне- му «Else»: x=x-4, y=1, и результат будет другой: x = -2, y = 1. Блок-схема для этой программы имеет вид: x=10 x>5 ? + - x=x-5 x=x-4 y=1 x>7 ? + - x=x+4 y=x x=x*x-1 y=x+8 Какие операции можно включать в условие? Условие – это логическая формула, значение которой может быть вычислено. Простейшее условие – это отношение: больше (>), меньше (<), больше или равно (>=), меньше или равно (<=), не равно (<>). Более сложные условия составляются из простых с помо- щью операций конъюнкции (в VBA это And), дизъюнкции (Or), отрицания (Not), импликации (Imp). Например, условие х меньше пяти, но больше или равно двум, записывается как (x<5) And (x>=2). 1.2.4. Оператор цикла Цикл означает повторяющийся набор действий. Например, суммируется набор из 20-ти чисел, вводимых с клавиатуры. Действия: «ввести число» и «до- бавить его к сумме» будут повторяться 20 раз. В задаче: складывать числа, вво- димые с клавиатуры, до тех пор, пока не встретится 0, эти действия будут по- вторяться столько раз, сколько выполняется (истинно) условие: «введенное число не равно нулю». Для обозначения повторений в записи алгоритмов ис- пользуют конструкции, называемые циклами: цикл с параметром (счетчиком), цикл с предусловием и цикл с постусловием. Цикл с предусловием является 9 наиболее общей конструкцией: этого оператора достаточно, чтобы записать любые циклические действия алгоритмов. Повторяющаяся группа действий называется телом цикла, однократное выполнение этой группы – шагом цикла. Часть конструкции, в которой опре- деляется, продолжать выполнение цикла или нет, называют заголовком цикла. Заголовок, как правило, содержит условие, истинность или ложность которого требует повторения операторов тела цикла. Если условие задано так, что оно выполняется всегда, например, 4<7, то повторения будут длиться «вечно», то- гда говорят, что программа зациклилась. Если, наоборот, условие никогда не выполнится, например, 2<0, то операторы цикла не исполняются, вся конструк- ция игнорируется исполнителем алгоритма и управление передается следую- щим за оператором цикла действиям. Цикл с предусловием. Заголовок этого цикла содержит условие, которое проверяется всякий раз перед очередным исполнением тела цикла. Если усло- вие истинно, тело исполняется, если ложно, управление передается следующе- му за циклом оператору в алгоритме. Таким образом, тело цикла исполняется столько раз, сколько раз истинно условие цикла. Блок-схема этого оператора: Циклы с предусловием называют обычно циклами типа While или цикла- Условие + - Тело цикла + ми ПОКА (работает, пока условие выполняется). Синтаксис этих циклов в VBA: While <Условие> <Тело цикла> Wend или Do While <Условие> <Тело цикла> Loop) Например, исполнение фрагмента программы: a = 7 While a > 0 a = a - 1 Wend даст в результате значение а=0, т.к. тело цикла a = a–1 выполнялось столько раз, сколько выполнялось условие a>0. Последний раз оно выполнилось, когда 10 a=1, в результате a=1–1=0. Проверка условия (0>0) показала «ложь» и управление передалось операторам, следующим за Wend (граница цикла While). Таким образом, значение а осталось равным 0. Если заменить первый оператор фрагмента a=7 на a=0, то цикл не выполнится ни разу, т.к. условие a>0 ложно. Тело цикла не исполнится ни разу, если условие не выполняется уже вна- чале. В некоторых задачах необходимо, чтобы тело цикла хотя бы раз отрабо- тало. Можно, конечно, операторы тела цикла «продублировать», написав их еще раз до оператора цикла, тогда они исполнятся независимо от истинности условия. Но, если их много, программа выглядит громоздко. Для таких случаев удобно использовать цикл с постусловием. Цикл с постусловием. В таких циклах условие проверяется после того, как операторы тела цикла хотя бы раз отработают. Блок схема этого цикла та- кова: Тело цикла Условие + - В отличие от цикла с предусловием, данный цикл работает до выполне- ния условия, пока оно не верно, т.е. здесь истинность условия означает выход из цикла. Циклы с постусловием называют Until-циклами, циклами ПОКА НЕ или циклами ДО (работают до того, как условие выполнится). Синтаксис этих цик- лов в VBA: Do <Тело цикла> Loop Until <Условие>. Программа предыдущего примера, но с Until-циклом: a = 7 Do a = a - 1 Loop Until a < 0 даст другой результат: а=-1, т.к. после того, как значение а стало равным 0, тело цикла отработало еще раз (условие a<0 еще не выполнилось). Если заме- нить первый оператор фрагмента a=7 на a=0, то этот оператор цикла сработа- ет, т.к. до проверки условия выполнится a=a–1, и уже после этого произойдет 11 выход из цикла (значение а станет -1, поэтому условие завершения a<0 станет верным). При использовании рассмотренных видов циклов необходимо помнить, что в теле цикла должны быть операторы, которые влияют на значение условия и, в конце концов, приведут к изменению его значения. Неизменные, «окаме- невшие» условия, если они истинны, приведут к зацикливанию программы. Цикл с параметром. Эти циклы используются тогда, когда число повто- рений известно заранее – количество шагов задано, например, 20, 100, N, или может быть вычислено как результат какого-либо выражения до исполнения цикла. Параметром в цикле является счетчик шагов. Счетчик (это значение специально выделенной переменной) может изме- няться на единицу с каждым шагом или получать некоторое заданное прираще- ние, например, 0.15. Цикл тогда исполняется до тех пор, пока значение счетчи- ка не достигнет указанного в заголовке цикла значения. Циклы с параметром называют часто циклами типа For, т.к. в большинстве языков программирова- ния их заголовок начинается со слова For. Для VBA синтаксис этого цикла: For <переменная-счетчик> = <начальное значение> To <конечное значение> <Тело цикла> Next или, если используется счетчик с приращением значения, отличным от 1: For <переменная-счетчик> = <начальное значение> To <конечное значение> Step <приращение> <Тело цикла> Next Здесь переменная-счетчик – это имя переменной, взятой для счета шагов; начальное значение, конечное значение – выражения, в частности, целые числа или переменные, значения которых берутся в качестве начала и, соответствен- но, конца отсчета повторений тела цикла, приращение – выражение, значение которого на каждом шаге добавляется к счетчику цикла (приращение может быть и отрицательной величиной, тогда оно вычитается из счетчика и началь- ное значение в этом случае должно быть больше конечного). Оператор цикла с параметром работает следующим образом. Тело цикла исполняется столько раз, сколько значение счетчика меньше или равно конеч- ному значению. После каждого шага цикла к счетчику добавляется 1, если при- ращение не указано, или значение приращения, если оно указано. Условие на счетчик после этого проверяется и, если конечное значение не превышено, тело цикла вновь исполняется. После присваивания счетчику начального значения условие также проверяется. Обозначим начальное значение счетчика i как i 0 , конечное значение – N, приращение – h. Тогда блок-схема этого оператора имеет вид: 12 i=i 0 i N + Тело цикла i=i+h - Как видно, цикл с параметром является частным случаем цикла с преду- словием типа While. Пример использования цикла-For в программе VBA: k = 2 m = 4 For i = k + 1 To m * 2 + 1 Step 0.5 k = k + i Next Этот цикл выполняется, начиная со значения счетчика i, равного 3-м, и продолжается, пока счетчик не превзойдет величину 9 (4*2+1=9); на каждом шаге значение счетчика увеличивается на 0.5, поэтому число шагов будет не 7, а 13. В результате значение k = 80. Несмотря на то, что значение k на каждом шаге меняется, начальное значение k+1=3 не пересчитывается и к нему испол- нение цикла не возвращается. Обратите внимание, что заголовок цикла For: начальное, конечное зна- чения счетчика и шаг - вычисляется один раз, до первого выполнения тела цик- ла, и не перевычисляется, несмотря на возможные изменения переменных, вхо- дящих в выражения для этих значений. Досрочный выход из цикла. При использовании циклических конструк- ций может возникнуть необходимость досрочного выхода из цикла. Например, получен искомый результат, а условие цикла еще истинно и позволяет продол- жить исполнение этого оператора. В языке VBA оператором досрочного выхо- да является Exit, причем в циклах For он имеет вид Exit For, а в циклах, начинающихся с |