AP1 2071-10-27

p1.cc

// Cerca lineal en un vector 


#include <iostream>
#include <vector>
#include <cstdlib>              // permet usar el rand() i el srand()
#include <ctime>                // permet usar el time() i el clock()
using namespace std;


// La funció now() dóna el temps de processador usat des del principi del procés, en segons.
// Típicament s'utilitza per mesuras diferències de temps (com al main()).
// Més informació: man clock

double now() {
    return clock() / double(CLOCKS_PER_SEC);
}


// Retorna un índex i tq v[x]==i si x és en v
// i, sinó, retorna -1.
// Temps: O(n).

int cerca(const vector<int>& v, int x) {
    int n = v.size();
    for (int i = 0; i < n; ++i) {
        if (v[i] == x) {
            return i;
        }
    }
    return -1;
}


int main() {
    // inicialitza el generador de nombres aleatoris en funció de l'hora actual
    srand(time(0));

    // llegeix mida del vector, el crea i l'omple amb valors aleatoris parells
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        v[i] = 2*(rand()%n);
    }

    // crida la cerca binària sobre un element x senar (que no trobarà)
    // tot cronometrant el temps.
    int x = 1 + 2*(rand()%n);
    double t1 = now();    
    int r = cerca(v, x);
    double t2 = now();

    // escriu el temps i el resultat de la cerca
    cout << t2 - t1 << endl;
    cout << r << endl;
}

p2.cc

// Cerca binària en un vector ordenat


#include <iostream>
#include <vector>
#include <cstdlib>              // permet usar el rand() i el srand()
#include <ctime>                // permet usar el time() i el clock()
using namespace std;


// La funció now() dóna el temps de processador usat des del principi del procés, en segons.
// Típicament s'utilitza per mesuras diferències de temps (com al main()).
// Més informació: man clock

double now() {
    return clock() / double(CLOCKS_PER_SEC);
}


// Prec: El vector v està ordenat creixentment.
// Retorna un índex i tq v[x]==i si x és en v
// i, sinó, retorna -1.
// Temps: O(log n).

int cerca_binaria(const vector<int>& v, int x) {
    int n = v.size();
    int esq = 0;
    int dre = n - 1;
    while (esq <= dre) {
        int mig = (esq + dre) / 2;
             if (v[mig] < x) esq = mig + 1;        
        else if (v[mig] > x) dre = mig - 1;
        else return mig;
    }
    return -1;
}


int main() {
    // inicialitza el generador de nombres aleatoris en funció de l'hora actual
    srand(time(0));

    // llegeix mida del vector, el crea i l'omple amb valors creixents parells
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        v[i] = 2*i;
    }

    // crida la cerca binària sobre un element x senar (que no trobarà)
    // tot cronometrant el temps.
    int x = 1 + 2*(rand()%n);
    double t1 = now();    
    int r = cerca_binaria(v, x);
    double t2 = now();

    // escriu el temps i el resultat de la cerca
    cout << t2 - t1 << endl;
    cout << r << endl;
}

p3.cc

#include <vector>
using namespace std;


// Retorna l'element mínim d'un vector v d'n elements (n>0) amb n comparacions.

double minim(const vector<double>& v) {
    double min = v[0];
    for (double x : v) {
        if (x < min) {
            min = x;
        }
    }
    return min;
}


// Retorna l'element màxim d'un vector v d'n elements (n>0) amb n comparacions.

double maxim(const vector<double>& v) {
    double max = v[0];
    for (double x : v) {
        if (x > max) {
            max = x;
        }
    }
    return max;
}


// Calcula els elements màxim i mínim d'un vector v d'n elements (n>0) amb 2n comparacions.

void minim_i_maxim_1(const vector<double>& v, int& min, int& max) {
    min = minim(v);
    max = maxim(v);
}


// Calcula els elements màxim i mínim d'un vector v d'n elements 
// (n>0 i n senar) amb 3n/2 comparacions.
// [Arregleu per n parell!]

void minim_i_maxim_2(const vector<double>& v, int& min, int& max) {
    int n = v.size();
    min = max = v[0];       
    for (int i = 1; i < n; i += 2) {
        if (v[i] < v[i+1]) {
            if (v[i  ] < min) min = v[i  ];
            if (v[i+1] > max) max = v[i+1];
        } else {
            if (v[i  ] > max) max = v[i  ];
            if (v[i+1] < min) min = v[i+1];            
        }
    }
}

Merci!