1493346
столько раз учителя, ученики и родители
посетили сайт «Инфоурок»
за прошедшие 24 часа
Добавить материал и получить бесплатное
свидетельство о публикации
в СМИ №ФС77-60625 от 20.01.2015
ИнфоурокИнформатикаКонспектыУрок в профильном классе «Рекуррентные соотношения»

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

ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону N273-ФЗ «Об образовании в Российской Федерации» педагогическая деятельность требует от педагога наличия системы специальных знаний в области обучения и воспитания детей с ОВЗ. Поэтому для всех педагогов является актуальным повышение квалификации по этому направлению!

Дистанционный курс «Организация работы с обучающимися с ограниченными возможностями здоровья (ОВЗ) в соответствии с ФГОС» от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (72 часа).

Подать заявку на курс

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

библиотека
материалов

Задача 1

Составить программу, в которой вычисляются первые n членов арифметической прогрессии при условии, что a1=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 –ый элемент последовательности, заданной следующим образом:

B1=1; b2=2; bn= (bn-1- bn-2)/(n-1)2

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

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

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

Для вычисления чисел Фибоначчи первый этап выглядит следующим образом:
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

библиотека
материалов
Решение задачи 3 program z_3; var p,p1,s:longint; n,d:integer; f,g:text; BEGI...
задача 1
Задача 2
Задача 3
Решение задачи 4 Program z_4 var s,i:longint; O:longint; Input, output:text;...

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

1 слайд Решение задачи 3 program z_3; var p,p1,s:longint; n,d:integer; f,g:text; BEGI
Описание слайда:

Решение задачи 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.

2 слайд задача 1
Описание слайда:

задача 1

3 слайд Задача 2
Описание слайда:

Задача 2

4 слайд Задача 3
Описание слайда:

Задача 3

5 слайд Решение задачи 4 Program z_4 var s,i:longint; O:longint; Input, output:text;
Описание слайда:

Решение задачи 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.

6 слайд
Описание слайда:

7 слайд
Описание слайда:

8 слайд
Описание слайда:

9 слайд
Описание слайда:

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

библиотека
материалов

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

1 уровень

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

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

2 уровень

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

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

b1=1; b2=2; bn= (bn-1- bn-2)/(n-1)2

  1. Амебы

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

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

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

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

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

Примеры:

Вход

9

Выход

8

  1. Винни Пух

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

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

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

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

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

Примеры:

Вход

1

Выход

0.1

Вход

4

Выход

0.3

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

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

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

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

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

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

Примеры:

Вход

1

Выход

1

Вход

5

Выход

99


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


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

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

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

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

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

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

Примеры:

Вход

6

Выход

3


Курс профессиональной переподготовки
Учитель информатики
Почему учителям и воспитателям следует проходить курсы повышения квалификации и профессиональной переподготовки в учебном центре «Инфоурок» ?

• Огромный каталог:  677 курсов профессиональной переподготовки и повышения квалификации;
• Очень низкая цена, при этом доступна оплата обучения в рассрочку – первый взнос всего 10%, оставшуюся часть необходимо оплатить до конца обучения;
• Вы можете начать обучение уже сегодня (группы формируются ежедневно);
• Курсы проходят полностью в дистанционном режиме (форма обучения в документах не указывается);
• Возможность оплаты курса за счёт Вашей организации.
• Дипломы и Удостоверения от проекта «Инфоурок» соответствуют всем установленным законодательству РФ требованиям. (Согласно ФЗ «Об образовании в Российской Федерации» от 2012 года).
Найдите материал к любому уроку,
указав свой предмет (категорию), класс, учебник и тему:
также Вы можете выбрать тип материала:
Краткое описание документа:
Данный материал поможет ввести понятие и возможности работы с рекуррентными соотношениями, а также приводится подборка задач с решениями (в презентации) для отработки данной темы в профильном классе 10 классе. Обработка последовательностей - весьма распространенная задача в программировании. В подобных задачах требуется чередовать три действия: чтение данных из файла и вывод их на экран, получение очередного элемента сводилось к оператору Read, обработка - к оператору Writeln, а проверка окончания состояла в поиске конца файла. Перечисленные действия должны выполняться циклически, то есть по кругу. Круг этот можно проходить в двух направлениях: по ходу часовой стрелки и против хода часовой стрелки. Выбор направления обхода зависит от того, можно ли произвести проверку окончания до обработки элемента. Если можно, то круг следует проходить по ходу часовой стрелки.
Общая информация

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

Курс повышения квалификации «Табличный процессор MS Excel в профессиональной деятельности учителя математики»
Курс повышения квалификации «Методика преподавания информатики в начальных классах»
Курс повышения квалификации «Организация работы по формированию медиаграмотности и повышению уровня информационных компетенций всех участников образовательного процесса»
Курс повышения квалификации «Облачные технологии в образовании»
Курс профессиональной переподготовки «Информационные технологии в профессиональной деятельности: теория и методика преподавания в образовательной организации»
Курс профессиональной переподготовки «Управление в сфере информационных технологий в образовательной организации»
Курс профессиональной переподготовки «Математика и информатика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Современные тенденции цифровизации образования»
Курс повышения квалификации «Современные языки программирования интегрированной оболочки Microsoft Visual Studio C# NET., C++. NET, VB.NET. с использованием структурного и объектно-ориентированного методов разработки корпоративных систем»
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.
Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.