Θέμα: ΠΡΟΒΛΕΨΕΙΣ ΓΙΑ ΤΑ ΘΕΜΑΤΑ 2014

[tsabatman]

μαγικο τετραγωνο απο το τετραδιο εργασιων?

[Νίκος Αδαμόπουλος]

Το σωστό είναι μάλλον διδιάστατος.

δισδιάστατος

[Κανένας]

δι ή δισ
http://www.translatum.gr/forum/index.php?topic=49793.0
http://www.eleto.gr/download/Conferences/7th%20Conference/7thConference_RoundTable_PantazidouMarina.pdf

[Νίκος Αδαμόπουλος]

Εγώ είμαι Μπαμπινιωτικός...!

[Νίκος Αδαμόπουλος]

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

[jennifer]

Ρε παιδιά, τι κωδικοποίηση είναι αυτή της λύσης που δίνετε πιο πάνω? Δώστε το σε pdf ή τουλάχιστον γράψ'τε το εδώ να το δούμε...

[nikolasmer]

Ρε παιδιά, τι κωδικοποίηση είναι αυτή της λύσης που δίνετε πιο πάνω? Δώστε το σε pdf ή τουλάχιστον γράψ'τε το εδώ να το δούμε...

Δεν αξίζει τίποτα. Είναι πατάτα. Το αποκηρύσσω.

[apoldem]

Μερικές ασκήσεις για τους μαθητές που παρακολουθούν το φόρουμ και θέλουν να είναι προπονημένοι μέχρι την τελευταία στιγμή. Είναι όλες κλεμμένες και παρόμοιας δυσκολίας με ότι έχει πέσει μέχρι τώρα. Δεν είναι πρόβλεψη, αλλά για να μην ανοίγω καινούργιο ποστ, ταιριάζει εδώ. Μερικές λύνονται με θεϊκό τρόπο, αλλά αν δεν μπορείτε να σκεφτείτε σε 5' κάτι καλύτερο, τότε εξαντλητική αναζήτηση.

1. Σε έναν πίνακα (Ν-1) θέσεων είναι αποθηκευμένοι όλοι οι ακέραιοι αριθμοί από 1 έως Ν ανακατεμένοι, εκτός από έναν που λείπει. Βρείτε τον αριθμό που λείπει (χωρίς ταξινόμηση).

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

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

4. Σε έναν πίνακα ακεραίων Ν θέσεων βρείτε (αν υπάρχει) έναν υπό-πίνακα που το άθροισμα των στοιχείων του να είναι μηδέν.

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

6. Σε έναν πίνακα ακεραίων Ν θέσεων (ανακατεμένες θετικές και αρνητικές τιμές) βρείτε τον υπό-πίνακα με το μέγιστο άθροισμα.

7. Να υπολογιστεί το ακέραιο μέρος της τετραγωνικής ρίζας ενός πραγματικού αριθμού, χωρίς την χρήση των συναρτήσεων Α_Μ() και Τ_Ρ().

8. (και ένα λίγο πιο δύσκολο).  Σε ένα πίνακα ακεραίων Ν θέσεων, βρείτε το μέγιστο πλήθος επανάληψης του ίδιου αριθμού σε διπλανές θέσεις. Δλδ, αν δεν υπάρχουν διπλανές θέσεις με τον ίδιο αριθμό τότε η απάντηση είναι 1. Αν υπάρχει έστω μία φορά ο ίδιος αριθμός σε δύο διπλανές θέσεις τότε η απάντηση είναι 2, αν υπάρχουν τρεις διπλανές θέσεις με τον ίδιο αριθμό, η απάντηση είναι 3 ..., αν όλος ο πίνακας έχει τον ίδιο αριθμό, η απάντηση είναι Ν.

[alkisg]

Πολύ ωραία! Τα περισσότερα βγαίνουν με μονή σάρωση του πίνακα "O(n)", αλλά σε αυτά που γράφω "O(n²);" παρακάτω, γίνεται κάτι καλύτερο; Δεν μπόρεσα να το βρω σε λιγότερο από 5' (συνολικά)...

1. O(n)
2. O(n)
3. O(n)
4. O(n²);
5a. O(n²); (εκτός αν χρησιμοποιήσουμε hash tables που ξεφεύγουν πολύ από την ύλη...)
5b. O(n)
6. O(n²);
7. O(logn)
8. O(n)

[evry]

Επειδή αυτό είναι που μπερδεύει πολλούς μαθητές όταν λέμε O(n) δεν εννοούμε απαραίτητα μια σάρωση του πίνακα. Εννοούμε αυτό που λέει ο Άλκης μονή σάρωση. Δηλαδή αν ο μαθητής κάνει 4 π.χ. μονές σαρώσεις πάλι O(n) θα είναι.

Άλκη μπορείς να πεις εκτός από τον χρόνο σε ποια χρησιμοποιήσες παραπάνω μνήμη, δηλαδή να δώσεις και πολυπλοκότητα στη μνήμη ?   

[petrosp13]

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

[alkisg]

Άλκη μπορείς να πεις εκτός από τον χρόνο σε ποια χρησιμοποιήσες παραπάνω μνήμη, δηλαδή να δώσεις και πολυπλοκότητα στη μνήμη ?   

Δεν χρησιμοποίησα πουθενά πίνακα, εκτός φυσικά από αυτούς των Δεδομένων των προβλημάτων... Απλές μεταβλητές / αθροιστές / μετρητές κλπ.

[apoldem]

Καμία παρεξήγηση petrosp13. Εγώ πάλι νομίζω ότι όλα τα θέματα (εκτός από το τελευταίο) λύνονται με μεθόδους που διδάχτηκαν πολύ καλά οι μαθητές. Το σχόλιο περί "εξαντλητικής αναζήτησης" απευθύνεται στους μαθητές. Δεν ψάχνουμε καμία εμπνευσμένη λύση. Το πολύ πολύ που χρειάζεται να κάνουν είναι έναν διπλό βρόγχο (τριπλό για το 4 και 6, αλλά ο εσωτερικός βρόγχος απλώς προσθέτει και μπορεί να γίνει συνάρτηση). Σε κάποια απ' αυτά (όχι το 4 και το 6) οι πιο ικανοί μπορεί να σκεφτούν και κάτι πιο γρήγορο και έτσι να κερδίσουν χρόνο για τα υπόλοιπα θέματα. Όλοι θα βαθμολογηθούν με άριστα, οπότε είναι νομίζω δίκαιο (από την άποψη ότι ο καλός μαθητής θα κερδίσει χρόνο) να είναι κάποια θέματα λίγο πιο έξυπνα. Το 5β είναι εκτός ύλης οπότε αγνοήστέ το (κακώς το έβαλα) και το 8 είναι σαφώς πιο δύσκολο, αλλά το έβαλα σαν πρόκληση.

Τα υπόλοιπα σχόλια κάτω από την γραμμή δεν αφορούν τους μαθητές
-------------------------------------------------------------------------
@alkisg, θεωρητικά όλες οι ασκήσεις απαιτούν το πολύ O(n) πολυπλοκότητα χωρίς επιπλέον μνήμη, εκτός από το 5 για το οποίο δεν έχω λύση καλύτερη από Ο(n^2) και το 5 που απαιτεί hash table στο τελευταίο βήμα (αλλιώς γίνεται σε Ο(n^2) χωρίς hash) και επίσης το 6 έχει την πιο αναπάντεχη λύση σε Ο(n). Αυτά τα δύο προβλήματα 4 και 6 είναι πραγματικά πολύ δύσκολο να λυθούν σε Ο(n), αλλά επαναλαμβάνω δεν θέλουμε τέτοια λύση από τους μαθητές (έτσι κι αλλιώς το 4 δεν λύνεται χωρίς hash σε Ο(n)). Για να μην σε τυραννάει η περιέργεια:
Στο 4, με ένα πέρασμα βρίσκουμε όλα τα αθροίσματα των υπό-πινάκων με αρχή το πρώτο στοιχείο και τελευταίο το στοιχείο που επισκεπτόμαστε, και τα αποθηκεύουμε πάνω στον ίδιο τον πίνακα (είναι εφικτό επειδή κάθε νέο άθροισμα είναι το παλιό συν το στοιχείο που επισκεπτόμαστε). Μετά λέμε ότι για να υπάρχει υπό-πίνακας με άθροισμα μηδέν θα πρέπει η διαφορά των προηγούμενων αθροισμάτων να είναι μηδέν, αφού τα ενδιάμεσα στοιχεία δεν προσφέρουν τίποτα στο άθροισμα. Τελικά ψάχνουμε να βρούμε δύο τουλάχιστον ίδιες τιμές μέσα στον πίνακα των αθροισμάτων που φτιάξαμε στο προηγούμενο βήμα (εδώ χρειάζεται hash για να γίνει σε Ο(n)).
Στο 6, το σκεπτικό είναι ότι οι υπό-πίνακες εκείνοι που έχουν αρνητικό άθροισμα αποκλείεται να είναι μέρος της λύσης. Γι' αυτό κινούμαστε άπληστα, προσθέτουμε συνεχώς και όσο βρίσκουμε μεγαλύτερο άθροισμα το κρατάμε. Αν όμως καθώς προχωράμε βγάλουμε αρνητικό άθροισμα, τότε αυτό σημαίνει ότι η λύση είναι Ή αυτή που έχουμε μέχρι εκείνη την στιγμή Ή βρίσκεται πέρα από το σημείο που βγήκε αρνητικό το άθροισμα. Έτσι ξεκινάμε νέα αναζήτηση από το σημείο που έγινε αρνητικό το άθροισμα και μετά.
Μην γουρλώνετε τα μάτια  . Κι εγώ λυμένα τα βρήκα, δεν τα σκέφτηκα μόνος μου.

[alkisg]

Ωραία, συμφωνούμε σε όλα λοιπόν εκτός από το 4 και το 6 που ακόμα δεν τα έχω καταλάβει.
Υποπίνακες λέμε αυτούς που φτιάχνονται από συνεχόμενα στοιχεία ενός πίνακα, σωστά;
Δηλαδή, για πίνακα Α[3], έχουμε:
Α[1:1], Α[1:2], Α[1:3], Α[2:2], Α[2:3], Α[3:3]
Άρα 6 υποπίνακες.
Πώς θα αποθηκευτούν τα αθροίσματά τους σε πίνακα με 3 θέσεις;

Επίσης, στο 6 μπορεί να έχουμε "θετικό άθροισμα" "αρνητικό άθροισμα" "θετικό άθροισμα" και ο μέγιστος να προκύπτει από την ένωση και των τριών...

[apoldem]

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

Για το 6 έχεις δίκιο, δεν το διατύπωσα σωστά λέγοντας ότι δεν μπορεί να περιλαμβάνεται υπό-πίνακας με αρνητικό άθροισμα στην λύση. Μπορεί πράγματι να έχουμε (+), (-) και (+) και όλα μαζί να είναι μεγαλύτερα από το κάθε (+) χωριστά. Ο άπληστος αλγόριθμος όμως, προσθέτει το πρώτο (+) με το (-) και αν βγει όλο μαζί αρνητικό, τότε ξέρει ότι η λύση είναι μόνο μέσα στο (+) και άρα την έχει βρει ή ότι η λύση βρίσκεται στα παρακάτω στοιχεία που δεν έχει επισκεφθεί ακόμη. Και αφού το πρώτο (+) με το (-) βγήκαν μαζί και τα δύο αρνητικά, τότε αποκλείεται κάποιο μέρος τους να είναι μέρος της λύσης που θα βρει παρακάτω. Το πρόβλημα είναι ακραίο παράδειγμα απληστίας, οπότε μην το κουράζεις άλλο. Σε κάθε περίπτωση η ενδεδειγμένη λύση, για τα γήινα δεδομένα, είναι εξαντλητική αναζήτηση με μικρές βελτιώσεις.