Отправляет email-рассылки с помощью сервиса Sendsay

Всё о работе в Интернет

Подписаться Бесплатная «Серебряная» новостная рассылка Подписчиков 7.350 RSS
←   Июнь 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней 1 выпусков (1 раз в 2 месяца)


Сайт рассылки: http://bestinvestblog.com
Открыта: 10-02-2009

Автор
bestinvestblog

Статистика

7.350 подписчиков
0 за неделю
←   Все выпуски   →

Занятие 41.


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

Очень важно изначально усвоить, в каких типичных случаях возможно применение циклических алгоритмов. Ещё более важным является понимание основных принципов их записи.

ОБЩИЕ ПРЕДСТАВЛЕНИЯ О ЦИКЛИЧЕСКИХ АЛГОРИТМАХ

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

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

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

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

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

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

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

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

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

В элементарной математике арифметическая прогрессия определяется как последовательность, в которой разность между последующим и предыдущим членами остаётся неизменной. Эта неизменная разность называется разностью прогрессии. Её знак определяет либо возрастание, либо убывание прогрессии. Обязательным элементом любой арифметической прогрессии является первый её член. Например, натуральный ряд чисел 1, 2, 3, ... является возрастающей арифметической прогрессией с первым членом и разностью, равными единице.

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

Так, сумма первых n членов арифметической прогрессии a1, a2, ..., an выражается формулой sn = (a1 + an) * n / 2. А для арифметической прогрессии с разностью r член с порядковым номером n можно вычислить по формуле an = a1 + r * (n – 1).

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

2. Рекуррентные соотношения – основа цикла.

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

Для использования в цикле рекуррентное соотношение должно быть приведено к специфической форме, особенностью которой является использование безындексных переменных. Указанная особенность известна в литературе под названием “отбрасывание индексов”.

Рассмотрим образование рекуррентных соотношений на примере задачи вычисления суммы членов последовательности a1, a2, a3, a4.

Требуется вычислить значение S = a1 + a2 + a3 + a4, что, вообще говоря, можно сделать “обычным” способом. Однако, наша задача состоит в упорядочении этого процесса.

Построим последовательность частичных сумм:

S0 = 0;            {первоначальное значение суммы}
S1 = S0 + a1;   {первая частичная сумма}
S2 = S1 + a2;   {вторая частичная сумма}
S3 = S2 + a3;   {третья частичная сумма}
S4 = S3 + a4.   {четвёртая частичная сумма}   

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

Несколько необычным на “бытовом” уровне кажется наличие первоначальной суммы S0. Обычно начинают с первой частичной суммы S1, считая её равной члену a1. А иногда даже начинают со второй частичной суммы S2, считая её равной сумме первых двух членов a1 + a2.

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

Для частичных сумм нами было получено пять разных значений, представленных пятью разными переменными S0, S1, S2, S3 и S4. При этом совершенно очевидно, что после получения очередного значения частичной суммы нет никакой необходимости сохранять все её предыдущие значения. Поэтому возникает вполне законный вопрос: а нельзя ли в таком случае для обозначения частичных сумм обойтись одной переменной? Оказывается, не только можно, но и нужно. Получаем следующий процесс образования частичных сумм:

S := 0;           {первоначальное значение суммы}
S := S + a1;   {первая частичная сумма}
S := S + a2;   {вторая частичная сумма}
S := S + a3;   {третья частичная сумма}
S := S + a4.   {четвёртая частичная сумма}   

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

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

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

S := 0; i = 1;          {первоначальное значение суммы}
S := S + a1; i = 2;   {первая частичная сумма}
S := S + a2; i = 3;   {вторая частичная сумма}
S := S + a3; i = 4;   {третья частичная сумма}
S := S + a4; i = 5.   {четвёртая частичная сумма}   

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

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

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

S := 0; i := 1;               {первоначальное значение суммы}
S := S + a1; i := i + 1;   {первая частичная сумма}
S := S + a2; i := i + 1;   {вторая частичная сумма}
S := S + a3; i := i + 1;   {третья частичная сумма}
S := S + a4; i := i + 1.   {четвёртая частичная сумма}   

А вот теперь значения индексов у переменных, обозначающих члены последовательности, можно отбросить. Для обозначения члена последовательности будем использовать одну и ту же переменную a. Индекс же для неё нами уже вычисляется отдельно. Окончательно процесс образования частичных сумм представляется в следующем виде:

S := 0; i := 1;                 {первоначальное значение суммы}
S := S + a(i); i := i + 1;   {первая частичная сумма}
S := S + a(i); i := i + 1;   {вторая частичная сумма}
S := S + a(i); i := i + 1;   {третья частичная сумма}
S := S + a(i); i := i + 1.   {четвёртая частичная сумма}   

Здесь обозначение a(i) имеет смысл обращения к некоторой функции, которая по заданному значению индекса находит соответствующее значение члена последовательности.

Так естественным образом мы подошли к идее использования цикла для решения нашей задачи. Напомню, что мы должны были вычислить значение суммы S = a1 + a2 + a3 + a4.

При этом две команды присваивания S := 0 и i := 1 необходимо выполнить непосредственно перед циклом. Подобные команды обычно называют командами инициализации переменных цикла. Их назначение – установить первоначальные значения для переменных, входящих в состав рекуррентных соотношений, использованных в самом цикле.

Сам же цикл следует построить таким образом, чтобы одна и та же пара команд S := S + a(i); i := i + 1 была повторена ровно четыре раза.

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

S := 0; i := 1;
пока i <= 4
выполнять нс S := S + a(i); i := i + 1 кс

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

S := 0; i := 1;
повторять
   S := S + a(i); i := i + 1
до i = 5

Однако наболее компактной выглядит запись с использованием команды повторения с параметром:

S := 0;
для i от 1 до 4
выполнять S := S + a(i) 

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

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

Уважаемые подписчики! На следующем занятии мы начнём рассматривать конкретные задачи с применением циклов.

Уважаемые подписчики! При необходимости задать вопрос, проконсультироваться, уточнить или обсудить что-либо обращайтесь через Гостевую книгу моего персонального сайта http://a-morgun.narod.ru. При этом настоятельно рекомендую пользоваться браузером Internet Explorer.

С уважением, Александр.
В избранное