Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
Avatar
jip123
Člen
Avatar
jip123:10.3.2021 13:13

Momentálně se zabývám rekurzí, pochopil jsem faktoriál i Fibonacciho posloupnost.
Ale narazil jsem u Hanojských věží. Nějak nechápu, jak se dospělo pro disk 1 k C,B,A. V grafu je to označeno červeným kroužkem. Asi bych potřeboval nějaké polopatičtější vysvětlení.

Zkusil jsem: Nenašel jsem přijatelné vysvětlení. Na Google.

Chci docílit: Pochopit alespoň základy rekurze

 
Odpovědět
10.3.2021 13:13
Avatar
Lubor Pešek
Člen
Avatar
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.

Nahoru Odpovědět
24.3.2021 9:37
Existují dva způsoby, jak vyřešit problém. Za prvé vyhoďte počítač z okna. Za druhé vyhoďte okna z počítače.
Avatar
Lubor Pešek
Člen
Avatar
Lubor Pešek:24.3.2021 9:41

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 PismenaVBinar­niSoustave, 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
 */
Editováno 24.3.2021 9:43
Nahoru Odpovědět
24.3.2021 9:41
Existují dva způsoby, jak vyřešit problém. Za prvé vyhoďte počítač z okna. Za druhé vyhoďte okna z počítače.
Avatar
jip123
Člen
Avatar
Odpovídá na jip123
jip123:18.4.2021 17:34

Moc děkuji za odpovědi. Pomohly.

Editováno 18.4.2021 17:35
 
Nahoru Odpovědět
18.4.2021 17:34
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.