MpOuKaLAs Δημοσ. 8 Ιουλίου 2010 Δημοσ. 8 Ιουλίου 2010 Δεν μπορω να καταλαβω για ποιο λογο τα σωστα αποτελεσματα ειναι 3 , 1 , 6 , 1 , 4 ,2 εχω την παρακατω αναδρομικη συναρτηση και την καλω απο την main με ορισμα τον αριθμο 6 και μου δινει τα παραπανω αποτελεσματα. > //--------------------------------------------------------------------------- #include <stdio.h> #pragma hdrstop #include <tchar.h> //--------------------------------------------------------------------------- int func(int n){ if( n > 0 ) { func( n - 3 ); printf("\n einai:%d",n); func( n - 2 ); } printf("\nEND:"); } #pragma argsused int _tmain(int argc, _TCHAR* argv[]) { int n = 6; func(n); getchar(); return 0; } //--------------------------------------------------------------------------- ΑΣ ΔΟΥΜΕ ΜΑΖΙ ΤΑ ΒΗΜΑΤΑ 1)Στελνω οως ορισμα τον αριθμο 6 ΟΚ! 2)Το 6 ειναι > του 0 ? TRUE 3)Εκτελειται η func( n - 3 ) με αποτελεσμα 3 4)Στελνω ως ορισμα το 3 5)Το 3 ειναι > του 0 ? TRUE 6)Εκτελειται η func( n - 3 ) με αποτελεσμα 0 7)Στελνω ως ορισμα το 0 8)Το 0 ειναι > του 0 ? FALSE απο την στιγμη που δεν εκτελειται η if μετα πως μπορει και συνεχιζει?
bnvdarklord Δημοσ. 8 Ιουλίου 2010 Δημοσ. 8 Ιουλίου 2010 Οταν τελειώσει η τελευταία func θα συνεχίσει η προηγούμενη απο κεί που είχε μείνει, μολις τελειώσει αυτή, θα συνεχίσει η προηγούμενη της και θα συνεχίσει ετσι μεχρι να ολοκληρωθεί η func(6) που δώθηκε στην αρχή.
MpOuKaLAs Δημοσ. 8 Ιουλίου 2010 Μέλος Δημοσ. 8 Ιουλίου 2010 Μπορεις να το εξηγησεις λιγο καλυτερα ποια ειναι η τελευταια function ? func( n - 2 ) Η func(n-3) Η το τελος καποιας απο τις δυο δεν εχω καταλαβει... Εννοεις πως οταν θα φτασει η func( n - 3 ) να δωσει αποτελεσμα 0 τοτε ασχετα με την if που δεν θα εκτελεστει θα προχωρησει παρακατω στην printf() και την func( n - 2 ) με ορισμα την τελευταια τιμη πριν η func( n -3 ) δωσει 0 ? ( η τιμη που λεω ειναι η 3 ). και ποτε θα σταματησει να τρεχει ο αλγοριθμος τελείως?
bnvdarklord Δημοσ. 8 Ιουλίου 2010 Δημοσ. 8 Ιουλίου 2010 Κανε ετσι την func ωστε να δεις καλυτερα πως εκτελούνται > void func(int n){ printf("Func %d stated\n", n); if( n > 0 ) { func( n - 3 ); printf("\n einai:%d\n",n); func( n - 2 ); } printf("Func %d ended\n", n); } την εκανα void μιας και δεν επιστρεφει τίποτα.
MpOuKaLAs Δημοσ. 8 Ιουλίου 2010 Μέλος Δημοσ. 8 Ιουλίου 2010 Ηδη το εχω κανει αυτο που ειπες και εμφανιζει την σειρα εκτελεσης. Δεν μπορω να το καταλαβω ομως για ποιο λογο αφου δεν εκτελειται η If εκτελειται η συναρτηση func( n - 2 ) που βρικσετε μεσα στην if. Επισης ποτε θα τερματιστει και γιατι? Τα βηματα μου ειναι: > void func(int n){ if( n > 0 ) { func( n - 3 ); printf("\n einai:%d\n",n); func( n - 2 ); } } 1) Δεχομαι το πρωτο πρωτο ορισμα που ειναι το 6 2) 6 > 0 ΑΛΗΘΕΣ 3) func ( 6 - 3 ) = 3 4) ΑΝΑΔΡΟΜΗ 1) Δεχομαι το 3 2) 3 > 0 ΑΛΗΘΕΣ 3) func( 3 - 3 ) = 0 4) ΑΝΑΔΡΟΜΗ 1) Δεχομαι το 0 2) 0 > 0 ΨΕΥΔΕΣ 3) Εκτελειται η printf και εμφανιζει 3 ( αλλα γιατι 3 και οχι 0 ? ) 4) ?
V.I.Smirnov Δημοσ. 8 Ιουλίου 2010 Δημοσ. 8 Ιουλίου 2010 Αφού ρωτάς πότε και γιατί θα τερματιστεί σημαίνει ότι δεν έχεις καταλάβει τις βασικές αρχές της αναδρομικής κλήσης. Σου είπα στο άλλο thread ότι πρέπει να τις μελετήσεις πρώτα διότι αλλιώς θα παιδευτείς να καταλάβεις τι γίνεται....με επιβεβαίωσες. Οι αναδρομικές κλήσεις συσωρεύονται στο stack διότι κάθε κλάδος πριν εκτελεστεί πλήρως δημιουργεί νέους. Μόλις τερματιστεί ένας υποκλάδος η εκτέλεση λαμβάνει από τον stack τον αμέσως προηγούμενο και συνεχίζει μ' αυτόν. Κάθε κλάδος τερματίζεται όταν συναντήσει την βασική υπόθεση που εδώ είναι το if( n > 0 )... Αν προκύψει για κάποιον κλάδο n<=0 δεν εκτελεστεί. Δες τι γίνεται όπως τα έγραψες : Α 1) Δεχομαι το πρωτο πρωτο ορισμα που ειναι το 6 2) 6 > 0 ΑΛΗΘΕΣ 3) func ( 6 - 3 ) = 3 4) ΑΝΑΔΡΟΜΗ Β 1) Δεχομαι το 3 2) 3 > 0 ΑΛΗΘΕΣ 3) func( 3 - 3 ) = 0 4) ΑΝΑΔΡΟΜΗ Γ 1) Δεχομαι το 0 2) 0 > 0 ΨΕΥΔΕΣ άρα δεν προχωρεί εντός του if και δεν κάνει νέα αναδρομή. Ανασύρει από το stack την πιο πρόσφατη κλήση που είναι η Β και συνεχίζει απο εκεί που την άφησε. Για την Β, ήδη εκτελέστηκε η εντολή f(n-3) με n=3. Προχωρά στην επόμενη, δηλ. τυπώνει 3. ( Προφανώς το 0 δεν θα τυπωθεί διότι δεν γίνεται δεκτή η εκτέλεση του κλάδου για n=0 και δεν φτάνει στην pritntf. ) Και μετά συνεχίζει με την f(n-2), (της Β ) που δημιουργεί νέο κλάδο... κλπ Κάθε κλήση f(n-2) δημιουργεί καινούριους κλάδους με την f(n-3) που συσωρεύονται και εκτελούνται LIFO, δηλ. όπως αποθηκεύονται στο stack. Φτιάξε ένα διάγραμμα με τις εκτελέσεις για ένα μικρό όρισμα όπως το 6 και θα το δεις μόνος σου. Ξέρω ότι είναι μπέρδεμα...
MpOuKaLAs Δημοσ. 8 Ιουλίου 2010 Μέλος Δημοσ. 8 Ιουλίου 2010 Εσυ φιλαρακι στην microsoft δουλευεις? Πάντως γραφοντας τα στο χαρτι με την μεθοδο LIFO βγαινει σιγα σιγα....
V.I.Smirnov Δημοσ. 8 Ιουλίου 2010 Δημοσ. 8 Ιουλίου 2010 Εσυ φιλαρακι στην microsoft δουλευεις? Πάντως γραφοντας τα στο χαρτι με την μεθοδο LIFO βγαινει σιγα σιγα.... Αν το λες σε μένα και με ειρωνία, ε τι να σου πω...κρίμα που προσπάθησα να σε βοηθήσω. Δεν δουλεύω στην MS ούτε έχω σπουδές πληροφορικής, είμαι ερασιτέχνης. Πριν χρόνια μελέτησα πώς δουλεύουν οι αναδρομικές συναρτήσεις. Δες και το πρόβλημα του ιππότη - αν έχεις το κουράγιο - όπως το έλυσα πριν από πολύ καιρό με αναδρομική συνάρτηση (να περάσει από όλα τα τετράγωνα μιας σκακιέρας ένας ίππος περνώντας από το κάθε ένα μόνο μια φορά και να τυπωθεί η διαδρομή) εδώ : http://www.insomnia.gr/forum/showthread.php?t=376940&highlight=%CE%B9%CF%80%CF%80%CE%BF%CF%84%CE%B7&page=2
RubiksCube Δημοσ. 8 Ιουλίου 2010 Δημοσ. 8 Ιουλίου 2010 Αν το λες σε μένα και με ειρωνία, ε τι να σου πω...κρίμα που προσπάθησα να σε βοηθήσω... Δεν νομίζω να το είπε ειρωνιικά. @ Mpoukalas Βασικά πρέπει να ξεκαθαρίσεις στο μυαλό σου τι είναι το stack και πως λειτουργεί. Από τις ερωτήσεις σου καταλαβαίνω ότι νομίζεις ότι μόλις γίνει η αναδρομική κλήση, η συνάρτηση που έκανε την κλήση εξαφανίζεται. Ενώ στην πραγματικότητα περιμένει να έρθει η σειρά της για να συνεχίσει από εκεί που είχε μείνει.
V.I.Smirnov Δημοσ. 8 Ιουλίου 2010 Δημοσ. 8 Ιουλίου 2010 Από τις ερωτήσεις σου καταλαβαίνω ότι νομίζεις ότι μόλις γίνει η αναδρομική κλήση, η συνάρτηση που έκανε την κλήση εξαφανίζεται. Ενώ στην πραγματικότητα περιμένει να έρθει η σειρά της για να συνεχίσει από εκεί που είχε μείνει. Ακριβώς ! Αυτό του εξηγώ κι εγώ πιο πάνω. Αλλά ακόμα κι' αν δεν το σκεφτεί με χρήση του stack, μπορεί να δει τη σειρά εκτέλεσης αν φτιάξει όπως του είπα ένα 'δέντρο' που δείχνει όλους τους κλάδους που δημιουργούνται. Για μικρό όρισμα είναι εύκολο.
MpOuKaLAs Δημοσ. 9 Ιουλίου 2010 Μέλος Δημοσ. 9 Ιουλίου 2010 Καλα πλακα κανεις που θα σε ειρωνευτω?Εσυ με βοηθησες απλα εντυπωσιαστηκα και απο το αλλο ποστ και το ειπα. Το ξεχναμε αυτο σαν να μην γραφτηκε ποτε. Λοιπον εκατσα και το εκανα στο χαρτι και ειδα πως λειτουργει η LIFO στην αναδρομη. Γενικα στο μυαλο μου το εχω το ολο θεμα πως οταν η συνθηκη if ειναι ΑΛΗΘΗΣ τοτε αμεσως ο αριθμος αποθηκευεται στο stack ενω καθε φορα που ειναι ΨΕΥΔΗΣ "τραβαει" απο το stack τις τιμες.Ετσι το εκανα και μου βγηκε τωρα αν εχετε κατι περισσοτερο να προσθεσετε καλο θα ηταν. ευχαριστω παντως ---------- Προσθήκη 09-07-2010 στις 00:04 ---------- Προηγούμενο μήνυμα 08-07-2010 στις 22:54 ---------- > int func(int n){ if( n > 0 ) { func( n - 3 ); printf("\n einai:%d",n); func( n - 2 ); } } Δειτε το σκεπτικο μου και πειτε μου αν ειμαι οκ: Εστω οτι το αρχικο n ειναι 5. 1) n = 5 2) if ( 5 > 0 ) TRUE 3) func( 5-3 ) = 2 4) ( τοποθετω το 5 στην στοιβα ) και αναδρομη 1) n = 2 2) if( 2 > 0 ) TRUE 3) func( 2 - 3 ) = -1 4) ( τοποθετω το 2 στην στοιβα ) και αναδρομη > int func(int n){ if( n > 0 ) { func( n - 3 ); printf("\n einai:%d",n); func( n - 2 ); } } 1) n = -1 2) if( -1 > 0 ) FALSE και δεν εκτελειται η if 3) Φορτωνω το 2 απο την στοιβα 4) printf( 2 ) 5) func( 2 - 2 ) = 0 6) αναδρομη 1) n = 0 2) if( 0 > 0 ) FALSE και δεν εκτελειται η if 3) Φορτωνω το 5 απο την στοιβα 4) printf( 5 ) 5) func( 5 - 2 ) = 3 6) αναδρομη 1) n = 3 2) if( 3 > 0 ) TRUE 3) ( τοποθετω το 3 στην στοιβα ) 4) func( 3 - 3 ) = 0 > int func(int n){ if( n > 0 ) { func( n - 3 ); printf("\n einai:%d",n); func( n - 2 ); } } 1) n = 0 2) if( 0 > 0 ) FALSE και δεν εκτελειται η if 3) Φορτωνω το 3 απο την στοιβα 4) printf( 3 ) 5) func( 3 - 2 ) = 1 6) αναδρομη 1) n = 1 2) if( 1 > 0 ) TRUE 3) ( τοποθετω το 1 στην στοιβα ) 4) func( 1 - 3 ) = -2 > int func(int n){ if( n > 0 ) { func( n - 3 ); printf("\n einai:%d",n); func( n - 2 ); } } 1) n = -2 2) if( -2 > 0 ) FALSE 3) Φορτωνω το 1 απο την στοιβα 4) func( 1 - 2 ) = -1 ΤΕΛΟΣ ΓΙΑΤΙ ΕΧΩ ΑΔΕΙΑ ΣΤΟΙΒΑ ειμαι σωστος βρε παιδια ?
V.I.Smirnov Δημοσ. 9 Ιουλίου 2010 Δημοσ. 9 Ιουλίου 2010 Πολλά μπορούν να ειπωθούν για την αναδρομή, αλλά όχι εδώ λόγω χώρου. Επισημαίνω εν διαβάσει μερικές παρατηρήσεις που μου έρχονται στο μυαλό. Η αναδρομική λύση κάποιου προβλήματος μπορεί να είναι πολύ πιο σύντομη από την αντίστοιχη επαναληπτική. Δυστυχώς σε πολλές περιπτώσεις είναι λιγότερο αποδοτική. Οι παράγοντες που το καθορίζουν αυτό είναι κύρια δύο : α) η επιβάρυνση που σχετίζεται με τις κλήσεις της συνάρτησης β) η ενδογενής ακαταλληλότητα που μπορεί να έχει ένας αναδρομικός αλγόριθμος Το α) δεν αφορά αποκλειστικά τις αναδρομικές συναρτήσεις αλλά όλες τις συναρτήσεις γενικά. Σε μια κλήση συνάρτησης πάντα υπάρχει μια επιβάρυνση από τις πληροφορίες που πρέπει να αποθηκευτούν στο stack για να γίνει η κλήση (bookkeeping overhead). Στις αναδρομικές συναρτήσεις αυτή η επιβάρυνση είναι πολύ μεγαλύτερη διότι μια κλήση παράγει μεγάλο αριθμό άλλων κλήσεων. Π.χ. ο αναδρομικός υπολογισμός του παραγοντικού, ν! , παράγει ν κλήσεις. Το κέρδος είναι ότι κάποιο πολύπλοκο πρόβλημα ίσως μπορεί να λυθεί πιο καθαρά με αναδρομικό αλγόριθμο παρά με επαναληπτικό και αυτό συχνά είναι σπουδαιότερο. Πχ. για την περίπτωση του παραγοντικού ο αναδρομικός υπολογισμός του πρέπει να αποφεύγεται αφού με την ίδια σαφήνεια μπορεί να λυθεί και επαναληπτικά και με μόνον μία (ή καμία) κλήση. Η αναδρομική λύση είναι προτιμότερη όταν κάποιο πρόβλημα δεν έχει απλή επαναληπτική λύση. Το β) αφορά την 'χαμηλή' απόδοση που μπορεί να έχει ενδογενώς ένας αναδρομικός αλγόριθμος. Αυτό δεν έχει καμιά σχέση με το α). Το α) σχετίζεται στενά με το πώς ο compiler χειρίζεται τις συναρτήσεις (αποθήκευση δεδομένων στο stack κλπ). Το β) σχετίζεται με το υπολογιστικό φορτίο που απαιτεί ο αλγόριθμος για να εκτελεστεί. Π.χ. έστω η αναδρομική συνάρτηση που δίνει τους όρους της ακολουθίας fibonacci : > { 1 για n<=2 fibon(n)= { { fibon(n-1)+fibon(n-2) για n>2 Μια κλήση με μια μέση τιμή για το n, έστω fibon(100), πρακτικά δεν θα τελειώσει ποτέ - αν και πληρεί τις προϋποθέσεις - διότι δημιουργεί ένα τεράστιο πλήθος κλάδων και κλήσεων. (Και αν χωράει και το stack τόσα δεδομένα.) Δοκίμασέ τη. Το θεμελιώδες πρόβλημα της παραπάνω είναι ότι υπολογίζει τις ίδιες τιμές ξανά και ξανά. Για μια μέση τιμή του n, οι ίδιες τιμές υπολογίζονται άσκοπα τρισεκατομύρια φορές καθιστώντας την λύση εξαιρετικά σπάταλη υπολογιστικά και πρακτικά ανέφικτη. Σε αυτήν την περίπτωση μια επαναληπτική εκδοχή είναι αναπόφευκτη. Ένας αναδρομικός αλγόριθμος μπορεί να μετατραπεί σε επαναληπτικό. Η μετατροπή είναι σχετικά εύκολη αν η αναδρομική συνάρτηση καλεί ενδογενώς τον εαυτό της μόνον μια φορά. Π.χ. η παραπάνω συνάρτηση, fibon, (και η δική σου, func) καλεί τον εαυτό της δύο. Επίσης η μετατροπή ευκολύνεται αν η αναδρομική συνάρτηση καλεί τον εαυτό της στο τέλος. Αυτό λέγεται tail recusrsion. H δική σου είναι tail recursion. H fibon και η παραγοντική > { 1 για n==0 fact(n)= { { n*fact(n-1) για n>0 ΔΕΝ είναι (σκέψου γιατί). Κι' άλλα μπορούν να γραφούν αλλά φτάνει. Έχε τα αυτά κατά νου όταν δουλεύεις με αναδρομικές συναρτήσεις. Για τα άλλα που παραθέτεις, ναι σωστός. Αλλά σου ξέφυγε κάτι. Το 1 στο τέλος θα τυπωθεί διότι παρεμβάλλεται η printf(1) πριν την func( 1 - 2 ) = -1 . Αν κάνεις ένα διάγραμμα με τις κλήσεις που δημιουργούνται θα καταλάβεις την σειρά πιο εύκολα. Μπορείς και να δοκιμάσεις να βάλεις το printf πριν το if (εντός της func βέβαια) για να δεις με τι τιμές φτάνει η εκτέλεση στην func κάθε φορά. Δεν θα είναι ίδιες με αυτές που τυπώνει διότι τώρα το printf είναι εντός του if και δεν φτάνεται πάντα. Άντε καληνύχτα...
MpOuKaLAs Δημοσ. 9 Ιουλίου 2010 Μέλος Δημοσ. 9 Ιουλίου 2010 Ε μετα απο αυτο το αρθρο πως να μην σκεφτω οτι δουλευεις στην microsoft πλακα κανεις? Ευχαριστω και καταλαβα γιατι ΔΕΝ ειναι εκει που ρωτας!!!( αλιμονο ). Αν εχεις την καλοσυνη σχετικα με την ακολουθια fibonacci γιατι ασχοληθηκα και με αυτο μπορεις να μου πεις δυο τρια λογια ? Γνωριζω οτι defined by F(1) = 1, F(2) = 1, and F(n) = F(n-1) + F(n-2) for n = 3, 4, 5, ... δηλαδη καθε νεος αριθμος προκυπτει απο το αθροισμα των δυο προηγουμενων , ωραια μεχρι εδω. Η διευκρινηση που θα ηθελα να κανεις σχετικα με την συναρτηση π.χ (fibonacci( n - 1 ) + fibonacci( n - 2 )) σχετιζετε με το + ( συν ) μεταξυ των συναρτησεων.Δηλαδη πρωτα εκτελειται η αριστερη fibonacci ας πουμε ( παιρνει το n - 1 ) και στην επομενη εκτελειται η fibonacci( n - 2 ) για να παρει το προ - προηγουμενο στοιχειο ? και αφου τα παρει μετα τα προσθετει μεταξυ τους ? καταλαβα καλα?
V.I.Smirnov Δημοσ. 9 Ιουλίου 2010 Δημοσ. 9 Ιουλίου 2010 Nαι, το + εκτελείται αφού υπολογιστεί και ο τελεστέος στα δεξιά του, δηλ. αφού υπολογιστεί και το F(n-2). Η αναδρομική συνάρτηση fibonacci μοιάζει πολύ με την δική σου παραπάνω. Η διαφορά είναι ότι ενώ εσύ παρεμβάλεις το printf μεταξύ των κλήσεων, στην αναδρομική fibonacci υπάρχει το + . Για να γίνει η πρόσθεση πρέπει να υπολογιστούν αμφότεροι οι όροι, συνεπώς η πρόσθεση εκτελείται στο τέλος. Ο compiler αλλάζει ενδογεννώς την σειρά για να κάνει την πράξη. Το ίδιο γίνεται και αν κλήση δεν είναι αναδρομική, πχ cos(a)+sin(a). Πρώτα υπολογίζει τους όρους και μετά τους προσθέτει. Απλώς τώρα η κατάσταση είναι πιο πολύπλοκη επειδή λόγω των αναδρομών αποθηκεύονται πολλά ενδιάμεσα στοιχεία στο stack. Στην πραγματικότητα είναι >n1= F(n-1) n2= F(n-2) return n1+n2 Αυτός είναι ο λόγος που δεν είναι tail recursion (όπως και η παραγοντική) : πριν καλέσει ξανά τον εαυτό της κάνει κάτι άλλο, πρόσθεση (η παραγοντική τον πολλαπλασιασμό n* f(), όπου το f() το έχει ήδη υπολογίσει.) Ένας άλλος τρόπος να το σκεφτείς είναι ότι, υπολογίζει το F(n-1), το αποθηκεύει στο stack, αποθηκεύει επίσης το + στο stack, γίνεται ο υπολογισμός στα δεξιά του δηλ. το F(n-2), μετά ανακτά το +, ανακτά και το F(n-1) και τότε τα προσθέτει κανονικά. Άντε πάω να κοιμηθώ, φτάνει για σήμερα...
Προτεινόμενες αναρτήσεις
Αρχειοθετημένο
Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.