Informatika1-2011/Gyakorlat4
A MathWikiből
(Változatok közti eltérés)
Ador (vitalap | szerkesztései) |
Ador (vitalap | szerkesztései) a (→Egyszerűbb rekurzív függvények) |
||
(egy szerkesztő 3 közbeeső változata nincs mutatva) | |||
1. sor: | 1. sor: | ||
=== Egyszerűbb rekurzív függvények === | === Egyszerűbb rekurzív függvények === | ||
− | # Írj egy Sage függvényt ''palindroma'' néven, amely bemenetként kap egy | + | # Írj egy Sage függvényt ''palindroma'' néven, amely bemenetként kap egy stringet (''s'') és eldönti, hogy a string egy palindróma-e! (Azt nevezzük palindrómának ami visszafelé olvasva is ugyanaz, pl 'almaamla' vagy 'abcdcba'). |
# Írj egy függvényt ''bst_beszur'' néven, amely bemenetként kap egy bináris keresőfát (''bst'') és egy elemet (''elem'') és ha az elem már a fában van akkor False értékkel tér vissza, egyébként beszúrja az elemet a megfelelő helyre a fába és True-t ad vissza. | # Írj egy függvényt ''bst_beszur'' néven, amely bemenetként kap egy bináris keresőfát (''bst'') és egy elemet (''elem'') és ha az elem már a fában van akkor False értékkel tér vissza, egyébként beszúrja az elemet a megfelelő helyre a fába és True-t ad vissza. | ||
− | === Gráfok === | + | === Gráfok létrehozása === |
+ | |||
+ | * Hozz létre egy irányítatlan gráfot a szomszédsági mátrixának megadásával! Legyen 5 csúcsa, és 7 éle! Rajzold is ki a ''show()'' függvénnyel! | ||
+ | (segítség: négyzetes és szimmetrikus mátrixot adj meg! Például egy 3 csúcsú gráf így adható meg márixxal: | ||
+ | M = matrix([[0,1,0],[1,0,1],[0,1,0]]) | ||
+ | g = Graph(M) | ||
+ | show(g) | ||
+ | ) | ||
+ | |||
+ | * Hozz létre egy irányítatlan, 3 mélységű bináris fát ''G'' névvel: | ||
+ | |||
+ | G = graphs.BalancedTree(2,3) | ||
+ | |||
+ | Adj hozzá egy élet hogy kör is legyen benne: | ||
+ | |||
+ | G.add_edge(6,4) | ||
+ | |||
+ | Nézd meg, milyen lett! | ||
+ | |||
+ | * Hozz létre egy véletlenszerű irányított gráfot a ''digraphs'' csomag ''RandomDirectedGNP()'' függvényének használatával! Példa: | ||
+ | d1 = digraphs.RandomDirectedGNP(9,0.2) | ||
+ | Itt egy 9 csúcsú gráfot hozunk létre, és minden pontpár között 0.2 valószínűségegl húzunk be élet. | ||
+ | |||
+ | |||
+ | === Gráfok bejárása === | ||
+ | |||
+ | # Írj egy függvényt ami egy gráfban '''mélységi''' keresés szerint keres meg egy elemet, egy adott, másik elemből kiindulva! Segítség, pszeudo-kód: [http://en.wikipedia.org/wiki/Depth-first_search#Pseudocode DFS-wikipedia] | ||
+ | # Írj egy függvényt ami egy gráfban '''szélességi''' keresés szerint keres meg egy elemet, egy adott, másik elemből kiindulva! Segítség, pszeudo-kód: [http://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode BFS-wikipedia] | ||
+ | # Próbáld ki a kétféle keresést a ''g'' és a ''G'' gráfokon! |
A lap jelenlegi, 2011. október 7., 16:02-kori változata
Egyszerűbb rekurzív függvények
- Írj egy Sage függvényt palindroma néven, amely bemenetként kap egy stringet (s) és eldönti, hogy a string egy palindróma-e! (Azt nevezzük palindrómának ami visszafelé olvasva is ugyanaz, pl 'almaamla' vagy 'abcdcba').
- Írj egy függvényt bst_beszur néven, amely bemenetként kap egy bináris keresőfát (bst) és egy elemet (elem) és ha az elem már a fában van akkor False értékkel tér vissza, egyébként beszúrja az elemet a megfelelő helyre a fába és True-t ad vissza.
Gráfok létrehozása
- Hozz létre egy irányítatlan gráfot a szomszédsági mátrixának megadásával! Legyen 5 csúcsa, és 7 éle! Rajzold is ki a show() függvénnyel!
(segítség: négyzetes és szimmetrikus mátrixot adj meg! Például egy 3 csúcsú gráf így adható meg márixxal:
M = matrix([[0,1,0],[1,0,1],[0,1,0]]) g = Graph(M) show(g)
)
- Hozz létre egy irányítatlan, 3 mélységű bináris fát G névvel:
G = graphs.BalancedTree(2,3)
Adj hozzá egy élet hogy kör is legyen benne:
G.add_edge(6,4)
Nézd meg, milyen lett!
- Hozz létre egy véletlenszerű irányított gráfot a digraphs csomag RandomDirectedGNP() függvényének használatával! Példa:
d1 = digraphs.RandomDirectedGNP(9,0.2)
Itt egy 9 csúcsú gráfot hozunk létre, és minden pontpár között 0.2 valószínűségegl húzunk be élet.
Gráfok bejárása
- Írj egy függvényt ami egy gráfban mélységi keresés szerint keres meg egy elemet, egy adott, másik elemből kiindulva! Segítség, pszeudo-kód: DFS-wikipedia
- Írj egy függvényt ami egy gráfban szélességi keresés szerint keres meg egy elemet, egy adott, másik elemből kiindulva! Segítség, pszeudo-kód: BFS-wikipedia
- Próbáld ki a kétféle keresést a g és a G gráfokon!