Уточнение многоместных (n - арных) операций

S = =x₁+x₂+x₃+...+x_n

S=U₁ * U₂ * U₃*... * U_n S = = x₁∙ x₂∙ x₃∙...∙ x_n

обобщенный вид S = X^N= x∙ x∙ x∙...∙ x

n – арной операции N раз

S = X! =1∙ 2∙ 3∙ 4∙...∙ X

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

Для решения поставленной задачи (замены многоместной операции последовательностью 2-местных) составим соответствующий линейный алгоритм:

S₁=U₁ Можно заметить, что строки, начиная со второй, можно записать

S2=S₁ * U₂ в следующей обобщенной форме (на Псевдокоде):

S₃=S2 * U₃ для i от 2 до n повторить

S₄=S3 * U₄ S_i=S_i_-1 * U_i - рекуррентная формула (от слова рекурсия )

......

S_n=S_n_-1 * U_n

В этой последовательности начиная со второй строки хорошо видна однотипность вычислений. Поэтому, заметив эту однотипность, попытаемся найти обобщенную запись. Обобщенная запись последовательности шагов, на каждом из которых последующее значение результата получается с использованием предыдущего, называется рекуррентной формулой (от слова рекурсия). Рекурсия в общем случае - это выражение (определение) какого-то понятия самого через себя. В данном случае осуществляется вычисление нового значения переменной S через ее старое значение (i-е промежуточное значение S вычисляется через (i-1)-ое). Если удалось получить такую обобщенную формулу, то это означает, что можно свернуть группу действий (для которой удалось найти обобщенную запись) в цикл (с заранее известным числом повторений). В общем случае цикл будет состоять из трех частей (порядок их важен):

Подготовка

Заголовок

Тело

В тело цикла включается то, что удалось записать в виде рекуррентной формулы, т.е. тело цикла - это те действия, которые надо многократно повторять. Заголовок цикла задает закон изменения т.н. параметра цикла, из которого определяется количество повторения цикла (из приведенного выше заголовка цикла видно, что цикл будет выполняться n-1 раз для i от 2 до n). В подготовку цикла включаются те действия, которые не удалось подвести под рекуррентную формулу. Подготовка цикла настраивает цикл на первое правильное выполнение. На Псевдокоде цикл для выполнения рассмотренной выше последовательности действий имеет вид:

подготовка S₁=U₁

заголовок Для i от 2 до n повторить

тело цикла S_i=S_i_-1 * U_i

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

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

В данном случае подготовка простой не является, потому что в правой части используется переменная U₁ - с индексом. Для упрощения подготовки составляется система уравнений:

- в 1-е уравнение переписывается сам оператор присваивания из подготовки цикла;

- 2-е уравнение получается из рекуррентной (обобщенной) формулы путем подстановки в нее (в левую и правую часть оператора присваивания) нужных значений (тех, которые используются в подготовке) индексов (в данном случае i=1):

S₁=U₁

S₁=S₀ * U₁

Частные случаи:

- если обобщенная операция " +", то S₀=0;

- если обобщенная операция " *", то S₀=1.

В общем случае присваивание для простой подготовки цикла должно иметь вид: S₀=const.

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

В данном случае цикл примет следующий вид:

S₀: =const;

Для i от 1 до n повторить

S_i: =S_i_-1 * U_i

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

S = const

Для i от 1 до n повторить

S=S * U_i

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

Например:

S= xⁱ

i=1

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

n n

S= xⁱ = u_i, где u_i = xⁱ

i=1 i=1

более простая запись

Далее в дополнение к поиску обобщенной формулы для самой многоместной операции необходимо попытаться найти обобщенную запись для вычисления каждой сложной компоненты многоместной операции вида: U_i = f(U_i_-1). При этом самый простой способ для нахождения нужной формулы – это деление типа

Z=U_i/U_i_-1.

Тогда при известном Z можно вычислить U_i через U_i_-1:

U_i=Z*U_i_-1

Для данного примера такая формула имеет следующий вид: U_i=U_i_-1∙ x

Замечание: вместо деления аналогичным образом можно выполнить вычитание.

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

вычислить U₁=X для шагов, начиная со 2-го можно записать

принять S₁=U₁для i от 2 до n повторить

вычислить U₂=U₁*X нач

принять S₂=S₁+U₂ U_i=U_i_-1*X

вычислить U₃=U₂*X S_i=S_i_-1+U_i

принять S₃=S₃+U₂кон

............

В подготовке теперь тоже будет не одно действие, а два:

1) Вычислить U₁=X

2) Принять S₁ = U₁

Упростим эту подготовку:

S₀ = 0

упрощенная подготовка цикла

U₀ = 1

В итоге получим следующий цикл.

S₀=0; U₀=1

Для i от 1 до n повторить

нач

U_i=U_i-1*X

S_i=S_i-1+U_i

кон

10.7 Подведение выражения под n-арную операцию ( нахождение компактной записи ).

Часто встречаются такие случаи, когда необходимо длинную последовательность действий подвести под цикл:

S=1+3/4+4/6+5/8+...= 1 +

Подходов к решения этой задачи много. Самыми простейшими из них являются следующие:

а) поделить все следующие элементы последовательности на предыдущие и попробовать получить геометрическую прогрессию

Например:

S = 1 + ½ + ¼ + 1/8 ++...

Возможны два варианта нахождения решения: 1) решение вида a_i = f(i), т.е. нахождение формулы для прямого вычисления элементов ряда 2) решение вида a_i = f(a_i_-1), т.е. нахождение формулы для вычисления Текущего значения элемента ряда из предыдущего значения.

Для нахождения обоих видов решения надо составить таблицу:

a_i	½	1/4	1/8	1/16
i

Из таблицы видно, что обобщенные формулы для двух видов решения имеют вид:

S = 1 + или S = 1 + , где a_i = a_i-1 *(1/2)

обобщенная запись вида a_i = f(a_i_-1)

a_i (здесь нужна подготовка цикла: S₀: = 1;

a₀: = 1)

обобщенная запись вида a_i = f(i)

(здесь подготовка цикла не нужна)

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

Например:

S = 1 + 3 + 5 + 7+ 9 + 11 =

Для нахождения обобщенной формулы, как уже говорилось выше, есть 2 пути:

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

u_i
i

Из таблицы видно, что u_i = 2*i – 1 (здесь подготовка цикла не нужна)

В итоге получим цикл:

S: =0;

For i: =1 to 6 do

S: = S + 2*i – 1

2 путь: угадать рекуррентную формулу для вычисления u_i вида: u_i = f(u_i_-1)

u_i
i

Из таблицы видно, что u_i = u_i_-1 + 2 (для i от 2 до 6)

(здесь подготовка цикла нужна:

u₁ = 1; упрощенная подготовка

u₁ = u₀ +2;

В итоге получим цикл:

S: =0; u: =-1;

for i: =1 to 6 do

begin

u: = u + 2;

S: = S + u;

end;

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

Например:

s = 1+3+5+7+9+11= = 1+

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

u_i
i

Из таблицы видно, что при прямом вычислении u_i = 2i+1 (для i от 1 до 5)

Здесь подготовка цикла нужна только для S (s₀ = 1):

В итоге получим цикл:

S: =1;

For i: =1 to 5 do

S: = S + 2i+1;

Из той же таблицы видно, что при рекурсивном вычислении u_i имеем:

u_i = u_i_-1+2 (для i от 1 до 5)

Здесь подготовка цикла нужна и для S (s₀ = 1) и для u:

u₁ = 3;

u₁ = u₀ +2;

В итоге получим цикл:

S: =1; u: =1;

for i: =1 to 5 do

begin

u: = u+2;

S: = S + u;

end;

г) Если не удается найти обобщенную запись для дробного выражения в целом, надо представить дробь в виде следующей общей записи:

S= a_i/b_i

i=1

После этого отдельно для числителя и знаменателя расписывается последовательность значений. Так для случая

S=1+3/4+4/6+5/8+...

получим:

a_i
i

b_i
i

a₁ /b₁ = 1

Замечание:

Часто ряд значений бывает знакопеременным, например

S=1 - 3/4+4/6 - 5/8+6/10...=

В этом случае в программе категорически не надо возводить (-1) в степень. Вместо этого надо завести дополнительную переменную a и делать так:

{Подготовка}

a: =1; {Знак a специально подбирается исходя из того, перед каким элементом ряда – четным

или нечетным стоит знак минус}

s: =0;

{Тело цикла}

.....

a: = a * (-1); {инвертируем - переключаем знак a при каждом повторении тела}

S: = S +((i+1)/(2*i))*a; { меняем знак у слагаемого путем умножения на a}

.....

11. Средства языка Паскаль для циклов с известным числом повторений.

переменная выражение тело цикла

Такие циклы называются еще счетными циклами или циклами с параметром. Форма записи таких циклов имеет вид:

For < параметр> : = < начальное значение> to < конечное значение> do оператор;

или

For < параметр> : = < начальное значение> downto < конечное значение> do оператор;

1.один оператор

2.пустой оператор

3.составной оператор

...do; ...

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

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

Var

r: real;

i: integer;

begin

r: =0.0;

for i: =1 to 10 do

r: = r + 0.1;

или r будет изменяться от 0 до 1.0 с шагом 0.1

r: = (i-1) * 0.1;

Порядок выполнения оператора цикла следующий:

1). Проверяется значение следующего логического выражения:

для верхнего " начальное значение" < = " конечное значение"

для нижнего " начальное значение" > = " конечное значение"

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

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

2). Дальнейшее выполнение цикла проходит следующие шаги:

2.1 Выполняются действия в теле цикла

2.2 Проверяется соотношение текущего значения параметра цикла с конечным значением, Вид соответствующего (проверяемого) логического выражения зависит от вида цикла:

для верхнего примера параметр цикла < " конечное значение"

для нижнего примера параметр цикла > " конечное значение"

Если это логическое выражение имеет значение " истина", то будет изменено на +1 (для верхнего случая) или -1 (для нижнего случая) значение параметра цикла и выполнен еще один повтор тела цикла, т.е. будет еще раз повторен пункт 2.

Если это логическое выражение имеет значение " ложь", то выполнение цикла завершится.

Рассмотрим два простых примера:

1) 2)

Var Var

i: integer; i: integer;

begin begin

i: =-2; i: =-2

for i: =0 to 4 do for i: =0 to -1 do

writeln(i); writeln(i);

end. End.

1)Цикл будет выполняться пять раз. 2)Цикл не будет выполняться не разу потому, что

Выведет значение i: 0, 1, 2, 3, 4, 4 начальные условия (см. п.1) не выполняются. В результате

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

цикла равен последнему значению Writeln(i) выведет (-2). Начальное значение параметр цикла

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

выполнялось тело цикла.

В Турбо Паскале, начиная с 7-й версии, появились 2 псевдооператора, которые позволяют менять ход выполнения цикла:

For i: = 1 to 10 do

begin

...

break;

continue;

...

end;

Break - позволяет выполнить внезапный (одноуровневый) выход из цикла.

Continue выполняет следующее:

- прерывается текущее выполнение тела цикла при текущем значении параметра цикла

- изменяется значение параметра цикла на следующее

- начинается следующая итерация цикла (со следующим значением параметра цикла).

Табулирование функций

Табулирование функций - построение таблиц функций.

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

шапка тело таблицы

Х1

Х2

...

Хn

Анализ объекта, который надо построить (таблицы), позволяет разбить его на шапку и тело. Поэтому задача по выводу распадается на 2 подзадачи: вывод шапки и вывод тела.

Вывести шапку

Вывести таблицу

Вывести тело

WriteLn ('| X | Y |');

WriteLn ('+-------+-------+');

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

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

Создание каждой строки на экране будет состоять из трех шагов:

1. Получить текущее значение x.

2. Вычислить значение функции y = f(x).

3. Вывести значения x и y.

В итого получим следующую последовательность действий для вывода тела:

1шаг {создание 1-ой строки тела}

Х₁ = А

Y₁ = F(X₁);

WriteLn(Х1 и Y1

2шаг {создание 2-ой строки тела}

X₂ = X₁ + h

Вычислить Y₂ = F(X₂).

WriteLn( X₂ и Y₂можно свернуть в цикл

3шаг {создание 3-ей строки тела}

X₃ = X₂ + h

Вычислить Y₃ = F (X₃)

WriteLn(X₃ и Y₃

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

X_i = X_i_-1+ h Вычислить Y_i = F (X_i) WriteLn(X_i и Y_i)

То, что не удалось обобщить, нужно включить в подготовку цикла, и ее надо сразу упростить, чтобы включить в цикл (тело цикла) все шаги, начиная с 1-го:

X₁ = A X₀ + h = A X₀ = A - h

X₁ = X₀ + h упрощенная подготовка цикла

В общем случае, цикл получится следующим:

X₀ = A – h;

for i: = 1 to n do

begin

точнее n = round((B - A) / h) + 1

X_i = X_i-1+ h

Y_i = f(X_i)

WruteLn(X_i и Y_i);

end;

В этом фрагменте программы остаются неизвестными 2 момента:

1) чему равняется n?

2) как выводить строку со значением X_i и Y_i?

Для вычисления n обычно используется формула: n = (B - A) / h + 1, где h - заданный шаг.

Вывод строк в шапке таблицы можно будет уточнить после того, как определим, как выводится каждая детальная строка в теле таблицы:

Например:

9 позиций 9 позиций

Writeln('| ', x: 9: 4, ' | ', y: 9: 4, ' |'); вывод детальной строки

Writeln('| X | Y |); вывод строки шапки

9 позиций 9 позиций

В общем случае заранее ширина шапки неизвестна (она определяется тогда, когда станет ясна форма вывода строк тела шапки).

Разветвляющиеся алгоритмы

Таблица ситуаций и команда выбора.

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

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

- перечислить эти ситуации и указать этот перечень исполнителю алгоритма,

- для каждой ситуации надо описать:

а) как проверять факт её наличия (наступлении) или отсутствия (ненаступления),

б) что надо делать при наличии (наступлении) ситуации.

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

Ситуация	Действие
Ситуация 1	Действие 1
Ситуация 2	Действие 2
...	...
Ситуация n	Действие n

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

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒