Специальные методы. Метод накопления

1.

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

2.

Пример 5. Найти сумму элементов массива.
1 Постановка задачи
1.1 Исходные данные
n: целое;
x: массив [1..n]: вещественных;
1.2 Ограничения
n>1
1.3 Результаты
S: вещественное;

3.

1.4 Связь
S = x1 + x2 + x3 + ... + xn
2 Метод
S = S + xi
для i = 1..n
S=0
Промежуточные данные
i: целое;
Если в методе требуются вспомогательные
переменные, их описывают после метода в том
же синтаксисе, что и исходные данные.

4.

Пример 6. Найти произведение элементов
массива.
1 Постановка задачи
1.1 Исходные данные
n: целое;
x: массив [1..n]: вещественных;
1.2 Ограничения
n>1
1.3 Результаты
P: вещественное;

5.

1.4 Связь
P = x1 * x2 * x3 * ... * xn
2 Метод
P = P * xi
для i = 1..n
P=1
Промежуточные данные
i: целое;

6.

3.2.2 Метод перебора
Пример 7. Найти количество положительных
элементов массива.
1 Постановка задачи
1.1 Исходные данные
n: целое;
x: массив [1..n]: вещественных;
1.2 Ограничения
n>1
1.3 Результаты
K: целое;

7.

1.4 Связь
K = количество ( x i > 0), i = 1..n
2 Метод
K = K + 1 при xi > 0
для i = 1..n
K=0
Промежуточные данные
i: целое;

8.

Пример 8. Найти минимум и его номер.
1 Постановка задачи
1.1 Исходные данные
n: целое;
x: массив [1..n]: вещественных;
1.2 Ограничения
n>1
1.3 Результаты
min: вещественное;
num: целое

9.

1.4 Связь
min = минимум (xi) , i = 1..n;
num = номер (min);
2 Метод
min = xi
num = i
при xi < min
для i = 2..n
min = x1
num=1
Промежуточные данные
i: целое;

10.

Рассмотренный
алгоритм
местоположение первого среди
минимальных элементов массива.
находит
нескольких
Чтобы найти местоположение последнего
среди одинаковых минимальных элементов
массива, нужно иначе записать условие:
ai <= min

11.

3.2.3 Метод последовательных приближений
Пример 9. Вычислить y = ex по формуле
x x2
x3
xn
y =1+ +
+
+ ... +
1!
2!
3!
n!
с заданной точностью.
1 Постановка задачи
1.1 Исходные данные
x: вещественное; {аргумент}
: вещественное; {точность}
1.2 Ограничения
>0
1.3 Результаты
y: вещественное;

12.

1.4 Связь
x x2
x3
xn
y =1+ +
+
+ ... +
1!
2!
3!
n!
Если
n x i n -1 x i
n -1 x i
∑
- ∑
< ξ , то y = ∑
; n = 1,2,3...
i =1 i! i =1 i!
i =1 i!
≡
n -1 x i
xn
< ξ , то y = ∑
; n = 1,2,3...
n!
i =1 i!
n xi
Можно также как резулььат брать y = ∑
i =1 i!

13.

2 Метод
i = i +1
xi
y = y+
i!
y =1
i =1
xi
пока
>= ξ
i!
Операция факториал (!) недоступна, заменяем
умножением:
n=n*i
i=i+1
где n – факториал, i – аргумент.

14.

Объединяем оба метода
n = n*i
i = i +1
S
S = S * x пока >= ξ
n
S
y = y+
n
y =1
n =1
s=x
i =1

15.

Промежуточные данные
S: вещественное {i-ая степень x}
n: целое {факториал}
i: целое {номер итерации}

16.

При
решении
подобных
использовать массивы:
задач
нельзя
1) Мы не можем заранее знать количество
членов в этой последовательности.
2) Нет необходимости хранить все m членов
этой последовательности, а достаточно
иметь два соседних элемента (текущий и
следующий или текущий и предыдущий).
3) При
переходе
к
следующему
шагу
повторяющихся
вычислений
текущее
значение делают предыдущим и вычисляют
новое текущее значение.

17.

4. Разработка алгоритмов
Алгоритм – это последовательность действий,
которые преобразуют исходные данные в
результаты.
Свойства алгоритма:
─ дискретность;
─ результативность (направленность);
─ массовость;
─ конечность (финитивность);
─ определенность (определенность, точность,
однозначность);
─ корректность.

18.

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

19.

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

20.

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

21.

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

22.

Для записи алгоритма используют такие языки:
1. Вербальный (на естественном языке);
2. Символьный
(псевдокод:
учебный
алгоритмический язык Ершова и др.);
3. Графические (блок (граф)-схемы, ДРАКОНсхемы).
Мы будем рассматривать графический язык
блок-схем.

23.

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

24.

Базовые операторы:
1. Ввод исходных данных
a, b, c
2. Вычисление значений
y := <выражение>
3. Вызов подпрограммы
y := <имя_подпр-мы>
(<список_аргументов>)
<имя_подпр-мы>
(<список_аргументов>)

25.

4. Вывод результатов
"x1=", x1
"x2=", x2
Алгоритм
последовательно
исходные данные в результаты.
преобразует
Если он не может это сделать непосредственно,
то он использует промежуточные вычисления,
которые хранятся в промежуточных данных.

26.

5. Условный оператор
+
<условие>
<действие 1>
+
<действие 1>
-
<действие 2>
<условие>
-

27.

Условный оператор выполняется так:
1) Вычисляется значение условия.
2) Если оно равно "истина", то выполняются
операторы ветки "то" и переход на оператор,
следующий за условным.
3) Если условие равно "ложь", то выполняются
операторы ветки "иначе" (если она есть) и
переход на оператор, следующий за
условным.

28.

6. Оператор цикла
Цикл с известным числом повторений:
i := 1 .. n, <шаг>
<тело_цикла>
Если шаг отсутствует, то он по умолчанию
равен +1

29.

Цикл с неизвестным числом повторений:
С предусловием:
С постусловием:
<условие>
<тело_цикла>
<тело_цикла>
<условие>

30.

Пример 10.
Упрощённая печать степеней 2 в римской
системе счисления.
Изображение
1
I
5
V
10
X
50
L
100
C
500
D
1000
M
Степени двойки
1
I
2
II
4
IIII (допущение)
8
VIII
16
XVI
32
XXXII
64
LXIIII

31.

Начало
y:=1
y < 5000
x:=y
x, " = "
1
2

32.

x >= 1000
'M'
x:=x-1000
x >= 500
+
'D'
x:=x-500
-

33.

x >= 100
'C'
x:=x-100
x >= 50
+
'L'
x:=x-50
-

34.

x >= 10
'X'
x:=x-10
-
x >= 5
+
'V'
x:=x-5

35.

1
2
x >= 1
'I'
x:=x-1
y:=y*2
Конец

36.

Альтернативная графическая запись алгоритма

37.

38.

39.

40.

Пример 11.
Уплотнить строку символов S.
i:=1
S[i] ≠ #
S[i] = " "
+
j:=i
S[j] ≠ #
S[j]:=S[j+1]
j:=j+1
-
i:=i+1