Diskuze: Rekurze v Javě při řešení Hanojských věží
V předchozím kvízu, Online test znalostí Java, jsme si ověřili nabyté zkušenosti z kurzu.
Člen
Lubor Pešek:24.3.2021 9:37
A co na tom nechápeš? Však ti dokonce popisuje tu cestu dole těmi
čárkami. Na rekurzi je skvělé používat debugger - tam krásně vidíš, co
ti to provádí.
Ty máš na vstupu tedy hodnoty v tomto pořadí - A C B
Když ti projde rekurze do první konečné větve, tak ti to přehodí A s C
(takže pořadí máš najednou C A B
Pak přejde do druhé větve a prohodí A s B (takže pořadí je najednou C B
A)
No a tak dále.
Lubor Pešek:24.3.2021 9:41
Editováno 24.3.2021 9:43
Kdysi dávno jsem tu popisoval v jednom komentáři rekurzi. Snad ti to pomůže k pochopení (docela jsem se v ní rozepsal:) )
Třída Pismeno, která představuje jedno písmenko + dvě, které se od něj větví binární soustavou (něco jako by "Pismeno a" byla matka a "Pismeno b" byl otec "Pismena":)
public class Pismeno {
private final Pismeno a;
private final Pismeno b;
private final String nazev;
public Pismeno(String nazev, Pismeno a, Pismeno b) {
this.a = a;
this.b = b;
this.nazev = nazev;
}
public String getNazev(){
return nazev;
}
public Pismeno getA() {
return a;
}
public Pismeno getB() {
return b;
}
}Třída PismenaVBinarniSoustave, která představuje rekurzivní test stejný jako je v třetím příkladu:
public class PismenaVBinarniSoustave{
private final Pismeno k = new Pismeno("k", null, null);
private final Pismeno j = new Pismeno("j", null, null);
private final Pismeno i = new Pismeno("i", null, null);
private final Pismeno h = new Pismeno("h", null, null);
private final Pismeno g = new Pismeno("g", null, null);
private final Pismeno f = new Pismeno("f", null, k);
private final Pismeno e = new Pismeno("e", i, j);
private final Pismeno d = new Pismeno("d", h, null);
private final Pismeno c = new Pismeno("c", f, g);
private final Pismeno b = new Pismeno("b", d, e);
private final Pismeno a = new Pismeno("a", b, c);
public PismenaVBinarniSoustave() {
rekurze(a);
}
public static void main(String[] args) {
new PismenaVBinarniSoustave();
}
private void rekurze(Pismeno p) {
if (p != null) {
System.out.println(p.toString().toUpperCase());
System.out.println(" 1:" + p.getA());
System.out.println(" 2:" + p.getB());
rekurze(p.getA());
System.out.println("*******");
rekurze(p.getB());
}
}
}
/**Postup
* Půjde nám o takovýto strom:
* H - I J - K - - H = potomek D I a J = potomci E G nemá žádné potomky
* \ / \ / \ / \ /
* D E F G D a E = potomci B F a G = potomci C
* \ / \ /
* \ / \ /
* B C B a C = potomci A
* \ /
* \ /
* \ /
* \ /
* A A = Hlavní předek
*
* Nejdřív zadáme do rekurze Pismeno A (tím myslím instanci třídy Pismeno, ne skutečné písmeno)
* Proběhne první rekurze (rekurze Áčka):
* A není null, takže podmínka platí a spustí se první řádek, který dělá novou rekurzi - rekurzi Pismene B:
* B není null, takže podmínka platí a spustí se první řádek, který dělá novou rekurzi - rekurzi Pismene D:
* D není null, takže podmínka platí a spustí se první řádek, který dělá novou rekurzi - rekurzi Pismene H:
* H není null, takže podmínka platí a spustí se první řádek, který dělá novou rekurzi - rekurzi prvního null:
* null je null, takže podmínka neprojde a žádná rekurze nevznikne. Toto je první větev rekurze H, takže se pokračuje dál ve druhé větvi
* druhá větev H je null
* null je null, takže podmínka neprojde a žádná rekurze nevznikne. Toto je druhá větev rekurze H, takže Háčko končí
* druhá větev D je null
* null je null, takže podmínka neprojde a žádná rekurze nevznikne. Toto je druhá větev rekurze D, takže Déčko končí
* druhá větev B je E
* E není null, takže podmínka platí a spustí se první řádek, který dělá novou rekurzi - rekurzi Pismene I:
* I není null, takže podmínka platí a spustí se první řádek, který dělá novou rekurzi - rekurzi prvního null:
* null je null, takže podmínka neprojde a žádná rekurze nevznikne. Toto je první větev rekurze I, takže se pokračuje dál ve druhé větvi
* druhá větev I je null
* null je null, takže podmínka neprojde a žádná rekurze nevznikne. Toto je druhá větev řekurze I, takže Íčko končí
* Druhá větev E je J
* J není null, takže podmínka platí a spustí se první řádek, který dělá novou rekurzi - rekurzi prvního null:
* null je null, takže podmínka neprojde a žádná rekurze nevznikne. Toto je první větev rekurze J, takže se pokračuje dál ve druhé větvi
* druhá větev J je null
* null je null, takže podmínka neprojde a žádná rekurze nevznikne. Toto je druhá větev řekurze J, takže Jéčko končí
* Jelikož E už třetí větev nemá, tak končí i Éčko
* Jelikož B už třetí větev nemá, tak končí i Béčko
* druhá větev A je C
* C není null, takže podmínka platí a spustí se první řádek, který dělá novou rekurzi - rekurzi Pismene F:
* F není null, takže podmínka platí a spustí se první řádek, který dělá novou rekurzi - rekurzi prvního null:
* null je null, takže podmínka neprojde a žádná rekurze nevznikne. Toto je první větev rekurze F, takže se pokračuje dál ve druhé větvi
* druhá větev F je K
* K není null, takže podmínka platí a spustí se první řádek, který dělá novou rekurzi - rekurzi prvního null:
* null je null, takže podmínka neprojde a žádná rekurze nevznikne. Toto je první větev rekurze K, takže se pokračuje dál ve druhé větvi
* druhá větev K je null
* null je null, takže podmínka neprojde a žádná rekurze nevznikne. Toto je druhá větev řekurze K, takže Jéčko končí
* Jelikož F už třetí větev nemá, tak končí i eFko
* druhá větev C je G
* G není null, takže podmínka platí a spustí se první řádek, který dělá novou rekurzi - rekurzi prvního null:
* null je null, takže podmínka neprojde a žádná rekurze nevznikne. Toto je první větev rekurze G, takže se pokračuje dál ve druhé větvi
* druhá větev G je null
* null je null, takže podmínka neprojde a žádná rekurze nevznikne. Toto je druhá větev řekurze G, takže Géčko končí
* Jelikož C už třetí větev nemá, tak končí i Céčko
* Jelikož A už třetí větev nemá, tak končí i Áčko
*
* Když půjdete řádek po řádku a zakreslovat si správně vazby, měl by vám vyjít tento obrázek:
*
* null null null null null null null null
* \ / \ / \ / \ /
* \ / \ / \ / \ /
* \ / \ / \ / \ /
* H null I J null K null null
* \ / \ / \ / \ /
* \ / \ / \ / \ /
* \ / \ / \ / \ /
* \ / \ / \ / \ /
* D E F G
* \ / \ /
* \ / \ /
* \ / \ /
* \ / \ /
* \ / \ /
* \ / \ /
* \ / \ /
* \ / \ /
* B C
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* A
*/
Odpovídá na jip123
jip123:18.4.2021 17:34
Editováno 18.4.2021 17:35
jip123:18.4.2021 17:34
Moc děkuji za odpovědi. Pomohly.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.
Zobrazeno 4 zpráv z 4.