Algoritmi lezione 9

//scansione lineare ma a passo due

#include <iostream>
#include <chrono>
#include <ctime>
#include <random>

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



string cerca_stringa_min_max(string v[], int dimensione)
{
  string stringa_max = v[0];
  string stringa_min = v[0];

  for (int i=1; i<dimensione; i++)
    if (v[i]>stringa_max)
      stringa_max = v[i];
    else
      if (v[i]<stringa_min)
        stringa_min = v[i];

  return stringa_min + "/" + stringa_max;
}






string cerca_stringa_min_max_SMART(string v[], int dimensione)
{

  string stringa_max = "";
  string stringa_min = "";
  int inizia_da = -1;

  //ipotesi semplificatica: il numero di elementi è pari
//  if (dimensione%2 ==  0)  //numero pari di elementi
//  {
//    if (v[0]<v[1])
//    {
//      stringa_min = v[0];
//      stringa_max = v[1];
//    }
//    else
//    {
//      stringa_min = v[1];
//      stringa_max = v[0];
//    }
//    inizia_da = 2;
//  }
//  else  //numero dispari di elementi
//  {
//    stringa_max = v[0];
//    stringa_min = v[0];
//
//    inizia_da = 1;
//  }

  if (v[0]<v[1])
  {
    stringa_min = v[0];
    stringa_max = v[1];
  }
  else
  {
    stringa_min = v[1];
    stringa_max = v[0];
  }
  inizia_da = 2;

  for (int i=inizia_da; i<dimensione-1; i+=2)
    if (v[i]<v[i+1])
    {
      if (v[i] < stringa_min)
        stringa_min = v[i];

      if (v[i+1] > stringa_max)
        stringa_max = v[i+1];
    }
    else
    {
      if (v[i] > stringa_max)
        stringa_max = v[i];

      if (v[i+1] < stringa_min)
        stringa_min = v[i+1];
    }


  return stringa_min + "/" + stringa_max;
}

const int QUANTI_ELEMENTI = 3000;
const int LUNGHEZZA = 2000;
string v[QUANTI_ELEMENTI];

int main()
{

  carica_vettore_stringhe(v, QUANTI_ELEMENTI, LUNGHEZZA);



  return 0;
}