προβλημα με αναδρομη!

[MpOuKaLAs]

οχι evgenios

 

 

V.I.Smirnov ευχαριστω για τις υπερπολυτιμες οδηγιες σου.

 

Κατι τελευταιο θα ηθελα να σε ρωτησω ( φτανει δλδ αρκετα σε επριξα ) επειδη δεν καταλαβα

αυτο που μου ελεγες σχετικα με τους κλαδους στην αναδρομη μηπως θα μπορουσες να φτιαξεις

ενα ψευτοδιαγραμμα ?

[V.I.Smirnov]

Nα σου δείξω.

Για την ακολουθία fibonacci που υλοποιείται αναδρομικά δες ένα τέτοιο διάγραμμα, τo πήρα με scanner.

(Εδώ το όνομα είναι rabbit αλλά δεν έχει σημασία, είναι ακριβώς η συνάρτηση που λέγαμε πιο πάνω...)

 

Είναι για την τιμή 7.

Όπως βλέπεις φαίνονται όλες οι κλήσεις χωρίς να χρειαστεί το stack.

 

Παρατήρησε αυτό που είπα πιο πάνω :

για ένα τόσο μικρό όρισμα υπολογίζονται οι ίδιες τιμές ξανά και ξανά καθιστώντας την

αναδρομική συνάρτηση τελείως ακατάλληλη για τον υπολογισμό της ακολουθίας fibonacci.

Για κάποια τιμή πχ. 100 θα προκύψουν τρισεκατομύρια άχρηστες κλήσεις και άσκοποι

υπολογισμοί - δεν τολμώ να φανταστώ πόσα...

 

Hθικό δίδαγμα :

η ευκολία της αναδρομής είναι συχνά παραπλανητική και πρέπει να εξετάζεται το υπολογιστικό

φορτίο που επάγει πριν εφαρμοστεί αναδρομική λύση.

[MpOuKaLAs]

Εχω επισης μια απορια:

 

εστω οτι εχω

 

>
//---------------------------------------------------------------------------

#include <stdio.h>
#pragma hdrstop

#include <tchar.h>
//---------------------------------------------------------------------------


int synar(int n){

int x;

if( n == 1 || n == 2)
	{
		x = 1;
	}
else
	{
		x = synar(n-2)+synar(n-1);
	}

return x;
}


#pragma argsused
int _tmain(int argc, _TCHAR* argv[])
{
int n = 6;
n = synar(n);
printf("\n%d",n);
getchar();
return 0;
}
//---------------------------------------------------------------------------

 

ΟΛΑ τα βηματα τα εκτελω σωστα 100% και φτανω στο σημειο οπου πρεπει να

τερματιστει η αναδρομη και πραγματι τερματιζετε.

 

Δεν μπορω να καταλαβω στο τελος τι προστιθετε και δινει αποτελεσμα 8 ?

 

θα ηθελα επισης αν γνωριζεις για το RPN (reverse polish notation) να μου πεις δυο τρια λογια

η να μου στειλεις κανενα tutorial στα ελληνικα αν εχεις.

 

thanks!

[V.I.Smirnov]

ΟΛΑ τα βηματα τα εκτελω σωστα 100% και φτανω στο σημειο οπου πρεπει να

τερματιστει η αναδρομη και πραγματι τερματιζεται.

 

Δεν μπορω να καταλαβω στο τελος τι προστιθεται και δινει αποτελεσμα 8 ?

 

 

Δεν έχεις κατανοήσει πλήρως πώς επιδρά η συνθήκη τερματισμού στο συγκεκριμένο πρόβλημα.

 

Θέλεις να τερματίζεις την αναδρομή για τιμές μικρότερες από 1.

Βάζεις και τους δυο ελέγχους, n==1, n==2 διότι έτσι καλύπτεις τις περιπτώσεις όπου σε κάποιο βήμα εμφανίζεται 2-2=0 ή 3-2=1.

Έτσι είσαι σίγουρος ότι "πιάνεις" όλες τις περιπτώσεις για να μην προχωρήσει η αναδρομή παρακάτω.

Μέχρι εδώ σωστά, η αναδρομή τερματίζει σίγουρα.

Το θέμα είναι πού ακριβώς τερματίζει. Προφανώς όχι εκεί που νομίζεις.

 

Το n==1 || n==2 σταματά την εκτέλεση για n<=2.

Αν κάνεις το διάγραμμα με τους κλάδους των κλήσεων βλέπεις το εξής.

Για n=3 η επόμενη κλήση δίνει 1 και γυρίζει πίσω.

Για n=2 η επόμενη κλήση δίνει επίσης 1 και γυρίζει πίσω.

Δηλ. για n=2 δεν προχωρά παρακάτω.

 

Δες το πρόχειρο διάγραμμα διάγραμμα που επισυνάπτω.

Με κόκκινο σημειώνονται οι τιμές που προστίθεται σε κάθε επιστροφή.

 

Αν δώσεις n<=1, οι κλάδοι με το 2 αναπτύσσονται άλλη μια φορά (το κάθε 2 θα δώσει 2 μονάδες) και το άθροισμα θα είναι 13.

 

 

 

θα ηθελα επισης αν γνωριζεις για το RPN (reverse polish notation) να μου πεις δυο τρια λογια

η να μου στειλεις κανενα tutorial στα ελληνικα αν εχεις.

 

Για το RPN (αντίστροφη πολική σημειογραφία στα ελληνικά) γνωρίζω αρκετά αλλά δεν μπορώ να γράψω εδώ διότι θα καταλήξουμε σε on line μάθημα.

Θα σου πω σε pm από πού να διαβάσεις.

 

Τέλος παρακαλείσαι να μην χρησιμοποιείς το ψευδώνυμό μου στον τίτλο του thread...

[MpOuKaLAs]

Δες τα βηματα οπως τα εχω κανει:

 

1) synar(6) : ELSE : x = synar(4) + synar(5); -> push 4 , 5

2) synar(4) : ELSE : x = synar(2) + synar(3); -> push 2 , 3

3) synar(2) : IF : pop

4) synar(3) : ELSE : x = synar(1) +synar(2);

5) synar(1) : IF : pop

6) synar(2) : IF : pop

7) synar(5) : ELSE : x = synar(3) + synar(4);

8) synar(3) : ELSE : x = synar(1) + synar(2);

9) synar(1) : IF : pop

10) synar(2) : IF : pop

11) synar(4) : ELSE : x = synar(2) + synar(3);

12) synar(2) : IF : pop

13) synar(3) : ELSE : x = synar(1) + synar(2);

14) synar(1) : IF : empty stack

15) synar(2) : IF : empty stack

 

END

 

εδω τωρα τι προσθετει και δινει αποτελεσμα 8 ?

[V.I.Smirnov]

Η εκτέλεση σε κάθε κλάδο προχωρεί μέχρι να υπολογιστούν όλοι οι όροι που χρειάζονται για κάθε πρόσθεση.

 

1) synar(6) : ELSE : x = synar(4) + synar(5); -> push 5

2) synar(4) : ELSE : x = synar(2) + synar(3); -> push 3

3) synar(2) : IF : pop ( 1 λόγω του synar(2) του 2) ) Α

 

4) synar(3) : ELSE : x = synar(1) +synar(2);

5) synar(1) : IF : pop ( 1 λόγω του synar(1) του 4) ) Β

6) synar(2) : IF : pop ( 1 λόγω του synar(2) του 4) ) Γ

 

Η εκτέλεση στον κλάδο του synar(4) δεν προχωρεί βαθύτερα.

Όλοι οι όροι έχουν υπολογιστεί και μπορούν να γίνουν οι προσθέσεις.

 

Β+Γ : 1+1= 2 Δ

Δ+Α : 2+1=3 E

Άρα στο 1) είναι synar(4) = Ε =3

 

 

7) synar(5) : ELSE : x = synar(3) + synar(4); -> push 4

8) synar(3) : ELSE : x = synar(1) + synar(2);

9) synar(1) : IF : pop ( 1 λόγω του synar(1) του 8 ) Ζ

10) synar(2) : IF : pop ( 1 λόγω του synar(2) του 8 ) Η

 

Ζ+Η : 1+1=2 Θ

 

11) synar(4) : ELSE : x = synar(2) + synar(3);

12) synar(2) : IF : pop ( 1 λόγω του synar(2) του 11 ) Ι

13) synar(3) : ELSE : x = synar(1) + synar(2); push 2

 

14) synar(1) : IF : pop ( 1 λόγω του synar(1) του 13 ) Κ

15) synar(1) : IF : pop ( 1 λόγω του synar(2) του 13 ) Λ

 

Η εκτέλεση στον κλάδο του synar(5) δεν προχωρεί βαθύτερα.

Όλοι οι τελεστέοι έχουν υπολογιστεί και μπορούν να γίνουν οι προσθέσεις.

 

Κ+Λ : 1+1=2 M

 

M+I : 2+1=3 N

 

N+Θ : 3+2=5 Ξ

 

Άρα στο 1) είναι synar(5) = Ξ =5

 

Άρα στο 1) είναι synar(4) + synar(5) = 3+5 =8

 

 

To λάθος που κάνεις είναι ότι θεωρείς ότι στα 14) και 15) ότι το stack είναι άδειο και η εκτέλεση σταματά.

Αλλά τα synar(1), synar(2) που υπάρχουν στα 13) και 14) καλούν το καθένα άλλη μια φορά την συνάρτηση. ( Είναι το ίδιο που γίνεται στα 4) και 8) )

Κάνουν push και αμέσωs pop. Tα περιεχόμενα του stack δεν αλλάζουν αφού η τιμή μπαίνει και βγαίνει αμέσως αλλά η πρόσθεση γίνεται δίνοντας 2 το οποίο προστίθεται "ανοδικά" στους κλάδους.

 

Μην το σκέφτεσαι με χρήση του stack. Kάνε το διάγραμμα που είναι πολύ πιο εποπτικό.