Elemi programozási tételek V.: metszet, unió
Elemi programozási tételek V.: metszet, unió
A metszetképzés tétele
Általános feladat: Rendezésünkre áll egy N és egy M elemű halmaz az A() és a B() vektorban ábrázolva. Készítsük el a két halmaz metszetét a C() vektorba!
Algoritmus:
Eljárás
CN:=0
Ciklus I=1-től N-ig
J:=1
Ciklus amíg J<=M és A(I)<>B(J)
J:=J+1
Ciklus vége
Ha J<=M akkor CN:=CN+1 : C(CN):=A(I)
Ciklus vége
Eljárás vége.
Unióképzés tétele
Általános feladat: Rendezésünkre áll egy N és egy M elemű halmaz az A() és a B() vektorban ábrázolva. Készítsük el a két halmaz egyesítését a C() vektorba!
Algoritmus:
Eljárás
Ciklus I=1-től N-ig
C(I):=A(I)
Ciklus vége
CN:=N
Ciklus J=1-től M-ig
I:=1
Ciklus amíg I<=N és A(I)<>B(J)
I:=I+1
Ciklus vége
Ha I>N akkor CN:=CN+1 : C(CN):=B(J)
Ciklus vége
Eljárás vége.
Hozzászólások (3)
ezek az algoritmusok hibatlanok ez 100 %.En nem teszteltem oket de ranezesre a programozasi ismereteim alapjan jok.
A fenti (eredeti) algoritmusok jók – legalábbis “borz” által említett hibáik nem léteznek.
Kedves borz!
A ciklus addig ismétlődik, amíg különböznek az összevetett tömbelemek, vagyis akkor áll le, amikor egyezőt találtunk, vagy persze ha elfogyott a hasonlítani való. Ezek után egy elágazás dönti el, hogy az előbbi két ok közül melyik is az igaz, így ha elfogyott az elem, nem volt egyező (ezt használjuk az uniónál), ha viszont még akadna, akkor egyezés történt (ezt meg a metszetnél tesszük az eredménybe). Teljesen korrekt tehát az egyenlőtlenség a ciklusfeltételben, hiszen ezzel találjuk meg az egyező elemeket.
Üdv!
Szerintem egy apró, de lényeges hiba van a megadott algoritmusokban. Természetesen én ellenőriztem is.
(Nem ellenőriztétek!?)
1. Metszetképzés tétele
Szerintem, és a próba alapján is a következő sorban a nem egyenlő helyett egyenlőre lenne szükség!
Ciklus amíg J<=M és A(I)B(J)
helyett:
Ciklus amíg J<=M és A(I)=B(J)
Hiszen a metszetben azokat az elemeket kell szerepeltetni, amelyek mindkét halmazban megtalálhatóak, azaz a megegyezőket.
2. Únióképzés tétele
Sajnos az únióképzés algoritmusa is hibás!!
Abban is hasonló a hiba, tehát:
Ciklus amíg I<=N és A(I)B(J)
helyett:
Ciklus amíg I<=N és A(I)=B(J)
szükséges, mert most éppen az egyezőket kell kiejteni!
Remélem segíthettem. Jó munkát!