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

Выберите документ из архива для просмотра:

~$исок задач к уроку.docx Задача 1.docx Обработка последовательностей.docx Обработка рекуррентной последовательности.docx Рекуррентные соотношения.pptx Список задач к уроку.docx

Выбранный для просмотра документ Задача 1.docx

Задача 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.

Скачать материал

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

Как учитель может зарабатывать на Инфоуроке?

Выбранный для просмотра документ Обработка последовательностей.docx

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

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

Так в задаче 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.

Скачать материал

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

Как учитель может зарабатывать на Инфоуроке?

Выбранный для просмотра документ Обработка рекуррентной последовательности.docx

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

Говорят, что элементы $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.

Скачать материал

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

Как учитель может зарабатывать на Инфоуроке?

Выбранный для просмотра документ Рекуррентные соотношения.pptx

Скачать материал

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

Описание презентации по отдельным слайдам:

1 слайд

Рекуррентные соотношения
практикум
2 слайд

задача 1
3 слайд

Задача 2
4 слайд

Задача 3
5 слайд

Решение задачи 1
program Z_1;
var n,x,i: integer;
input, output:text;
begin
assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);
readln(n);
x:=1;
for i:=1 to n div 3 do x:=x*2;
writeln(x);
close(input);
close(output);
end.
6 слайд

Задача 4
7 слайд

Решение задачи 2
program z_2;
var n,i:byte;
a,c,b:real;
input, output:text;
begin
assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);
readln (n);
a:=0.1;
b:=0.1;
if n<3 then c:=a;
for i:=3 to n do
begin
c:=a+b;
a:=b;
b:=c;
end;
writeln (c:5:1);
close(input);
close(output);
end.
8 слайд

Решение задачи 3
program z_3;
var p,p1,s:longint;
n,d:integer;
f,g:text;
BEGIN
assign(f,'input.txt');
reset(f);
Readln(f,n);
close(f);
p1:=1;
d:=2;
s:=1;
while d<=n do
begin
p:=p1*2+d;
s:=s+p;
p1:=p;
d:=d+1;
end;
assign(g,'output.txt');
rewrite(g);
writeln(g,s);
close(g);
END.
9 слайд

Решение задачи 4
Program z_4
var s,i:longint;
O:longint;
Input, output:text;
begin
assign(input,'input.txt');
assign(output,'output.txt');
reset(input); rewrite(output);
read(O);
s:=0;
i:=1;
while S<O do begin
s:=s+i;
i:=i+1;
end;
writeln(i-1);
close(input);
close(output);
end.

Выбранный для просмотра документ Список задач к уроку.docx

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

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)$ , подсчитанное Татьяной.

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

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

Примеры:

Вход

Выход

Скачать материал

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

Как учитель может зарабатывать на Инфоуроке?

Краткое описание документа:

Данный материал поможет ввести понятие и возможности работы с рекуррентными соотношениями, а также приводится подборка задач с решениями (в презентации) для отработки данной темы в профильном классе 10 классе. Обработка последовательностей - весьма распространенная задача в программировании. В подобных задачах требуется чередовать три действия: чтение данных из файла и вывод их на экран, получение очередного элемента сводилось к оператору Read, обработка - к оператору Writeln, а проверка окончания состояла в поиске конца файла. Перечисленные действия должны выполняться циклически, то есть по кругу. Круг этот можно проходить в двух направлениях: по ходу часовой стрелки и против хода часовой стрелки. Выбор направления обхода зависит от того, можно ли произвести проверку окончания до обработки элемента. Если можно, то круг следует проходить по ходу часовой стрелки.

Скачать материал

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 653 902 материала в базе

Найти материалы

Скачать материал

Другие материалы

zip

Урок + презентация по теме «Поиск информации в сети Интернет»

Рейтинг: 5 из 5

01.12.2012
5959
12

docx

Практические работы для 10 класса (профильный уровень) на тему «Операции с файлами и папками»

30.11.2012
16027
92

rar

Презентация «Графический редактор Paint»

30.11.2012
4805
3

docx

Конспект урока на тему «Шаблоны, стили и оглавление в Microsoft Word»

30.11.2012
7730
103

pptx

Социальный проект на тему «Дневник.ру КАЖДОМУ!»

29.11.2012
1621
3

docx

Доклад на тему «Использование системно-деятельностного подхода на уроках информатики»

29.11.2012
4292
3

rar

Рабочие программы по информатике 5-9 класс

27.11.2012
3377
0

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

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

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Автор материала

Шевченко Ольга Викторовна
- На сайте: 9 лет и 3 месяца
- Подписчики: 1
- Всего просмотров: 2733
- Всего материалов: 2