Algoritmuselmélet gyakorlat (2)
1. Legyen adott egy egészekből álló A[1:n] tömb valamint egy b egész szám. Szeretnénk hatékonyan eldönteni, hogy van-e két olyan ![]() ![]() 2. A (növekvően) rendezett A[1:n] tömb k darab elemét valaki megváltoztatta. A változtatások helyeit nem ismerjük. Javasoljunk ![]() 3. Adott egy rendezett univerzum n különböző eleméből álló S halmaz. Legyen ![]() ![]() ![]() ![]() 4. Adott egy egész számokat tartalmazó A[1:n] tömb, amelyben legfeljebb n elempár áll inverzióban egymással. (Két elem akkor áll inverzióban, ha a nagyobb megelőzi a kisebbet.) Igaz-e, hogy a buborékrendezés rendezi a tömböt (a) legfeljebb n összehasonlítással? (b) legfeljebb n cserével? 5. Adjunk konstans szorzó erejéig optimális számú összehasonlítást használó módszert az ![]() 6. Adjunk hatékony algoritmust egy kupac tizedik legkisebb elemének a megtalálására. Elemezzük a módszer költségét. 7. Egy rendezett halmazból n elem kupacban van elhelyezve. Bizonyítsuk be, hogy a legnagyobb elem megkereséséhez ![]() 8. Adott egy dobozban n különböző méretű anyacsavar, valamint egy másik dobozban a hozzájuk illő apacsavarok. Kizárólag a következő összehasonlítási lehetőségünk van: Egy apacsavarhoz hozzápróbálunk egy anyacsavart. A próbának háromféle kimenete lehet: ![]() ![]() ![]() ![]() 9. Vázoljunk egy O(n) időigényű algoritmust (az időkorlát bizonyításával együtt) n olyan egész számból álló sorozat rendezésére, melynek elemei az (a) ![]() (b)(*) ![]() 10. Adottak a sík egész koordinátájú ![]() ![]() 11. Valaki egy összehasonlításon alapuló állítólagos rendezési algoritmusról azt mondja, hogy mivel az eljárás minden olyan sorozatot jól rendez, amelyben a rendezett sorrendhez képest csak egyetlen pár van felcserélve, ezért az algoritmus tetszőleges soroztot rendez. Helyes-e ez a következtés? Gondolkozni való feladat 12. Hány összehasonlítással lehet rendezni öt elemet? 13. Egy n-szer n-es táblázatban úgy van elhelyezve n2 db különböző szám, hogy mind a sorok mind az oszlopok monoton növekvőek. Mutassuk meg, hogy ekkor a keresés lépésszáma ![]() |