A b c d e f g h i j k l m n o p q r s t u v w y z

Дата добавления: 2013-12-23; просмотров: 4591; Нарушение авторских прав

Блок-схема приведенного выше примера будет выглядеть следующим образом:

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

Пример. Составить алгоритм вычисления суммы заданных чисел 1,1+1,3+1,5+…+5,3.

Исходной информацией для решения этой задачи являются сами числа. В этой задаче мы встречаемся с распространенной задачей расчета суммы. Сумма получается путем накопления слагаемых в какой-либо переменной (в нашей задаче это переменная S). Накопление осуществляется в цикле. В цикле к текущему значению суммы прибавляется значение очередного слагаемого Х, т.е. S = S + X.

Решение данной задачи представим двумя способами:

цикл с постусловием

цикл с параметром

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

Количество повторений цикла можно вычислить по формуле:

где n - число повторений,

х₀ - начальное значение параметра цикла,

х_к - конечное значение параметра цикла,

h - шаг изменения параметра цикла,

[ ]- взятие целой части от деления.

для нашего случая количество повторений

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

В данном примере i – параметр цикла показывает количество повторений, т.е. сколько раз будет выполняться цикл. До цикла необходимо задать первое значение переменной Х, а в цикле требуется использовать блок для изменения этой переменной. Как видим, в данном примере применение цикла этого типа не рационально.

Пример. Составить алгоритм вычисления суммы факториалов 1!+2!+3!+…+n!, где n!=1×2×3×…×n.

В этой задаче необходимо рассчитать сумму путем накопления слагаемых, в качестве которых выступают факториалы чисел. Каждое последующее значение факториала получается из предыдущего значения: P₁=1; P₂= 1×2= P₁×2; P₃= 1×2×3 = P₂×3 и т.д.

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

Для данной задачи P_i=P_i-1× i. Для расчета величины текущего факториала необходимо знать его порядковый номер и значение предыдущего факториала.

Решение данной задачи также представим двумя способами:

блок-схема с предусловием

блок-схема с параметром

Пример. Задана последовательность из n чисел. Составить алгоритм вычисления среднего арифметического чисел, не равных нулю.

Подсчет количества чисел последовательности будет осуществлять переменная I. Среди всех чисел последовательности необходимо подсчитать количество и сумму чисел, не равных нулю. Для подсчета суммы возьмем переменную S, а для подсчета количества – переменную К, начальные значения которых полагаем равным нулю.

Решение данной задачи представим с использованием блока модификации:

Чтобы определить количество чисел, не равных нулю, нужно перебрать все вводимые числа и проверить условие а¹0. Если условие выполняется, то необходимо вести подсчет таких чисел, т.е. переменную K увеличивать на единицу каждый раз, пока верно условие.

До сих пор циклы имели заданное число повторений. Рассмотрим на примерах алгоритмы с неизвестным числом повторений.

Пример. По заданному натуральному числу a вычислить минимальное такое n, при котором n!³a. Число a задается вводом.

Исходной информацией является целое число a. В данной задаче число повторений неизвестно, так как неизвестен порядковый номер последнего множителя.

Рис. 1.25

По условию задачи при F³a расчет факториала необходимо прекратить. Именно это условие и будет условием окончания расчетов. Следует обратить внимание на то, что выводится значение n-1. Это объясняется тем, что условие F³a проверяется для предыдущего значения n.

Пример. Вычислить сумму бесконечного ряда

с заданной точностью e. Число х задается вводом.

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

Решение данного примера представим с помощью циклической структуры с предусловием:

Рис. 1.26

Если элемент, равный превышает e, то данный элемент необходимо добавлять к сумме. При невыполнении условия расчет завершится.

1.3.4. Алгоритмы со структурой вложенных циклов

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

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

Для демонстрации алгоритмов со структурой вложенных циклов рассмотрим пример.

Пример.Составить схему алгоритма длявычисления значений функции Z = SinХ+CosY для всех значений Х от 1 до 8 с шагом 1 и для всех значений Y от -3 до 2 с шагом 0.5.

Такие вычисления значений заданной функции называются табулированием.

При одном значении Х = 1 необходимо вывести 11 раз значение Z.

Выполняя табулирование, необходимо последовательно перебрать все значения Х в указанном диапазоне и для каждого Х перебрать все значения Y в диапазоне изменения Y.

Блок модификации 1 организует внешний цикл по Х, где Х меняет значения от 1 до 8 с шагом 1. Телом внешнего цикла является внутренний цикл с блоком модификации 2. Y принимает все значения от -3 до 2 с шагом 0,5 для каждого значения Х.

Пример. Вычислить сумму бесконечного ряда

с заданной точностью e для всех значений Х от 1 до 8 с шагом 1.

На рисунке 26 представлена блок-схема для одного фиксированного значения Х. В данной задаче переменная Х меняет свое значение, поэтому мы добавляем внешний цикл по Х.

Обратите внимание — при составлении алгоритмов вложенных циклов необходимо соблюдать следующее дополнительное условие: все блоки внутреннего цикла должны полностью располагаться в теле внешнего цикла.

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

1.4 ПОДЧИНЕННЫЕ АЛГОРИТМЫ

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

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

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

Пример. Составить алгоритм вычисления числа сочетаний. Число сочетаний рассчитать по формуле:

В данной задаче необходимо трижды вычислить факториал: n!, m!, (n-m)!. Вычисление факториала оформим в виде подалгоритма. Вместо полной записи последовательности блоков подалгоритма, которая должна повторяться трижды в основной схеме, используем блок предопределенного процесса как обращение к подалгоритму.

Рис. 1.31

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

Контрольные вопросы

1. Что такое алгоритм? Каким свойствам должен он удовлетворять?

2. Что из нижеперечисленного является свойством алгоритма:

a) результативность

b) эффективность

c) завершенность

d) массовость

e) определенность

3. Какие вы знаете способы записи алгоритма? Приведите примеры алгоритмов, записанных разными способами.

4. Назовите основные блоки, используемые при графическом способе представления алгоритма?

5. Какие основные структуры алгоритмов вы знаете?

6. Дайте понятие алгоритма линейной структуры?

7. Составьте алгоритм определения площади круга, если известна длина окружности.

8. Какие вы знаете конструкции алгоритма разветвляющейся структуры?

9. Какой блок обязателен при графическом способе представления алгоритма разветвляющейся структуры?

10. Какой алгоритм называется циклическим алгоритмом?

11. Какие структуры алгоритмов повтора вы знаете?

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

13. В чем отличие циклической структуры с предусловием от цикла с постусловием?

14. В какой циклической структуре используют блок “модификация?

15. Для чего необходимо подсчитать количество повторений цикла и по какой формуле?

16. Для чего используется параметр цикла и что произойдет при его отсутствии?

17. Что такое вложенные циклы? Какие дополнительные условия необходимо соблюдать при организации вложенных циклов?

18. В каких случаях предпочтительно использовать подчиненные алгоритмы?

19. Блок-схема какого алгоритма представлена ниже?

20. Какое значение получит переменная М при выводе, если начальные значения M=18, N=12?

ГЛАВА 2

Алгоритмический язык ПАСКАЛЬ

2.1 АЛФАВИТ ЯЗЫКА ПАСКАЛЬ

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

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

Алфавит языка Паскаль включает в себя все символы, представленные в кодировочной таблице, которая в настоящий момент загружена в оперативную память или хранится в ПЗУ компьютера. Каждому символу алфавита соответствует индивидуальный числовой код от 0 до 255. Символы с кодом от 0 до 127 представляют собой так называемую основную таблицу кодов ASCII.

2.1.1 Символы алфавита

1. Символы, используемые для составления идентификаторов (имен для обозначения каких-либо объектов):

¨ прописные и строчные буквы латинского алфавита:

¨ арабские цифры: