Algoritmai


Informatikos Špera. Paieška paprastame sąraše. Nuosekli paieška. Paieška interpoliavimas. Binarinė paieška. Posąrašio dydžio nustatymo metodas. Ribos numeris visada 2 laipsnyje. Rūšiavimo algoritmai. Algoritmai grafuose. Išrinkimas. Operacijų apjungti ir rasti atlikimo algoritmas.


Tegu įrašai išdėstyti atsitiktinai kaip buvo įrašyti. Reikia surasti duotą įrašą pagal raktą. Nuosekliai ieškant reikia peržiūrėti visus įrašus nuosekliai. Vid. Peržiūrėų įrašų sk. Ieškant yra lap =l/. Jei įrašo nėra teks peržiūrėti visus įrašus l. Tarkim ieškomo įrašo su tikimybe p0 nėra sąraše, tada vid. Peržiūrėtų įrašų sk. Lap=l*p0+åi=1l (i*pi ); pi=1-p0/l. Ieškant įrašo sutvarkytame faile(įrašai išdėstyti pagal raktą) reikia peržiūrėti iš eilės, todėl vid. Peržiūrėtų įrašų sk. Tas pats: lsp=l/. Jei ieškomo įrašo nėra, tai paieška nutraukiama kai eilinis raktas bus didesnis už užduotą. Atliekant k įrašų paiešką jei sąrašai surūšiuoti ir žinomas pirmo įrašo raktas k(1) ir paskutinio k(n) tai galima apskaičiuoti p=x-k(1)/k(n)-k(1)naudojama surūšiuotame masyve. Jis dalinamas pusiau ir ieškomas raktas lyginamas su vidurio raktu. Idealus masyvo dydis 2n-. Jei 31 įrašas reikės žingsnių, kad surasti įrašą 31=25-. Bendru atveju 2n-1-1< n £ 2n-. Kai įrašų sk. Bet koks, tai naudojami tokie alg.

Algoritmai. (2010 m. Kovo 03 d.). http://www.mokslobaze.lt/algoritmai.html Peržiūrėta 2016 m. Gruodžio 03 d. 08:56