Forum » Programiranje » [NALOGA] Java: REKURZIJA
[NALOGA] Java: REKURZIJA
Timon ::
živjo!
mam še en majhen problemček z rekurzijo, in sicer z sledečo nalogo:
Realizirati moram program, ki bo na vhodu prebral število N in zapisal vse pravilno vgnezdene izraze z N oklepaji.
primer:
Program na začetku prebere celo število N ter izpiše vsa znakovna zaporedja, ki vsebujejo N znakov '(' in N znakov ')', ki jih lahko interpretiramo kot veljavno vgnezdene oklepaje. To pomeni, da nobeden prefiks ne vsebuje več znakov ')' kot znakov '('.
Na primer, za vhod N = 3 dobimo naslednje izraze:
((()))
(()())
(())()
()(())
()()()
hvala za pomoč
mam še en majhen problemček z rekurzijo, in sicer z sledečo nalogo:
Realizirati moram program, ki bo na vhodu prebral število N in zapisal vse pravilno vgnezdene izraze z N oklepaji.
primer:
Program na začetku prebere celo število N ter izpiše vsa znakovna zaporedja, ki vsebujejo N znakov '(' in N znakov ')', ki jih lahko interpretiramo kot veljavno vgnezdene oklepaje. To pomeni, da nobeden prefiks ne vsebuje več znakov ')' kot znakov '('.
Na primer, za vhod N = 3 dobimo naslednje izraze:
((()))
(()())
(())()
()(())
()()()
hvala za pomoč
DavidJ ::
Problem je rekurziven.
število parov oklepajev / možni načini
0 / -
1 / ()
2 / ()(), (())
3 / ()()(), ()(()), (())(), ((()))
....
n / ()[n-1], ([n-1])
Obrazec za n pomeni, da boš npr. za 4 dobil
()()()(), ()()(()), ()(())(), ()((())), (()()()), (()(())), ((())()), (((()))).
Sprogramirat pa zdej ne bo problem, a? ;)
število parov oklepajev / možni načini
0 / -
1 / ()
2 / ()(), (())
3 / ()()(), ()(()), (())(), ((()))
....
n / ()[n-1], ([n-1])
Obrazec za n pomeni, da boš npr. za 4 dobil
()()()(), ()()(()), ()(())(), ()((())), (()()()), (()(())), ((())()), (((()))).
Sprogramirat pa zdej ne bo problem, a? ;)
"Do, or do not. There is no 'try'. "
- Yoda ('The Empire Strikes Back')
- Yoda ('The Empire Strikes Back')
Zgodovina sprememb…
- spremenil: DavidJ ()
frudi ::
Tole pa ne bo držalo. Za n = 3 je 5 kombinacij, za 4 jih je že 14, za 5 42...
1ACDoHVj3wn7N4EMpGVU4YGLR9HTfkNhTd... in case I've written something useful :)
DavidJ ::
Pa res! Sem pozabil na en rekurzivni klic. (Sem ga pomotoma zanemaril, zaradi delnega ponavljanja.)
1 / ()
2 / ()(), (())
3 / ()()(), ()(()), (()()), ((())), (())()
Obrazec za n:
()[n-1], ([n-1]), [n-1]() in odstrani ponavljajoče vzorce
Še enkrat za 4:
()((()))
()(()())
()(())()
()()(())
()()()()
(((())))
((()()))
((())())
(()(()))
(()()())
((()))()
(()())()
(())()()
()(())() -- ponavljanje
()()()() -- ponavljanje
1 / ()
2 / ()(), (())
3 / ()()(), ()(()), (()()), ((())), (())()
Obrazec za n:
()[n-1], ([n-1]), [n-1]() in odstrani ponavljajoče vzorce
Še enkrat za 4:
()((()))
()(()())
()(())()
()()(())
()()()()
(((())))
((()()))
((())())
(()(()))
(()()())
((()))()
(()())()
(())()()
()(())() -- ponavljanje
()()()() -- ponavljanje
"Do, or do not. There is no 'try'. "
- Yoda ('The Empire Strikes Back')
- Yoda ('The Empire Strikes Back')
frudi ::
Hm, imaš samo 13 kombinacij, jaz jih dobim 14; mislim, da ti manjka (())(())? A si jo samo spregledal kje, ali ti je algoritem sploh ne zgenerira?
Jaz sem sicer uporabil precej drugačen pristop...
Jaz sem sicer uporabil precej drugačen pristop...
1ACDoHVj3wn7N4EMpGVU4YGLR9HTfkNhTd... in case I've written something useful :)
alexa-lol ::
namig...
znotraj rekurzije klici enkrat rekurzijo, ki tvojmu stringu doda "(" in nekrat ")"...naredi, da bo vsako ddodajanje "(" vsoti stringa dalo +1 in "(" odtelo 1 (-1)... zdaj bi moral dojeti..
razmisli, kaj bi bil ustavitveni pogoj in kaj bi bil pogoj za regularnost izpisa
znotraj rekurzije klici enkrat rekurzijo, ki tvojmu stringu doda "(" in nekrat ")"...naredi, da bo vsako ddodajanje "(" vsoti stringa dalo +1 in "(" odtelo 1 (-1)... zdaj bi moral dojeti..
razmisli, kaj bi bil ustavitveni pogoj in kaj bi bil pogoj za regularnost izpisa
DavidJ ::
Frudi, pa res. Prečrtaj tale moj poskus. Si bom, če bo tekom tega vikenda še čas, podrobneje pogledal. Je pa alexa dal zanimiv namig, vidim.
"Do, or do not. There is no 'try'. "
- Yoda ('The Empire Strikes Back')
- Yoda ('The Empire Strikes Back')
frudi ::
Ja, jaz sem rešil na tak način, kot ga predlaga alexa...
Glavna ideja je, da v vsakem koraku rekurzije iz obstoječega niza narediš dva nova - enega z dodanim "(", drugega z ")". Ostalo so podrobnosti - kdaj prekiniti, kdaj ne smeš dodati "(" ali ")", kdaj izpisati, ipd.
Glavna ideja je, da v vsakem koraku rekurzije iz obstoječega niza narediš dva nova - enega z dodanim "(", drugega z ")". Ostalo so podrobnosti - kdaj prekiniti, kdaj ne smeš dodati "(" ali ")", kdaj izpisati, ipd.
1ACDoHVj3wn7N4EMpGVU4YGLR9HTfkNhTd... in case I've written something useful :)
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Matematika: Deljivost naravnih in celih števil.Oddelek: Šola | 3250 (3052) | lebdim |
| » | matematična indukcija + inverz f(x) (pomoč)Oddelek: Šola | 1179 (1135) | minusnič |
| » | Matematična indukcija!?!Oddelek: Šola | 4252 (3673) | lebdim |
| » | Python - naloga z računanjemOddelek: Programiranje | 2084 (1561) | ktka |
| » | Kako izračunati št. kombinacijOddelek: Pomoč in nasveti | 13502 (13238) | milc |