NOVINKA: Kurz kybernetické bezpečnosti s akreditací MŠMT, nyní již od 0 Kč. Staň se žádaným profesionálem. Zjisti více:
NOVINKA: Staň se datovým analytikem a získej jistotu práce, lepší plat a nové kariérní možnosti. Více informací:
Avatar
david novotny
Člen
Avatar
david novotny:9.12.2016 6:25

Ahoj, učím se Objective Caml. Snažím se vymyselt algoritmus, který by pomíchal list následovně:

[6; 4; 8; 2; 3; 10; 7; 9] ---> ([4; 8; 2; 7]) 6 ([3; 10; 9])

To znamená pivotka doprostřed, a pak jestli na liché pozici ze zbytku bude číslo větší než pivotka, dá se do listu napravo; jestli větší ta pak nalevo. Pro čísla na sudých pozicích by to pak bylo přesně opačně.

Vrtám si s tím dlouho hlavu a napadají mě jenom samé komplikované věci. Určitě existuje nějaké elegantní řešení. Poraďte, prosím! Děkuji

 
Odpovědět
9.12.2016 6:25
Avatar
Libor Šimo (libcosenior)
Tvůrce
Avatar
Libor Šimo (libcosenior):9.12.2016 8:31

Ukaz to svoje komplikovane.

Nahoru Odpovědět
9.12.2016 8:31
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
david novotny
Člen
Avatar
david novotny:9.12.2016 14:00

Ahoj, napadla mě třeba následující myšlenka. Přijde mi ale dost stupidní i komplikovaná, a asi by to šlo vymyslet tisíckrát snadněji různým filtrováním, akorát bych potřeboval poradit jak...

1. Napsat pomocný program, který vezme list s tím že vynechá první číslo, například
(6, 5, 2, 7, 9) -> (1, 2, 3, 4)

2.. napsat pomocný program, který z listu napíše další list, který bude indikovat, jestli pozice v zadaném listu jsou sudé nebo liché, například
( 5, 2, 7, 9) -> (1, 2, 3, 4)
Tohle bych asi vymyslel nějakou rekurzivní funkcí, nevím jestli by to šlo prostým mappingem.

3. napsat pomocný program, který vezme ze zadaného listu pivotku a list nechá bez pivotky, například
(6, 5, 2, 7, 9) -> 6

4. Mám tedy dva listy a pivotku
(5, 2, 7, 9) , náš list bez pivotky
(1, 2, 3, 4) , list který indikuje jestli pozice prvního listu jsou sudé nebo liché
6

Vytvořil bych pak program který vezme tyto dva listy a pivotku, a do kterého jsou ještě vloženy dva různé prázdné listy, levý a pravý.

Tento program by pak porovnal jestli první číslo v listu je 1 nebo 2, a podle toho by pak vyhodnotil vložil číslo buď do levého listu nebo pravého podle příslušných pravidel. To by samozřejmě fungovalo rekurzivně, a šlo by se postupně po každém místě, dokud by první dva listy nebyly prázdné.

5. Pak by se tedy musel ještě vytvořit program, který by všechny výše zmíněné pomocné spojil dohromady.

 
Nahoru Odpovědět
9.12.2016 14:00
Avatar
Libor Šimo (libcosenior)
Tvůrce
Avatar
Libor Šimo (libcosenior):9.12.2016 14:21

V jednom liste oddelujes cisla ; a v inom ,
Co je spravne?
Da sa v liste pristupovat k jednotlivym prvkom tatkto: list[0] je prvy prvok atd.?
Nepoznam jazyk objective caml, preto sa pytam.

Nahoru Odpovědět
9.12.2016 14:21
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Libor Šimo (libcosenior)
Tvůrce
Avatar
Libor Šimo (libcosenior):9.12.2016 14:38

Algoritmus by mohol byt:

  • premenna pivotka = list[0]
  • novy list_lavy, novy list_pravy
  • v cykle prechadzas list od druhej pozicie
  • ak je pozicia licha a zaroven je vacsia ako pivotka

    pridaj hodnotu do list_pravy

  • v opacnom pripade

    pridaj hodnotu do list_lavy

Podobne to bude aj so sudou poziciou, len pridavanie bude opacne.

Nakoniec to len vypises.

Nahoru Odpovědět
9.12.2016 14:38
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
coells
Tvůrce
Avatar
Odpovídá na david novotny
coells:9.12.2016 18:29

Jestli zvládneš obyčejnou partition funkci pomocí akumulátoru, tak to můžeš řešit identicky.
Jenom použiješ akumulátory dva a prohazuješ je.

Učesat to, dodělat a případně převést na TRO verzi (přes lfold) už bys měl zvládnout sám, nástřel myšlenky je jasný.

List.fold_right
        (fun x (pivot, swap, lacc, racc) -> if x < pivot
                then (pivot, not swap, racc, x::lacc)
                else (pivot, not swap, x::racc, lacc))
        [4; 8; 2; 3; 10; 7; 9]
        (6, false, [], [])
;;

Libor Šimo (libcosenior)

OCaml je funkcionální jazyk, věta v cykle prechadzas list od druhej pozicie se považuje za vrchol barbarství ;-)

 
Nahoru Odpovědět
9.12.2016 18:29
Avatar
Libor Šimo (libcosenior)
Tvůrce
Avatar
Odpovídá na coells
Libor Šimo (libcosenior):9.12.2016 18:36

Sorry, ocaml nepoznam. Chcel som len pomoct, lebo ten jeho navrh sa mi zdal dost prehnany.

Nahoru Odpovědět
9.12.2016 18:36
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
coells
Tvůrce
Avatar
Odpovídá na Libor Šimo (libcosenior)
coells:9.12.2016 20:32

Až tak přehnaný není, jen dělá chybu, když místo definice lokální vlastnosti (sudá, lichá), definuje vlastnost globální (index).

 
Nahoru Odpovědět
9.12.2016 20:32
Avatar
david novotny
Člen
Avatar
Odpovídá na coells
david novotny:10.12.2016 19:04

Ahoj díky moc za pomoc, funguje to krásně. Akorát mi to vyhazuje ty listy v opačném pořádí, pravý a pak levý. Nějaký nápad jak to opravit?

 
Nahoru Odpovědět
10.12.2016 19:04
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 9 zpráv z 9.