Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
pmli Forumaš(ica)
Pridružen/a: 09. 11. 2009. (12:03:05) Postovi: (2C8)16
Spol:
|
Postano: 18:10 pon, 1. 11. 2010 Naslov: |
|
|
[quote="eve"]Procitala sam to al nisam nasla kako da preko stoga izracunam prefix izraz...moze pomoc...?[/quote]
(1) Učitaš dio iz prefix izraza. Ako nema ništa za učitati, goto (3)
Ako učitaš operator, staviš ga na stog. Goto (1)
Ako učitaš operand, pogledaš što je na vrhu stoga. (2)
> Ako je na vrhu stoga operator, staviš operand na stog (pretpostavka je da su sve operacije binarne). Goto (1)
> Ako je na vrhu operand, izvadiš ga iz stoga, pa zatim i operator koji je bio ispod njega, primjeniš taj operator na dva operanda i njihov rezultat je novi operator i glumiš da si ga učitala. Goto (2)
(3) Rezultat je operand na vrhu stoga.
To bi bio pseudokod (valjda). Bilo bi dobro da goto naredbe zamjeniš s petljama, jer bi ti se inače moglo neko [url=http://xkcd.com/292/]zlo[/url] dogoditi. :)
eve (napisa): | Procitala sam to al nisam nasla kako da preko stoga izracunam prefix izraz...moze pomoc...? |
(1) Učitaš dio iz prefix izraza. Ako nema ništa za učitati, goto (3)
Ako učitaš operator, staviš ga na stog. Goto (1)
Ako učitaš operand, pogledaš što je na vrhu stoga. (2)
> Ako je na vrhu stoga operator, staviš operand na stog (pretpostavka je da su sve operacije binarne). Goto (1)
> Ako je na vrhu operand, izvadiš ga iz stoga, pa zatim i operator koji je bio ispod njega, primjeniš taj operator na dva operanda i njihov rezultat je novi operator i glumiš da si ga učitala. Goto (2)
(3) Rezultat je operand na vrhu stoga.
To bi bio pseudokod (valjda). Bilo bi dobro da goto naredbe zamjeniš s petljama, jer bi ti se inače moglo neko zlo dogoditi.
|
|
[Vrh] |
|
eve Forumaš(ica)
Pridružen/a: 13. 07. 2009. (23:07:06) Postovi: (192)16
Spol:
|
|
[Vrh] |
|
kaj Forumaš(ica)
Pridružen/a: 15. 11. 2009. (21:02:20) Postovi: (B8)16
|
|
[Vrh] |
|
pbakic Forumaš(ica)
Pridružen/a: 05. 10. 2009. (17:48:30) Postovi: (143)16
Spol:
|
|
[Vrh] |
|
teapot Forumaš(ica)
Pridružen/a: 12. 02. 2009. (22:01:19) Postovi: (36)16
|
Postano: 21:08 pon, 1. 11. 2010 Naslov: |
|
|
Molim vas, da mi neko provjeri jeli mi točan ovaj zadatak, a zadatak glasi:Zadan je aritm.izraz (A-(B+D)*(C-A-D)+A)-C*D. Dijkstrinim algoritmom pretvorite ga u postfix oblik.A=2,B=1,C=6,D=3.
Ja sam dobila da je postfix oblik: ABD+-CA-D-*A+CD*- i rez sam dobila da je 18.
Molim vas, da mi neko provjeri jeli mi točan ovaj zadatak, a zadatak glasi:Zadan je aritm.izraz (A-(B+D)*(C-A-D)+A)-C*D. Dijkstrinim algoritmom pretvorite ga u postfix oblik.A=2,B=1,C=6,D=3.
Ja sam dobila da je postfix oblik: ABD+-CA-D-*A+CD*- i rez sam dobila da je 18.
|
|
[Vrh] |
|
pbakic Forumaš(ica)
Pridružen/a: 05. 10. 2009. (17:48:30) Postovi: (143)16
Spol:
|
|
[Vrh] |
|
kratki89 Forumaš(ica)
Pridružen/a: 19. 09. 2009. (23:36:13) Postovi: (27)16
Lokacija: Zemlja i okolica
|
|
[Vrh] |
|
Marvin Forumaš(ica)
Pridružen/a: 01. 12. 2006. (15:46:10) Postovi: (56)16
|
|
[Vrh] |
|
patlidzan Forumaš(ica)
Pridružen/a: 05. 11. 2009. (19:17:28) Postovi: (76)16
Spol:
|
|
[Vrh] |
|
kratki89 Forumaš(ica)
Pridružen/a: 19. 09. 2009. (23:36:13) Postovi: (27)16
Lokacija: Zemlja i okolica
|
|
[Vrh] |
|
pbakic Forumaš(ica)
Pridružen/a: 05. 10. 2009. (17:48:30) Postovi: (143)16
Spol:
|
Postano: 17:34 uto, 2. 11. 2010 Naslov: |
|
|
evo dijkstra za prvi:
[table=;]Ulaz ; Stog ; Izlaz
x ; ; x
* ; * ; x
y ; * ; xy
+ ; + ; xy*
z ; + ; xy*z
/ ; +/ ; xy*z
( ; +/( ; xy*z
x ; +/( ; xy*zx
- ; +/(- ; xy*zx
y ; +/(- ; xy*zxy
- ; +/(- ; xy*zxy-
z ; +/(- ; xy*zxy-z
) ; +/ ; xy*zxy-z-
- ; - ; xy*zxy-z-/+
z ; - ; xy*zxy-z-/+z
; ; xy*zxy-z-/+z-
[/table]
Pejstam cijeli kod ako treba, al to bi bilo malo glomazno, pa evo prvo ideja:
U queue Q1 spremamo elemente, u Q2 njihove kratnosti.
Dakle, dok god (while) nas stack S nije prazan (!EMPTY(S)) radimo sljedece:
Spremimo TOP(S) u neku varijablu, npr x
provjerimo je li Q1 prazan;
[b]ako je:[/b] enqueueamo element x u Q1 i 1 (kao trenutnu kratnost elementa x) u Q2
[b]ako nije:[/b]
spremimo front od Q1 u neku pomocnu varijablu (npr pom), enqueueamo ga na kraj Q1, i maknemo s pocetka (efektivno, pomaknuli smo prvi element na kraj reda i zabiljezili njegovu vrijednost u pom)
Isto napravimo u Q2, ali ne moramo spremati vrijednost
Sada se krecemo po Q1 dok ne naidjemo na pom
(kretanje ostvarujemo prebacivanjem elementa s fronta od Q1 na kraj)
paralelno radimo iste operacije na Q2
Ako smo naisli na isti element kao x u Q1, onda samo njegovu kratnost u Q2 povecamo za jedan
Ako nismo, u cijelom obilasku Q1, naisli na element x, onda ga stavimo u Q1, a njegovu kratnost (1) stavimo u Q2
to je generalna ideja (ne nuzno jedina moguca), ak ce trebat kod il nesto, vici...
evo dijkstra za prvi:
Ulaz | Stog | Izlaz |
---|
x | | x | * | * | x | y | * | xy | + | + | xy* | z | + | xy*z | / | +/ | xy*z | ( | +/( | xy*z | x | +/( | xy*zx | - | +/(- | xy*zx | y | +/(- | xy*zxy | - | +/(- | xy*zxy- | z | +/(- | xy*zxy-z | ) | +/ | xy*zxy-z- | - | - | xy*zxy-z-/+ | z | - | xy*zxy-z-/+z | | | xy*zxy-z-/+z- |
Pejstam cijeli kod ako treba, al to bi bilo malo glomazno, pa evo prvo ideja:
U queue Q1 spremamo elemente, u Q2 njihove kratnosti.
Dakle, dok god (while) nas stack S nije prazan (!EMPTY(S)) radimo sljedece:
Spremimo TOP(S) u neku varijablu, npr x
provjerimo je li Q1 prazan;
ako je: enqueueamo element x u Q1 i 1 (kao trenutnu kratnost elementa x) u Q2
ako nije:
spremimo front od Q1 u neku pomocnu varijablu (npr pom), enqueueamo ga na kraj Q1, i maknemo s pocetka (efektivno, pomaknuli smo prvi element na kraj reda i zabiljezili njegovu vrijednost u pom)
Isto napravimo u Q2, ali ne moramo spremati vrijednost
Sada se krecemo po Q1 dok ne naidjemo na pom
(kretanje ostvarujemo prebacivanjem elementa s fronta od Q1 na kraj)
paralelno radimo iste operacije na Q2
Ako smo naisli na isti element kao x u Q1, onda samo njegovu kratnost u Q2 povecamo za jedan
Ako nismo, u cijelom obilasku Q1, naisli na element x, onda ga stavimo u Q1, a njegovu kratnost (1) stavimo u Q2
to je generalna ideja (ne nuzno jedina moguca), ak ce trebat kod il nesto, vici...
|
|
[Vrh] |
|
matka Forumaš(ica)
Pridružen/a: 03. 03. 2008. (11:07:54) Postovi: (38)16
|
|
[Vrh] |
|
suza Forumaš(ica)
Pridružen/a: 24. 10. 2009. (14:37:50) Postovi: (65)16
Spol:
|
|
[Vrh] |
|
pbakic Forumaš(ica)
Pridružen/a: 05. 10. 2009. (17:48:30) Postovi: (143)16
Spol:
|
Postano: 19:00 uto, 2. 11. 2010 Naslov: |
|
|
evo koda:
[code:1]
#include <stdio.h>
#include "atp_queue.c"
#include "atp_stack.c"
void ispis(QUEUE Q){
while(!Q_EMPTY(Q))
{
printf(" %d ",FRONT(Q));
DEQUEUE(&Q);
}
printf("\n");
}
void kratnost(STACK *S, int k){
QUEUE Q1,Q2;
int i,pom,x,aux;
Q_MAKE_NULL(&Q1);
Q_MAKE_NULL(&Q2);
while(!S_EMPTY(*S)){
x=TOP(*S);
aux=0;
if(Q_EMPTY(Q1)){
ENQUEUE(x,&Q1);
ENQUEUE(1,&Q2);
}
else{
pom=FRONT(Q1);
if(x==pom){
ENQUEUE(pom,&Q1);
DEQUEUE(&Q1);
ENQUEUE(FRONT(Q2)+1,&Q2);
DEQUEUE(&Q2);
aux=1;
}
else{
ENQUEUE(FRONT(Q1),&Q1);
DEQUEUE(&Q1);
ENQUEUE(FRONT(Q2),&Q2);
DEQUEUE(&Q2);
}
while(FRONT(Q1)!=pom){
if(FRONT(Q1)==x){
ENQUEUE(FRONT(Q1),&Q1);
DEQUEUE(&Q1);
ENQUEUE(FRONT(Q2)+1,&Q2);
DEQUEUE(&Q2);
aux=1;
}
else{
ENQUEUE(FRONT(Q1),&Q1);
DEQUEUE(&Q1);
ENQUEUE(FRONT(Q2),&Q2);
DEQUEUE(&Q2);
}
}
if(aux==0){
ENQUEUE(x,&Q1);
ENQUEUE(1,&Q2);
}
}
POP(S);
}
while(!Q_EMPTY(Q1)){
for(i=0; i<k && i<FRONT(Q2); ++i) PUSH(FRONT(Q1),S);
DEQUEUE(&Q1);
DEQUEUE(&Q2);
}
return;
}
int main(){
int i,n,a,k;
STACK S;
S_MAKE_NULL(&S);
scanf("%d", &n);
for(i=0; i<n; ++i){
scanf("%d", &a);
PUSH(a,&S);
}
printf("Maksimalna kratnost=");
scanf("%d",&k);
kratnost(&S,k);
printf("\n");
while(!S_EMPTY(S)){
printf("%d",TOP(S));
POP(&S);
}
scanf("%%");
return 0;
}
[/code:1]
evo koda:
Kod: |
#include <stdio.h>
#include "atp_queue.c"
#include "atp_stack.c"
void ispis(QUEUE Q){
while(!Q_EMPTY(Q))
{
printf(" %d ",FRONT(Q));
DEQUEUE(&Q);
}
printf("\n");
}
void kratnost(STACK *S, int k){
QUEUE Q1,Q2;
int i,pom,x,aux;
Q_MAKE_NULL(&Q1);
Q_MAKE_NULL(&Q2);
while(!S_EMPTY(*S)){
x=TOP(*S);
aux=0;
if(Q_EMPTY(Q1)){
ENQUEUE(x,&Q1);
ENQUEUE(1,&Q2);
}
else{
pom=FRONT(Q1);
if(x==pom){
ENQUEUE(pom,&Q1);
DEQUEUE(&Q1);
ENQUEUE(FRONT(Q2)+1,&Q2);
DEQUEUE(&Q2);
aux=1;
}
else{
ENQUEUE(FRONT(Q1),&Q1);
DEQUEUE(&Q1);
ENQUEUE(FRONT(Q2),&Q2);
DEQUEUE(&Q2);
}
while(FRONT(Q1)!=pom){
if(FRONT(Q1)==x){
ENQUEUE(FRONT(Q1),&Q1);
DEQUEUE(&Q1);
ENQUEUE(FRONT(Q2)+1,&Q2);
DEQUEUE(&Q2);
aux=1;
}
else{
ENQUEUE(FRONT(Q1),&Q1);
DEQUEUE(&Q1);
ENQUEUE(FRONT(Q2),&Q2);
DEQUEUE(&Q2);
}
}
if(aux==0){
ENQUEUE(x,&Q1);
ENQUEUE(1,&Q2);
}
}
POP(S);
}
while(!Q_EMPTY(Q1)){
for(i=0; i<k && i<FRONT(Q2); ++i) PUSH(FRONT(Q1),S);
DEQUEUE(&Q1);
DEQUEUE(&Q2);
}
return;
}
int main(){
int i,n,a,k;
STACK S;
S_MAKE_NULL(&S);
scanf("%d", &n);
for(i=0; i<n; ++i){
scanf("%d", &a);
PUSH(a,&S);
}
printf("Maksimalna kratnost=");
scanf("%d",&k);
kratnost(&S,k);
printf("\n");
while(!S_EMPTY(S)){
printf("%d",TOP(S));
POP(&S);
}
scanf("%%");
return 0;
}
|
|
|
[Vrh] |
|
.anchy. Forumaš(ica)
Pridružen/a: 14. 11. 2007. (20:03:46) Postovi: (1BC)16
Lokacija: Zgb
|
|
[Vrh] |
|
heidi75 Forumaš(ica)
Pridružen/a: 18. 02. 2009. (21:51:01) Postovi: (8)16
|
|
[Vrh] |
|
pbakic Forumaš(ica)
Pridružen/a: 05. 10. 2009. (17:48:30) Postovi: (143)16
Spol:
|
Postano: 19:51 uto, 2. 11. 2010 Naslov: |
|
|
@anchy:
za par-nepar, mozes prelijevati iz jednog stoga u drugi.
Kad ides npr sa S1 na S2, kad naidjes na prvi parni element, spremis ga u pomocnu varijablu. Nakon sto prelijes ostatak S1, stavis taj element na vrh S2.
Onda ides nazad iz S2 u S1, radis isto, al samo prvi neparni element stavis na vrh
(Ovime smo postigli da je nakon 2 runde prebacivanja u S1 imamo sigurno jedan parni element na dnu, a neparni na vrhu)
Sad ovo ponavljas sve dok je potrebno (a dal je potrebno isto biljezis u neku pomocnu varijablu; npr. ako poslije prvog parnog ne naidjes vise na neparni element, nije potrebna zamjena); na kraju dobijes stack u kojem su na vrhu parni, a na dnu svi neparni.
Ovaj osmi se valjda jedino rekurzivno moze bez dodatnih atp-ova...
(U svaki nivo rekurzije udjes sa stackom za jedan manjim od prosli put)
@anchy:
za par-nepar, mozes prelijevati iz jednog stoga u drugi.
Kad ides npr sa S1 na S2, kad naidjes na prvi parni element, spremis ga u pomocnu varijablu. Nakon sto prelijes ostatak S1, stavis taj element na vrh S2.
Onda ides nazad iz S2 u S1, radis isto, al samo prvi neparni element stavis na vrh
(Ovime smo postigli da je nakon 2 runde prebacivanja u S1 imamo sigurno jedan parni element na dnu, a neparni na vrhu)
Sad ovo ponavljas sve dok je potrebno (a dal je potrebno isto biljezis u neku pomocnu varijablu; npr. ako poslije prvog parnog ne naidjes vise na neparni element, nije potrebna zamjena); na kraju dobijes stack u kojem su na vrhu parni, a na dnu svi neparni.
Ovaj osmi se valjda jedino rekurzivno moze bez dodatnih atp-ova...
(U svaki nivo rekurzije udjes sa stackom za jedan manjim od prosli put)
|
|
[Vrh] |
|
homesweethome Forumaš(ica)
Pridružen/a: 21. 10. 2009. (16:25:25) Postovi: (1C)16
|
Postano: 19:59 uto, 2. 11. 2010 Naslov: Re: 1. kolokvij 2010. |
|
|
4. zadatak:
a)
[code:1]void saren( BTREE B)
{
node n;
n=ROOT(T);
if( ( LABEL(n,T)%2==0) && ( LEFT_CHILD(n,T)%2==0 || RIGHT_CHILD(n,T)%2==0) )
printf("...", LABEL(n,T));
saren(LEFT_SUBTREE(T, *TL));
saren(RIGHT_SUBTREE(T, *TR));
return;
}[/code:1]
nije mi jasno kod poziva fje saren, zar je ispravno napisati
[code:1]
saren(LEFT_SUBTREE( T, *TL));
[/code:1]
dakle fja LEFT_SUBTREE treba primiti prvo adresu nekog TL, il...
4. zadatak:
a)
Kod: | void saren( BTREE B)
{
node n;
n=ROOT(T);
if( ( LABEL(n,T)%2==0) && ( LEFT_CHILD(n,T)%2==0 || RIGHT_CHILD(n,T)%2==0) )
printf("...", LABEL(n,T));
saren(LEFT_SUBTREE(T, *TL));
saren(RIGHT_SUBTREE(T, *TR));
return;
} |
nije mi jasno kod poziva fje saren, zar je ispravno napisati
Kod: |
saren(LEFT_SUBTREE( T, *TL));
|
dakle fja LEFT_SUBTREE treba primiti prvo adresu nekog TL, il...
|
|
[Vrh] |
|
Cobs Forumaš(ica)
Pridružen/a: 21. 01. 2008. (13:32:15) Postovi: (206)16
Spol:
Lokacija: Geto
|
|
[Vrh] |
|
miam Forumaš(ica)
Pridružen/a: 03. 11. 2009. (11:19:45) Postovi: (70)16
Spol:
|
|
[Vrh] |
|
|