Question

Napisz w c++ funkcję rekurencyjną, która zwraca z tablicy przekazanej jako parametr indeks(liczbę) najbliższą wartością średniej.

Proszę też o wytłumaczenie co w danej linijce programu sie dzieje.. Ale tylko to co jest najwazniejsze.

Dziękuję.

Answer 1

To zadanie, to perfekcyjny przykłąd, gdzie NIE należałoby korzystać z rekurencji... ech.

Mały disclaimer na początek (odnośnie wersji rekurencyjnej):
Kod ten pisany jest pod standard C++0x (inaczej C++11); jeżeli korzystasz z Dev-cośtam 4.9.x.x, nie łudź się, że ten kod skompilujesz (w końcu środowisko to ma już 8 lat, a C++11 jest stosunkowo nowy).
Bezproblemowo kompiluje się i działa* natomiast pod GCC 4.7.2 (czego dowodem jest link do Ideone znajdujący się poniżej), więc prosiłbym o niepisanie mi, że "u mnie to nie chce się skompilować", tylko pobranie normalnego środowiska z najnowszym GCC.
Also 1 - jeżeli nie rozumiesz którejś z części kodu, weź do ręki książkę, a nie pisz mi wiadomości; nie jestem nauczycielem i nie wytłumaczę tego lepiej, niżeli porządna lektura o C++11.
Also 2 - kod korzysta z wyrażeń lambda, inaczej nie miałem pomysłu na wykorzystanie rekurencji w tym zadaniu.

* - nie robiłem żadnych testów jednostkowych ani niczego w tym rodzaju - sprawdzałem jedynie na przykładowych danych i na nich działało.
Drobna informacja: program zakłada, że `tab` ma przynajmniej jeden element, inaczej będzie dzielenie przez zero w funkcji `get_average_value`.

Anyway, wersja do sformatowanego kodu:
Wersja rekurencyjna: http://ideone.com/8NqbuO
Wersja iteracyjna: http://ideone.com/PSqBlW (ta powinna kompilować się także na tym ośmioletnim G++).

Wersja niesformatowana:
#include <functional>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

/* find_nearest

@Description:
Funkcja wyszukuje wartość, która jest "najbliżej" wartości `search_value` w naszej tablicy i zwraca odnalezioną wartość przez wynik funkcji.

@Param:
tab -> lista z liczbami
search_value -> szukana wartość

@Return:
Zwraca tę odnalezioną liczbę.
*/
int find_nearest(vector<int> tab, double search_value)
{
double nearest = tab[0]; // musimy przyjąć jakąś początkową wartość; można by równie dobrze najprawdopodobniej przyjąć NaN bądź INF, ale afair operacje na tych "liczbach" są nieokreślone

for_each(tab.begin(), tab.end(), [&nearest, search_value](int value) // przeszukujemy każdy element tablicy
{
if (fabs(search_value - nearest) > fabs(value - search_value)) // sprawdzamy, czy jest on potencjalnie 'najbliższy'
nearest = value;
});

return nearest; // zwracamy wynik
}

/* get_average_value

@Description:
Funkcja liczy średnią arytmetyczną liczb w tablicy.

@Param:
tab -> lista liczb

@Return:
Zwraca średnią wartość liczb wewnątrz tablicy.
*/
double get_average_value(vector<int> tab)
{
double sum_value = 0;

function<void(unsigned int)> sum;
sum = [tab, &sum, &sum_value](unsigned int element_id) // funkcja ta (wyrażenie lambda) sumuje liczby w tablicy. Miała być rekurencja, więc i rekurencja - chociaż równie bezsensowna, co samo zadanie - jest.
{
sum_value += tab[element_id];

if (element_id > 0)
sum(element_id-1);
};

sum(tab.size()-1);

return sum_value/tab.size(); // dzielimy sumę przez ilość elementów w tablicy
}

/* do_magic

@Description:
Funkcja szuka wartości w tablicy, która jest "najbliższa" średniej arytmetycznej liczb tej tablicy.

@Param:
tab -> lista liczb

@Result:
Wartość z tablicy.
*/
int do_magic(vector<int> tab)
{
return find_nearest(tab, get_average_value(tab));
}

/* main */
int main()
{
vector<int> tab;

tab.push_back(10);
tab.push_back(20);
tab.push_back(30);
tab.push_back(40);
tab.push_back(50);

cout << do_magic(tab);
}