Új hozzászólás Aktív témák

• #348 Miracle senior tag Cathfaern #344

  Új Válasz 2004-11-16 00:31:00 #348

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Miracle

  senior tag

  válasz Cathfaern #344 üzenetére

  sorry.
  mondjuk így néz ki amit akarsz:
  
  int a[1..100]; /* ebbe a tömbbe eltárolod a számokat, amikben keresni akarsz, persze _növekvő_ sorrendben.*/
  struct nincs_meg{};
  
  ekkor a függvény(a pontos a sorok elején csak a tabulálás miatt vannak ott):
  
  int logker(const int[] t, const int b, const int e, const int what)
  {
  . int temp = (b+e) /2;
  . if (t[temp] > what)
  . {
  . return logker(v, b, temp, what);
  . }
  . else
  . {
  . if (v[temp] == what) return temp;
  . if (b = e) throw(nincs_meg);
  . return logker(v, temp, e, what);
  . }
  }
  
  ez egy rekurzív megvalósítás, nem garantálom, hogy műxik, nem fordítottam le, de szerintem működni fog. vedd észre, hogy hiába statikus az a tömb mérete, ezt a függvény nem használja ki, bármekkora tömböt átadhatsz neki, csak a 2. és a 3. változó 0, illetve tömbméret-1 legyen. megvalósítható templatekkel is, de nem szeretném bonyolítani. így tudod használni
  
  try
  {
  logker(a,0,99,40) //a fenti a tömbben keressük a 40 értéket
  }
  catch(nincs_meg){std :: cout << ''nincs ilyen értékű elem a tömbben\n'';}
  
  remélem érthető(és működik)
  
  a műveletigény azt jelenti, hogy ezzel az algoritmussal ha n hosszú a tömb, akkor legrosszab esetben log_2(n) felső-egész-rész lépésben megtalálod a keresett számot, log2n pedig az a szám, mire 2őt emelve n-et kapunk, így tudod kiszámolni számológéppel: log_2(n) = lg(n) / lg(2) (itt lg tetszőleges logaritmus, amit találsz a számológépeden) megjegyzem, hogy az átlagos műveletigény azt feltételezve, hogy a keresett száém megtalálásának valószínűsége minden rekeszben 1/n log_2(n) felső-egészrész -1
  és bocs hogy összezavartalak, remélem kiengeszteltelek..

Új hozzászólás Aktív témák