Паскаль: цикл "поки" та його використання, Детальна інформація
Паскаль: цикл "поки" та його використання
Тип документу: Реферат
Сторінок: 9
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 21.5
Скачувань: 1038
while m
begin
fc:=fa+fb; m:=m+1;
fa:=fb; fb:=fc
end;
{m=n, значення змінних fc і fb – шукане}
Відзначимо, що присвоювання fa:=fb та fb:=fc ні в якому разі не можна переставляти – можете проімітувати початок виконання цього алгоритму з переставленими присвоюваннями й переконатися, що значеннями змінної fc будуть аж ніяк не числа Фібоначчі. \xF0E7
У загальному випадку рекурентне співвідношення задає залежність члена рекурентної послідовності sn від k попередніх у вигляді деякого виразу sn=F(sn-k, … , sn-1). Число k називається порядком рекурентного співвідношення. Якщо відомі sn-k, ... , sn-1, то вираз F фактично задає обчислення sn. Назвемо це обчислення застосуванням рекурентного співвідношення.
Припустимо, нам відомо рекурентне співвідношення sn=F(sn-k, ... , sn-1) і перші k членів рекурентної послідовності. Треба за номером p обчислити sp. Знаючи перші k членів, можна застосувати до них співвідношення й обчислити sk+1; аналогічно за s2, ... , sk+1 обчислюється sk+2 тощо. Щоразу для обчислення чергового члена потрібні тільки k останніх із попередніх.
Отже, для опису цих обчислень потрібні:
k змінних для k останніх членів (нехай їх імена A, B, … , X),
змінна для нового члена (нехай її ім'я Y),
змінна M для номера останнього з обчислених членів.
Треба створити "деталі конструктора", тобто запрограмувати:
ініціалізацію змінних A, B, … , X першими k значеннями послідовності;
застосування рекурентного співвідношення, тобто обчислення нового члена й запам'ятовування його в змінній Y;
присвоювання значень змінних B, … , X, Y відповідно змінним A, B, … , X (назвемо це переприсвоюванням).
Тоді розв'язання задачі має вигляд:
ініціалізація змінних A, B, … , X;
M:=k;
while умова продовження do
begin
присвоїти Y результат застосування рекурентного співвідношення до значень змінних A, B, … , X;
M:=M+1;
A:=B; ... ; X:=Y {переприсвоювання}
end
У нашому випадку умова продовження – це просто вираз MРозв'язанням такого вигляду є алгоритм обчислення числа Фібоначчі за його номером (приклад 4.3). Там k=2 і використано імена fa, fb, fc замість A, ... , X, Y.
Далі ми наведемо приклади розв'язання задач з іншими умовами продовження й іншим розташуванням "деталей конструктора", хоча в основі алгоритму все рівно буде цикл while.
begin
fc:=fa+fb; m:=m+1;
fa:=fb; fb:=fc
end;
{m=n, значення змінних fc і fb – шукане}
Відзначимо, що присвоювання fa:=fb та fb:=fc ні в якому разі не можна переставляти – можете проімітувати початок виконання цього алгоритму з переставленими присвоюваннями й переконатися, що значеннями змінної fc будуть аж ніяк не числа Фібоначчі. \xF0E7
У загальному випадку рекурентне співвідношення задає залежність члена рекурентної послідовності sn від k попередніх у вигляді деякого виразу sn=F(sn-k, … , sn-1). Число k називається порядком рекурентного співвідношення. Якщо відомі sn-k, ... , sn-1, то вираз F фактично задає обчислення sn. Назвемо це обчислення застосуванням рекурентного співвідношення.
Припустимо, нам відомо рекурентне співвідношення sn=F(sn-k, ... , sn-1) і перші k членів рекурентної послідовності. Треба за номером p обчислити sp. Знаючи перші k членів, можна застосувати до них співвідношення й обчислити sk+1; аналогічно за s2, ... , sk+1 обчислюється sk+2 тощо. Щоразу для обчислення чергового члена потрібні тільки k останніх із попередніх.
Отже, для опису цих обчислень потрібні:
k змінних для k останніх членів (нехай їх імена A, B, … , X),
змінна для нового члена (нехай її ім'я Y),
змінна M для номера останнього з обчислених членів.
Треба створити "деталі конструктора", тобто запрограмувати:
ініціалізацію змінних A, B, … , X першими k значеннями послідовності;
застосування рекурентного співвідношення, тобто обчислення нового члена й запам'ятовування його в змінній Y;
присвоювання значень змінних B, … , X, Y відповідно змінним A, B, … , X (назвемо це переприсвоюванням).
Тоді розв'язання задачі має вигляд:
ініціалізація змінних A, B, … , X;
M:=k;
while умова продовження do
begin
присвоїти Y результат застосування рекурентного співвідношення до значень змінних A, B, … , X;
M:=M+1;
A:=B; ... ; X:=Y {переприсвоювання}
end
У нашому випадку умова продовження – це просто вираз MРозв'язанням такого вигляду є алгоритм обчислення числа Фібоначчі за його номером (приклад 4.3). Там k=2 і використано імена fa, fb, fc замість A, ... , X, Y.
Далі ми наведемо приклади розв'язання задач з іншими умовами продовження й іншим розташуванням "деталей конструктора", хоча в основі алгоритму все рівно буде цикл while.
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021