// Ricerca binaria in modalità "ricorsiva"
/* 
 * File:   main.cpp
 * Author: maurizio
 *
 * Created on 4 maggio 2010, 7.30
 */

#include <stdlib.h>
#include <iostream>

using namespace std;

/*
 * 
 */

// numero massimo previsto di elementi del vettore 
const int MAX=20;

int ricercaBinariaRicorsiva(int x, int v[], int n, int l, int r);
void stampa(int v[], int n);

int main(int argc, char** argv) {

    // considero un array di interi ORDINATO
    // se gli elementi non sono in ordine
    // posso sempre ordinare l'array
    int v[MAX]={2,5,6,7,9,10,11,14,16,20,22,23,29,31};

    // numero di elementi del vettore v
    // le locazioni complessive sono 14
    // le altre 6 rimangono libere
    int n=14;

    cout << "Numero di elementi: " << n << endl;

    if (n>MAX)
	return -2;

    stampa(v,n);

    // elemento da cercare
    int x=16;

    // trovo la posizione dell'elemento
    int i=ricercaBinariaRicorsiva(x,v,n,0,n-1);

    if (i!=-1)
        // la visualizzo
        cout << "Trovato l'elemento " << x << " in posizione " << i << "." << endl;
    else
        cout << "Elemento non trovato o numero massimo di elementi superato." << endl;

    return (EXIT_SUCCESS);
}

// effettua una ricerca binaria dell'elemento x nel vettore v lungo n
// l punta all'"elemento di sinistra" dell'array (puntatore di sinistra)
// r punta all'"elemento di destra" dell'array (puntatore di destra)
int ricercaBinariaRicorsiva(int x, int v[], int n, int l, int r) {
    // se ci sono elementi
    if (l<=r) {
        // trovo la posizione "centrale"
        int i=(l+r)/2;

        // se trovo l'elemento restituisco la posizione in cui si trova
        if (v[i]==x)
            return i;

        // se l'elemento x si trova nella "seconda metà" dell'array
        if (v[i]<x)
            // faccio la ricerca nella seconda metà
            return ricercaBinariaRicorsiva(x,v,n,i+1,r);
        else
            // faccio la ricerca nella prima metà
            return ricercaBinariaRicorsiva(x,v,n,l,i-1);
    }

    // significa che non ho trovato l'elemento
    return -1;
}

void stampa(int v[], int n) {
    for (int i=0; i<n; i++)
        cout << "Elemento di posto " << i << ": " << v[i] << endl;
}


// Esercizio 12 pag. 175
#include <cstdlib>
#include <iostream>

using namespace std;

int prodRic(int a, int b) {
       if (b==0)
          return 0;

       return prodRic(a,b-1)+a;
}

int main(int argc, char *argv[])
{
    int a=7;
    int b=4;

    int c=prodRic(a,b);

    cout << "Prodotto ricorsivo " << c << endl;

    return EXIT_SUCCESS;
}


// Esercizio 13 pag. 175
/* 
 * File:   main.cpp
 * Author: maurizio
 *
 * Created on 27 maggio 2010, 17.33
 */

#include <stdlib.h>
#include <iostream>
#include <math.h>

using namespace std;

/*
 * 
 */

double powRic(double x, int n);

int main(int argc, char** argv) {
    double x=32.0;
    
    int n=7;
    
    cout << x << " elevato a " << n << ": " << powRic(x,n) << endl;
    cout << "Confronto con la funzione built-in pow appartenente alla libreria standard math.h" << endl;
    cout << x << " elevato a " << n << ": " << pow(x,n) << endl;

    return (EXIT_SUCCESS);
}

double powRic(double x, int n) {
    if (n==1)
        return x;

    return x*powRic(x,n-1);
}