100732

Рекурентні послідовності

Конспект урока

Информатика, кибернетика и программирование

Ознайомити з рекурентними послідовностями, формувати вміння та навики створювати і реалізовувати програми з оператором циклу задач з рекурентними послідовностями мовою Паскаль. Вказівка повторення з передумовою — while

Украинкский

2018-02-10

127 KB

0 чел.

Клас 10-А          Урок №56/1

ТЕМА. РЕКУРЕНТНІ ПОСЛІДОВНОСТІ.

Мета:

Навчальна. Ознайомити з рекурентними послідовностями, формувати вміння та  навики створювати і реалізовувати програми з оператором циклу задач з рекурентними послідовностями мовою Паскаль.

Розвиваюча. Розвивати логічне мислення, самостійність, вміння застосовувати набуті знання до практичних завдань.

Виховна. Виховувати наполегливість, естетичність у оформленні, грамотно висловлювати свої думки, вміння раціонально використовувати час.

Тип уроку:Засвоєння нових знань, вмінь і навичок.

План уроку

1. Організаційний момент. Актуалізація опорних знань (5 хв.)

2. Вивчення нового матеріалу. (25 хв.)

3. Розв’язування задач. (10 хв.)

4. Перевірка первинного засвоєння знань. (3 хв.)

5. Підведення підсумків уроку. Повідомлення домашнього завдання. (2 хв.)

Хід уроку

1. Організаційний момент. Актуалізація опорних знань (5 хв.)

І.  Тест.

ІІ. Питання.

 

  1. Поясніть синтаксис і правила виконання оператора циклу з передумовою.
  2. Поясніть синтаксис і правила виконання оператора циклу з післяумовою.
  3. Поясніть структуру і правила виконання оператора циклу з параметром.

        III.Вказівка повторення з передумовою (Цикл— while )

Вказівка повторення з передумовою — while призначена для організації багатократного виконання групи вказівок (тіло циклу) до тих пір, поки залишається істинною умова виконання циклу.

Значення службового слова while — поки

 

Синтаксис оператора while:

while <умова> do <оператор>;

де <умова> - вираз логічного типу;

<оператор> - простий або складений оператор Паскаля.

 

Вказівка повторення з післяумовою (Цикл-repeat-until)

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

Синтаксис оператора repeat:

repeat <оператори> until <умова>;

де <умова> - вираз логічного типу;

<оператор> - послідовність операторів Паскаля, яка складає тіло циклу.

 

Вказівка повторення з параметром виконується таким чином:

1. Вказівка For — to — do.

Наприклад.

for і:=K to N do

begin

 <вказівка1>;

 <вказівка2>;

 …...............

  <вказівка N>;

end;

Параметру циклу і присвоюється початкове значення К. Він порівнюється з кінцевим значенням N. Якщо К<=N, то виконується тіло вказівки повторення. Значення К автоматично збільшується на 1 (тобто стає наступним елементом) і знову порівнюється зі значенням N. Якщо під час перевірки отримаємо, що К>N, то виконання вказівки повторення припиняється і виконується наступна після неї вказівка програми. Якщо під час першого порівняння К і N виявиться що К>N, то тіло вказівки не виконується жодного разу.

2. Вказівка For — downto — do.

Наприклад.

for і:=К downto to N do

begin

<вказівка1>;

<вказівка2>;

…...............

<вказівка N>;

end;

Параметру циклу і присвоюється початкове значення К. Він порівнюється з кінцевим значенням N. Якщо К>=N, то виконується тіло вказівки повторення. Значення К автоматично зменшується на 1 (тобто стає попереднім елементом) і знову порівнюється зі значенням N. Якщо під час перевірки отримаємо, що К<N, то виконання вказівки повторення припиняється і виконується наступна після неї вказівка програми. Якщо під час першого порівнення К і N виявиться, що К<N, то тіло вказівки не виконується жодного разу.

  1. Вивчення нового матеріалу. (25 хв.)

Серед задач, для розв'язування яких необхідна побудова циклічних конструкцій, велику частку займають задачі додавання, до яких належать задачі обчислення п-го члена (суми п членів) арифметичних та геометричних прогресій та обчислення суми нескінченних числових рядів.

 

Рекурентний спосіб задання послідовностей

У математиці серед «золотих» чисел почесне місце посіли числа Фібоначчі (Леонардо Пізанський, XIII ст.). Кажуть, що свого часу відомий учений в послідовності цих чисел відобразив закон розмноження кроликів. Ці числа мають такий вигляд:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,... .

Можна помітити, що, починаючи з третього числа, кожне наступне дорівнює сумі двох попередніх. Тобто, починаючи з третього члена цієї послідовності існує така залежність:

Fnew   =Fold1+Fold2.

Залежність нового значення члена послідовності від певної кількості попередніх називається рекурентною, а програми, які обчислюють ці значення, називаються відповіднорекурентними.

Формули, що виражають черговий член послідовності через один чи декілька попередніх членів, називаються рекурентними співвідношеннями: a[n]=F(a[n-1]).

Як обчислити n-ний член послідовності, заданої рекурентним співвідношенням? Якщо простої формули немає чи вона невідома, членени послідовності обчислюють за рекурентним співвідношенням один за одним від і=1  до і=n.

Найвідомішим прикладом рекурентних послідовностей є арифметичні та геометричні прогресії.

Алгоритм обчислення n-ного члена прогресії

Означення арифметичної прогресії:

а[0]=а;

a[n]=a[n-l]+d; n=1,2,...

Задаємо позначення:

А - перший член послідовності;

d - різниця арифметичної прогресії;

N - номер поточного члена прогресії;

К -задана кількість членів;

S - сума N членів прогресії.

Алгоритм обчислення n-го члена послідовності та суми n членів складається з виконання таких дій:

  • задаються початкові значення члена послідовності Ао, різниці , кількості членів, які потрібно обчислити;
  • задаються початкові значення лічильнику членів послідовності (N:=0) і сумі (S:=0);
  • поки номер N члена послідовності, який обчислено, не досягне значення К -заданої кількості членів, повторюються дії: номер поточного члена збільшується на 1; обчислюється значення наступного члена А; обчислене значення А додається до суми S.

Блок-схема алгоритму наведена на малюнку.

При обчисленні п-го члена комірка А містить поточне значення величини.

 

Приклад 1. Робота з блок-схемою. Дана послідовність 3, 7, 11, 15... Які значення потрібно надати A, d, К, щоб отримати суму 10 членів цієї послідовності?

Рекурентна залежність: Аn = Аn-1 + 4; Ао= -1.

Програма, складена за блок-схемою, має такий вигляд:

Var A, d, S : Real;   к, N : integer;

Begin

A:= -1;

k:=10;

d:= 4;

S:=0;

For N:=1 то к Do

Begin

     A := A + d;

     S := S + A

End;

           writeln ('s=’, S);

End.

 

Приклад 2. Розглянемо послідовність 2, 3, 5, 9, 17...

Рекурентна залежність: An=2*An-1-1; А1=2 А0=1.5

Наступний цикл призначений для обчислення 10-го члена послідовності:

А:=1.5;

For і:=1 То 10 Do А:=2*А-1;

 

Приклад 3. Числами Фібоначчі називають числа, які знаходять за таким правилом: F[1] = F[2] = 1; F[n]=F[n-1] + F[n-2].

Ряди Фібоначчі завжди відігравали велику роль у математиці.

Якщо послідовно ділити два поточних останніх члени ряду один на одного, то будемо одержувати результат, відомий за назвою "золотий перетин".

Для обчислення N-гo числа використовується така ідея:

■ виділяються комірки А і В для збереження F[n-1 ] і F[n-2];

■ сума A+B заноситься в комірку С;

■ на наступному кроці циклу В= F[n-1]  стає (n-2)-м членом, тому А:=В; С= F[n] стає (n-1)-м членом, тому В:=С;

F[1] = F[2] = 1, тому обчислення починається з N=3.

Дана програма призначена для обчислення 10 перших чисел Фібоначчі:

Begin

A:=1; Writeln (А);

B:=1;  writeln (B);

For n:=3 То 10 Do

Begin

С:=А+В;

А:=В;

В:=С;

Writeln (С)

        End;

        End.

Для визначення номера першого числа Фібоначчі, яке більше 1000, потрібен цикл з післяумовою:

А:=1; В:=1;

Repeat

   С:=А+В; А;=В; В:=С;

until С > 1000;

Writeln (С);

3. Розв’язування задач. (10 хв.)

Задача 1. Знайти суму ряду, загальний член якого

аn =2*(n!)2 / (3*(2n)! з точністю є=10-3.

n! - це факторіал натурального числа n.

Факторіал обчислюється за формулою:

n! = 1*2*3*...*п.

1) При визначенні суми членів ряду варто використовувати рекурентну формулу для одержання наступного члена ряду. Для одержання рекурентної формули можна обчислити відношення наступного члена ряду до поточного:

аn+1/an=(2((n + 1)!)2-3(2n)!)/3(2n + 2)!*2(n!)2= (n + 1)/2(2n+1)

звідки аn+1=аn*(n+1)/(2(2n+1))

2)  При складанні програми будемо вважати, що точність досягнута, якщо |аn| < є. Якщо поточний доданок менше заданої величини точності, це означає, що |Sn+1-Sn | < є, і подальше обчислення не має сенсу.

3) Опишемо змінні та константи, потрібні для розв'язування задачі:

Program Sum;

 Const Е=0.ІЕ-3;

  Var N: integer; An, Summa: Real;

Задамо початкові значення змінних. При N = 1 An дорівнює 1/3.

Begin

Summa := 0; N := 1; An := 1/3;

4) Цикл виконується доти, поки |аn| < є. В тілі циклу поточне значення доданку додається до значення Summa, обчислюється наступне значення An, номер N члена ряду збільшується на 1.

While Abs(An)>E Do

Begin

  Summa:=Summa+An;

N:=N+1;

An:=An*(N+i)/2/(2*N+l)

       End;

 WriteLn ('Сума=', Summa:6:3, 'An=!,An);

       End.

5)        Виконайте програму. Протокол роботи програми:

Сума 0.473 Аn=4.113534Е-05

Значення Аn виведено у формі з плаваючою крапкою. Укажіть формат виведення для Аn таким чином, щоб значення виводилось з трьома десятковими знаками.

6) Внесіть до основної програми такі зміни, щоб разом із загальною сумою на екран виводилося значення поточного члена послідовності.

Задача 2. Скласти програму обчислення n-го члена послідовності 3, 6, 12, ...

1. Елементи даної послідовності підлягають рекурентній залежності Аn=2 • Аn-1 (тобто послідовність є геометричною прогресією зі знаменником 2). А0=1. Складіть програму, користуючись блок-схемою алгоритму обчислення n-го члена прогресії. Обчисліть 10-й член послідовності.

2. Чому дорівнює сума перших 13 членів даної послідовності?

Додайте до тіла циклу оператор для обчислення значення суми, змініть діапазон зміни параметра в операторі For на 1..13.

3. Чому дорівнює сума A1+A3+A5+А7?

Одним з можливих способів розв'язування цього завдання може бути такий: розглянемо підпослідовність A1 A3, А5, А7 заданої геометричної прогресії. Елементи підлягають рекурентній залежності А3=А1*22 і т.д. Цикл потрібно повторити 4 рази:

S:=0; А:=1;

For n:=1 То 4 Do

       Begin

А:=А*4;

S:=S+A

    End;

4.Який номер має елемент послідовності, який дорівнює 768?

Для визначення номера члена прогресії, який дорівнює 768, потрібен цикл з післяумовою:

A:=l; N:=0;

Repeat

  А:=А*2;

  N:=N+1;

Until А=768; Writeln (N);

5. Обчисліть кількість членів прогресії, які дають в сумі 6141.

Для розв'язуваня цього завдання до циклу, складеного в попередньому пункті, потрібно додати оператор обчислення суми і змінити умову виходу з циклу:

S:=0; A:=l; N:=0;

Repeat

 А:=А*2;

 N:=N+1;

 S:=S+A

Until S = 6141;

Writeln (N);

Дана геометрична прогресія, перший член якої а=0.32, знаменник q=0.4. Внесіть зміни до програми і знайдіть номер члена даної прогресії, величина якого дорівнює 3.3554432*10-5.

4. Перевірка первинного засвоєння знань. (3 хв.)

1. Які послідовності називають рекурентними ?

2. Випишіть рекурентні співвідношення і продовжіть вліво послідовності:

а)   1, 2, 6, 24, 120, 720, 5040,

б) 1, 4, 11,26,57, 120, 247,

в)  1, 1, a 1, -1, 2, -З, 5, -8, 13, -21, ...

3. Заповніть пропуски в програмі, що підсумовує 6 членів послідовності: 1, -1, -3, -5...

А:=...; D:-...; S :=...;

For i:=... То... Do

Begin А:=.... ; S:=..... End;

Writeln (S=',S);

5. Підведення підсумків уроку. Повідомлення домашнього завдання. (2 хв.)

1. Вивчити конспект.

2. Дана послідовність 11, 18, 25, 32, ... . Складіть програму для обчислення суми а1+а4+а7+а10.

3. Дана послідовність 5, 9, 13, 17, ... . Скільки доданків треба взяти, щоб одержати суму, рівну 324?


 

А также другие работы, которые могут Вас заинтересовать

72578. ПО КАКОМУ ПУТИ РАЗВИВАТЬСЯ КРИМИНОЛОГИИ СЕГОДНЯ? 176.5 KB
  В приведенном тезисе автор выражает свое однозначное отношение к биологическому: если в преступном поведении человека природные качества играют определяющую роль значит он невменяемый т. Ошибка криминологов думается состоит в том что многие из них продолжают отождествлять личность...
72579. ИНСТИТУТ ГОСУДАРСТВЕННОЙ РЕГИСТРАЦИИ ПРАВА СОБСТВЕННОСТИ В ФЕДЕРАЛЬНОМ И РЕГИОНАЛЬНОМ ЗАКОНОДАТЕЛЬСТВЕ 203.5 KB
  В России институт государственной регистрации появился только в постсоветский период (дореволюционный проект Вотчинного Устава, аналога государственной регистрации, так и не был принят). Для сравнения: в европейских странах государственная регистрация как действующая система применялась уже в 1860-х гг.
72580. ПОНЯТИЕ И ПРАВОВЫЕ ОСНОВАНИЯ РЕАЛИЗАЦИИ ПРАВА АПЕЛЛЯЦИОННОГО ОБЖАЛОВАНИЯ РЕШЕНИЯ АРБИТРАЖНОГО СУДА 171 KB
  В суде первой инстанции арбитражного процесса право на судебную защиту реализуется в форме подачи иска либо заявления. Достаточно продолжительное время в науке гражданского и арбитражного процесса в качестве оснований возникновения права на предъявление иска рассматривалась система предпосылок.
72581. ОСНОВАНИЯ ПРЕКРАЩЕНИЯ ГРАЖДАНСТВА РОССИИ И ЗАРУБЕЖНЫХ ГОСУДАРСТВ 165 KB
  Обстоятельства служащие основаниями прекращения гражданства определяются внутренним законодательством каждого государства а в некоторой части и международными договорами. Однако в законодательстве иных государств вопросы прекращения гражданства регулируются довольно типично что позволяет...
72582. ПРОЦЕССУАЛЬНЫЕ ОСОБЕННОСТИ ДЕЯТЕЛЬНОСТИ ВЫСШЕГО АРБИТРАЖНОГО СУДА РОССИЙСКОЙ ФЕДЕРАЦИИ 173.5 KB
  Согласно части 1 статьи 11 Федерального конституционного закона от 28 апреля 1995 г. № 1ФКЗ Об арбитражных судах в Российской Федерации Высший Арбитражный Суд действует в составе1: Пленума Высшего Арбитражного Суда; Президиума Высшего Арбитражного Суда; судебной коллегии по рассмотрению...
72583. ОБЕСПЕЧЕНИЕ ПРАВА ЧЕЛОВЕКА НА ЖИЗНЬ В РОССИЙСКОМ ТЕКУЩЕМ ЗАКОНОДАТЕЛЬСТВЕ 160.5 KB
  Сущность права на социальное обеспечение по возрасту в случае болезни инвалидности потери кормильца для воспитания детей и в иных случаях установленных законом состоит в том что государство гарантирует предоставление достаточных средств гражданам в силу объективных обстоятельств лишенным...
72584. Педагогико-правовые аспекты совершенствования повышения квалификации сотрудников Федеральной миграционной службы 271 KB
  Разрешение проблем образования и повышения квалификации и переподготовки кадров, в частности, безусловно, относится к области первоочередных задач, стоящих перед государством и обществом. Модернизация образования — это одна из составляющих развития человеческого капитала.
72586. Государственный контроль за ограничивающими конкуренцию соглашениями хозяйствующих субъектов 15.99 KB
  Механизм государственного контроля за ограничивающими конкуренцию соглашениями хозяйствующих субъектов предусматривает две процедуры: рассмотрение антимонопольным органом представляемых хозяйствующими субъектами имеющими намерение достичь соглашения заявлений о проверке соответствия проекта...