Next: About this document ...
Megoldások az második gyakorlathoz
1. A teljes feladatsorban szerepel a megoldás a Rendezés 21. feladatnál.
2. A teljes feladatsorban szerepel a megoldás a Rendezés 10. feladatnál.
3. Vegyünk
elemet, ezeket rendezzük. Ez
lépés.
Az így kiválasztott elemek lesznek a keresett Si halmazok első elemei.
Most hogy már megvannak a halmazok, azt kell
csak eldönteni, hogy a többi elemek mely halmazokba kerüljenek.
Ehhez vegyünk egyet a maradék elemek közül
és határozzuk meg, hogy melyik két alapítóelem közé esik. Ez
lépés bináris kereséssel. Tegyük ezután annak az alapítóelemnek
a halmazába, amelyik éppen nagyobb nála, vagy ha nincsen ilyen (
nagyobb a legnagyobbnál is), akkor a legnagyobbéba. Az így kapott
felosztás teljesíti a feladat feltételét, az elemek elhelyezése pedig
n darab bináris kersés, azaz
lépés.
4. A teljes feladatsorban szerepel a megoldás a Rendezés 18. feladatnál.
5. Az összefésüléshez hasonlóan járunk el, most m darab halmazt
fésünk össze. Ezt úgy tesszük, hogy felveszünk egy mk
méretű B tömböt a végeredménynek, ebbe írjuk majd ki az elemeket
rendezetten, az Ai tömbök még fel nem dolgozott legkisebb elemeit pedig
egy kupacban tartjuk. Az elején a B üres, a kupacba pedig minden
Ai-ből a legkisebb elemet tesszük. Egy lépés a következő: töröljük
a minimális elemet a kupacból és áttesszük a B-be, aztán pedig
abból az Ai-ből, ahonnan a most kirakott elem jött beszúrjuk a
következőt a kupacba. Összesen kell mk ilyen lépés, minden lépés egy
MINTÖR és egy BESZÚR művelet, ez összesen
lépés, mert a kupac
mérete m.
Ez optimális, mert már az Ai tömbök j-edik elemeinek rendezéséhez
is kell
lépés, ezek pedig rendezetten kiolvashatók
mk idôben a rendezett B
tömbből.
6. A teljes feladatsorban szerepel a megoldás a Rendezés 37. feladatnál.
7. A teljes feladatsorban szerepel a megoldás a Rendezés 40. feladatnál.
8. A teljes feladatsorban szerepel a megoldás a Rendezés 27. feladatnál.
9. A teljes feladatsorban szerepel a megoldás a Rendezés 29. feladatnál.
10. Keressük meg a legnagyobb x koordinátával rendelkező pontot, legyen ez
mondjuk a Pi, ezt n lépésben megtehetjük.
Számoljuk ki minden másik Pj pontra a Pi-Pj egyenes
meredekségét, ez egyenesenként konstans lépés, összesen O(n).
Ezen meredekségek közül válasszuk ki a legnagyobbat (O(n) lépés), az így kapott
egyenes jó lesz.
11. A teljes feladatsorban szerepel a megoldás a Rendezés 53. feladatnál.
12. A teljes feladatsorban szerepel a megoldás a Rendezés 16. feladatnál.
13. Tessék gondolkodni.
Next: About this document ...
Judit Csima
1999-11-10