THMMY.gr

Δίνεται το παρακάτω τμήμα ενός αλγορίθμου.
For i=1 To n Do
    For j=1 To i Do
        For k=1 To j*j Do
            S = S + 1
Ποια είναι και γιατί η  O(g(n))  του παραπάνω τμήματος αλγορίθμου;

Είναι παραπάνω η τάξη. Η πρώτη επανάληψη ναι μεν σου λέει, το εσωτερικό θα γίνει ν φορές, αλλά οι άλλες 2 είναι εξαρτόμενες από τη τιμή του n. Εποπτικά, βλέπω θα ναι n^4 (ή με λιγότερες πιθανότητες ν^3 ).

Εμένα στα θέματα, γιατί το ΝΕΟΣΑΡΧΙΕΠΙΣΚΟΠΟΣ (αυτό με το δέντρο) ποτέ δε μου βγαίνει όπως το υπολογίζω (δλδ να επαληθεύσω την απάντηση)? Μήπως έχει πολλές λύσεις?? Και τι πάει να πει, "σχεδόν πλήρες δέντρο" . Wtf.  Φεβρουάριος 2008...

Α και έχω μια απορία στις σημειώσεις. Αυτές οι σημειώσεις τι είναι? Έχει μέσα για πολυπλοκότητα? Είναι ΜΟΝΑΧΑ αποκλειστικά αυτά που είναι στο ethmmy?

Αυτό έλεγα και εγώ αλλά όταν το β΄ζω στην αυτοαξιολόγηση το μετράει ως λάθος .

Βρε μπας και είναι n^5  :???:  Γενικά πρέπει να το πάρεις μαθηματικά ...

Αν δεν είχαμε το μέσα-μέσα βρόχο θα μιλούσαμε για τάξη ν^2 πάντως, αυτό είναι σίγουρο.

Τι να σου πω με έχει μπερδέψει πάρα πολύ .

Πάντως σχετικά με το NEOΣΑΡΧΙΕΠΙΣΚΟΠΟΣ που ρώτησες παραπάνω  μόλις το έκανα και βγαίνει κανονικά.

Η μέθοδος που ακολούθησα ήταν :
 1. μετρησα τα γράμματα της συμβολοσειράς και εφτιαξα δυαδικό δένδρο τόσων θέσεων.
 2.Έκανα προδιατεταγμένη διάσχιση για να τοποθετήσω τα γράμματα ¨
- επισκεψη στη ρίζα (Βάζεις το Ν)
-Επισκεψη του αριστερού υποδένδρου (βάζεις το Ε)
---Μετα θεωρείς ότι το Ε είναι ριζα του υποδένδρου
---και επισκέφτεσαι το αριστερο υποδένδρο όπου βάζεις το Ο
Αφού τελείωσεις με τα υποδενδρα αυτά
επισκέφτεσαι τα δεξια υποδένδρα
οπότε προκύπτει το παρακάτω :
            

                                                   Ν
                                 Ε                                  Ι
                      Ο                  Ι                Σ               Π
             Σ              Χ      Ε       Π       Κ    Ο        Ο     Σ
          Α  Ρ
(Σορρυ που δεν το κάνω σε κάποιο πρόγραμμα για να φανεί καλύτερα άλλα δεν έχω πολύ χρόνο . αν δεν το καταλάβεις πες μου και θα το φτιάζω σε κανένα word το βράδυ , απλά προσπάθησε να τα βάλεις στο χαρτί όπως στα δίνω).

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

Αρχικά λοιπόν πας στο κάτω αριστερά παιδί και παίνεις το :   Α
Μετά στο κάτω αριστερά υποδένδρο και στο δεξί παιδί και παίρνεις το : Ρ
Επισκέπτεσαι την ρίζα του υποδένδρου αυτού και παίρνει το :  Σ
Θεωρείς την ρίζα του παραπάνω υποδέδρου σαν αριστερό παιδί του υποδένδου με ρίζα το Ο (ενα επίπεδο παραπάνω δλδ)
Εφόσον έχεις λάβει το αριστερό παιδί πας στο δεξί και αφού είναι φύλο το παίρνει δλδ το :Χ
Επισκέπτεσαι την ρίζα του υποδένδρου και παιρνεις το : Ο
Και στη συνέχεια επισκέφτεσαι το διξί παιδί -υποδένδρο  :
            Ι
       Ε      Π
Επειδή το  πας πρώτα αριστερά και παίρνεις το : Ε
μετά δεξιά και παίρνει το : Π
και μετά στη ρίζα και παίρνεις το : Ι
κ.ο.κ

ampoulog ωραιος φιλε,εγω το καταλαβα οπως το εγραψες!
Επισης στα ιδια θεματα μπορειτε να εξηγηστε το θεμα με την ΔΙΑΠΛΟΚΗ ?? Plz    ::) (καπου στη μεση τη διαδρομης το χανω  :-\)

Στο θέμα 10 β όταν λέει ότι η Array χρησιμοποιεί την Element τι εννοεί ?

μηπως στο πρωτο ποστ η πολυπλοκοτητα θα ειναι

n*(1+2+3...+n)*(1^2+2^2+...+n^2)

????

ετσι το σκεφτικα

Αυτό κάνω και εγώ και η τάξη μου βγαίνει Ο(n^4) . Αλλά μου το μετράει ως λάθος .

Κάτι άλλο
Μπορεί κάποιος να μου εξηγήσει τον αλγόριθμο ΚΜP και ΚΜP match .
Τι ακριβώς κάνουμε εκεί , πως λειτουργεί ??

Λοιπόν αλγόριθμος Boyer-Moore ακριβώς πριν τον κατακερματισμό.Γιατί στο παράδειγμα που έχει στις σημειώσεις του Μήτκα τελειώνει στα 15 βήματα? Κανονικά δεν θα έπρεπε πολύ πιο νωρίς??

Δεν κατάλαβα τι εννοείς .
Σε πόσα βήματα θα έπρεπε να τελειώνει ???

Αν παρατηρήσεις μετά το 3ο τα εξετάζει 1-1 δλδ 3+12=15
Κανονικά θα έπρεπε σε πολ'ύ λιγότερα βήματα να τελιώνει αφού κάθε φορά που ένα στοιχείο του Τ δεν εμπεριέχεται στο πατερν όλο το πατερν μεταφέρεται 1 στοιχειο μετά από αυτό.Οπως γίνεται αν δεις στα παραπάνω βήματα με το Η(2-3)

Κατάλαβα πως στο σκέφτεσαι .
Μάλλον έχει βάλει το 15 σαν τυχαίο αριθμό για να δείξει ότι υπάρχουν κάποια βήματα μέχρι το τέλος .
Θα το ρίξω μία ματια αργότερα πιο αναλυτικά και αν βγάλω άκρη θα σου πω .

1+2+... +n = 1/2n(n+1)
1^2+2^2+...n^2=1/2n(n+1)(2n+1)

apa n*(n(n+1))/2*(n(n+1)(2n+1))/2=n^6

??? τι λετε?

Αν αναφέρεσαι στο πρώτο θέμα ακούγεται λογικότατο .

Γιατί πολλαπλασιασμός? Οέο?

Βασικά πρέπει να κάνεις πράξεις με το Σ (εκείνο το μεγάλο το κεφαλαίο το μαθηματικό). Που να τρέχεις τώρα...

Δηλαδή αν κατάλαβα καλά υποστηρίζεις ότι η πολύπλοκότητα είναι Ο(n^3) ε?????

Παίδες με ανοιχτά βιβλία γράφουμε?

Yeap!

ΣΟΒΑΡΑ ΠΑΙΔΙΑ ΜΕ ΑΝΟΙΧΤΑ ΒΙΒΛΙΑ ΕΙΝΑΙ?????????  :o

Και τις σημειώσεις που μας έχει μοιράσει ???????????

Στις εξετάσεις μπορείτε να έχετε ανοιχτές τις σημειώσεις και ένα βιβλίο - αυτό που πήρατε (αν κάποιοι αγοράσατε και άλλα, τότε συνολικά μόνο ένα βιβλίο επιτρέπεται).

Οι σημειώσεις που μοιράστηκαν είναι αυτές που υπάρχουν στο ethmmy, σωστά?

Ναι αυτές είναι

Στην οριακη χειροτερη περιπτωση ομως που οι επαναληψεις θα ηταν απο 1 ως n,τοτε η πολυπλοκοτητα δεν θα ηταν λογικα n^4?Ειναι ομως λογικο τωρα με λιγοτερες επαναληψεις,να εχουμε μεγαλυτερη χρονικη πολυπλοκοτητα :n^6>n^4?

Αυτό είναι ένα ωραίο παράδοξο...  Κι εγώ το δοκίμασα με διάφορους τρόπους, και όλοι δίνουν n^6.  Παρ' όλα αυτά κάνει λιγότερες επαναλήψεις από έναν αλγόριθμο τάξης n^4 :P

Μήπως μπορεί κάποιος να μου εξηγήσει περιληπτικά πως λειτουργεί το διαίρει και βασίλευε ?????

Και επειδή ό,τι είναι παράδοξο κατά πάσα πιθανότητα κάτι πάει στραβά, δείτε λίγο και μια αντιμετώπιση στην εύρεση πολυπλοκότητας (απλά είναι ένας τρόπος, σε καμία περίπτωση δεν είναι ο μοναδικός...)

Ποια η χρησιμοτητα του this? Καποιο καλο παραδειγμα εχει κανεις?

Ωραίο παράδειγμα (και βρήκα πού είχα λάθος :D), αλλά στην αρχή του τόπικ ειπώθηκε ότι η αυτοαξιολόγηση δέχεται το n^4 ως λάθος... :???:

Από τις σημειώσεις μόνο αν διαβάσω είμαι καλυμένος???

Παιδιά όταν ρωτάει στην αυτοαξιόλογηση ποιος είναι ο μέγιστος αριθμών των μη μηδενικών στοιχείων σε έναν αραιό πίνακα ώστε ο βέλτιστος τρόπος αποθήκευσής του να είναι με τριάδες αριθμών, πώς το βρίσκουμε;
Και στον κώδικα Huffman υπάρχει κάποιος τρόπος να βρούμε πόσα bits ακριβώς χρειάζομαστε για ένα γράμμα;

Ο "βέλτιστος τρόπος αποθήκευσης" σημαίνει πως ο τάδε τρόπος αποθήκευσης απαιτεί μικρότερο χώρο από κάποιον άλλο. Στις σημειώσεις αναφέρει 3 τρόπους, όπου έχουν μέσα τύπους που μας δίνουν το χώρο που απαιτείται συναρτήσει των μη μηδενικών στοιχείων (Ν). Αν ζητάει μέγιστο έχεις να κάνεις με μια ανισότητα. π.χ. 3Ν < n*w  , Ν φυσικός... και βρίσκεις το N.

Δίνεται ταξινομημένος πίνακας με τα εξής στοιχεία: 6, 10, 13, 20, 22, 27, 55, 58, 87, 99, 121 Να βρείτε το συνολικό αριθμό των συγκρίσεων που απαιτούνται για την εύρεση του 99 με αναζήτηση άλματος με άλμα ίσο με 3.

Πώς βρίσκουμε αποτέλεσμα  ???????????

Nομιζω οτι κανεις search με αλμα 3 καθε φορα και οταν βρεις αριθμο μεγαλυτερο απο 99 πας προς τα πισω με αλμα 1 μιας και ειναι σε αυξουσα σειρα οι αριθμοι του πινακα

Ναι αλλά αν κάνεις αυτό που λες ξεπερνας τα περιθώρια του πίνακα.

λογικα σταματας στο 121

Ξεκινάς από το 6 και με διαδοχικά άλματα ανά 3 στοιχεία βρίσκεσαι στα στοιχεία 20, 55 και 99. Η πρώτη σύγκριση είναι με το 20. Άρα συνολικά 3 συγκρίσεις..
Νομίζω..(με βάση τις διαφάνειες απαντώ)

Λογικά θα δίνει από δίπλα ένα υλοποιημένο δέντρο κωδικοποίησης, αλλιώς δε βγαίνει..

Κάποιος ρε παιδιά!!!! ^beg^

Υποθέτω πως ναι....
Βέβαια καλό είναι, όπου οι σημειώσεις δεν είναι πολύ αναλυτικές, να ανατρέχεις στο  βιβλίο σαν βοηθητική πηγή!! :)

όπως τα λέει η athanasia...

Να 'στε καλά ευχαριστώ πολύ!!!! ;)  ^pcsleep^

Παιδια αν καποιος εχει λυσει το θεμα της java Φεβρουαριου 2008 ας το ανεβασει πλζ!! :)

Καποιος που να εκανε το θεμα με τον κατακερματισμο της ΔΙΑΠΛΟΚΗΣ???
ΔΕΝ το καταλαβαινω με τπτ >:(

τσεκαρε αυτο http://www.thmmy.gr/smf/index.php?topic=26468.0 , αν κ ειναι μονο για το πρωτο μερος.Αν καποιος μπορει να ανεβασει τη λυση του θεματος της java (οπως ειπε κι ο adianohtos) πλζ?

Για την ΔΙΑΠΛΟΚΗ
Βήμα 1: Γραφείς την ΑΒΓ...... και αντιστοιχεις :
-Α->1
-Β->2
-Γ->3
-Δ->4
κ.ο.κ
Βημα 2 : Βρισκεις τις θεσεις των αριθμων στον πίνακα κατακερματισμού . δηλαδή για το Δ πχ 4mod9=4
              Για τις συγκρούσεις κανεις ότι σου λέει σε κάθε περιπτωση .
Βήμα 3 : Κατασκευάζεις τους πίνακες με αριθμούς και στη συνέχει τους μετασχηματίζεις σε γράμματα δλδ 4->Δ

Το δοκίμασα με το άλμα αλλά στην αυτοαξιολόγηση μου βγάζει λάθος.

Αν κατέχεις σε ικανοποιητικό βαθμό τις σημειώσεις που έχουν ανέβει στο eTHMMY, ναι, θα είσαι καλυμένος...

παιδια, οταν κανουμε τον πινακα κατακερματισμου υπαρχει ενας στανταρ αριθμος θεσεων? απ οτι ειδα απο διαφορα παραδειγματα συνηθως δημιουργει τοσες θεσεις οσες λεει η συναρτηση κατακερματισμου (πχ αν κ mod 13 απο 0 μεχρι 12) αλλα εχω πετυχει παραδειγματα που κραταει μια παραπανω. τι γινεται??????

Το θεμα ειναι οτι οταν στο παραδειγμα των σημειωσεων το κλειδι 44 κανονικα θα πρεπε να παει στη θεση 13! (η οποια δεν υπαρχει σε εκεινο τον πινακα για καποιο λογο).ΑΛΛΑ στο θεμα του φεβ.2008 για την ΔΙΑΠΛΟΚΗ στη λυση υπαρχει αλλη μια θεση που βαζει αυτος επιπλεον.Ξερει κανεις τι πρεπει να γινεται??

δλδ οταν η συναρτηση κατακερματισμου ειναι πχ Κmodx ,τοτε πρεπει να εχω x θεσεις μνημης η να βαλω οτι να ναι??

Οι θέσεις θα είναι σίγουρα παραπάνω από τα στοιχεία που θέλεις να βάλεις . Συνήθως για 8 στοιχεία παίρνουμε 12 θέσεις . ( όπως στο παράδειγμα στις διαφάνειες ) Αν είναι περισσότερα πιθανολογώ ότι εξαρτάται από τον χώρο που θέλουμε να διαθέσουμε κάθε - μάλλον που έχουμε για να διαθέσουμε - σε έναν υπολογιστή . Για την εξέταση φαντάζομαι αν δεν είναι κάποιο στάνταρ πλήθος (πχ 8-9->12) φαντάζομαι θα τις δίνει .

Mην ξεχνάτε ότι η αναζήτηση στο  (55, 99) θα γίνει σειριακά...Άρα έχουμε 3 συγκρίσεις μέχρι να βρούμε το 99 (το κλειδί μας δεν έιναι μεγαλύτερο απο το 99) και άλλες 2 συγκρίσεις(55 με 87 και 87 με 99) ...σύνολο 5...Ετσι το καταλαβαίνω, αν υπάρχει λαθος παρακαλώ διορθώστε..

To πρωτο άλμα θα είναι απο :
6-20
το δευτερο απο 20-55
το τριτο απο 55-99
Αρα τρεις  βγάζω εγώ

Και μου λέει οτι είναι λανθασμενη στην αυτοαξιολόγηση
Μάλλον κάτι δεν καταλαβαίνω καλά ή είναι λάθος της βάσης δεδομένων .

Αν κάποιος το βγάζει αλλιώς ας πει

Γιατί η αναζήτηση από 55-99 να είναι σειριακή ???

Πρώτα θα συγκριθεί και με το 6 άρα 4 συγκρίσεις!

Αυτό ακούγεται πιο σωστό !

Τώρα που το σκέφτομαι καλύτερα όμως δεν πρέπει να ισχύει γιατί στις σημειώσεις θεωρεί σαν πρώτη διερεύνηση απο 20-55 και εκτός αυτού και το 20 να αναζητούσαμε θα μπορούσε να κάνει πρώτα την σύγκριση με το 55 και αφού το έβλεπε μικρότερο να εποστρέψει προς τα πίσω σειριακά.

Δίνεται ένας αραιός πίνακας ακεραίων διάστασης 6 x 5. Αν Ν είναι ο αριθμός των μη μηδενικών στοιχείων του πίνακα, ποια είναι η μέγιστη τιμή του Ν, ώστε ο βέλτιστος τρόπος αποθήκευσης του πίνακα να είναι ως τριάδες αριθμών, όπου κάθε τριάδα αντιστοιχεί σε ένα μη μηδενικό στοιχείο (γραμμή, στήλη, τιμή); Θεωρείστε ότι για την αποθήκευση ενός ακεραίου χρησιμοποιούνται 4 bits.


Ρε παιδια σε αυτο το θεμα δεν κανουμε

3Ν<= Ν+30/4
Ν<=30/8 αρα μαξ=3 ??

Γιατι η αυτοαξιολογηση ολο λαθος το βγαζει

γιατί 30/4??
Αφού ο κάθε ακαίρεος πιάνει 4 bits η εξισωση είναι 3Ν*4<=(Ν+30)*4 ---> Ν=15

Και το βγάζει σωστό στην αξιολόγηση απ'οσο θυμάμαι!!

w00t? O τυπος στις σημειωσεις με / ειναι και μαλιστα μονο σε nxm .

Δειτε σελ 6-5 απο σημειωσεις:
Για αλμα α παει απο την 1η θεση στην S(α) που ειναι η 5η
Αρα το αλμα ειναι 4 θεσεις μετα καθε ελεγχο  αλλα το αλμα το εχει σαν α που ειναι το 5 (S(a)=5o
νουμερο)
Δλδ απο οτι καταλαβα μετακινηση θεσεων= αλμα-1


ΓΙΑ ΟΣΟΥΣ ΕΧΟΥΝ ΤΙΣ ΚΑΙΝΟΥΡΓΙΕΣ ΣΗΜΕΙΩΣΕΙΣ ΝΑ ΔΟΥΝ ΑΝΑΖΗΤΗΣΗ ΑΛΜΑΤΟΣ ΑΠΛΑ

Στη σελ 2-4,2-5 το w τι ειναι?
Και επισης οταν λεμε nxm πινακας ενοουμε n γραμμες και m στηλες?

n γραμμές και m στήλες!!
Πάντως στον τύπο N + (n*m)/w... μου φαίνεται πιο λογικό το (N + (n*m))/w  ότι κι αν είναι το w  :-\

τσουκου.

το w ειναι το μηκος της λεξης(πχ 4 bit)

οποτε με αυτο τον τροπο χρειαζεσαι
N λεξεις(w*N bit) και ενα πινακα απο bit
που δειχνει που υπαρχουν τα μη μηδενικα
στοιχεια. αρα m*n bit (m*n)/w λεξεις.

Αυτός ο τύπος (N+(nxm)/w) αναφέρεται σε άλλο τρόπο αποθήκευσης αραιών πινάκων, διαφορετικό από αυτόν που λέει στο ερώτημα...  Στην επόμενη σελίδα έχει αυτό που θέλουμε...

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

Wade το ερωτημα θελει και τους τρεις τυπους αποθηκευσης και να βρεις για ποιο μεγιστο Ν ειναι πιο συμφερον ο τελευταιος

Btw κολησε η αυτοαξιολογιση ξερει κανεις πως ξεκολαει?

Α εντάξει τότε ;)

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

με 4 bit λεξεις.

αν αποθηκευσουμε κανονικα τα στοιχεια του πινακα
θελουμε 30*4=120 bit.

αν τα αποθηκευσουμε σαν τριαδες αριθμων(γραμη στηλη στοιχειο)
θελουμε 3*4*Ν bit

αν τα αποθηκευσουμε ως πινακα απο bit +πινακα με τα στοιχεια
θελουμε Ν*4+30 bit

για να ειναι βελτιστη η δευτερη μεθοδος πρεπει Ν*4+30> 3*4*Ν
αρα Νmax=3.

για Ν=2 εχουμε για τη δευτερη μεθοδο 24bit και με την τριτη 38.
για Ν=5 εχουμε για τη δευτερη μεθοδο 60bit και με την τριτη 50.
αρα το αποτελεσμα μας ειναι cool.
 
μου δινεται η αισθηση οτι κανω καποιο πολυ χαζο
λαθος. ολα μου φαινονται σωστα αλλα οι αλλοι δεν πειθονται.

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

Αν αποθηκευσουμε σαν πινακα nxm , πινακα με μη μηδενικες τιμες, πινακα με στοιχεια οσα και οι γραμμες του αρχικου πινακα , τα οποια αντιστοιχουν αθροιστικα στο πληθος των ασσων ανα γραμμη
βγαζει
N+n+(nxm)/w. Πως βγαινει αυτο?

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

megapixel
1 λεξη για καθε στοιχειο
1 λεξη για τον  αριθμο των στοιχειων σε καθε γραμη
και (n*m)/w λεξεις για τον πινακα απο bit
(n*m bit που αντιστοιχουν σε τοσες λεξεις) .

Δίνεται ο παρακάτω πίνακας. Επιλέξτε όσα κλειδιά μπορεί να βρεθούν αν εξεταστούν το πολύ δύο στοιχεία του πίνακα με τη μέθοδο της δυαδικής αναζήτησης. 1 2 3 4 5 6 7
1.   1
2.   2
3.   3
4.   4
5.   5
6.   6
7.   7


Σε αυτό τι ακριβώς ζητάει ?????????????????

1 2 3 4 5 6 7

1 2 3 4 5 6 7
         |

1 2 3 4 5 6 7         ή         1 2 3 4 5 6 7
   |                                                 |
 
δυαδικη: διαιρουμε στα 2 και συγκρινουμε με μια συγκριση μονο μπορουμε να βρουμε το 4
ενω με δυο συγκρισεις  μπορουμε το 2 και το 6
αρα σωστο ειναι το 2,4,6

Ερώτηση:  Δίνεται το παρακάτω τμήμα ενός αλγορίθμου:

int i = 1;
while ( i <= n ) {
    for (int j = 1; j <= n; j = j * 2 ){
        x = x - 2 ;
}
            i++;
}

και η απάντηση δεν είναι n²... :(

Στις σημειωσεις λεει οτι το δυαδικο δεντρο ειναι αυτο που εχει καθε κομβοσ 2 παιδια
ενω στο βιβλιο (σελ370) λεει οτι εχει το πολυ 2 παιδια. τελικα τι ειναι σωστο?

Έχει το πολύ δύο είναι το σωστό .

@ megapixel : το πολυ 2 παιδια .

πωπω θα αυτοκτονησω με αυτη την αναζητηση αλματος. γιατι το αλμα να μετραει μετα το πρωτο στοιχειο???αφου η πρωτη διερευνηση ειναι μετα το πρωτο αλμα!!!!!
σκεφτηκα το αλλο.αφου το ιδανικο βημα αλματος ειναι ριζα n,εστω οτι εχουμε 9 στοιχεια. αν ξεκινησουμε κατευθειαν απο την τριτη θεση μετα απο 3 διερευνησεις φτανει στο τελος του πινακα ακριβως στο τελευταιο στοιχειο.αν ωστοσο κανουμε το αλμα μετα απο το πρωτο στοιχειο, δηλαδη παμε στην θεση 4 για την πρωτη διερευνηση, μετα απο 3 αλματα ξεπερνιεται το μεγεθος του πινακα -.-
οποτε......

Από τις διαφάνειες φαίνεται ότι η πρώτη διερεύνηση γίνεται στο p[a] και όχι στο πρώτο στοιχείο ....

Με αυτο συμφωνειτε?

Αυτο που κανω εγω γιατι ειναι λαθος?
Μηπως δεν ειναι πληρες?
Τι φταιει?

Μήπως θυμάσαι τις άλλες επιλογές???
Νομίζω θα πρέπει να είναι n*logn λόγω του δεύτερου βρόχου


Ερώτηση:

Δίνεται το παρακάτω τμήμα ενός αλγορίθμου:

int x = 1;
for (int i = 1; i <= n; i++) {
    for (int j = n; j >=i; j--){
        x /= n;
    }
}

Ποια τάξη O(g(n)) χαρακτηρίζει πιο πιστά την πολυπλοκότητα του παραπάνω τμήματος αλγορίθμου;

Ο(n²) ????

ρε παιδιά πως κανουμε επανεξεταση στην αυτοαξιολογηση?
αν παρεις πανω απο 5 λεει "Η εξέταση έχει ολοκληρωθεί επιτυχώς" και δεν μπορω να κανω αυτοαξιολογηση
αν παρεις κατω απο 5 και πατησεις επανεξεταση γραφει προσπαθειες για επανεξεταση : 1 αλλα και παλι δεν μπορω να κανω επανεξεταση

Λέγοντας δυαδικό δενδρο συνηθώς αναφερόμαστε σε μία πιο συμμετρική μορφή .
Το δενδρο που έχεις φτιάξει εσύ ναι μεν είναι δυαδικό αλλά υστερη σε συμμετρία με αυτό που σου δείχνω παραπάνω .

H συμετρια πως ακριβως οριζεται?
Δλδ καποιος που εχει μια μικροδιαφορα με σενα θα βγαλει αλλο αποτελεσμα=> οι απαντησεις ποικοιλουν?

Απλά ο πιο συνηθες τρόπος κατασκευής ενός δένδρου - όταν βέβαια δεν αναφέρεται κάτι άλλο είναι :
-αν Ν ο αριθμός των στοιχείων που θέλεις να κατατάξεις
να θεωρήσεις ένα στοιχείο η ρίζα το δεύτερο ως αριστερό παιδί τις ρίζες και το τρίτο ως δεξί παιδί τις ρίζας , το τέταρτο στοιχείο θα είναι το αριστερό παιδί του αριστερού παιδιού τις ρίζας , το πέμπτο το δεξί παιδί του αριστερού παιδιού της ρίζας , το έκτο το αριστερό παιδί του δεξιού παιδιού της ρίζας ,το εβδομο το δεξι παιδί του δεξιού παιδιού της ρίζας κ.ο.κ.
ξεκινώντας πάντα από αριστερά προς τα δεξιά .
Προκύπτει έτσι η δομή του δένδρου .
Και στη συνέχεια κατατάσεις τα στοιχεία με βάση τη μέθοδο που σου λέει .

Ναι αλλα συμφωνα μ ετην εκφωνηση εγω γιατι δεν ειμαι σωστος?

Με την εκφώνηση είσαι σωστός . Απλά όταν έφτιαχνα την άσκηση μάλλον θεώρησαν πιο προφανή την περίπτωση που σου περιγράφω.
Παίζει βέβαια και το γεγονός ότι είχε κάνε εκτενέστερες αναφορές περι συμμετρίας μέσα στην τάξη.
Παρόλα αυτά αν η ερώτηση θέλει αιτιολόγηση και το παρουσιάσεις σωστά δεν βρίσκω το λόγο να μην το δεκτούν.

Μπορει να μου πει κάποιος τι στο καλό κάνω λάθος ?????

έβαλες ένα λάθος γραμματάκι :P

Ευχαριστώ . Χτυπιέμαι ώρες τώρα και δεν το έβλεπα....

εχει ενα θεμα ταξινομηση φυσαλιδας στο ΖΑΓΟΡΑΚΗΣ  με 5 συγκρισεις. βγάζω σαν λυση το ΑΓΖΟΑΡΚΗΣ αλλα δεν μου το δινει ολο σωστο. και σε ενα αλλο θεμα ταξινομησης quicksort με pivot 5 της 5 3 8 9 1 7 0 2 6 4 για μια διαμεριση βρισκω αποτελεσμα 0 3 4 2 1 5 7 9 6 8 και το παιρνει το μισο σωστο. αμα ξερει καποιος ας βοηθησει...  

αν η σειρα αποθηκευσης ειναι 1 60 24 7 28 8 4  πως τοποθετουνται σε δυαδικο δεντρο αναζητησης? γιατι το εκανα αλλα στην αυτοαξιολογηση μου το βγαζει λαθος.,

                 1        (ρίζα)
                    60    (δεξί παιδί ρίζας)
               24          (αριστερό παιδί του 60)
           7      28       (7:αριστερο παιδί του 24 , 28:δεξί παιδί του 24)
         4  8               (4:αριστερο παιδι και 8: δεξί παιδί του 7)

το εδωσες σαν απαντηση και στο δεχτηκε? δεν χρειαζεται να ειναι ισοζυγισμενο?

Όχι δεν του έδωσα καμία απάντηση αλλά πρέπει να είναι σωστό η εκφώνηση δεν λέει ισοζυγισμένο αλλά δυαδικό δένδρο αναζήτησης . Αν θέλεις δοκίμασε το και πες μου .

για την bubblesort που ρωτησα πριν ξερεις?

Ναι παιδιά για την bubblesort αν κάποιος μπορεί να μας πει πως θα γίνει το Ζαγοράκης και γιατί θα του ήμουν υπόχρεη!

παιδια ας μας πει καποιος πως γινεται αυτο..

Ξέρει κανεις???
 ^banghead^

κανείς ρε παιδιά..??? ο λαός θέλει ΖΑΓΟΡΑΚΗ....

Μπορει καποιος να μου εξηγησε πως λυνεται αυτο :
Μια παραλλαγη της quicksort ειναι αντι για το κλασσικο pivot σε καθε διαμεριση, να επιλεγεται ενα
τυχαιο στοιχειο της συγκεκριμενης διαμερισης και να γινεται swap με το στοιχειο στη θεση low, ωστε
καθε φορα στη θεση low να βρισκεται τυχαιο pivot.Γραψτε τους τρεις αξονες(pivot) για τους τρεις
πρωτους διαμερισμους, καθως και την τελικη μορφη του πινακα που δινεται 19 6 33 19 3 75 30 60 43 1
 Plz.... ::)

ελα ενας αγιος ανθρωπος για ζαγορακη κ quicksort!!! ^ytold^

Εδω ποιο ειναι το σωστο? (αλγοριθμος ευθειας επιλογης)

Πηρα 0,38/1 δλδ 3 σωστα.

AΓΖΟΑΡΚΗΣ πρέπει να είναι το αποτέλεσμα δεν βγαίνει κάτι αλλο.... :-\
αλγόριθμο ευθείας επιλογής κάποιος μια εξήσηση???

πως το βγαζεις ετσι?

παιδια οσον αφορα την αναζητηση αλματος εστειλα το μεσημερι μαιλ στον ψωμοπουλο και μου απαντησε το εξης :

στην αναζήτηση άλματος ξεκινάμε από το πρώτο στοιχείο, και πηγαίνουμε κατευθείαν στο 1+α στοιχείο.
Εάν το άλμα πάει να βγει έξω από τα όρια του πίνακα, τότε το στοιχείο ελέγχου θα είναι το τελευταίο στοιχείο του πίνακα.


οποτε επιτελους λυθηκε η απορια λολ

o algorithmos taksinomisis fisalidas pou xrisimopoeitai pios einai akribws?

(ZAGAORIKS meta apo 5 sigkriseis )

γινεται να μας πεις πως σου βγηκε ετσι πλζ? μπας κ βρουμε το σωστο

Mαλλον χρησιμοποιωντας την αντιστοιχια του καθε γραμματς με τη σειρα του στο αλφαβητο
πχ Α->1   Δ-> 4    Ι->9

den kserw akribws pios einai o algorithmos

symfwna mauto pou exei sto ethmmy

BEGIN
1   for (i ← 1 to length[A])
2      do
3         for (j ← length[A] downto i + 1)
4            do
5               if (A[j] < A[j-1])
6                  then
7                     exchange A[j] and A[j-1]
END

for(i=0;i<9;i++){
for(j=8;j>i;j--) {
if(a [j ]<a[ j-1 ]) {
temp=a[ j ];
a[ j ]=a[ j-1 ];
a[ j-1 ]=temp;
}
}

}
an einai autos mporeis na ftiakseis ena pinaka xaraktirwn na valeis to ZAGORAKIS kai na to trekseis..prin to telefteo } grapse ena system.out.print kai tha ektypwnei meta apo kathe sygkrish..

den kserw an einai swsto  :(

Ναι αλλα δε συμφωνει με οτι εχει στη σελιδα της αναζητησης του σφαλματος
Δλδ το α=4?
Ή θεωρει οτι το πρωτο στοιχειο βρισκεται στη θεση 0?

Ερώτηση:  Δίνεται ο πίνακας ακεραίων αριθμών: 5, 3, 8, 9, 1, 7, 0, 2, 6, 4 Να δώσετε τη μορφή του πίνακα μετά από 2 αναδρομικές κλήσεις του αλγόριθμου ταξινόμησης με συγχώνευση


Ποτε σταματαει ρε παιδια ο αλγοριθμος?????????Καμια λυση?

ναι.αν προσεξεις στις σημειωσεις ξεκιναει απο το πρωτο και κανει αλμα 4 .

Στα θέματα του 2008 το θέμα με τον ΝΕΟΑΡΧΙΕΠΙΣΚΟΠΟ πως λύνετε???


2)Η φραση
ΝΕΟΣΑΡΧΙΕΠΙΣΚΟΠΟΣ
προκυπτει αν διασχισουμε ενα σχεδον πληρες δυαδικο δενδρο με προδιατεταγμενη διασχιση. Αν
διασχισουμε το ιδιο δενδρο με μεταδιατεταγμενη διασχιση ποια φραση προκυπτει;


(Απ:ΑΡΣΧΟΕΠΙΕΚΟΣΟΣΠΙΝ)

καποιος ρε παιδια εχω κολλησει απο το καψιμο...
Μια παραλλαγη της quicksort ειναι αντι για το κλασσικο pivot σε καθε διαμεριση, να επιλεγεται ενα
τυχαιο στοιχειο της συγκεκριμενης διαμερισης και να γινεται swap με το στοιχειο στη θεση low, ωστε
καθε φορα στη θεση low να βρισκεται τυχαιο pivot.Γραψτε τους τρεις αξονες(pivot) για τους τρεις
πρωτους διαμερισμους, καθως και την τελικη μορφη του πινακα που δινεται 19 6 33 19 3 75 30 60 43 1

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

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

χμ,καλη εξηγηση  :-[ ,τοση ωρα κοιμαμαι ορθιος

θα θελα να ρωτήσω και γω κάτι σχετικό!
Εφόσον διαλέγουμε τυχαία το αρχικό pivot, τα επιμέρους pivots που προκύπτουν δεν θα ναι εξαρτώμενα από το πρώτο; Με επιλογή άλλου pivot κάθε φορά θα έχουμε διαφορετικά δευτερεύοντα pivots;

εδιτ: πριν καν ποστάρω απαντήθηκε η απορία μου! :)

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

BEGIN
1   for (i ← 1 to length[A])
2      do
3         for (j ← length[A] downto i + 1)
4            do
5               if (A[j] < A[j-1])
6                  then
7                     exchange A[j] and A[j-1]
END

1 2  3 4  5  6  7 8  9               A[9]
Z A Γ Ο  Ρ Α Κ Η Σ

j              
9               A[ 9 ]<A[ 8 ]
8                A[ 8 ]< A[ 7 ]            ΖΑΓΟΡΑ-ΗΚ-Σ
7                A[ 7 ]<A[ 6 ]
6                 A[ 6 ]<A[ 5 ]             ΖΑΓΟ-ΑΡ-ΗΚΣ
5                  A[ 5 ]< A[ 4 ]           ΖΑΓ-ΑΟ-ΡΗΚΣ

ΖΑΓΑΟΡΗΚΣ

δεν εχω κανει ολους τους πιθανους συνδυασμους αλλα λογικα ναι, εφ οσον το μονο θεωρητικα ταξινομημενο στοιχειο σου ειναι το pivot καθε φορα, ο υπολοιπος πινακας θα προκυπτει με βαση αυτο .
λολ και τζαμπα απαντησα και ειπα οτι να ναι -.-  αποσυρομαι 0.0

παρθενοι (ζωδιακα) εκει εξω παιξτε κινο και τζοκερ αυτες τις μερες θα σας ερθουν λεφτα π δεν τα περιμενατε!!!! σημερα εγω βρηκα 20 ευρω!!!!!!

αρε λιτσα!!!!

(ασχετοοοοοοοοοοοοοοοοοοοοοοοοο)

Ευχαριστώ πολύ! Κόντεψα να σκάσω μέχρι να καταλάβω τη ριμάδα τη quicksort!

ευχαριστώ stefos...είχα κάνει λάθος το δέντρο...

Να σου πω, για να κάνω το δέντρο από την φράση πως θα καταλάβω τι ύψος θα έχει???
Εγώ είχα κάνει ένα στην "τύχη"

μετρας τα γραμματα. στη συγκεκριμενη περιπτωση ειναι 18 .  χρησιμοποιεις τον τυπο στις σημειωσεις και βρισκεις το υψος . νομιζω βγαινει 4 ( με το μηδεν μεσα )

Μπορεί κάποιος να μου εξηγήσει την εισαγωγή/διαγραφή κλειδιών σε Β-Δέντρα και πότε ένας κόμβος είναι πλήρης???
:)

Είναι λίγο περίεργα τα Β δέντρα. Ισχύουν οι παρακάτω κανόνες:
(καταρχάς κάθε κόμβος και κάθε φύλλο μπορεί να έχει περισσότες από μια τιμές).

Το δέντρο είναι ταξινομημένο όπως το διαβάζεις από αριστερά προς τα δεξιά.
η ρίζα έχει το ελάχιστο 1 στοιχείο, και μέγιστο 2d
οι υπόλοιποι κόμβοι και τα φύλλα έχουν το ελάχιστο d και μέγιστο 2d κλειδιά.
Τα παιδιά κάθε κόμβου είναι κατα 1 περισσότερα από τα στοιχεία του

Η εισαγωγή γίνεται πάντα στα φύλλα.
Όταν με την επόμενη εισαγωγή που θέλεις να κάνεις, τα στοιχεία του κόμβου πρόκειται να γίνουν 2d + 1 τότε τα πρώτα d γίνονται ένα φύλλο, τα τελευταία d άλλο ένα και το μεσαίο στοιχείο πηγαίνει στον πατρικό κόμβο.

Κατα τη διαγραφή, όταν έχεις > d στοιχεία στον κόμβο δεν υπάρχει πρόβλημα.
Όταν έχεις d τότε τα πράγματα μπερδεύονται λίγο... πρέπει να κάνεις συγχωνεύσεις για να οδηγηθείς σε σωστή δομή του δέντρου. Πάντα να έχεις κατα νού την από αριστερά προς τα δεξιά ταξινόμιση.

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


btw, οι απαντήσεις για τα τεστ αυτοαξιολόγησης βρίσκονται μέσα στον κώδικα HTML του ethmmy... Εδώ να σας δώ, τι κάνατε στα συστήματα του πρώτου έτους :p (είναι ένα input με name = qstAnswer)

αφού είναι server side το script που τα ελέγχει και η σωστή απάντηση στη βάση δεδομένων ειναι. Τα στοιχεία φόρμας είναι άσχετα με το τι είναι σωστό...

ναι, server based είναι, η php υπολογίζει τα αποτελέσματα, αλλά οι λύσεις πάλι υπάρχουν (who knows why...)

tested :D

δε βλέπω τπτ τέτοιο. Για ρίξε κώδικα...

και δεν ίναι php , είναι jsp

Δίνεται ταξινομημένος πίνακας με τα εξής στοιχεία: 3, 5, 6, 10, 18, 19, 20, 23, 27, 74, 99 Να βρείτε το συνολικό αριθμό των συγκρίσεων που απαιτούνται για την εύρεση του 99 με γραμμική αναζήτηση.

diavazw diavazw diavazw posts k den vlepw tpt gia ton algoruthmo KMP k mia teliki apantisi gia tous array pinakes k tis lekseis..kserei kaneis??pls

yeah όντως έτσι είναι , στις υπολογιστικές! Στις πολλαπλής όπως βλέπω δεν...

KMP αλγόριθμος ταξινόμισης

Εξετάζει το πρότυπο που έχουμε, ωστε να βρεί κάποια κομμάτια που επαναλαμβάνονται. Πιο συγκεκριμένα:

a b a b a c
0 0 1 2 3 0

ξεκινάει από το 2ο χαρακτήρα, και όταν βρεί τον ίδιο με τον πρώτο ξεκινάει να μετράει. Όσο οι επόμενοι χαρακτήρες ακολουθούν την ίδια σειρά με τους αρχικούς ανεβαίνει στο μέτρημα. Άν όχι, κατα κάποιον τρόπο μηδενίζει.

Παράδειγμα από το ethmmy:
χ α χ ο χ α
0 0 1 0 1 2


Αφού το κάνει αυτό, εξετάζει το string που θέλουμε να ψάξουμε ώς εξής:

τοποθετεί την αρχή του προτύπου στην αρχή του string, και εξετάζει ένα προς ένα τα γράμματα. άν τα βρεί όλα σταματάει την αναζήτηση.

Άν κάποιο από τα γράμματα δεν είναι ίδιο, τότε τοποθετεί τον πρώτο χαρακτήρα του προτύπου ΠΟΥ ΕΙΝΑΙ ΙΔΙΟΣ με αυτόν στον οποίο είχε σταματήσει στο string. Αν δεν υπάρχει, τότε ξεκινάει από την αρχή.

Ο αλγόριθμος στη σελίδα 7-6 βοηθάει πολύ...

Ελπίζω να μην ισχύει, αλλά νομίζω πως βλέπω αρκετά λάθη στις απαντήσεις τους...

Για τους array πίνακες και τις λέξεις:

στο ethmmy στις απαντήσεις λέει για το 6χ6 οτι το Ν πρέπει να είναι 11. Ωστόσο αυτό είμαι σίγουρος πως είναι λάθος, καθώς στους 11 χαρακτήρες η μορφή με τις συντεταγμένες χρειάζεται 3Ν = 33 byte ενώ η μορφή με τον πίνακα bit χρειάζεται Ν + 6*6/4 = N + 9 = 20 byte...

Νομίζω ότι τα αποτελέσματα τα βγάζουνε μόνο από το 6*6...

ps:
ισχύουν οι τύποι:

για την κανονική αποθήκευση:   n*m (είναι όλα χαρακτήρες)
για την αποθήκευση με πίνακα bit: Ν + n*m/w (ένας πίνακας με χαρακτήρες μεγέθους Ν και ένας με bits μεγέθοθς n*m)
για την αποθήκευση με συντεταγμένες: 3Ν (3 χαρακτήρες για κάθε μη μηδενικό στοιχείο)

Γιατι μου το βγαζει λαθος??????????

3Ν*4 < Ν*4 + 6*6 =>  12Ν<4Ν+36 => 8Ν<36 => Ν<4,5 Αρα Ν=4!

τα γράφεις πολύ σωστά, έτσι πρέπει να βγαίνει. Αυτοί υπολογιζουν από το n x m...

Εδω το O(n) δεν ειναι το σωστο?
Αφου στο 2ο βροχο θα κανει απο 1 εως n αλλα με βηαμα j^2 αρα λιγοτερες φορες απο n
                                                        n
αρα συνολο=n*(κατι λιγοτερο απο n)=/  ή
                                                       \n^2

re seis ta dentra AVL einai simantika????Den ta polikatalaba

???

Κάτσε να το κάνουμε αναλυτικά...

χ α χ ο χ α

   1   2   3   4   5   6   7  
i | 1  2   3   3   4   5   6
j | 0  0   1   0   0   1   2

1: f(1) = 0; i=2
2: f(2) = 1; i=3; j=1
3: j=0;
4: f(3)=0; i=4;
5: f(4)=1; i=5; j=1;
6: f(5)=2; i=6; j=2;

το f(0) μπαίνει από την αρχή 0 απ' ότι κατάλαβα...
ενδέχεται βέβαια να μην το έχω καταλάβει καλά, οπότε διορθώστε με :p

Ρε παίδες ο πίνακας που έχει μόνο 0 και 1 μέσα γιατί να μην μετριέται όπως και οι άλλοι? Το 0 και το 1 δεν είναι ακέραιοι? Γιατί να μην πιάνουν και αυτοί 4 bits?
Με αυτή τη λογική η εξίσωση είναι 3Ν*4 < Ν*4 + 6*6*4

auto me tin poluplokotita tha eprpepe na einai n^2 efoson sou zitaei taksi k oi prakseis einai peripou (n^2)/2.. omws i autoaksiologisi vgazei lathos..evala gia dokimi to n*logn k mou to evgale swsto..ti k pws den kserw..

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

έχω την εντύπωση ότι βγαίνει:
5 24 135 58 71 60 24 10

κάνεις 7 συγκρίσεις για να βάλεις το 5 στην αρχή, και μετά κάνεις και άλλες 3 μέχρι τις 10

ta 0,1 einai monobita.. diladi na min dosoume vasi sta apotelesmata autoaksiologisis?? i lusi tou megapixel einai swsti..telos.. thanks ted

that's what I'll do ...

είναι για την ερωτηση της αυτοαξιολόγησης για το μέγιστο Ν έτσι??
Οι τύποι του βιβλίου αναφέρονται σε λέξεις, άρα για να βρεις ποιος τρόπος χρειάζεται τις λιγότερες λέξεις είναι:
3N<N+(6x5)/4===>N<3.75
έτσι πιστεύω ότι είναι άλλα μπορεί να έχω λάθος, γιατί γενικά οι απόψεις είναι πολλες
αντε να την πέσουμε να σηκωθούμε αύριο να γράψουμε  :)

επίσης για την άσκηση με τον ΝΕΟΣΑΡΧΙΕΠΙΣΚΟΠΟΣ χωρίς να είμαι σιγουρος νομιζω σχεδον πλήρες δέντρο σημαίνει όλα τα φύλλα του στο ίδιο επίπεδο.ο ποιο εύκολος τρόπος κατασκευής του δέντρου είναι να θεωρήσεις την φράση σαν πίνακα (το 0 αντιστοιχεί στη ρίζα και τα 2 πρώτα στοιχεία στα παιδιά της) και μετα βρίσκεις τους κόμβους και τα παιδιά τους συμφωνα με την παρατήρηση ότι το στοιχείο στη θέση κ έχει γιους στις θέσεις 2κ+1 και 2κ+2 και πατέρα τον [κ/2-1]
(οι αγκύλες σημαίνουν ακέραιο μέρος.)

Αυτό τουλάχιστον λεει το βιβλίο του μποζάνη σελ.98

και μια ερώτηση..οι σωροί με 3 παιδια ανα κόμβο που υπερέχουν σε σχέση με τους κλασικους??
Να θυμάστε τους σημερινούς σκόρερ των φιλικών μπορεί να πέσει κάτι σχετικό... :D
καλή επιτυχία σε όλους μας  ;D

Ερώτηση:

Υποθέστε ότι θέλουμε να ταξινομήσουμε τον παρακάτω πίνακα: 29, 12, 7, 75, 56, 43, 65, 34, 71, 24 με τη μέθοδο ταξινόμησης με σωρό (heapsort). Δείξτε την τελική μορφή του σωρού, όταν από τα στοιχεία του πίνακα δημιουργήσουμε έναν σωρό και στη συνέχεια αναδιατάξουμε τα κλειδιά του σωρού, έτσι ώστε αυτός να είναι ένας σωρός ελαχίστων.

Ρε παδιά πως γίνεται να μου απαιτεί ταξινόμηση σωρού αφού δίνει 10 στοιχεία και κατα συνέπεια ο σωρός δεν θα είναι πλήρης αφού, σύμφωνα με τη HeapSort, για να κατασκευάσω το σωρό θα ξεκινήσω από κάτω προς τα πάνω (από παιδιά φύλλα δηλαδή) ???
Άντε για να κοιμηθούμε καμια ώρα!!!!

θεώρησε ότι τα στοιχεία σου είνα ένας πίνακας και σχημάτισε ένα δένδρο με τη μέθοδο που ανέφερα παραπάνω,αυτό με τα 2κ και 2κ+1 για τα παιδια και τα σχετικα. Αφού ολοκληρώσεις το δέντρο ξεκινάς να εφαρμόζεις την συνθήκη του σωρού από τον δεξιότερο κόμβο(που έχει παιδια) του προτελευταίου επιπέδου (το τελευταίο επίπεδο έχει μόνο φύλλα άρα δεν χρειάζεται να ελέγξεις κάτι)
και συνεχίζεις προς τα αριστερά.Μετα ανεβαίνεις ένα επίπεδο και κάνεις την ίδια δουλεια...
έτσι πιστεύω πως γίνεται αν και δεν το έχω δοκιμάσει...

Μπορει να μου εξηγήσει κάποιος στις σημειώσεις του Μήτκα τι κάνει στην διαγραφή του 409 στα Β-δέντρα???

Άσχετο με το παραπάνω, αλλά σχετικό με το μάθημα, αυτό είναι ένα καλό λινκ για όσους έχουν πρόβλημα με την quicksort : ;)

http://pages.stern.nyu.edu/~panos/java/Quicksort/ (http://pages.stern.nyu.edu/~panos/java/Quicksort/)

409 στα Β - δέντρα

διαγράφει το 409, οπότε ο κόμβος εκείνος έχει < d κλειδιά

Συνενώνεται με το διπλανό κόμβο, και παίρνει και το 345 από τον πάνω, οπότε τώρα εκείνος έχει <d κλειδιά

εκείνος με τη σειρά του συνενώνεται με τον απέναντι και με το 210...

Καληνύχτα και καλή επιτυχία αύριο ! !

giati pairnei kai to 345???

γτ δεν εχει πλεον νοημα το 345 αφου αυτος ο κομβος δεν εχει πλεον 3 παιδια(2κ+1)

Eχεις λαθος γιατι λεει 6χ6 πινακας οχι 5χ6 που κανεις εσυ. Και με αυτον τον τροπο παλι Ν=4,5 βγαινει...

megapixel τελικα το 4 ειναι σωστο η οχι?!??!

Εγω αν μπει αυτο 4 θα βαλω παντως...

α ωραια,θα ειμαστε πολλοι  ;)

Βασικά κάπου εδώ λέει να βάλουμε κάτι της μορφής: σύμφωνα με το e-thmmy, η απάντηση είναι 11. Σύμφωνα με τη λογική, τα μαθηματικά και τις σημειώσεις είναι 4 :p

11 ειναι στο e-thmmy!?!?  :o :o :o

Μετα τις 7 συγκρισεις θα ειναι: 5 135 58 24 71 60 34 10
Μετα θα γινουν αλλες 3 συγκρισεις αλλα ΔΕΝ θα ανταλλαξουμε τα στοιχεια στη 10η συγκριση γιατι πολυ απλα δε τελειωσαν οι συγκρισεις για να βρουμε το μικροτερο!
Απλως διακοπτουμε τον αλγοριθμο!
αρα το αποτελεσμα θα ειναι το πανω!
Γιατι μου το βγαζει λαθος!?!?

Δίκιο έχεις, είχα μπερδεφτεί, σορρυ... Ουσιαστικά ο αλγόριθμος μπορεί να κάνει κινήσεις μετά από 7, 13, 18, 22, 25, 27, 28 για πίνακα 8 θέσεων (και θα κάνει μόνο αν το πρώτο στοιχείο δεν είναι το μικρότερο).

Οπότε στις 10 κινήσεις στο παράδειγμά μας αλλάζει μόνο το πρώτο στοιχείο με το μικρότερο του πίνακα

Aρα ακομη ενα λαθος της αυτοαξιολογησης?

στην εικόνα που στέλνεις αλλάζεις και άλλα 2 στοιχεία (το 4 και το 7). Μήπως τελικά μετράει τα λάθος και τα βαθμολογει?  :D :D :D

αν εννοείς αυτην την ερωτηση λεει 6x5..αν εννοεις αλλη..μην την ψαχνεις τετοια ωρα τετοια λογια  :P

Παιδια η υλη ποια ειναι????

σοσ .προλαβαινω να διαβασω???? :D ;D

η προσπαθεια μετραει ;D

χαχαχαχα! όχι, περίμενε μια ωρίτσα ακόμα και μετά άρχισε... :P

αντε, πολύ το ψάξαμε, πάμε κυλικείο για καφέ!! :D :D

Δίνεται η παρακάτω μέθοδος showStars:

void showStars(int n) {
    if (n >= 3) {
        showStars(n-1);
        System.out.print("***");
        showStars(n-2);
        System.out.print("*");
        showStars(n-3);
    }
}

Ποιος είναι ο αριθμός των αστερίσκων (*) που θα εκτυπωθούν στη κονσόλα μετά την κλήση της παραπάνω μεθόδου για n = 5;


Μπορεί κάποιος να μου δώσει μια απάντηση κ μια απλή εξήγηση?????ΕΥΧΑΡΙΣΤΩ

deleted

               

Απλή (νομίζω) εξήγηση:


Καλείται η συνάρτηση για n=5
1ο επίπεδο: το if θα εκτελεστεί ολόκληρο και θα καλέσει την Showstars(4), θα τυπώσει 3*, την showstars(3), θα τυπώσει 1* και την showstars(2).

Μέχρι τώρα έχουμε σύνολο 4 αστεράκια και κλήση 3 συναρτήσεων.

     2ο επίπεδο: -Η showstars(4) θα τυπώσει κι αυτή 4 αστεράκια και θα καλέσει τη showstars(3), τη showstars(2) και τη showstars(1)

                       -Η showstars(3) θα τυπώσει 4 αστεράκια και θα καλέσει τις showstars(2), showstars(1), showstars(0)
                       -Η showstars(2) δεν θα μπεί στο if και δεν θα κάνει τίποτα.

Άρα στο δεύτερο επίπεδο έχουμε 8 αστεράκια και κλήση 6 συναρτήσεων.

                    3ο επίπεδο:
                               Η showstars(3) θα τυπώσει 4 αστεράκια και θα καλέσει τις showstars(2),showstars(1),showstars(0) και όλες οι υπόλοιπες δεν θα κάνουν τίποτα γιατί n<3.

Αρα στο 3ο επίπεδο έχουμε 4 αστεράκια και κλήση 3 συναρτήσεων.

Τέλος στο 4ο επίπεδο, οι showstars(2),showstars(1),showstars(0) δεν θα κάνουν τίποτα γιατί n<3.

Σύνολο: 4+8+4= 16 αστεράκια


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

ΕΥΧΑΡΙΣΤΩ για τον χρόνο σας παιδιά.....νομίζω πως την κατάλαβα!!!!!thanks 8)) 8))

Εγώ είμαι πάλι...... :(!!!Επείδη έχω καταμπευρδευτεί με τις μεθόδους ταξινόμησης και θέλω να τα ξεκαθαρίσω λιγάκι στο κεφαλι μου,αν υπάρχει κάποιος που μπορεί να μου εξηγήση μια εκ των:

@@Ερώτηση:  Δίνεται ο πίνακας ακεραίων αριθμών: 5, 3, 8, 9, 1, 7, 0, 2, 6, 4 Να δώσετε τη μορφή του πίνακα μετά από 2 αναδρομικές κλήσεις του αλγόριθμου ταξινόμησης με συγχώνευση

@@Ερώτηση:  Δίνεται ο παρακάτω πίνακας. Χρησιμοποιώντας τον αλγόριθμο ταξινόμησης ευθείας επιλογής, να δώσετε τη μορφή του πίνακα μετά από 5 συγκρίσεις. Προσοχή! Συγκρίσεις μεταξύ δύο στοιχείων και όχι πλήρεις σαρώσεις του πίνακα. Σημειώστε πως τα αριθμητικά ψηφία έχουν μικρότερη τιμή από τα αλφαβητικά. ΑΡΧΙΚΟΣ ΠΙΝΑΚΑΣ Α Θ Η Ν Α 2 0 0 4

@@και αν κάποιος εχει ένα παράδειγμα τις quicksort!!!

Το ξέρω ζητάω πολλά αλλα πιστεύω να με νοιώθετε.................. ;) ;)

Εγώ το καταλαβαίνς ως επίπεδα. Δηλαδή έστω ρίζα Α με δυο παιδία τα Β και Γ.. Αν η Β έχει άλλα δυο παιδιά τα Δ και Ε, τότε συνολικά έχουμε 3 επίπεδα. στο πάνω πάνω είναι το Α, στο 2ο είναι το Β και το Γ, και στο τρίτο είναι το Δ και το Ε.  Δηλαδή άτω απο το Β υπάρχει ένα ακόμα επίπεδο , το οποίο το Γ δεν το έχει. Αρα έχει διαφορά ύψους 1. ΑΝ τώρα είχε παιδιά και το Δ ( πχ Ζ), τότε η διαφορά θα είναι 2. Τώρα δεν ξέρω.

Εγώ μπερδεύομαι με τις περιστροφές. Αν κάποος ξέρει και μπορεί να το εξηγήσει ας κάνει έναν κόπο..

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

3)Ποια φραση τυπωνεται για ορισμα n=4;
public void phrase(n){
switch(n){
case(1){
print("!");
phrase(n+2);
}
case(2){
print("hello");
phrase(n-1);
}
case(3){
print("world");
}
default{
while( n>=3 ){
print("*");
n-=1;
}
phrase(n);
}
}
}
(Απ: **hello!world)

Απο παληο θεμα

Μπορει καποιος να εξηγησει γιατι βγαινει αυτο το αποτελεσμα??

Προσοχη δεν εχει break οποτε ο ελεγχος "ρεει" προς τα κατω διαρκως

Όντως στο τέλος δεν θα πρέπει να τυπώνει worldworld...world...

Το πιο πιθανό είναι να έχει ξεχάσει το παιδί που έγραφε την εκφώνηση να βάλει break;

αλλιώς απλά μπαίνει και infinity loop (θα τυπώνει: **hello!world*hello!world*hello!world ...)

Λογικα δεν χρειαζεται break γιατι οταν μπαινει σε καποιο phrase(kati) ανεβαινει παλι πανω

ξεκιναει phrase(4) παει στο default  εκτυπωνει *
n-1=3
παλι στο default phrase(3) αλλο ενα *
n-1=2
phrase(2) εκτυπωνει hello και καπακι παει στην επομενη εντολη που ειναι το phrase(2-1) οποτε δεν χρειαζεται break
phrase(1) εκτυπωνει ! και κανει phrase(1+2) world
            
oντως ομως τωρα πως σταματαει χωρις break?

αφου εχει case(3) δεν επρεπε να τυπωνει πρωτα το case3 και μετα το default ( για ν=3 χωρις break)

?
edit δλδ τα δυο ** στην αρχη με προβληματιζουνε....

ναι πρωτα τυπωνει για Ν=4 * και καλει αμεσως phrase (3)

h phrase(3) δινει * και οχι το case της?

βασικα δες το πιο καλά... μπαίνεις στο default για n = 4. μετά έχεις while(n >= 3) οπότε κάνεις 2 μειώσεις στο n (στο while μεσα εχεις τις εντολές print("*") και n-=1) και βγαίνεις απ'το while με n = 2. και καλείς άρα την Phase(2);

 :D :D :D :D

Δεν "εβλεπα το while !!

THANX

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

η μηπως να κανουμε τις ηλεκτρονικες εξετασεις?  :P

παντως ελπιζω να μη βαλει καμια περιστροφη ::)

Θέματα του 09,10,11 δεν έχει ανεβάσει κανείς?Γιατί έτσι?

Γιατι γραφουμε πανω τους τις απαντησεις και τα δινουμε...

και επισης τα θεματα ειναι πολλα και θα χρειαστεις ολη την ωρα (ισως και παραπανω). οποτε δεν μπορουμε οτι να αντιγραψουμε σε προχειρο και να τα ανεβασουμε. ξερει τι κανει ο προεδρας!  8))