.: Menu :.
Home
Реферати
Книги
Конспекти уроків
Виховні заходи
Зразки документів
Реферати партнерів
Завантаження
Завантажити
Електронні книги


????????...

 
��������...
РЕКУРСІЯ І ІТЕРАЦІЯ 


РЕКУРСІЯ І ІТЕРАЦІЯ

РЕКУРСІЯ І ІТЕРАЦІЯ
Рекурсією називається такий спосіб організації обробки даних, при якому програма (чи функція) викликає сама себе чи безпосередньо, чи інших програм (функцій).
Функція називається рекурсивною, якщо під час її обробки виникає її повторний виклик, або безпосередньо, або опосередковано, шляхом ланцюжка викликів інших функцій.
Ітерацією називається такий спосіб організації обробки даних, при якому деякі дії повторюються багато раз, не приводячи при цьому до рекурсивних викликів програм ( функцій).
Теорема. Довільний алгоритм, реалізований в рекурсивній формі, може бути переписаний в  ітераційній формі і навпаки.
1. Факторіал числа. Факторіалом числа n називається добуток всіх натуральних чисел від 1 до n і позначається n!. Якщо f(n)= n!, то має місце рекурренте співвідношення:


рекурсивна реалізація    циклічна реалізація
int f(int n)
{
if(!n) return 1;
return n*f(n-1);
}
int f(int n)
{
int i,res = 1;
for(i=1;i<=n;i++) res = res * i;
return res;
}

2. Степінь числа за лінійний час. Обчислення степеня числа f(а, n)= an з тимчасовою оцінкою O(n) можна визначити за допомогою наступного рекуррентного співвідношення:


рекурсивна реалізація    циклічна реалізація
int f(int а,int n)
{
if (!n) return 1;
return a*f(а,n-1);
}
int f(int а,int n)
{
int i,res = 1;
for(i=0;i<n;i++) res = res * а;
return res;
}

3. Степінь числа за логарифмічний час. Обчислення степеня числа f(а, n)= an з тимчасовою оцінкою O(log2n) визначимо таким чином:



рекурсивна реалізація    циклічна реалізація
int f(int а, int n)
{
if (!n) return 1;
if (n & 1) return a * f(a*a,n/2);
return f(a*a,n/2);
}    int f(int a, int n)
{
int  res=1;
while(n>0)
{
if (n & 1) res *= a;
n >>= 1;
a *= a;
}
return res;
}

4. Сума цифр числа. Суму цифр натурального числа n можна знайти за допомогою функції f(n), визначеної таким чином:


рекурсивна реалізація    циклічна реалізація
int f(int n)
{
if (!n) return 0;
return n%10 + f(n/10);
}    int f(int n)
{
int res = 0;
for(;n>0;n=n/10) res = res + n % 10;
return res;
}

5. Число одиниць. Кількість одиниць в двійковому представленні числа n можна обчислити за допомогою функції f(n), визначеної таким чином (& - операція побітового ‘І’):


В результаті операції n = n & (n – 1) знищується остання одиниця в двійковому представленні числа n:
n = a1a2…ak-1ak10…0
n – 1 = a1a2…ak-1ak01…1
n & (n – 1) = a1a2…ak-1 000…0
Рекурсивний виклик функції f здійснюватиметься стільки разів, скільки одиниць в двійковому представленні числа n.

рекурсивна реалізація    циклічна реалізація
int f(int n)
{
if (!n) return 0;
return 1 + f(n & (n-1));
}    int f(int n)
{
int res = 0;
for(;n>0;n=n&(n-1))res++;
return res;
}

6. Біноміальний коефіцієнт. Значення біноміального коефіцієнта рівне

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

int c(int k, int n)
{
if (n == k) return 1;
if (k == 0) return 1;
return c(k-1,n-1)+ c(k,n-1);
}

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

int c(int k, int n)
{
int i,res = 1;
for(i=1;i<=k;i++)
res = res * (n - i + 1) / i;
return res;
}

7. Рекурсивна функція. Для заданого натурального n обчислити значення функції f(n), заданої рекурентними співвідношеннями:
f(2 * n)= f(n)
f(2 * n + 1)= f(n)+ f(n + 1)
f(0)= 0, f(1)= 1

8. Функція Аккермана. Функція Аккермана A(m, n) визначається рекурсивно таким чином:
A(0, n)= n + 1
A(m, 0)= A(m – 1, 1)
A(m, n)= A(m – 1, A(m, n – 1))
Реалізувати функцію A(m, n) і протестувати її для різних вхідних значень аргументів.

9. Великий модуль [Вальядолід, 374]. По заданих b, p, m обчислити значення виразу bp mod m.
Вхід. Містить декілька тестів. Числа b, p, m знаходяться в окремих рядках. Відомо, що 0 ≤ b, p ≤ 2147483647, 1 ≤ m ≤ 46340.
Вихід. Для кожного тесту вивести в окремому рядку значення bp mod m.
Приклад входу    Приклад виходу
3    13
18132    2
17    13195

17   
1765   
3   

2374859   
3029382   
36123   

10. Істина, захована в рекурентності [Вальядолід, 10547]. Функція f визначена таким чином:
f(0, 0)= 1
f(n, r)= , якщо n > 0 і 0 ≤ r ≤ n(k – 1)+ 1
f(n, r)= 0 інакше.
Обчислити значення x =  mod m, де m = 10t.
Наприклад, значення f(n, i) при k = 3 мають вигляд (у порожніх клітках стоять нулі):

n \ i    0    1    2    3    4    5    6    7    8
0    1                               
1    1    1    1                       
2    1    2    3    2    1               
3    1    3    6    7    6    3    1       
4    1    4    10    16    19    16    10    4    1
Вхід. На вхід подається не більше 1001 тесту. Кожен рядок містить три цілі числа: k, n і t (0 < k, n < 1019, 0 < t < 10). Останній тест містить k = n = t = 0 і не обробляється.
Вихід. Для кожного тесту разом з його номером в окремому рядку вивести значення x.
Приклад входу    Приклад виходу
1234 1234 4    Case #1: 736
2323 99999999999 8    Case #2: 39087387
4 99999 9    Case #3: 494777344
888 888 8    Case #4: 91255296
0 0 0   

11. f91 [Вальядолід, 10696]. Обчислити значення функції f91, заданої рекурентним співвідношенням:
f91(n) = 
Вхід. Кожен вхідний рядок містить натуральне число n (n ≤ 1000000). Число n = 0 є кінцем вхідних даних і не обробляється.
Вихід. Для кожного вхідного n вивести значення f91(n) як показано в прикладі нижче.
Приклад входу    Приклад виходу
500    f91(500) = 490
91    f91(91) = 91
0   

12. Йосип, що повторюється [Вальядолід, 10774]. По колу стоять n людей, пронумеровані від 1 до n. Починаючи відлік з першого і рухаючись по колу, страчуватимемо кожну другу людину доти поки не залишиться один. Хай той, що вижив має номер x. Розставимо по колу x людей і повторимо процес, після якого виживе людина з номером у. І так далі до тих пір, поки номер того, що вижив не стане рівним початковій кількості людей в поточному раунді.
Наприклад, при n = 5 послідовно будуть страчені 2, 4, 1, 5. Виживе номер 3. Він не рівний 5 (кількості людей в раунді), тому слід повторити процедуру. Для n = 3 страчені будуть 2, 1. Виживе людина з номером 3, рівним n. Процедура закінчується.
Вхід. Вхідні дані складаються з декількох тестів. Кожен тест в одному рядку містить одне число n (0 < n  ≤30000)
Вихід. Для кожного тесту вивести в окремому рядку його номер як вказано в прикладі, кількість повторень процедури страти після першої ітерації і номер того, що вижив в кінці процедури.


Приклад входу    Приклад виходу
2    Case 1: 2 7
13    Case 2: 8 1023
23403   

13. Просте додавання [Вальядолід, 10994]. Визначимо рекурсивну функцію f(n) таким чином:
f(n)= 
Визначимо функцію S(p, q) таким чином:
S(p, q)= 
У завданні необхідно обчислити значення S(p, q) по заданих p і q.
Вхід. Кожен рядок містить два ненегативні 32-бітові знакові числа p і q (p  q). Останній рядок містить два негативні цілі числа і не обробляється.
Вихід. Для кожної пари p і q вивести значення S(p, q).
Приклад входу    Приклад виходу
1 10    46
10 20    48
30 40    52
-1 -1   


ВКАЗІВКИ І РІШЕННЯ

7. Рекурсивна функція. У разі безпосередньої реалізації функції  f(n) час її обчислення експоненціально залежатиме від n. Визначимо функцію
g(n, i, j)= i * f(n)+ j * f(n + 1)
для якої мають місце рівність:
g(2 * n, i, j)= g(n, i + j, j)
g(2 * n + 1, i, j)= g(n, i, i +  j)
g(0, i, j)= i * f(0)+ j * f(1)= j
Використовуючи приведені співвідношення, можна обчислити значення f(n)= g(n, 1, 0) з тимчасовою оцінкою O(log n).

int g(int n, int i, int j)
{
if (!n) return j;
if (n % 2) return g(n/2, i, i + j);
return g(n/2, i + j, j);
}

int f(int n)
{
return g(n,1,0);
}

8. Функція Аккермана. Рекурсивна реалізація функції Аккермана має вигляд:

int а(int m, int n)
{
if (!m) return n+1;
if (!n) return а(m-1,1);
return а(m-1,a(m,n-1));
}

Для малих значень m функцію Аккермана можна виразити явно:
A(0, n)= n + 1
A(1, n)= 2 + (n + 3) – 3 = n + 2
A(2, n)= 2 * (n + 3) – 3 = 2 * n + 3
A(3, n)= 2n+3– 3

9. Великий модуль [Вальядолід, 374]. З обмежень на вхідні дані слідує, що в процесі обчислення досить використовувати тип даних int. Піднесення  до степеня bp виконаємо з логарифмічною тимчасовою складністю O(log p) використовуючи алгоритм, що базується на двійковому розкладанні показника степеня p:


Приклад. Для обчислення значення з першого тесту 318132 (mod 17) слід представити показник степеня в двійковій системі числення: 1813210 = 1000110110101002. Далі 318132 (mod 17) = 316384 * 31024 * 3512 *  3128 *  364 *  316 *  34 (mod 17) = 13.
Для другого тесту 171765 (mod 3) = (17 mod 3) 1765 (mod 3) = 2 1765 (mod 3) = 2.

Реалізація. Функція pow обчислює вираз bp mod m з оцінкою складності O(log p).

#include <stdio.h>

int b,p,m,res;

int pow(int b, int p, int m)
{
int  res=1;
while(p > 0)
{
if (p & 1) res = (res * b) % m;
p >>= 1;
b = (b * b) % m;
}
return res;
}

void main(void)
{

Прочитавши вхідні значення b, p і m, слід скористатися формулою
bp mod m = (b mod m)p mod m
При передачі параметрів функції pow основа степеня b повинна бути не більше ніж модуль m. Якщо цього не зробити, одержимо Time Limit. Окремо слід опрацювати випадок, коли p = 0: b0 mod m = 1.

while (scanf("%d %d %d",&b,&p, &m)== 3)
{
b = b % m;
if (!p) res = 1; else res = pow(b,p,m);
printf("%d\n",res);
}
}

10. Істина, захована в рекуррентности [Вальядолід, 10547]. Розглянемо всі n - цифрові числа в системі числення з основою k (включаючи числа з провідними нулями). Загальна їх кількість рівна kn. Нехай f(n, r) – кількість таких чисел, сума цифр яких рівна r. Тоді
f(n, r)= f(n – 1, r)+ f(n – 1, r – 1)+ . + f(n – 1, r – до + 1)= 
Мінімальна сума цифр для таких чисел рівна 0, максимальна (k – 1) * n.  Підсумувавши значення f(n, r) для r від 0 до (k – 1) * n, одержимо загальну кількість n - цифрових чисел в системі числення з основою k, тобто kn.
Таким чином x = kn (mod 10t). Оскільки t < 10, то при обчисленні модулярної експоненти досить використовувати 64-бітовий цілочисельний тип.
Приклад. Для першого тесту має місце рівність: 12341234 (mod 104) = 736.
Реалізація. При обчисленні використовуємо 64-бітовий цілий тип long long. Для простоти використання визначимо тип i64.

#include <stdio.h>

typedef long long i64;

i64 k,n,t,m,res;
int i;

Функція обчислення xy mod n з оцінкою складності O(log2y):

i64 powmod(i64 x, i64 y, i64 n)
{
i64  res=1;
while(y>0)
{
if (у & 1) res = (res * x) % n;
у >>= 1;
x = (x * x) % n;
}
return res;
}

void main(void)
{

Читаємо вхідні значення k, n, t, обчислюємо m = 10t. Знаходимо x = kn (mod 10t) = (k mod m)n (mod 10t). Оскільки k < 1019, то щоб уникнути переповнювання перед викликом функції powmod слід знайти залишок від ділення k на m. Таким чином значення першого аргументу k функції powmod буде не більше 109 і при обчисленні k * k не буде переповнювання. Виводимо результат з номером тесту cs.

int cs = 1;
while(scanf("%lld %lld %lld",&k, &n, &t),k>0,n>0,t>0)
{
m = 1; for(i=0;i<t;i++)m*=10;
res = powmod(до % m,n,m);
printf("Case #%d: %lld\n",cs++,res);
}
}

11. f91 [Вальядолід, 10696]. Необхідно обчислити значення функції f91(n) для n100.
Маємо: f91(100) = f91(f91(111)) = f91(101) = 91 f91(99) = f91(f91(110)) = f91(100) = 91. Аналогічно продовжуючи, можна відмітити що f91(n) = 91, де 1  n  100.
Таким чином, має місце співвідношення:
f91(n) = 
Реалізація. Читаємо вхідні значення n, поки не зустрінеться 0. Виводимо результат згідно приведеноuj вище співвідношення.

#include <stdio.h>

int n,res;

void main(void)
{
while(scanf("%d",&n), n != 0)
{
if (n >= 101) res = n-10; else res = 91;
printf("f91(%d)= %d\n",n,res);
}
}

12. Йосип, що повторюється [Вальядолід, 10774]. Хай n – кількість людей в колі. Позначимо через f(n) номер того, що останній уцілів. Покладемо f(1)= 1.
Якщо n = 2 * k – парне, то після проходу першого кола будуть вилучені люди з парними номерами: 2, 4, ..., 2 * k. Залишаться люди з непарними номерами, а відлік продовжуємо з номера 1. Це все одно, що якби у нас було k людей, а номер кожного подвоївся і зменшився на 1. Тобто одержимо співвідношення f(2 * k)= 2 * f(k) - 1.













Якщо n = 2 * k + 1 – непарне, то після проходу першого кола будуть вилучені люди з парними номерами 2, 4, ..., 2 * k, а жертва з номером 1 знищується відразу ж після жертви з номером 2 * k. Залишається k людей з номерами 3, 5, 7 ., 2 * k + 1. Це все одно, що люди пронумеровані від 1 до k, тільки номер кожного подвоївся і збільшився на 1. Одержуємо співвідношення: f(2 * k + 1)= 2 * f(k)+ 1.










Об'єднуючи одержані співвідношення, одержимо рекуррентность:
f(1)= 1
f(2 * k)= 2 * f(k) – 1, k  1
f(2 * k+ 1)= 2 * f(k)+ 1, k  1
Теорема. Значення f(n) отримується шляхом циклічного зміщення двійкового представлення n вліво на один біт. Наприклад, f(100)= f(11001002)= 10010012 = 73.
Багаторазове застосування функції f породжує послідовність спадаючих значень, що досягають нерухомої точки n такої що f(n)= n. Число n складатиметься з одних одиниць із значенням 2v(n) – 1, де v(n) – кількість одиниць в бінарному представленні числа n.
Приклад. Розглянемо вхідні дані для другого тесту. При n = 13 послідовно будуть страчені 2, 4, 6, 8, 10, 12, 1, 5, 9, 13, 7, 3. Виживе номер 11. Він не рівний 13 (кількості людей в раунді), тому слід повторити процедуру. Для n = 11 страчені будуть 2, 4, 6, 8, 10, 1, 5, 9, 3, 11. Виживе людина з номером 7, рівним n. При n = 7 виживе номер 7. Після першої ітерації проведено ще 2 повторення процедури страти.
Реалізація. Функція last по первинній кількості людей n в колі повертає номер того, що уцілів згідно рекуррентного співвідношення.

#include <stdio.h>

int k,n,i,r,tests;

int last(int n)
{
if (n == 1) return 1;
if (n%2 == 0) return 2*last(n/2)-1;
else return 2*last((n-1)/2)+1;
}

void main(void)
{
scanf("%d",&tests);
for(i=1;i<=tests;i++)
{

Змінна r містить кількість повторень процедури страти (спочатку r = 0). По заданому вхідному n шукаємо номер того, що уцілів k. Якщо він не рівний n, то повторюємо в циклі процедуру страти.

scanf("%d",&n); r = 0;
while ((k = last(n)) != n) r++, n = до;
printf("Case %d: %d %d\n",i,r,n);
}
}

13. Просте додавання [Вальядолід, 10994]. Приведена в умові функція f(n) знаходить останню ненульову цифру числа n. Позначимо через
g(p)= 
Тоді S(p, q)= g(q) – q(p – 1). Для обчислення функції g(p), суми останніх значущих цифр для чисел від 1 до p, розіб'ємо числа від 1 до p на три множини (операція ділення ‘/’ є цілочисельною):
1. Числа від (p/10)*10 + 1 до p;
2. Числа від 1 до (p/10)*10, що не закінчуються нулем;
3. Числа від 1 до (p/10)*10, що закінчуються нулем;
Наприклад, при p = 32 до першої множини належатимуть числа 31, 32, до другого 1 ., 9, 11  ., 19, 21 ., 29, до третього 10, 20.
Сума останніх значущих цифр в першій множині рівна 1 + 2 + . + p%10 = t(1 + t)/ 2, де t = p % 10. У другій множині шукана сума рівна p / 10 * 45, оскільки сума всіх цифр від 1 до 9 рівна 45, а число повних десятків рівне p / 10. Необхідну суму для третьої множини знайдемо рекурсивно: вона рівна g(p / 10).
Реалізація. Оскільки виконується обробка 32-бітових знакових чисел, то при обчисленнях використовуємо тип long long (__int64).

#include <stdio.h>

long long p,q;

Функція g(p) обчислює суму значень функції f(n) для значень аргументу n від 1 до р.

long long g(long long p)
{
long long t = p % 10;
if (!p) return 0;
return t*(1+t)/2 + p/10 * 45 + g(p/10);
return 0;
}

Значення функції S(p, q) рахуємо як g(q) – q(p – 1).

long long s(long long p, long long q)
{
return g(q) - g(p-1);
}

void main(void)
{

Основний цикл програми. Для кожної пари чисел p і q виводимо значення s(p, q).

while(scanf("%lld %lld",&p,&q),p+q>=0)
printf("%lld\n",s(p,q));
}
СПИСОК ВИКОРИСТАНИХ ЗАДАЧ

[Вальядолід] acm.uva.es/problemset:
374 (Великий модуль), 10547 (Істина, захована в рекуррентности), 10696 (f91), 10774 (Йосип, що повторюється), 10994 (Просте додавання).

Search:
????????...

діалог між двома учнями

характеристика гектора і ахілла

філософія нового часу цвінглі

вислови про виховання

зображення покріпачення україни в романі хіба ревуть воли як ясла повні

хто такий чіпка месник чи злочинець?

лабораторні роботи з менеджменту

малюнок на тему шкідливі звички

вірш про війну для 2 класу

Жульєн геніальний плебей



?????????? ????????? ????
   
Created by Yura Pagor, 2007-2010