Време е да дам и последните две задачки по Синтез и анализ на алгоритми – това са два прости примера от областта на рекурсията.
Задача 1: Да се изведат в обратен ред стойностите на едномерен масив.
#include <iostream> using namespace std; int arr[] = { 5, 4, 3, 2, 1 }; void izvedi(int arr[], int ndx){ cout << arr[ndx] << endl; if(ndx > 0) izvedi(arr, --ndx); } int main(){ int size=5; izvedi(arr, --size); return 0; }
Какво става: имаме функция, на която подаваме масив и номер на негов елемент, който искаме да изведем. Функцията извежда стойността на този елемент и вика себе си, подавайки същия масив и номера на предишния елемент. И така, докато стигнем нулевия елемент…
Задача 2: Да се изведе сумата на цифрите на естествено число.
#include <iostream> using namespace std; int poedno(int a){ if (a) return a%10 + poedno(a/10); } int main(){ cout << poedno(1234); return 0; }
Съвсем просто. На входа на функцията имаме число и ако то не е нула, извеждаме остатъка от делението на десет (т.е. последната му цифра) и викаме същата функция с аргумент частното на числото и 10.
Това е всичко. От домашното ни остана само една точка – съпоставка на сортиращите алгоритми. Но това следващия път…