Advertisement
fcamuso

Algoritmi lezione 8

Feb 13th, 2024
931
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.69 KB | None | 0 0
  1. //divide et impera
  2.  
  3. #include <iostream>
  4. #include <chrono>
  5.  
  6. using namespace std;
  7. #include "../utility_vettori.h"
  8.  
  9. long long tot_chiamate = 0;
  10.  
  11. string cerca_stringa_max(string v[], int sx, int dx)
  12. {
  13.   tot_chiamate++;
  14.  
  15.   string min_sx = "", min_dx = "";
  16.  
  17.   if (sx==dx) //un elemento solo
  18.   {
  19.     return v[sx];
  20.   }
  21.   else
  22.     if (sx + 1 == dx ) //due elementi
  23.     {
  24.       if (v[sx]>v[dx])
  25.         return v[sx];
  26.       else
  27.         return v[dx];
  28.     }
  29.     else
  30.     {
  31.       int mediano = sx +(dx - sx)/2;
  32.       //cout << sx << " " << mediano << endl;
  33.       min_sx = cerca_stringa_max(v, sx, mediano);
  34.  
  35.       //cout << mediano+1 << " " << dx << endl;
  36.       min_dx = cerca_stringa_max(v, mediano+1, dx);
  37.     }
  38.  
  39.     if (min_sx>min_dx)
  40.       return min_sx;
  41.     else
  42.       return min_dx;
  43. }
  44.  
  45.  
  46. const int QUANTI_ELEMENTI = 98304;
  47. string v[QUANTI_ELEMENTI];
  48.  
  49. int main()
  50. {
  51.   carica_vettore_stringhe(v, QUANTI_ELEMENTI - 1, 10);
  52.  
  53.   v[QUANTI_ELEMENTI-1] = string(100, 'z');
  54.  
  55.   //ordino dal piΓΉ piccolo al piΓΉ grande
  56.   for (int i=0; i<QUANTI_ELEMENTI-1; i++)
  57.     for (int j=i+1; j<QUANTI_ELEMENTI; j++)
  58.       if (v[j]>v[i]) swap(v[i], v[j]);
  59.  
  60.   int numero_run = 1;
  61.   int ripetizioni_per_run = 1;
  62.  
  63.  
  64. // RICERCA CON RESTITUZIONE DELL'ELEMENTO MASSIMO
  65.   string s = "";
  66.   Cronometro(Stato::START);
  67.   for(int conta_run =0; conta_run<numero_run; conta_run++)
  68.     for (int conta=0; conta<ripetizioni_per_run; conta++)
  69.       s = cerca_stringa_max(v, 0, QUANTI_ELEMENTI - 1);
  70.  
  71.   cout << "Tempo impiegato (ELEMENTO): " << Cronometro(Stato::STOP) << endl;
  72.   cout << "STRINGA MAX: " << s << endl;
  73.  
  74.   cout << "Numero chiamate alla funzione: " << tot_chiamate << endl;
  75.  
  76.   return 0;
  77. }
  78.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement