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?


 

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

66034. Разработка и оптимизация конструкции регулирующего клапана (РК) DN125 для системы САОЗ ВД энергоблока АЭС с ВВЭР-1000 малой серии 7.73 MB
  Цель работы: обеспечение безопасности работы реакторных установок В-320 и В-338 при речах 1 контура, компенсируемых работой САОЗ ВД на основе подхода управляемого снижения давления 1 контура с регулированием расхода впрыска борного расхода...
66035. Глобализация финансов 17.21 KB
  В глобализации финансов часто усматривают причину роста спекуляций и отвлечения со спекулятивными целями капитала от производства и создания новых рабочих мест. Процесс финансовой глобализации сконцентрирован прежде всего в трех основных центрах мировой экономики...
66036. Бюджетный дефицит. Виды и меры по его ликвидации в России 52 KB
  Виды дефицита бюджета В тех случаях когда имеющиеся у бюджета доходы недостаточны для осуществления расходов говорят о возникновении бюджетного дефицита.Бюджетный дефицит не обязательно свидетельствует о каком-то чрезвычайном положении в экономике страны.
66038. НАЛОГОВЫЕ СИСТЕМЫ ЗАРУБЕЖНЫХ СТРАН 18.27 KB
  Отличительная черта налоговой системы Франции высокая доля взносов в фонды социального назначения ФСН. Эластичность налоговой системы заключается в том что ежегодно в соответствии с изменениями политической и экономической конъюктуры законодательно уточняются ставки налогов.
66040. Органы управления финансами в разных странах 65.02 KB
  В России главными властными структурами по управлению финансами являются Федеральное Собрание, Президент и Правительство. Именно эти органы принимают окончательное решение при утверждении федерального бюджета и отчета о его исполнении. Участие Президента...