Организация вычислений с помощью рекуррентных соотношений

1.20M

Категория:

Программирование

Похожие презентации:

Вычисление суммы. Вычисление элементов последовательности

Циклы по условию на языке Pascal

Система программирования PascalABC.NET. Простейшие новые возможности

Алгоритмы и программы. Тестирование. Аналитическая верификация

Расширенный алгоритм Евклида. Разбор задач

Рекуррентные алгоритмы. Основы программирования

Введение в программирование на языке Pascal

Вычислительная математика. Лекция 6

Языки программирования QBasic и Turbo Pascal 7.0

понятие подпрограмм. Механизм реализации подпрограмм с помощью процедур и функций

Лекцция_8_2_Организация вычислительных процессов

1. ОРГАНИЗАЦИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

Половина И.П.
доцент, к.т.н.

2.

Циклы предусматривают выполнение
некоторых операторов несколько раз.
В языке предусмотрено несколько способов
организации циклов:
с предусловием
с послесловием
с параметрами
_
пц:= нз,кз,ш
?
S
+
S
S
_
?
+

3. ЦИКЛ С ПРЕДУСЛОВИЕМ

WHILE <лог_выр> DO <оператор>; !!!!
Указанный оператор выполняется до тех пор, пока
условие (лог_выр) истинно.
Если при выполнении этого цикла условие ложно
сразу же, то тело цикла не выполняется ни разу.
Здесь <оператор> может быть как простым, так и
составным, т.е. операторы (!) заключаются в
операторные скобки begin - end..

4. ЦИКЛ С ПОСЛЕСЛОВИЕМ

REPEAT<операторы> UNTIL<условие>;
В цикле условие проверяется после выполнения тела
цикла.
При этом тело цикла выполняется хотя бы один раз
или много.

5. ЦИКЛ С ПАРАМЕТРОМ

FOR <п.ц> := <нз> TO <кз> DO <оператор>;
Здесь П.Ц - параметр цикла - переменная любого
скалярного типа, кроме вещественного;
нз, кз - выражения, тип совпадает с типом параметра
цикла.
TO - шаг: +1;
DOWNTO - шаг: -1.

6. Операторы: break, continue, exit

• Оператор break вызывает немедленный выход из цикла.
Используется, если обнаружена нецелесообразность
дальнейшего выполнения тела цикла (лучше заменить
командой exit).
• Оператор continue немедленно передает управление
заголовку цикла. Оставшаяся часть тела цикла не
выполняется.
• Оператор exit. Единственное назначение – немедленно
завершить работу той программной единицы, в которой
он встретился.

7. LOOP n DO FOR-TO-STEP-DO

8. НОД – наибольший общий делитель

НОД нужен, когда надо найти «максимально крупное
единое звено», на которое без остатка делятся два или
больше числа.
Сокращение дробей - это самый наглядный и частый
случай. Чтобы дробь a/b стала несократимой, числитель и
знаменатель делят на их НОД:

9.

Приведение дробей к общему знаменателю
Чтобы сложить
можно использовать общий
знаменатель b⋅d, но он часто получается слишком
большим.
Более «экономный» общий знаменатель — это НОК
(наименьшее общее кратное), который легко выразить
через НОД:
То есть НОД нужен как промежуточный шаг, чтобы
получить наименьший возможный общий знаменатель.

10.

В программировании и алгоритмах:
• Упрощение вычислений. Если в формуле встречается дробь, её сокращение
уменьшает риск переполнения и делает числа меньше.
• Проверка взаимной простоты. Если НОД(a,b)=1, то числа называют
взаимно простыми — это важно, например, в криптографии и при выборе
параметров для хеш-функций.
• Работа с пропорциями и масштабированием. Например, если нужно
масштабировать прямоугольник a×b так, чтобы пропорции сохранились, а
размеры были целыми, используют деление на НОД: новые размеры будут
a/НОД и b/НОД.
• Расписание и периодичность. Если одно событие происходит каждые 6
дней, а другое — каждые 8 дней, то они совпадут через НОК(6,8)=24 дня. А
чтобы понять, насколько «согласованы» периоды, смотрят на НОД(6,8)=2:
чем больше НОД, тем чаще совпадения.
• Массивы и шаги циклов. Иногда шаг цикла выбирают так, чтобы он был
делителем длины массива — НОД помогает проверить, покроет ли такой шаг
весь массив без пропусков.

11.

Алгоритм Евклида на делении с остатком
(более практичный)
Идея: НОД(a, b) = НОД(b, a mod b).
Остаток от деления «быстро уменьшает» числа, и алгоритм
сходится за очень малое число шагов.
while n <> 0 do
begin
m := m mod n;
Swap(m, n);
end;

12. Алгоритм Евклида на вычитании

Идея: НОД не меняется, если из большего числа
вычесть меньшее. Повторяя это, приходим к двум
одинаковым числам — это и есть НОД.
Формально:
НОД(a, b) = НОД(a−b, b) при a > b.
while m <> n do
if m > n then m := m - n
else n := n - m;
//В конце m - НОД

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

При решении задач на вычисление сумм
(произведений) членов конечных или бесконечных
последовательностей, вычисления пределов
последовательностей, наибольшую трудность
представляет получение рекуррентной формулы.
Далеко не во всех задачах закономерность,
связывающая предыдущий и последующий члены
последовательности, очевидна, как, например, в
последовательности: Х, Х2 , Х3 , Х4 ,… Хn

14.

Примеры рекуррентной последовательности:
1). арифметическая прогрессия.
Рекуррентное соотношение: аn = аn – 1 + d ,
где d – разность прогрессии;
2). геометрическая прогрессия.
Рекуррентное соотношение: bn = bn – 1 * q ,
где q – знаменатель прогрессии;
3). последовательности Фибоначчи.
Рекуррентное соотношение: аn = аn – 1 + аn – 2 ,
где а1 = а2=1;

15.

Пример 1. Общий член ряда известен.
1 ; 1 ; … 1
Дан
следующий ряд: 1; 2! 3!
.
n!
Получить рекуррентное соотношение для данного ряда
и разработать программу для вычисления суммы n
заданных элементов ряда

16.

17.

Пример 2. Общий член ряда неизвестен.
1
1
an = n + n .
5
4

18.

Фрагмент кода:
Можно было бы вспомнить математику:
НО:

19.

Вычислить сумму ряда s = 1/a + 2/a2 +… + 12/a12 при заданном значении а
i=
1 2 …. 12
Числитель совпадает с i
Рассмотрим знаменатели: pn = an , pn-1 = an-1
Рекурентное отношение: pn = pn-1 *a

20.

Вычислить сумму ряда s = 1/a + 2/a2 +… + 12/a12 при заданном значении а
начало
Ввод a
s := 0
p := 1
i:=1,12,1
p:= p*a
s := s + i/p
Вывод s
конец

21.

Сумма =:

22.

23.

Вычислить сумму знакопеременного ряда s=1-1/2+1/3-1/4+…
Вычисления производить до тех пор, пока очередное слагаемое
по модулю не станет < ε. А сколько шагов надо сделать?
начало
Ввод е
s:= 0; z:=1; i:=1
e:=0.01;
abs(1/i)=>e
+
s:= s+z/i;
i:=i+1
z := -z
конец

24.

Дана последовательность. Найти произведение a0a1…a14 , где a0 = a1 =1, ai = ai-2+ai-1/2i-1
(в массивах)
var
i:integer;
a0,a1,a2,p:real;
begin
a0:=1; a1:=1;
p:=a0*a1;
i:=2;
while i<=14 do
begin
a2:=a0+a1/power(2,i-1);
p:=p*a2;
a0:=a1;
a1:=a2;
inc(i);
end;
writeln('',p:10:4);
end.
начало
a0:=1; a1:=1;
p:=a0*a1
i:=2
i<=14
+
a2:=a0+a1/2i-1
p:=p*a2
«Перезапоминаем»
данные
a0:=a1
a1:=a2
i:=i+1
Вывод(p)
p=
413.1202
конец

25.

начало
Ввод (x)
s:=0; e=0,001
n:=1
a:=x
a=>e
+
s:=s+a
n:=n+1
a= - a*x/n
Вывод(s)
конец

26.

const e=0.005;
var s,a,x:real;
n:integer;
begin
write(' при x= ');read(x);
writeln;
s:=0; n:=1;
a:=x;
while abs(a)>e do
begin
s:=s+a;
inc(n);
a:=-a*x/n;
writeln(' n= ',n,' a= ',a:6:4);
end;
writeln(' s = ',s:6:3);
end.

27. ВЛОЖЕННЫЕ ЦИКЛЫ

Циклы могут быть вложены друг в друга.
Алгоритм работы:
i:=1,n,1
i := 1;
j:=1,n,1
j:=1, 2,…n
s
i:= 2;
j:=1, 2,…n
……

28.

Разработать программы:
(i < j) and (i + j < n + 1)
(j > i) and (i + j > n + 1)
i=j
1)
i+j=n+1
2)
3)
(i > j) and (i + j > n + 1)
4)
5)
6)
7)

29.

30.

Задача: Составить программу вычисления значений
функции у = х1· х2 логического умножения для
различных значений аргументов и результаты вывести в
виде таблицы:
начало
x1
x2
y
Вывод заголовка
0
0
0
x1:=0, 1
0
1
0
x2:=0, 1
1
0
0
1
1
1
y:= x1*x2
В редакции PascalABC:
Вывод(x1,x2)
0 – False;
1 – True.

31.

var
x1,x2,y:integer;
begin
writeln (' x1
x2
y ');
writeln ('---------------------------');
for x1 := 0 to 1 do
for x2 := 0 to 1 do
begin
y:=x1 * x2;
writeln (x1:8, x2:8, y:8)
end
end.
В этом цикле только один
оператор For, поэтому
операторных скобок
begin-end нет