» Poradna » Programy

Prolog - strom

 |   | 

Potreboval by som poradit s Prolog-om.
Potrebujem spravit program, ktory by dokazal rozpoznat nasledujucu strukturu binarneho stromu.

list stromu je oznaceny ako: leaf(Label). takze napr. leaf(3), leaf(7) su listy a taktiez najmensimi moznymi binarnymi stromami.

Ak mame binarne stromu B1 a B2, ich kombinaciou ziskame novy binarny strom:
tree: tree(B1,B2).
takze mozeme vytvorit napriklad strom: tree(leaf(1), leaf(2)).
alebo
tree(tree(leaf(1),leaf(2)),leaf(4)).

potrbujem definovat funkciu swap/2, ktore vymeni prvy v strome takze:
?- swap(tree(tree(leaf(1), leaf(2)), leaf(4)),T).
T = tree(leaf(4), tree(leaf(2), leaf(1))).
yes

Prolog sa este len ucim a nad touto ulohou som stravil dost casu, skusal som aj google, ale k nicomu nepriviedol. Budem vdacny za akukolvek radu.

Vdaka.

Mohlo by vás také zajímat

Odpovědi na otázku

 |   | 

Nejsem si jisty, zda jsem pochopil co chces presne udelat. Chces v jednom stromu prohodit levou a pravou stranu?
Me prijde, ze ten strom mas vytvoreny nejak zbytecne slozite. Asi bych to udelal nasledovne.

definice listu:
leaf(X).

definice stromu:
tree((leaf|leaf)). //uzel v posledni vrstve
tree((tree|tree)). //vsechny ostatni uzly

prohozeni stran:
swap(tree(X|Y), tree(Y|X)). //funkce, kde jeden argument je prevraceny strom, ktery je ve druhem argumentu

Prolog uz jsem nejaky ten patek nevidel a tak se omlouvam, pokud placam nesmysly.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

No, skor si myslel tu definiciu s hranatymi zatvorkami, tudiz:

tree([leaf|leaf]). %uzel v posledni vrstve
tree([tree|tree]). %vsechny ostatni uzly

Cize podla teba je stromom zoznam obsahujuci bodka dvojicu v tvare "leaf . leaf" alebo "tree . tree" (kde leaf aj tree su termy)...

a) za | v zozname musi byt zoznam, cize ked uz tak [tree|[tree]], ale to je zbytocnost, to mozes rovno napisat [tree, tree].

b) kedze leaf/0 ani tree/0 nemas zadefinovane, tak tvoj predikat tree sa splni vtedy a len vtedy, ked doslova napises:

tree([tree|tree]).

alebo

tree([leaf|leaf]).

c) podla tvojej definicie nemoze mat uzol jedneho potomka list a druheho potomka podstrom, pripustas len uzly s oboma potomkami stromami alebo oboma potomkami listami.

------------------------------------------------------------------

Ked uz by si na to siel cez zoznam, tak:

leaf(_).

tree(leaf(_)).
tree([tree(_), tree(_)]).


Predikat s vymenou by bol:

swapped(leaf(X), leaf(X)).
swapped(tree([X,Y]), tree([Y,X])).

Pripadne na vsetkych urovniach stromu:

swapped(leaf(X), leaf(X)).
swapped(tree([AL,AR]), tree([BL,BR])) :-
swapped(AL,BR),
swapped(AR,BL).


Potom yay-ov priklad:

swapped(tree([tree([leaf(1),leaf(2)]),leaf(4)]),T).
T = tree([leaf(4), tree([leaf(2), leaf(1)])]).


-----------------------------------------------------------------------

"//funkce, kde jeden argument "

Kristepane, odkedy su v prologu funkcie? A tiez preto by sa to nemalo volat "swap" (co vyjadruje cinnost, ze sa ma nieco urobit), ale skor "swapped" (co vyjadruje vztah, medzi argumentami), resp. idealne by malo byt mozne nazov predikatu vlozit "do stredu" a malo by to zniet ako veta, napriklad:

is_swapped(A,B). by sa dalo citat (a mimochodom, prolog by to v takomto tvare aj zobral):

A is_swapped B.


alebo napriklad


maluje(janko, portret). by sa dalo citat:

janko maluje portret.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

"za | v zozname musi byt zoznam"

Teda nemusi, ale to potom pracujes s "holou" bodka dvojicou a tusim ze nie vsetky prology to vobec dovoluju.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

ad c) Ano, myslel jsem vyvazeny strom
ad vsechno ostatni: psal, jsem, ze prolog us jsem delsi dobu nevidel a snazil jsem se jenom zapsat myslenku, nikoliv dokonale spravne reseni, kter pujde interpreter sezere.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

Tak to si potom myslel vyvazeny strom LEN s parnym poctom listov.

Ak pripustas nasledovnikov len prave dva listy alebo prave dva stromy, ako by si spravil vyvazeny strom s tromi listami?

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

Vzdyt v dotazu se pise, ze strom ma byt binarni.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

Ja neviem, nerobis si ty uz srandu? ;) Asi by si si mal zopakovat definiciu binarneho stromu. :)

Binarny strom znamena, ze kazdy uzol ma maximalne dvoch nasledovnikov (cize moze mat 0 [vtedy je to list], 1 alebo 2). Dokonca aj keby si pripustil len 0 alebo 2 nasledovnikov, tak BINARNY strom s tromi vrcholmi perfektne zostrojis (a dokonca je aj vyvazeny):

KOREN
- list(1)
- strom(list(2),list(3))

(plus koren by mal hodnotu 2, vnutorny vrchol 3 a mame hned aj binarny vyhladavaci strom)



Wiki priklad binarneho stromu: upload.wikimedia.org ...

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

myslim, ze si mylis "binarny strom" a "vyvazeny binarny strom"

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

to malo byt k "jehoVista" a nie k STU

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

dakujem za odpoved.
zoznamy som sa este len zacal ucit a tak hned ako si o nich docitam kapitolu vyskusam riesenia, ktore si navrhol.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

No hned pre zaciatok - vseobecny binarny strom ma hodnoty aj vo vnutornych uzloch, cize spravne by si mal mat hodnotu aj v strukture tree, strom by som skor definoval takto (ak je aj prazdny strom stromom... nech sa to nekomplikuje):

tree(_,L,R) :-
tree(L), tree(R).
tree(nil).


"potrbujem definovat funkciu swap/2, ktore vymeni prvy v strome takze:"

Nenapisal si sice, ze co "prvy" sa ma vymenit... :P Ale pokial by si chcel vymenit podstromy len na prvej urovni, tak je to primitivne jednoduche:

swapped( tree(X,L,R), tree(X,R,L) ).


Ak to chces na vsetkych urovniach:

swapped( nil, nil ).
swapped( tree(X, L1, R1) , tree(X, L2, R2) ) :-
swapped( L1, R2 ),
swapped( R1, L2 ).


Potom to funguje napriklad takto:

?- swapped(tree(4,tree(1,nil,nil),tree(5,tree(4,nil,nil),tree(5,nil,nil))),X).
X = tree(4, tree(5, tree(5, nil, nil), tree(4, nil, nil)), tree(1, nil, nil)).

--------------------------------------------------------------------

Ak to nutne musi byt podla tvojej definicie, tzn. s leaf a bez hodnot vo vnutornych uzloch, tak definica:

leaf(_).

strom(leaf(_)).
strom(L,R) :-
strom(L),
strom(R).


Potom vymena iba priamych nasledovnikov rovnako jednoducho:

swapped(leaf(X), leaf(Y)).
swapped( tree(L,R), tree(R,L) ).


Alebo na vsetkych urovniach:

swapped( leaf(X), leaf(X) ).
swapped( tree(L1, R1) , tree(L2, R2) ) :-
swapped( L1, R2 ),
swapped( R1, L2 ).



Tvoj priklad:

?- swapped(tree(tree(leaf(1), leaf(2)), leaf(4)),T).
T = tree(leaf(4), tree(leaf(2), leaf(1))).



Btw. testoval som len "mnohourovnove" verzie a aj to iba zlahka, takze mozno su tam chyby...

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

Dakujem vsetkym za odpovede.
Skusil som zadat nasledujucu databazu:

leaf(_).

tree(leaf(_)).
tree(L,R) :- tree(L),tree(R).

A skusil som nasledujuce prikazy:
?- leaf(1).
true.

?- tree(leaf(1),leaf(2)).
true.

?- tree(tree(leaf(1),leaf(2)),leaf(3)).
false.

?- tree(tree(leaf(1),leaf(2)),tree(leaf(3),leaf(4))).
false.

Nerozumiem tomu, ako je to mozne.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

Ten predposledni false je podle me zrejmy. Mas sice nadefinovany strom s jednim listem, ale nemas nadefinovany strom, kde je v jedne vetvi strom a v druhe list.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

no neviem, podla toho, co som sa doteraz naucil a ako tomu ja rozumiem (co samozrejme nemusi byt vobec pravda), tak strom bud obsahuje iba list podla pravidla
tree(leaf(_)).

alebo 2 stromy podla pravidla:
tree(L,R) :- tree(L), tree(R).

ale tree(L) (a aj tree(R)) moze byt znova strom iba s listom alebo s 2 podstromami.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

No jak rikas. Strom muze byt strom jenom s listem, nebo s dvema podstromy. Nikoliv ale s listem a podstromem. Tak to alespon vidim ja.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

To nie je pravda, ked mas taketo rekurzivne riesenie, tak aj list je podstrom - tree(leaf(_)). Chyba tam je vsak v samotnom vnarani sa do rekurzie, ktoru som v polospanku v noci prehliadol.


Dokazujes napr.:

tree(tree(leaf(1),leaf(2)),leaf(3)).

Pouzije sa pravidlo tree(L,R) a teda sa naviaze L = tree(leaf(1),leaf(2)); R = leaf(3).

A teraz nastane problem, ze sa pokusi dokazat tree( L ), cize tree( tree(leaf(1),leaf(2) ) ). A take pravidlo tam nie je, je potrebne "rozbit" ten vnutorny tree na laveho a praveho potomka.


Definiciu je teda potrebne upravit takto:

leaf(_).

tree(leaf(_)).
tree(L,R) :-
treedec(L),
treedec(R).

treedec(tree(L,R)) :- tree(L,R),!. % ten rez je tam proforma, funguje to aj bez neho, len sa niekedy bude pytat, ci ma hladat dalsie riesenie; takto rovno skonci
treedec(X) :- tree(X).


(JE POTREBNE POUZIT INY PREDIKAT (napr. nazvany treedec() ) - tzn. nestaci iba dopisat tree(tree(L,R)), pretoze by potom "presiel" aj dotaz napriklad tree(tree(tree(tree(leaf(1),leaf(2))))). )



Mimochodom, na samotne riesenie otacania (swapped) toto NEMA vobec vplyv, pretoze predikat swapped() si rozklada struktury s tree() a leaf() sam a tuto definiciu nepouziva. Fungovalo by to aj uplne bez definicie leaf a tree, iba samotne swapped.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

A samozrejme by sa to dalo aj cez OR (;) priamo v tree, len by to bolo dlhsie.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

Me se zda, ze vychazis z toho, ze tree(leaf(_)) je to same jako leaf(_). To ale asi neplati. Ty tam mas vlastne tree(tree(_), leaf(_)).

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

Ty tam mas vlastne tree(tree(_), leaf(_)).


A to nie je problem, nakolko pri dokazovani sa naviaze:

L = tree(...)
R = leaf(_)

A dokazuje sa tree(R), cize tree(leaf(_)) a to tam prave je napisane.


Problem je ale naopak v tom tree, cize dokazujes tree(L), cize tree( tree(...) ) a to je problem, treba tu jednu uroven odstranit, tzn. dokazovat nie tree(L), ale ak L = tree(A,B), tak treba dalej dokazovat tree(A,B). Vid riesenie niekde naokolo.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

"Ten predposledni false je podle me zrejmy. Mas sice nadefinovany strom s jednim listem, ale nemas nadefinovany strom, kde je v jedne vetvi strom a v druhe list."

A rekurzia je co? Na rekurzivnu definiciu stromu ti uplne staci:

1) List je stromom. (Alebo nil je stromom. - podla toho ci pripustas sprazdny strom ako strom; zmeni sa to len v urovni ukoncenia rekurzie, v takomto pripade by si siel dalej aj z listu a narazil by si na dva prazdne stromy.)

2) Vrchol, ktoreho lavy nasledovnik je strom a pravy nasledovnok je strom je tiez strom.


A ak mas vrchol, ktory ma jedneho nasledovnika list a druheho strom, tak ten list je tiez strom, cize splnas pri pouziti def. 1 definiciu 2 a mas strom.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

No ale ja tam nikde definic, ze list je strom nevidim.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

tree(leaf(_)).


Opakujem, co som napisal vyssie, ze som len zabudol rozbit pri vnoreni sa do podstromu strukturu tree.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

Asi si to budu muset vyzkouset KAzdopadne diky za trpelivost.

Souhlasím  |  Nesouhlasím  |  Odpovědět
 |   | 

dakujem velmi pekne ze vysvetlenie.. este sa na to pozriem a dam vediet na co som prisiel.

Souhlasím  |  Nesouhlasím  |  Odpovědět

Související témata: Leaf, Tree, Strom


Určitě si přečtěte

Jak stáhnout video z Youtube: 5 nejlepších nástrojů

Jak stáhnout video z Youtube: 5 nejlepších nástrojů

** Videa nejen z Youtube se hodí stáhnout v případě, že může být smazáno ** Rovněž se hodí možnost získat pouze audio ** Použít lze desktopové aplikace, webové nástroje i doplňky

Stanislav Janů | 31

Stanislav Janů
TipyNejlepší programy
Konec modrých obrazovek smrti? Microsoft vydává mimořádnou aktualizaci pro Windows 10
Karel Kilián
Windows UpdateAktualizaceWindows 10
Nejlepší notebooky do 10 000 korun: Co má ještě smysl kupovat. A co ne?

Nejlepší notebooky do 10 000 korun: Co má ještě smysl kupovat. A co ne?

** Notebooky s cenou do deseti tisíc korun jsou plné kompromisů ** Existuje několik modelů dobře použitelných pro nenáročné použití ** Vhodnou alternativou jsou tablety nebo repasované počítače

David Polesný | 94

David Polesný
Jak vybrat notebookNotebooky
Jak se šíří Covid v Česku: Čerstvá data, semafor PES, mapy okresů a obcí. Každý den aktualizované grafy

Jak se šíří Covid v Česku: Čerstvá data, semafor PES, mapy okresů a obcí. Každý den aktualizované grafy

** Vývoj COVID-19 v Česku: nakažení, úmrtí, testovaní, hospitalizovaní ** Mapa podle okresů, přehled podle věku, situace v Evropě i ve světě ** Každý den aktualizované grafy a mapy

Marek Lutonský | 174

Marek Lutonský
COVID-19Koronavirus
Jak najít hranice území obcí a okresů, abyste věděli, kde se můžete pohybovat
Filip KůželJakub Čížek
KoronavirusMapy
Avast Omni: Krabička, která vám hackne síť a promění se v unikátní antivirus

Avast Omni: Krabička, která vám hackne síť a promění se v unikátní antivirus

** Počítač dnes ochrání kdejaký antivirus ** Drobná krabička Omni se postará rovnou o celou domácí síť ** Bude ji odposlouchávat, analyzovat a blokovat útoky

Jakub Čížek | 120

Jakub Čížek
AntivirusIoT
Nejlepší příslušenství k počítači. Tipy na osvědčené klávesnice, tiskárny, routery…

Nejlepší příslušenství k počítači. Tipy na osvědčené klávesnice, tiskárny, routery…

** Tipy na užitečné příslušenství k počítačům ** Poradíme, s jakými produkty neuděláte chybu ** Od drobností do USB až po routery a tiskárny

David Polesný, Stanislav Janů | 20

David PolesnýStanislav Janů
Příslušenství