Βοήθεια σε άσκηση με δυαδικά δέντρα και φράγματα

Συζητήσεις για την γλώσσα C και C++

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
stillos
Δημοσιεύσεις: 5
Εγγραφή: 25 Μαρ 2009 20:13

Βοήθεια σε άσκηση με δυαδικά δέντρα και φράγματα

Δημοσίευση από stillos » 25 Μαρ 2009 20:23

Χρειαζομαι βοήθεια σε μία άσκηση που έχω κολλήσει. Η εκφώνηση με λίγα λόγια είναι η εξής:
Δώστε ένα άνω φράγμα F(N) και ένα κάτω φράγμα f(N) οποιουδήποτε δυαδικού δέντρου με Ν κόμβους. Αποδείξτε τα φράγματα που δώσατε.

Please απαντήστε γρήγορα γιατί πρεπει αυριο να την παραδώσω.

Άβαταρ μέλους
soteres2002
S. & H. Moderator
Δημοσιεύσεις: 1524
Εγγραφή: 05 Μαρ 2004 22:17
Τοποθεσία: Ιωάννινα

Βοήθεια σε άσκηση με δυαδικά δέντρα και φράγματα

Δημοσίευση από soteres2002 » 25 Μαρ 2009 21:39

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

stillos
Δημοσιεύσεις: 5
Εγγραφή: 25 Μαρ 2009 20:13

Βοήθεια σε άσκηση με δυαδικά δέντρα και φράγματα

Δημοσίευση από stillos » 25 Μαρ 2009 21:55

Η άσκηση λέει τα εξής:
Ένα δυαδικό δέντρο ορίζεται αναδρομικά ως ένας κόμβος. Η ρίζα του δέντρου είτε δεν έχει κανένα παιδί και αποτελεί φύλλο του δέντρου είτε έχει 2 παιδιά που είναι και αυτά ρίζες δυαδικών δέντρων. Το ακόλουθο σχήμα απεικονίζει ένα δυαδικό δέντρο με 13 κόμβους στο οποίο οι 7 είναι φύλλα. Το ύψος ενός δέντρου ορίζεται ως το μέγιστο μήκος οποιασδήποτε διαδρομής από τη ρίζα προς κάποιο φύλλο. Έτσι το ύψος του δέντρου του παρακάτω σχήματος είναι 4. Δώστε ένα άνω φράγμα F(Ν) και ένα κάτω φράγμα f(Ν) οποιουδήποτε δυαδικού δέντρου με Ν κόμβους. Αποδείξτε τα φράγματα που δώσατε.


Αυτά λέει και έχει και ένα σχήμα με 13 κόμβους.

stillos
Δημοσιεύσεις: 5
Εγγραφή: 25 Μαρ 2009 20:13

Βοήθεια σε άσκηση με δυαδικά δέντρα και φράγματα

Δημοσίευση από stillos » 25 Μαρ 2009 22:00

απ όσο καταλαβαίνω μάλλον ζητάει φράγμα για το ύψος

Άβαταρ μέλους
dva_dev
Script Master
Δημοσιεύσεις: 3790
Εγγραφή: 16 Σεπ 2005 01:32
Επικοινωνία:

Βοήθεια σε άσκηση με δυαδικά δέντρα και φράγματα

Δημοσίευση από dva_dev » 25 Μαρ 2009 22:30

Από αυτά που αναφέρεις μάλλον λέει όταν έχεις Ν κόμβους, να βρείς ποιό μπορεί να είναι το ελάχιστο δυνατό ύψος του και ποιό το μέγιστο.

Το ελάχιστο δυνατό ύψος μπορεί να το έχει ένα τέλειο δέντρο (πλήρες ισορροπημένο), ενώ το μέγιστο ο εκφυλισμός του σε λίστα.

Νομίζω έχεις ένα καλό ξεκίνημα για να αρχίσεις το ψάξιμο.

stillos
Δημοσιεύσεις: 5
Εγγραφή: 25 Μαρ 2009 20:13

Βοήθεια σε άσκηση με δυαδικά δέντρα και φράγματα

Δημοσίευση από stillos » 25 Μαρ 2009 23:06

Μάλλον αυτό ζητάει. Ευχαριστώ για τη διευκρίνηση. Μήπως όμως θα μπορούσες να με βοηθήσεις λιγο περισσότερο? Για παράδειγμα ένα τέλειο δέντρο μπορεί να έχει 3, 7, 15 κτλ κόμβους και το ύψος θα είναι αντίστοιχα 1, 2 ,3 κτλ. Όμως δεν βρίσκω κάποια σύνδεση έτσι ώστε να πω πως ισχύει για γενικό Ν. Καμιά ιδέα?

stillos
Δημοσιεύσεις: 5
Εγγραφή: 25 Μαρ 2009 20:13

Βοήθεια σε άσκηση με δυαδικά δέντρα και φράγματα

Δημοσίευση από stillos » 25 Μαρ 2009 23:08

Δηλαδή για Ν κόμβους πόσο θα είναι το ύψος ενός τέλειου δέντρου (σε συνάρτηση με το Ν)? Αυτό προσπαθώ να βρω

Άβαταρ μέλους
dva_dev
Script Master
Δημοσιεύσεις: 3790
Εγγραφή: 16 Σεπ 2005 01:32
Επικοινωνία:

Βοήθεια σε άσκηση με δυαδικά δέντρα και φράγματα

Δημοσίευση από dva_dev » 25 Μαρ 2009 23:16

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

http://www.google.gr/search?q=τέλεια+δυαδικά+δέντρα

Απάντηση

Επιστροφή στο “C, C++”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες