Задачи за рекурсия
Рекурсия
Задача 1. Да се дефинира рекурсивна функция , която изчислява xn , като:
x 0 = 1
x 2 n = (xn)2
x 2 n+1 = x(xn)
Задача 2 . Да се дефинира рекурсивна функция , която изчислява биномния коефициент
C(0, n) = 1
C(n, n) = 1
C(m, n) = C(m-1, n-1) + C(m, n-1)
Задача 3 . Да се напише рекурсивна функция, която установява, дали в записа на естественото число n се съдържа цифрата k.
Задача 4 . Да се напише рекурсивна функция, която намира стойността на функцията на Акерман Ack(m, n), дефинирана за m ≥ 0 и n ≥ 0 по следния начин:
Ack(0, n) = n+1
Ack(m, 0) = Ack(m-1, 1), m > 0
Ack(m, n) = Ack(m-1, Ack(m, n-1)), m > 0, n > 0.
Задача 5 . Да се напише рекурсивна функция double min ( int n , double * x ) , която намира минималния елемент на редицата x 0 , x 1 ,…, xn .
Задача 6 . Да се напише рекурсивна функция , която проверява дали елементът x принадлежи на редицата x 0 , x 1 ,…, xn . .
Задача 7 . Дадена е правоъгълна матрица m x n , където a [ i ][ j ] = 1 , ако има директен път между градовете с номера i и j , a [ i ][ j ] = 0 ако няма директен път. Да се напише рекурсивна функция , която проверява дали съществува път между двата града.
Задача 8. Дадена е правоъгълна матрица m x n , където a [ i ][ j ] = 0 ако квадратчето ( i , j ) е проходимо, a [ i ][ j ] = 1 ако квадратчето ( i , j ) е непроходимо. Да се напише рекурсивна функция коята проверява дали съществува път ( i , j ) и ( k , l ) .
Задача 10 . Дадена е правоъгълна матрица m x n , където a [ i ][ j ] = 1 , ако има директен път между градовете с номера i и j , a [ i ][ j ] = 0 ако няма директен път. Да се напише програма, която намира пътя между два произволно зададени града в случай, че път между тях съществува.
Задача 11 . . Дадена е правоъгълна матрица m x n , където a [ i ][ j ] = 1 , ако има директен път между градовете с номера i и j , a [ i ][ j ] = 0 ако няма директен път. Да се напише булева функция fixway ( int i , int j , int p ), която установява дали съществува път от град i до град j с дължина p ( p ≥1).