7 Лабораторна робота. Рекурсiя в мовi сi
Мета роботи: освоїти прийоми складання рекурсивних алгоритмiв i програм на мовi Сi.
Контрольнi питання :
1 ) Що таке рекурсiя?
2 ) Назовiть види рекурсiї.
3 ) Назовiть основнi етапи проектування рекурсивних алгоритмiв.
4 ) Що таке "умова завершення рекурсiї"?
5 ) Назовiть достоїнства i недолiки рекурсивних алгоритмiв.
Рекурсiя як обчислювальний процес є альтернативою методу iтерацiй (послiдовних наближень).
7. 1 Органiзацiя рекурсiї при рiшеннi обчислювальних завдань по методу послiдовних наближень
Розрахунковi формули завдань (номери 1-35) являють iтерацiйнi алгоритми методу послiдовних наближень. Видiляють слiдуючi окремi випадки iтерацiйних процесiв.
7.1.1 Алгоритм обчислення по явно заданiй рекурентнiй формулi
Наприклад, обчислення квадратного кореня
y
=
=
yn+1=1/2
(yn
+ x/yn
) , n=
0,1,2... (7.1)
з похибкою | yn+1 - y n | < ε. (7.2)
Початкове наближення вираховується так:
x/2, если x>1
y0
=
(7.3)
2x, если x<=1
7.1.2 Алгоритм
обчислення значення функцiї
по формулi
разкладання функцiї
в ряд
y
= ex
= 1 + x
+
x2
+ ... +
xn
.... + ... (7.4)
з точнiстю
чергового члена ряду |
xn
| < ε.
При пiдсумуваннi подiбних рядiв для скорочування обсягу обчислень необхiдно вивести рекурентнi формули.
В даному випадку вони присутнi неявно i дозволяють виразити наступний член ряду через попереднiй:
an
=
xn
; a n+1
=
x
n+1 ;
(7.5)
a n+1 x
М
аємо
= ,
a n n+1
звiдкiля одержуємо необхiдну рекурентну формулу:
x
a
n+1
= * a
n
; (7.6)
n+1
7. 1. 3 Загальний член ряду має бiльш загальний вид
Наприклад, якщо загальний член має вид
x 2n+1
a
n
= ,
4n2 -1
то його доцiльно представити у виглядi двох множникiв, один з яких обчислюється за рекурентним спiввiдношенням, а iнший - безпосередньо.
Хай Cn = x2n+1 i вираховуємо рекурентно C n+1 = Cn * x .
Тодi
Cn
an+1
= (7.7)
4n2 -1
Управлiння iтерацiйними циклами здiйснюється по заданому значенню похибки обчислень.
Описанi iтерацiйнi процеси необхiдно звести до рекурсивного виклику функцiй в алгоритмiчнiй мовi.
7. 1. 4 Приклад 1
Визначити
функцiю
y
=
.
Будуємо iєрархiю функцiй, що дозволить визначити цiльову.
Вводимо визначення функцiй y0, next_y i body_sqrt. Iз (7.3) одержуємо функцiю початкового наближення :
float y0 (float x)
{ return (x>1.0 ? x/2 : x*2);}
Значення наступного члена ряду через попереднiй обчислюється за формулою (7.1) :
float next_y(float x, float yn)
{ return((yn+x/yn)/2);}
Iтерацiйний процес до досягнення заданої точностi обчислень за формулою (7.2) визначаємо:
float body_sqrt (float x, float yn, float ynplus1, float eps)
{if(fabs(ynplus1-yn)<eps)
return(ynplus1);
else
return (body_sqrt (x, ynplus1,next_y(x, ynplus1), eps));
}
На основi одержаної iєрархiї визначень функцiй складаємо визначення цiльової функцiї:
float main_sqrt (float x, float eps)
{ float yn, ynplus1;
yn= y0(x);
ynplus1= next_y(x, y0(x));
return (body_sqrt (x,yn, ynplus1, eps));
}
Це визначення може бути записано з використанням композицiї функцiй:
float main_sqrt (float x, float eps)
{ return (body_sqrt(x, y0(x),next_y(x, y0(x)),eps));
}
Виклик функцiї main_sqrt для значень x=32 i ε=0. 01 має вид:
main ()
{ float y; y=main_sqrt(32.0, 0.01); }
7.1.5 Програма на мовi Сi
#include <stdio.h>
#include <math.h>
/* ========== ФУНКЦIЯ ПОЧАТКОВОГО НАБЛИЖЕННЯ ===== */
float y0(float x)
{ return(x>1.0 ? x/2 : x*2);}
/* === ФУНКЦIЯ ОБЧИСЛЕННЯ СЛIДУЮЧОГО ЧЛЕНА РЯДУ == */
/* ================== ЧЕРЕЗ ПОПЕРЕДНIЙ ============== */
float next_y(float x, float yn)
{ return((yn+x/yn)/2);}
/* === РЕКУРСИВНА ФУНКЦIЯ ОБЧИСЛЕННЯ ЗНАЧЕННЯ Y === */
float body_sqrt (float x, float yn, float ynplus1, float eps)
{ if(fabs(ynplus1-yn)<eps)
return(ynplus1);
else
return (body_sqrt (x, ynplus1, next_y(x, ynplus1), eps )
);
}
/* ======== ФУНКЦIЯ ОБЧИСЛЕННЯ ЗНАЧЕННЯ Y ПО ====== */
/* ================== ЗНАЧЕННЯМ X И EPS ============= */
float main_sqrt (float x, float eps)
{ return (body_sqrt (x, y0(x), next_y(x, y0(x)), eps ));
}
/*==================== ГОЛОВНА ФУНКЦIЯ ============= */
main ()
{ float x, eps, y;
printf("Введiть x=");
scanf("%f", &x);
printf("та eps=");
scanf("%f", &eps);
y=main_sqrt(x, eps);
/* ПОРIВНЯННЯ ЗНАЧЕНЬ ФУНКЦIЇ, ВИЗНАЧЕНОЇ В MAIN_SQRT, */ /* ==================I БIБЛIОТЕЧНОЇ ФУНКЦIЇ (SQRT) =======*/ printf("Значення:\n");
printf("main_sqrt(%f, %f)=%f\n", x, eps, y);
printf(" sqrt(%f, %f)=%f\n", x, eps, y);
getch();
}
7.2 Органiзацiя рекурсiї при рiшеннi завдань обробки даних
Розглянемо органiзацiю таких рекурсивних обчислень на прикладi рiшення слiдуючого завдання: Визначити, чи є рядок st симетричним.
7.2.1. Постановка завдання
7.2.1.1 Початковi данi
n : цiле; {довжина рядка st}
st : рядок [1..n ]; {початковий рядок}
7.2.1.2 Обмеження
довжина (st)
0
( st - непустий )
7.2.1.3 Результат
повiдомлення: рядок [ 1.. 20 ]; {строка повiдомлень}
7.2.1.4 Зв'язок
Порiвнюємо по парам символи рядка st з iндексами i та j, розмiщенi симетрично щодо його середини:
st
|
|
|
|
|
|
1 2 3
... n
i j (початковий стан)
i
j (наступний
крок)
Якщо цi символи (st[i] i st[j]) рiвнi, то "скорочуєїмо" розмiр рядка на один символ лiворуч i праворуч, перемiщаючи iндекси i та j назустрiч одне одному.
Умови завершення рекурсii:
1) Якщо символи з iндексами i та j рiзнi, то перегляд завершений неуспїшно (st не є симетричним);
2) Якщо st [i] та st[j] збiглися, i рядок st парної довжини
st
|
|
|
|
|
|
i j
або рядок st парної довжини
st
|
|
|
|
|
i
j
i усi попереднi пари символiв спiвпадали, то перегляд завершений успiшно (st є симетричною).
-
Метод рiшення
j
:= j - 1
i := i + 1
не_кiнець := iстина st I = st J
доки
нi
( i = j
або
i = j - 1)
не_кiнець
:= неправда
st I
st J
i
не_кiнець
)
не_кiнець := iстина
i := 1
j := n
Промiжнi данi:
не_кiнець: логiчне; {ознака: рiвна iстина, якщо попереднi
симетричнi вiдносно середини st пари
символiв спiвпадають}
i : цiле; {iндекс лiвого символа, що порiвнюється}
j : цiле; {iндекс правого символа, що порiвнюється }
-
Текст програми на мовi Сi
#include <stdio.h>
#include <conio.h>
#define N 20
#define ESC 27
main ()
{/* ================== ВХIДНI ДАНI ================= */
char s[N];
/* ================= ПРОМIЖНI ДАНI =============== */
int i, /*порядковий номер символу, який введений в рядок */
m = 0; /* власне символ, який введений в рядок */
/* ============= прототип допомiжної функцiї sim ========= */
int sim(char *st,int i,int j);
/* ==== ЧАСТИНА АЛГОРИТМУ, ЩО ВИКОНУЄТЬСЯ=====*/
/* введення вхiдного рядка по символам i оформлення рядка */
while (m != ESC)
{ printf("\nВведiть рядок:\n ");
i=0;
do
s[i++] = getchar();
while (s[i-1]!='\n');
s[i-1]='\0'; /* оформлення масиву символiв як рядка */
if (sim(s, 0, strlen(s)-1))
printf("Цей рядок симетричний\n");
else
printf("Цей рядок несиметричний\n");
printf("Для виходу натиснiть ESC, для продовження - ENTER.");
m=getch(); /* продовження введення рядкiв */
}
}
/* === Допомiжна функцiя перевiрки рядка st на симетричнiсть ==*/
int sim(char *st, int i, int j)
{ if ((i==j)||((i==j-1)&&(st[i]==st[j])))
return 1;
else
if ((st[i]==st[j])&&(sim(st, i+1, j-1)==1))
return 1;
else return 0;
}