Algoritmi lezione 8

//divide et impera

#include <iostream>
#include <chrono>

using namespace std;
#include "../utility_vettori.h"

long long tot_chiamate = 0;

string cerca_stringa_max(string v[], int sx, int dx)
{
  tot_chiamate++;

  string min_sx = "", min_dx = "";

  if (sx==dx) //un elemento solo
  {
    return v[sx];
  }
  else
    if (sx + 1 == dx ) //due elementi
    {
      if (v[sx]>v[dx])
        return v[sx];
      else
        return v[dx];
    }
    else
    {
      int mediano = sx +(dx - sx)/2;
      //cout << sx << " " << mediano << endl;
      min_sx = cerca_stringa_max(v, sx, mediano);

      //cout << mediano+1 << " " << dx << endl;
      min_dx = cerca_stringa_max(v, mediano+1, dx);
    }

    if (min_sx>min_dx)
      return min_sx;
    else
      return min_dx;
}


const int QUANTI_ELEMENTI = 98304;
string v[QUANTI_ELEMENTI];

int main()
{
  carica_vettore_stringhe(v, QUANTI_ELEMENTI - 1, 10);

  v[QUANTI_ELEMENTI-1] = string(100, 'z');

  //ordino dal più piccolo al più grande
  for (int i=0; i<QUANTI_ELEMENTI-1; i++)
    for (int j=i+1; j<QUANTI_ELEMENTI; j++)
      if (v[j]>v[i]) swap(v[i], v[j]);

  int numero_run = 1;
  int ripetizioni_per_run = 1;


// RICERCA CON RESTITUZIONE DELL'ELEMENTO MASSIMO
  string s = "";
  Cronometro(Stato::START);
  for(int conta_run =0; conta_run<numero_run; conta_run++)
    for (int conta=0; conta<ripetizioni_per_run; conta++)
      s = cerca_stringa_max(v, 0, QUANTI_ELEMENTI - 1);

  cout << "Tempo impiegato (ELEMENTO): " << Cronometro(Stato::STOP) << endl;
  cout << "STRINGA MAX: " << s << endl;

  cout << "Numero chiamate alla funzione: " << tot_chiamate << endl;

  return 0;
}