Θέμα: Δύσκολες ασκήσεις εκτός λογικής πανελληνίων

[Κωστας τζιαννης]

~~~~~ΑΣΚΗΣΑΡΑΑΑΑΑΑΑΑΑΑ~~~~~~~~(εκτος λογικης πανελληνιων)

οι 2 πρωτοι αριθμοι της ακολουθιας φιμπονατσι ειναι α1=1,α2=1. ο καθε επομενος προκυπτει απο το αθροισμα των 2 προηγουμενων του.
οι πρωτοι 10 αριθμοι της ακολουθιας δλδ ειναι αυτοι 1,1,2,3,5,8,13,21,34,55

Να φτιαξετε προγραμμα σε γλωσσα που θα διαβαζει εναν ακεραιο>0 και θα τον εμφανιζει σαν αθροισμα αριθμων φιμπονατσι.Να χρησιμοποιηθει το ελαχιστο πληθος ορων.για παραδειγμα ο αριθμος 12=1+3+8 (που εχω 3 ορους) αλλα θα μπορουσα να τον γραψω και ετσι(12=3+3+3+3) που χρησιμοποιω 4 ορους.αρα ,αφου εγω θελω τους ελαχιστους ορους της ακολουθιας  θα τον γραψω σαν 12=1+3+8

[evry]

Αξίζει να μελετήσει κανείς την απόδειξη του θεωρήματος Zeckendorf

https://math.osu.edu/sites/math.osu.edu/files/henderson_zeckendorf.pdf

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

Έτσι για να θυμόμαστε που και που τι είναι πληροφορική.

[Κωστας τζιαννης]

!!!!~~~~~~~ΑΣΚΗΣAΡΑ TOP OF THE TOP OF THE TOP OF THE TOP(οχι για πανελληνιες)~~~~~~~~~~~~~~!!!!!!!
(ΤΕΛΙΚΑ ΧΑΖΟΜΑΡΑ ΗΤΑΝ ΑΠΛΑ ΗΘΕΛΕ ΝΑ ΞΕΡΕΙΣ ΑΠ ΕΞΩ ΕΝΑΝ ΑΛΓΟΡΙΘΜΟ.ΞΕΝΕΡΑ......)
Ισως η καλυτερη ασκηση που εχω δει ποτε μου.Να φτιαξετε προγραμμα σε γλωσσα που θα διαβαζει εναν πινακα ακεραιων 100 θεσεων
Α[100] ,οπου καθε αριθμος θα ειναι απο το 1-99. Να βρειτε εναν αριθμο του πινακα που εμφανιζεται τουλαχιστον 2 φορες(δε χρειαζεται να βρειτε περισσοτερους).Να μην χρησιμοποιηθει ταξινομηση και να χρησιμοποιηθoυν συνολικα οσο το δυνατον λιγοτερες μεταβλητες

[alkisg]

Η πιο προφανής λύση σε Ο(Ν) είναι να χρησιμοποιηθεί ένας άλλος πίνακας Συχνότητες[1..99], αρχικοποιημένος σε 0, και σαρώνοντας τον Α να αυξάνουμε το Συχνότητες[Α[ι]] κατά 1. Και σταματάμε την πρώτη φορά που κάποιο στοιχείο του φτάσει στο 2.

Τώρα αν για κάποιο λόγο θέλουμε μαζοχιστικά να αποφύγουμε δεύτερο πίνακα, μπορούμε να χρησιμοποιήσουμε τον ίδιο τον Α σαν να ήταν δύο πίνακες. Π.χ. αντί να προσθέτουμε "1" στον πίνακα Συχνότητες, να προσθέτουμε "256ρια" στον πίνακα Α, ώστε το "high byte" του κάθε στοιχείου του Α να μετράει συχνότητες και το "low byte" να συνεχίζει να κρατάει τους αριθμούς. Και αφού τελειώσουμε, πάλι σε Ο(Ν), μηδενίζουμε τα "high bytes" για να αφήσουμε τον πίνακα Α όπως τον βρήκαμε.
Άρα τελικά χρησιμοποιείται μόνο ένας μετρητής ι.
Εναλλακτικά αντί για το high byte μπορεί να χρησιμοποιηθεί το πρόσημο των στοιχείων του Α.

[Κωστας τζιαννης]

Η πιο προφανής λύση σε Ο(Ν) είναι να χρησιμοποιηθεί ένας άλλος πίνακας Συχνότητες[1..99], αρχικοποιημένος σε 0, και σαρώνοντας τον Α να αυξάνουμε το Συχνότητες[Α[ι]] κατά 1. Και σταματάμε την πρώτη φορά που κάποιο στοιχείο του φτάσει στο 2.

Τώρα αν για κάποιο λόγο θέλουμε μαζοχιστικά να αποφύγουμε δεύτερο πίνακα, μπορούμε να χρησιμοποιήσουμε τον ίδιο τον Α σαν να ήταν δύο πίνακες. Π.χ. αντί να προσθέτουμε "1" στον πίνακα Συχνότητες, να προσθέτουμε "256ρια" στον πίνακα Α, ώστε το "high byte" του κάθε στοιχείου του Α να μετράει συχνότητες και το "low byte" να συνεχίζει να κρατάει τους αριθμούς. Και αφού τελειώσουμε, πάλι σε Ο(Ν), μηδενίζουμε τα "high bytes" για να αφήσουμε τον πίνακα Α όπως τον βρήκαμε.
Άρα τελικά χρησιμοποιείται μόνο ένας μετρητής ι.
Εναλλακτικά αντί για το high byte μπορεί να χρησιμοποιηθεί το πρόσημο των στοιχείων του Α.

βασικα στελνω ακριβως τι θελει.ηταν ερωτηση για συνεντευξη απο microsoft σε κοσμο.

You should solve the problem in O(N ) using O(1)  memory. You are not allowed to modify the array.

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

[bugman]

Τη λύση την έχω βρει. Απλά να αναφέρω ότι στην χειρότερη περίπτωση οι επαναλήψεις είναι Ν*(Ν-1)/2 (Τρίγωνος αριθμός)
Δεν νομίζω να έχουμε λοιπόν Ο(Ν)

[alkisg]

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

[alkisg]

Εδώ το λύνουν με το πρόσημο που ανάφερα παραπάνω: https://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

[Κωστας τζιαννης]

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

ναι αυτη ειναι η ευκολη εκδοχη.οχι η εκφωνηση ηταν σε αλλο σαιτ και ηταν σε συνεντευξη της microsoft .μπορει να υπαρχουν περισσοτεροι απο ενας διπλος και καθε ενας ειναι απο 1-99 και επισης καποιος η καποιοι μπορει να υπαρχουν και 2 και 3 και 4 φορες πχ δεν υπαρχει περιορισμος.

[alkisg]

Στείλε το link με την εκφώνηση, προς το παρόν πιστεύω ότι κάτι έχεις μεταφέρει λάθος.

[Κωστας τζιαννης]

Στείλε το link με την εκφώνηση, προς το παρόν πιστεύω ότι κάτι έχεις μεταφέρει λάθος.

https://csacademy.com/contest/interview-archive/task/find-any-duplicate/

[alkisg]

https://www.quora.com/How-can-I-find-a-duplicate-element-in-an-array-with-a-time-complexity-less-than-O-n-2-and-a-space-complexity-of-O-1
https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoise_and_Hare

[Κωστας τζιαννης]

https://www.quora.com/How-can-I-find-a-duplicate-element-in-an-array-with-a-time-complexity-less-than-O-n-2-and-a-space-complexity-of-O-1
https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoise_and_Hare

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

[alkisg]

Γιατί καλέ δεν δουλεύει; Απλά η ερώτηση είναι "παγίδα" με την έννοια ότι σου ζητάνε τον συγκεκριμένο αλγόριθμο κι αν δεν τον ξέρεις την έκατσες. Δεν νομίζω ότι γίνεται να ανακαλύψεις αλγόριθμο για paper ενώ πας να λύσεις μια άσκηση με προθεσμία 2λεπτου...

https://csacademy.com/submission/1198745/
https://csacademy.com/submission/1203016/
κλπ κλπ, δηλαδή εκτός από τις λάθος λύσεις υπάρχουν και αρκετές σωστές που χρησιμοποιούν τον Floyd.

Το μόνο πρόβλημα που βλέπω είναι ότι αυτές οι ερωτήσεις δεν θα έπρεπε να μπαίνουν σε φόρουμ/θέμα με τίτλο "ενδιαφέρουσες ασκήσεις στην ΑΕΠΠ", είναι ξεκάθαρα για προχωρημένα θέματα αλγορίθμων πανεπιστημίου και όχι για εισαγωγικά μαθήματα β/θμιας!
Φτιάξε ένα θέμα εκτός του πίνακα "Λύκειο" να τα πούμε εκεί!

[Κωστας τζιαννης]

Γιατί καλέ δεν δουλεύει; Απλά η ερώτηση είναι "παγίδα" με την έννοια ότι σου ζητάνε τον συγκεκριμένο αλγόριθμο κι αν δεν τον ξέρεις την έκατσες. Δεν νομίζω ότι γίνεται να ανακαλύψεις αλγόριθμο για paper ενώ πας να λύσεις μια άσκηση με προθεσμία 2λεπτου...

https://csacademy.com/submission/1198745/
https://csacademy.com/submission/1203016/
κλπ κλπ, δηλαδή εκτός από τις λάθος λύσεις υπάρχουν και αρκετές σωστές που χρησιμοποιούν τον Floyd.

δουλευει αλλα δεν νομιζω οτι εχει Ο(ν) πολυπλοκοτητα αυτο εννοω.βασικα ακυρο ο(ν) εχει οντως