Урок в профильном классе «Рекуррентные соотношения»

Предпросмотр материала:

Выберите файл для просмотра:

Всего файлов: 6

Задача 1

Составить программу, в которой вычисляются первые n членов арифметической прогрессии при условии, что a₁=1/2, d=1/4.

program z_1;

var a,d:real;

n,i:byte;

begin

a:=0.5;

d:=0.25;

write (^,n=^,);

readln (n);

for i:= 2 to n do

begin

a:=a+d;

writeln (I,^,элемент:^,,a:5:2)

end;

end.

Задача 2

Составить программу в которой вычисляются первые n членов последовательности Фибоначи.

program z_2;

var a1,a2,a,n,i:integer;

begin

a1:=1;

a2:=1;

write (^,n=^,);

readln (n);

writeln (^,1 элемент:^,,a1);

writeln (^,2 элемент:^,,a2);

for i:= 3 to n do

begin

a:=a1+a2;

writeln (I,^,’’элемент:^,,a);

a1:=a2;

a2:=a;

end;

end.

Задача 3

Написать программу, в которой вычисляется n –ый элемент последовательности, заданной следующим образом:

B₁=1; b₂=2; b_n= (b_n-1- b_n-2)/(n-1)²

Program z_3;

Var b1,b2,b:real;

n,i:byte;

begin

b1:=1;

b2:=2;

write (^,n=^,);

readln (n);

for i:=3 to n do

begin

b:= (b1-b2)/sgr (i-1);

b1:=b2;

b2:=b;

end;

writeln (n,^,элемент:^,,b:6:3)

end.

Обработка последовательностей

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

Так в задаче Modul4_3 (чтение данных из файла и вывод их на экран) получение очередного элемента сводилось к оператору Read, обработка - к оператору Writeln, а проверка окончания состояла в поиске конца файла.

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

Рассмотрим теперь вопрос, с какого места круга начинать обход. Мы изучили два оператора цикла: while-do и repeat-until. Обход по часовой стрелке запишется в виде:

While <условие продолжения>
do
begin
<обработка элемента>;
<получение очередного элемента>;
end;

Repeat
<обработка элемента>;
<получение очередного элемента>;
until <условие завершения>;

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

Пример.
Будем считать, что исходные данные представляют собой последовательность чисел в текстовом файле. Требуется вывести на экран минимальное из вводимых из файла чисел.
Как и раньше в задаче Modul4_3, получение очередного элемента сводится к его вводу, проверка окончания - к поиску признака конца файла, а вот обработка элемента записывается сложнее. Пусть переменная Minimum хранит минимальное из введенных чисел. Тогда этап обработки элемента должен иметь вид:

{Обработка элемента}
read (f, a);
If Minimum>a then Minimum:=a;

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

Program Modul4_4;
var
f: text;
a,minimum: integer;
begin
{Открытие файла для чтения}
assign (f, 'input.txt');
reset (f);
{Чтение первого элемента}
read (f, a);
minimum:=a;
{Перебор остальных элементов}
while not (eof(f))
do
   begin
    read (f, a);
    if minimum>a
      then minimum:=a;
   end;
{Вывод результата на экран}
writeln (minimum);
close (f);
end.

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

Разберем теперь случай, когда проверку окончания можно организовать только после обработки очередного элемента. Тогда круг из трех действий следует проходить против часовой стрелки, а сам цикл запишется в виде:

While <условие продолжения>
do
begin
<получение очередного элемента>;
<обработка элемента>;
end;

Repeat
<получение очередного элемента>;
<обработка элемента>;
until <условие завершения>;

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

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

Program Modul4_5;
var
f: text;
s, a: integer;
begin
{Открываем файл для чтения}
assign (f, 'input.txt');
reset (f);
{Задаем стартовое значение суммы}
s:=0;
{Читаем числа из файла и суммируем их до тех пор, пока сумма не превысит 100 или не будет встречен конец файла}
repeat
read (f, a);
s:=s+a;
until (s>100) or (eof(f));
{Проверяем ситуацию выхода из цикла}
if s>100
then writeln ('Сумма превысила 100 и составила ',s)
else writeln ('Сумма всех чисел не достигла 100');
close (f);
end.

Обработка рекуррентной последовательности

Говорят, что элементы $a_{1}$ , $a_{2}$ , …, $a_{n}$ , … образуют рекуррентную последовательность -того порядка, если заданы первые членов последовательности $a_{1}$ , $a_{2}$ , …, $a_{k}$ , а для : $a_{n}=f(a_{n-1},\cdots,a_{n-k})$ , где — некоторая функция аргументов.

Известным примером рекуррентной последовательности второго порядка является последовательность чисел Фибоначчи, для которой $a_{1}=a_{2}=1$ , а для : $a_{n}=a_{n-1}+a_{n-2}$ .

Применительно к рекуррентным последовательностям часто ставится задача найти -й элемент последовательности. Для решения этой задачи достаточно хранить в памяти элемент последовательности. Решение задачи разбивается на два основных этапа: начальную установку и продвижение по последовательности.

Для вычисления чисел Фибоначчи первый этап выглядит следующим образом:
a:=1; b:=1
Продвижение по последовательности на один элемент вперед выполняется так:

for k:=3 до n do
begin
c:=a+b;
a:=b;
b:=c;
end;

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

program Modul4_9;
var
n, f, a, b, c, k: integer;
begin
writeln ('Введите число n');
readln ( n );
a:=1; b:=1
for k:=3 to n do
begin
c:=a+b;
a:=b;
b:=c
end;
f:=c;
writeln (n, '-й член последовательности Фибоначчи равен ', f);
end.

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

Рассмотрим задачу суммирования ряда: $S=1+\frac{1}{2}+\frac{1}{4}+\cdots +\frac{1}{2^{n}}=\sum_{k=0}^{n}\frac{1}{2^{k}}$

Конечно, можно для каждого слагаемого вычислять $2^{k}$ , но тогда время суммирования сильно возрастет. Вычисление можно ускорить, если воспользоваться соотношением: $2^{k}=2^{k-1} \cdot 2$ . Слагаемые ряда можно определить при помощи рекуррентной последовательности первого порядка:

$a_{0}=1$ , $a_{k}=\frac{a_{k-1}}{2}$ .

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

program Modul4_10;
var
n, k: integer;
a, s: real;
begin
writeln ('Введите целое число n');
readln ( n );
a:=1;
s:=a;
for k:=1 to n do
begin
a:=a/2;
s:=s+a;
end;
writeln ('Сумма равна ', s:5:3);
end.

1/9

Урок в профильном классе «Рекуррентные соотношения»

Список задач к уроку «Рекурретнные соотношения»

1 уровень

1. Составить программу, в которой вычисляются первые n членов арифметической прогрессии при условии, что a₁=1/2, d=1/4.

2. Составить программу, в которой вычисляются первые n членов геометрической прогрессии при условии, что в₁=1, g=2.

2 уровень

1. Составить программу в которой вычисляются первые n членов последовательности Фибоначи. (Известным примером рекуррентной последовательности второго порядка является последовательность чисел Фибоначчи, для которой $a_{1}=a_{2}=1$ , а для : $a_{n}=a_{n-1}+a_{n-2}$ .)

2. Написать программу, в которой вычисляется n –ый элемент последовательности, заданной следующим образом:

b₁=1; b₂=2; b_n= (b_n-1- b_n-2)/(n-1)²

3. Амебы

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

Формат входных данных

На вход программе подается единственное целое число ( n). Гарантируется, что делится на 3.

Формат выходных данных

Выведите единственное число - ответ на задачу.

Примеры:

Вход

Выход

4. Винни Пух

На каждом следующем дне рождения Винни Пух съедает столько же меда, что и на двух предыдущих. На двух первых днях рождения у Пяточка и у Кролика он съел по 100 г меда. Написать программу, определяющую, сколько килограммов меда съест Винни Пух на -ом дне рождения.

Формат входных данных

Во входном файле задано единственное число ( $1 \le N \le 40$ ).

Формат выходных данных

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

Примеры:

Вход

Выход

0.1

Вход

Выход

0.3

5. Богатый дядюшка

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

Формат входных данных

На вход программе подается единственное число $N(1 \le N \le 20)$ .

Формат выходных данных

Выведите единственное число - ответ на задачу.

Примеры:

Вход

Выход

Вход

Выход

Домашнее задание

Татьяна Ларина

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

Формат входных данных

На вход программе подается единственное число $O (1 \le O \le 10^9)$ , подсчитанное Татьяной.

Формат выходных данных

Выведите единственное число - ответ на задачу.

Примеры:

Вход

Выход

Урок в профильном классе «Рекуррентные соотношения»

Информатика

Конспекты

RAR

03.12.2012

2571

Информатика

Конспекты

Файл будет скачан в формате:

RAR

Автор материала

Шевченко Ольга Викторовна

учитель информатики

На сайте: 11 лет и 2 месяца
Всего просмотров: 3689
Подписчики: 1
Всего материалов: 2

3689
просмотров
2
материалов
1
подписчиков

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