Програмчлалын тэмцээн уралдаан, ер нь аль ч тохиолдолд болж өгвөл Рекурсээс татгалзах хэрэгтэй. Рекурс нь өөрийгөө дуудах бүртээ санах ойд тухайн функцын хэрэглэж байгаа санах ойн хэмжээг дахин яг хуулбарлаж үүсгэдэг. Энэ нь компьютерийн стак мемориг дүүргэж Ажиллах үеийн алдаа болгон програмыг зогсоодог(RTE - Run Time Error). Таны зохиосон алгоритм хугацааны үнэлгээг Рекурсыг ашигласнаар O(LogN), эсвэл O(N) хүртэл буурч байвал хэрэглэхэд тохиромжтой.
Мөн нэмж хэлэхэд Фибаночийн дарааллыг олох Рекурсив функц санах ойд ямар мод үүсгэж байгааг бид харсан. Ажигласан бол өмнө олцон байсан утгуудыг маш олон удаа дахин олж байгаа. Хэрвээ бид тухайн ямар нэгэн утгыг олцон гэж тэмдэглээд, зөвхөн олоогүй түвшинлүү л рекурс дуудалтыг явуулаад байвал Рекурс маань илүү төгс болох байх. эгэхээр ийм зүйлүүдээс татгалзахын тулд memo[] зэрэг өөрт нь тохирсон өгөгдөлийн бүтцийг тодорхойлж эдгээр хий дэмий үйлдлүүдээс бултаж болно. Жишээ болгож Фибаночийн дарааллыг олох функцыг бичие.
#include<cstdio>
#include<cstdlib>
using namespace std;
int n;
int memo[11];//i-r Gishuuniig oloogui bol -1, olson bol utgiig ni hadgalna
int fib(int k){
if(memo[k]!=-1)return memo[k];
memo[k] = fib(k-1);
memo[k] += fib(k-2);
return memo[k];
}
int main(){
scanf("%d", &n);
for(int i=0; i<=n; i++)memo[i]=-1;
memo[0]=0;
memo[1]=1;
fib(n);
for(int i=1; i<=n; i++)
printf("%d ", memo[i]);
system("pause");
return 0;}
Ерөнхийдөө дээрх жишээнд Динамик Програмчлал ашиглаж байгаа ба өөрөө дундаас дээд түвшнийх биш гэж үздэг бол энэнд санаа зовж оролдох хэрэггүй :).
Дараах дасгалуудыг бүгдийг нь Рекурсив функцээр хийгээрэй.
Дасгал 1:
N ширхэг тоо өгөгдөв, тоонуудыг Массивд хадгалаад урвуу дарааллаар нь хэвлэнэ үү.
Input:
5
69 87 45 21 47
Output:
47 21 45 87 69
Дасгал 2:
Массивт байгаа тоог дараах байдлаар хэвлэнэ үү.
[0] [n-1]
[1] [n-2]
.........
.........
[(n-1)/2] [n/2]
Input:
5
1 5 7 8 9
Output:
1 9
5 8
7 7
Дасгал 3:
Массивт байгаа тоонуудаас сондгой тоонуудыг хасаад массивт үлдсэн тонуудыг хэвлэ. Нэмэлт массив ашиглаж болохгүй, таны програм зөвхөн гараас тоонуудаа массивт хадгалаад Рекурсив функцээ дуудсны дараа main() функцээс хариунуудаа хэвлэнэ.
Input:
6
1 54 88 6 55 7
Output:
54 88 6
Дасгал 4:
N өгөгдөхөд олон гишүүнтийг хэвлэ
1 + x + x^2 + ................. + x^n-1
Input:
5
Output:
1 + x + x^2 + x^3 + x^4
Дасгал 5:
x n өгөгдөхөд дээрх олон гишүүнтээ бодно уу.
Жишээ нь n x=2 and n=5, 1 + x + x2 + ................. + xn-1 = 31
Input:
2 5
Output:
31
Дасгал 6:
Мэдээж n!
Input:
5
Output:
120
Дасгал 7:
n-р фибаночи.
Input:
6
Output:
8
Дасгал 8:
Өгөгдсөн тоо анхных мөн эсэхийг шалга.
Input:
49
999983
1
Output:
not prime
prime
not prime
Дасгал 9:
Өгөгдсөн 2 тооны хамгийн их ерөнхий хуваагчийг ол.
Input:
25 8895
Output:
5
Дасгал 10:
Өгөгдсөн 2 тооны хамгийн бага ерөнхий хуваагдагчийг ол. Дараах Ё-г ашиглахгүй шүү. lcm(a,b) = (a x b) / gcd(a,b);
Input:
23 488
Output:
11224
Дасгал 11:
Массивт байгаа тоонуудаас хамгийн ихийг олох функц бич.
Input:
5
7 4 9 6 2
Output:
9
Дасгал 12:
11-р дасгалын хувьд 2 дахь хамгийн том тоог олно уу.
Input:
5
5 8 7 9 3
Output:
8
Дасгал 13:
Шугаман хайлтыг хийх функц бич, Оролтын формат N, N ширхэг тооны дараа Q буюу хэдэн ширхэг тоо хийх ёстойг илэрхийлнэ, үүний дараа Q ширхэг К тоо байх ба хэрэв К тоо дээрх Массивт байгаа бол хэддэх байрлалд байгааг ол.(0..N-1) гэж дугаарлаарай.
Input:
5
2 9 4 7 6
2
5 9
Output:
not found
1
Дасгал 14:
2тын хайлтыг бичнүү. Дээрх бодлоготой адилхан оролттой, мэдээж Массив эрэмбэлэгдсэн байгаа.
Input:
5
1 2 3 4 5
2
3 -5
Output:
2
not found
Дасгал 15:
Өгөгдсөн тооны хөрвөсөн тоог олох функц зохионуу. Зохиосон функц чинь int төрөл буцаах ёстой шүү.
Input:
123405
Output:
504321
Дасгал 16:
15-р дасгалыг тэмдэгт мөрийн хувьд хийнэ үү. Нэмэлт массив ашиглах ёсгүйг анхаараарай.
Input:
helloo
Output:
oolleh
Дасгал 17:
Бүгд Фибаночийн дарааллыг олох Рекурсив функц санах ойд ямар мод үүсгэж байгааг харсан билээ. Тэгвэл тухайн модонд дараах нэвтрэлтүүдийг хий.
Оролт:
5
Гаралт:
Inorder: 1 3 2 5 2 4 1 3 2
Preorder: 5 3 1 2 4 2 3 1 2
Postorder: 1 2 3 2 1 2 3 4 5
Бодолт
