Υπολογισμός δεύτερου μικρότερου στοιχείου

[Mathletic]

Γειά

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

Σκέφτηκα να το αποδείξω επαγωγικά ως εξής:

Για χρειαζόμαστε μία σύγκριση, προκειμένου να βρούμε το δεύτερο μικρότερο στοιχείο.




Υποθέτουμε ότι, έχοντας στοιχεία, χρειαζόμαστε συγκρίσεις για την εύρεση του δεύτερου μικρότερου στοιχείου.


Πώς μπορώ να συνεχίσω και να αποδείξω ότι αν έχουμε στοιχεία, χρειαζόμαστε συγκρίσεις για την εύρεση του δεύτερου μικρότερου στοιχείου;


Ή υπάρχει καλύτερος τρόπος να αποδειχθεί η πρόταση;

[Mihalis_Lambrou]

Πώς μπορώ να συνεχίσω και να αποδείξω ότι αν έχουμε στοιχεία, χρειαζόμαστε συγκρίσεις για την εύρεση του δεύτερου μικρότερου στοιχείου;

Είναι πολύ απλό.

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

[Αντώνης Πάπαρης]

Έστω ότι έχεις τοποθετημένους τους αριθμούς σε μια γραμμή
Δημιουργείς νέα γραμμή συγκρίνοντας τα στοιχεία: το 1 με το 2, το 3 με το 4 κοκ, και παίρνοντας το μικρότερο.
Συνεχίζεις μέχρι να φτάσεις να έχεις γραμμή με 1 στοιχείο

Μέχρι εδώ έχεις N-1 συγκρίσεις. Μόνο που έχεις βρει το μικρότερο.

Πηγαίνεις στην προηγούμενη γραμμή, παίρνεις το μεγαλύτερο στοιχείο (αυτό που "έχασε" από το μικρότερο), το ορίζεις ως τρέχων και ακολουθείς την πορεία του μικρότερου προς τα πίσω, συγκρίνοντας το "τρέχων" με το "μεγαλύτερο του ζεύγους" και ορίζοντας ως νέο τρέχων το μικρότερο. Έτσι βρίσκεις το 2ο μικρότερο με συγκρίσεις.

Έτσι έχεις βρει το 2ο μικρότερο με συγκρίσεις.

[Mathletic]

Έστω ότι έχεις τοποθετημένους τους αριθμούς σε μια γραμμή
Δημιουργείς νέα γραμμή συγκρίνοντας τα στοιχεία: το 1 με το 2, το 3 με το 4 κοκ, και παίρνοντας το μικρότερο.
Συνεχίζεις μέχρι να φτάσεις να έχεις γραμμή με 1 στοιχείο

Μέχρι εδώ έχεις N-1 συγκρίσεις. Μόνο που έχεις βρει το μικρότερο.

Για να μπορούμε να συγκρίνουμε τα στοιχεία ανά ζεύγη υποθέτουμε ότι το πλήθος είναι δύναμη του ;
Ή πρέπει να πάρουμε περιπτώσεις για το ;


Θα πρέπει να αποδείξουμε ότι μέχρι εδώ έχουμε συγκρίσεις;

Μπορούμε να το δείξουμε ως εξής;

Στην πρώτη γραμμή συγκρίνουμε τους αριθμούς ανά ζεύγη, άρα έχουμε συγκρίσεις.
Στην δεύτερη γραμμή έχουμε αριθμούς, τους οποίους συγκρίνουμε ανά ζεύγη, άρα έχουμε συγκρίσεις.
...
Στην προτελευταία γραμμή έχουμε αριθμούς, άρα έχουμε μία σύγκριση.

Ο συνολικός αριθμός των συγκρίσεων ισούται με .

Πηγαίνεις στην προηγούμενη γραμμή, παίρνεις το μεγαλύτερο στοιχείο (αυτό που "έχασε" από το μικρότερο), το ορίζεις ως τρέχων και ακολουθείς την πορεία του μικρότερου προς τα πίσω, συγκρίνοντας το "τρέχων" με το "μεγαλύτερο του ζεύγους" και ορίζοντας ως νέο τρέχων το μικρότερο. Έτσι βρίσκεις το 2ο μικρότερο με συγκρίσεις.

Έτσι έχεις βρει το 2ο μικρότερο με συγκρίσεις.

Οπότε για να βρούμε το 2ο μικρότερο στοιχείο, συγκρίνουμε όλους τους αριθμούς, ανά ζεύγη, οι οποίοι έχασαν από το μικρότερο, σωστά;

Πώς βρίσκουμε ότι το πλήθος των αριθμών αυτών ισούται με ;

[Mathletic]

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

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


Συνολικά έχουμε το πολύ συγκρίσεις.








Εφόσον ισχύει η ανισότητα ισχύει έχουμε το πολύ συγκρίσεις, σωστά;

[Αντώνης Πάπαρης]

Δεν χρειάζεται το Ν να είναι δύναμη του 2. Αν σε κάποιο βήμα δεν έχουμε άρτιο πλήθος το "τελευταίο" στοιχείο περνάει χωρίς σύγκριση. Αυτό οδηγεί σε "δέντρο" ύψους το πολύ

Το πλήθος των συγκρίσεων βγαίνει πολύ εύκολα. Με κάθε σύγκριση "φεύγει" ένα στοιχείο και για να "φύγει" ένα στοιχείο απαιτείται μία σύγκριση.
Αφού έχουμε Ν στοιχεία και έχει μείνει 1, σημαίνει ότι έχουν "φύγει" Ν-1 στοιχεία, άρα έχουν γίνει Ν-1 συγκρίσεις.

Έστω ότι έχεις τοποθετημένους τους αριθμούς σε μια γραμμή
Δημιουργείς νέα γραμμή συγκρίνοντας τα στοιχεία: το 1 με το 2, το 3 με το 4 κοκ, και παίρνοντας το μικρότερο.
Συνεχίζεις μέχρι να φτάσεις να έχεις γραμμή με 1 στοιχείο

Μέχρι εδώ έχεις N-1 συγκρίσεις. Μόνο που έχεις βρει το μικρότερο.

Για να μπορούμε να συγκρίνουμε τα στοιχεία ανά ζεύγη υποθέτουμε ότι το πλήθος είναι δύναμη του ;
Ή πρέπει να πάρουμε περιπτώσεις για το ;


Θα πρέπει να αποδείξουμε ότι μέχρι εδώ έχουμε συγκρίσεις;

Μπορούμε να το δείξουμε ως εξής;

Στην πρώτη γραμμή συγκρίνουμε τους αριθμούς ανά ζεύγη, άρα έχουμε συγκρίσεις.
Στην δεύτερη γραμμή έχουμε αριθμούς, τους οποίους συγκρίνουμε ανά ζεύγη, άρα έχουμε συγκρίσεις.
...
Στην προτελευταία γραμμή έχουμε αριθμούς, άρα έχουμε μία σύγκριση.

Ο συνολικός αριθμός των συγκρίσεων ισούται με .

Πηγαίνεις στην προηγούμενη γραμμή, παίρνεις το μεγαλύτερο στοιχείο (αυτό που "έχασε" από το μικρότερο), το ορίζεις ως τρέχων και ακολουθείς την πορεία του μικρότερου προς τα πίσω, συγκρίνοντας το "τρέχων" με το "μεγαλύτερο του ζεύγους" και ορίζοντας ως νέο τρέχων το μικρότερο. Έτσι βρίσκεις το 2ο μικρότερο με συγκρίσεις.

Έτσι έχεις βρει το 2ο μικρότερο με συγκρίσεις.

Οπότε για να βρούμε το 2ο μικρότερο στοιχείο, συγκρίνουμε όλους τους αριθμούς, ανά ζεύγη, οι οποίοι έχασαν από το μικρότερο, σωστά;

Πώς βρίσκουμε ότι το πλήθος των αριθμών αυτών ισούται με ;

[Mathletic]

Δεν χρειάζεται το Ν να είναι δύναμη του 2. Αν σε κάποιο βήμα δεν έχουμε άρτιο πλήθος το "τελευταίο" στοιχείο περνάει χωρίς σύγκριση. Αυτό οδηγεί σε "δέντρο" ύψους το πολύ

Πώς συμπεραίνουμε ότι το ύψος του δέντρου είναι το πολύ ;

Το πλήθος των συγκρίσεων βγαίνει πολύ εύκολα. Με κάθε σύγκριση "φεύγει" ένα στοιχείο και για να "φύγει" ένα στοιχείο απαιτείται μία σύγκριση.
Αφού έχουμε Ν στοιχεία και έχει μείνει 1, σημαίνει ότι έχουν "φύγει" Ν-1 στοιχεία, άρα έχουν γίνει Ν-1 συγκρίσεις.

Κατάλαβα!
Ο τρόπος με τον οποίο το απέδειξα εγώ είναι λάθος;


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

Θα πρέπει να αποδείξουμε ότι μέχρι εδώ έχουμε συγκρίσεις;

Μπορούμε να το δείξουμε ως εξής;

Στην πρώτη γραμμή συγκρίνουμε τους αριθμούς ανά ζεύγη, άρα έχουμε συγκρίσεις.
Στην δεύτερη γραμμή έχουμε αριθμούς, τους οποίους συγκρίνουμε ανά ζεύγη, άρα έχουμε συγκρίσεις.
...
Στην προτελευταία γραμμή έχουμε αριθμούς, άρα έχουμε μία σύγκριση.

Ο συνολικός αριθμός των συγκρίσεων ισούται με .

Πηγαίνεις στην προηγούμενη γραμμή, παίρνεις το μεγαλύτερο στοιχείο (αυτό που "έχασε" από το μικρότερο), το ορίζεις ως τρέχων και ακολουθείς την πορεία του μικρότερου προς τα πίσω, συγκρίνοντας το "τρέχων" με το "μεγαλύτερο του ζεύγους" και ορίζοντας ως νέο τρέχων το μικρότερο. Έτσι βρίσκεις το 2ο μικρότερο με συγκρίσεις.

Έτσι έχεις βρει το 2ο μικρότερο με συγκρίσεις.

Οπότε για να βρούμε το 2ο μικρότερο στοιχείο, συγκρίνουμε όλους τους αριθμούς, ανά ζεύγη, οι οποίοι έχασαν από το μικρότερο, σωστά;

Πώς βρίσκουμε ότι το πλήθος των αριθμών αυτών ισούται με ;

[Αντώνης Πάπαρης]

Πώς συμπεραίνουμε ότι το ύψος του δέντρου είναι το πολύ ;

Προσπάθησε να το αποδείξεις.
Υπόδειξη: Γιατί σκέφτηκες ότι το Ν είναι δύναμη του 2 για να συνεχίσεις την απόδειξη? Σε τι σε βοήθησε? Θα μπορούσες να χρησιμοποιήσεις κάποια δύναμη του 2 για να φτάσεις στο αποτέλεσμα?

Ο τρόπος με τον οποίο το απέδειξα εγώ είναι λάθος;

Πρόσθεσες + κοκ
Αυτοί είναι ακέραιοι? Δουλεύει ο τρόπος σου αν αυτοί δεν είναι ακέραιοι?

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

Το πλήθος των συγκρίσεων εννοείς. Μάλλον δεν έχεις καταλάβει το "τελευταίο βήμα".

Για να το "δεις" κάνε ένα σχέδιο με 13 αριθμούς (για να καταλάβεις και γιατί το μήκος είναι ). Πάρε τυχαίους αριθμούς (για να σου είναι πιο εύκολο, να μην έχει δύο φορές τον ίδιο αριθμό) και δοκίμασε πως δουλεύει.

[Demetres]

Ίσως βοηθάει να το δούμε επαγωγικά. (Ουσιαστικά όμως είναι ο ίδιος αλγόριθμος με του Αντώνη.)

Θα δείξω ότι με το πολύ συγκρίσεις μπορώ να βρω το μικρότερο και το δεύτερο μικρότερο στοιχείο. Αυτό είναι άμεσο για . Έστω λοιπόν ότι ισχύει για κάθε .

Αν τα χωρίζω σε ζεύγη και κάνω συγκρίσεις. Από κάθε σύγκριση παίρνω τον μικρότερο αριθμό. Επαγωγικά, με το πολύ συγκρίσεις βρίσκω το μικρότερο και το δεύτερο μικρότερο στοιχείο αυτών των αριθμών, έστω τα με . Έστω επίσης ότι στις πρώτες συγκρίσεις συγκρίθηκε το με το και το με το . Τότε το μικρότερο στοιχείο του αρχικού συνόλου είναι το ενώ το δεύτερο μικρότερο στοιχείο είναι είτε το είτε το . Με μία επιπλέον σύγκριση μπορούμε να βρούμε ποιο από το δύο είναι. Συνολικά κάναμε

συγκρίσεις.

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

συγκρίσεις.

Στην τελευταία ισότητα, επειδή ο είναι φυσικός, έχω

[Demetres]

Πώς μπορώ να συνεχίσω και να αποδείξω ότι αν έχουμε στοιχεία, χρειαζόμαστε συγκρίσεις για την εύρεση του δεύτερου μικρότερου στοιχείου;

Είναι πολύ απλό.

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

Μιχάλη, αυτό δεν είναι σωστό. Στο (β), αν αυτό που έβγαλες έξω είναι ελαφρύτερο από το δεύτερο μικρότερο αντικείμενο τότε πρέπει να το συγκρίνεις και με το μικρότερο αντικείμενο των . Τότε όμως ουσιαστικά αυτός ο αλγόριθμος θα θέλει στην χειρότερη περίπτωση συγκρίσεις. (Δύο επιπλέον συγκρίσεις για κάθε επιπλέον στοιχείο.)

[Mathletic]

Ίσως βοηθάει να το δούμε επαγωγικά. (Ουσιαστικά όμως είναι ο ίδιος αλγόριθμος με του Αντώνη.)

Θα δείξω ότι με το πολύ συγκρίσεις μπορώ να βρω το μικρότερο και το δεύτερο μικρότερο στοιχείο. Αυτό είναι άμεσο για . Έστω λοιπόν ότι ισχύει για κάθε .

Αν τα χωρίζω σε ζεύγη και κάνω συγκρίσεις. Από κάθε σύγκριση παίρνω τον μικρότερο αριθμό. Επαγωγικά, με το πολύ συγκρίσεις βρίσκω το μικρότερο και το δεύτερο μικρότερο στοιχείο αυτών των αριθμών, έστω τα με . Έστω επίσης ότι στις πρώτες συγκρίσεις συγκρίθηκε το με το και το με το . Τότε το μικρότερο στοιχείο του αρχικού συνόλου είναι το ενώ το δεύτερο μικρότερο στοιχείο είναι είτε το είτε το . Με μία επιπλέον σύγκριση μπορούμε να βρούμε ποιο από το δύο είναι. Συνολικά κάναμε

συγκρίσεις.

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

συγκρίσεις.

Πολύ ωραία Το κατάλαβα!

Στην τελευταία ισότητα, επειδή ο είναι φυσικός, έχω

Μπορείτε να μου εξηγήσετε περαιτέρω γιατί ισχύει η ισότητα ;