Πρόβλημα #2
Πρόβλημα #2
Έχουμε έναν πίνακα Ν χ Ν όπου κάθε στοιχείο του είναι 0 ή 1. Κάθε γραμμή και κάθε στήλη του έχει ένα κουμπί. Πατώντας το κουμπί μιας γραμμής ή μιας στήλης εναλλάσονται όλα τα στοιχεία της (τα 0 γίνονται 1 και τα 1 γίνονται 0). Θέλουμε πατώντας κάποια κουμπιά να αλλάξουμε τον πίνακα ωστέ τελικά να αποτελείται μόνο από μηδενικά. Βρείτε αλγόριθμο που να διαβάζει έναν πίνακα και 1) να ελέγχει αν υπάρχει λύση, 2) να βρίσκει μια λύση που να αποτελείται από τον ελάχιστο αριθμό πατημάτων. Γράψτε time και memory complexıty.
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Re: Πρόβλημα #2
Μού ρχεται στο μυαλό παραλλαγή ενός γνωστού αλγορίθμου...
- Spoiler: show
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
Re: Πρόβλημα #2
Το μέγιστο Ν εξαρτάται από την πολυπλοκότητα του αλγορίθμου σου...thetrojan01 έγραψε:Ο αλγόριθμος για τι «περιβάλλον προορίζεται» ? Μέγιστο Ν?
![Wink ;)](./images/smilies/icon_e_wink.gif)
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Πρόβλημα #2
Εμένα πάλι γιατί το μόνο που με έρχεται στο μυαλό είναι μια brute force που για Ν > 10 θα αργεί μισό λεπτό
;
![Very Happy :D](./images/smilies/icon_e_biggrin.gif)
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Re: Πρόβλημα #2
Ναι, αλλά πώς ελέγχεις εάν όντως υπάρχει λύση; (χμμμ κάτι μου λέει ότι αυτό είναι το πιο δύσκολο κομμάτι του αλγορίθμου)...Κηπουρίδης έγραψε:Εμένα πάλι γιατί το μόνο που με έρχεται στο μυαλό είναι μια brute force που για Ν > 10 θα αργεί μισό λεπτό;
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
Re: Πρόβλημα #2
@thetrojan01 + Κηπουρίδης: Σκέφτηκα αυτό που σκεφτήκατε, άλλα με την βοήθεια του feedWARd κατέλειξα πως χρειάζεται κάτι πολύ καλύτερο. Για N>5 θα αργεί δραματικά πολύ η bruteforce BFS. Εάν το έπρεπε να το λύσω σε διαγωνιστικό περιβάλλον, θα έκανα αυτήν την χαζή λύση και αν το N είναι μεγαλύτερο από 5 θα θεωρούσα πως δεν υπάρχει δυνατή λύση.
Πιστεύω πως έχω βρεί μια αρχή. Σχεδόν.
edit: @tt1, αν δεν υπάρχει λύση μια απλή bfs απλά θα τελειώσει χωρίς να έχει βρεί λύση. Βέβαια για N>5 δεν θα τελειώσει![Razz :P](./images/smilies/icon_razz.gif)
Πιστεύω πως έχω βρεί μια αρχή. Σχεδόν.
- Spoiler: show
edit: @tt1, αν δεν υπάρχει λύση μια απλή bfs απλά θα τελειώσει χωρίς να έχει βρεί λύση. Βέβαια για N>5 δεν θα τελειώσει
![Razz :P](./images/smilies/icon_razz.gif)
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Re: Πρόβλημα #2
Όντως, μια BFS θα τερματίσει χωρίς να δώσει απάντηση
Αμάν εσείς οι ηλεκτρονικοί και οι πύλες NOT σας!
(πλακίζω, πλιζ δίνε μας προβλήματα feedWARd!)
![Geek :geek:](./images/smilies/icon_e_geek.gif)
Αμάν εσείς οι ηλεκτρονικοί και οι πύλες NOT σας!
(πλακίζω, πλιζ δίνε μας προβλήματα feedWARd!)
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Πρόβλημα #2
Ε , αυτό είναι εύκολο , εγώ το συντομότερο νομίζω δεν μπορώ να βρω ........ θα το δοκιμάσω μεθαύριο και θα σε πω .thetrojan01 έγραψε:Ναι, αλλά πώς ελέγχεις εάν όντως υπάρχει λύση; (χμμμ κάτι μου λέει ότι αυτό είναι το πιο δύσκολο κομμάτι του αλγορίθμου)...Κηπουρίδης έγραψε:Εμένα πάλι γιατί το μόνο που με έρχεται στο μυαλό είναι μια brute force που για Ν > 10 θα αργεί μισό λεπτό;
Ακριβώς εκεί που κοιτιέται ο chris ψάχνομαι κι εγώ αλλά δεν έχω βρει κάτι ενδιαφέρον . Ρε feedWARd , μήπως να μας πεις αν υπάρχει μη - brute force λύση ( τουλάχιστον αν έχεις βρει εσύ κάποια ) , μη παιδευόμαστε άδικα ;
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Re: Πρόβλημα #2
Πάντα υπάρχει brute-force λύση σε κάποιο πρόβλημα. Όντως BFS θέλει και είσαι έτοιμος. Το πρόβλημα αυτό το έχω ξαναδεί νομίζω κάπου.
Re: Πρόβλημα #2
Υπάρχει μη - brute force λύση. Δεν το έβαλα το πρόβλημα για να μου πείτε "brute force"Κηπουρίδης έγραψε: Ρε feedWARd , μήπως να μας πεις αν υπάρχει μη - brute force λύση ( τουλάχιστον αν έχεις βρει εσύ κάποια ) , μη παιδευόμαστε άδικα ;
![Razz :P](./images/smilies/icon_razz.gif)
Ήδη με την παρατήρηση του chris μπορούμε να κατασκευάσουμε μια πολύ καλύτερη brute-force λύση από την BFS-brute force.
Btw, αν θυμάμαι καλά με τον chris βρήκαμε οτί το BFS είναι πολυπλοκότητας Ο(N * 2^(N^2) ) και ίσως και χειρότερο (ανάλογα με το πως θα κωδικοποιήσεις το state σου).
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Re: Πρόβλημα #2
BFS με ευριστικούς σκεπτόμουν.
Μα και πάλι, δε μου έρχεται κανένας ευριστικός στο μυαλό.
Θα το παλέψω μόλις βρω λίγη ησυχία στο σπίτι.
Μα και πάλι, δε μου έρχεται κανένας ευριστικός στο μυαλό.
![Surprised :o](./images/smilies/icon_e_surprised.gif)
Θα το παλέψω μόλις βρω λίγη ησυχία στο σπίτι.
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
- kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: Πρόβλημα #2
Νομίζω γίνεται σε
χρόνο Ν^2
και χώρο Ν^2
(Όχι ακριβώς, αλλά το Ν^2 είναι το σημαντικότερο)
ΕΝΤΙΤ: Έτοιμο!
Θεωρητικά δουλεύει μέχρι Ν=20, μετά πρέπει να αλλάξεις τα μεγέθη των πινάκων.
Μπορεί κάποιος να μου εξηγήσει γιατί δεν παίρνει αρχεία με κατάληξη BAS;
χρόνο Ν^2
και χώρο Ν^2
(Όχι ακριβώς, αλλά το Ν^2 είναι το σημαντικότερο)
ΕΝΤΙΤ: Έτοιμο!
![Very Happy :D](./images/smilies/icon_e_biggrin.gif)
Θεωρητικά δουλεύει μέχρι Ν=20, μετά πρέπει να αλλάξεις τα μεγέθη των πινάκων.
Μπορεί κάποιος να μου εξηγήσει γιατί δεν παίρνει αρχεία με κατάληξη BAS;
- Συνημμένα
-
- PIXELS.TXT
- Αεροτομή!!!
- (2.96 KiB) Μεταφορτώθηκε 590 φορές
Τελευταία επεξεργασία από το μέλος kernelpanic την Δευ Αύγ 02, 2010 7:37 pm, έχει επεξεργασθεί 2 φορές συνολικά.
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
Re: Πρόβλημα #2
ΟΟΟΟΟΟΟΟΟΟΟΟΧΧΧΧΧΧΧΧΧΧΧΧΧΧΧΧΧΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙ BASIC!kernelpanic έγραψε:Νομίζω γίνεται σε
χρόνο Ν^2
και χώρο Ν^2
(Όχι ακριβώς, αλλά το Ν^2 είναι το σημαντικότερο)
Τώρα το υλοποιώ σε Basic...Θα κάνω έντιτ μόλις τελειώσω.
Αστειεύομαι
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
- kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: Πρόβλημα #2
QuickBasic, για να είμαι πιο ακριβής.
Σοβαρά τώρα, τη προτιμώ όταν θέλω να κάνω διάφορα πειράματα, ειδικά όταν αφορούν γραφικά. Κυρίως για την ταχύτητα ανάπτυξης, όμως, όταν θέλω να φτιάξω κάτι απλό.
Και το πιο σημαντικό: γιατί ήταν, είναι και θα μείνει η μοναδική μου αγάπη.![Laughing :lol:](./images/smilies/icon_lol.gif)
![Twisted Evil :twisted:](./images/smilies/icon_twisted.gif)
Σοβαρά τώρα, τη προτιμώ όταν θέλω να κάνω διάφορα πειράματα, ειδικά όταν αφορούν γραφικά. Κυρίως για την ταχύτητα ανάπτυξης, όμως, όταν θέλω να φτιάξω κάτι απλό.
Και το πιο σημαντικό: γιατί ήταν, είναι και θα μείνει η μοναδική μου αγάπη.
![Laughing :lol:](./images/smilies/icon_lol.gif)
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Re: Πρόβλημα #2
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
- kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: Πρόβλημα #2
Βασικά έκανα λάθος πριν:
Γίνεται σε χρόνο Ν^2 και χώρο Ν, με λίγες αλλαγές.
Ποστάρω σε λίγο.![Embarrassed :oops:](./images/smilies/icon_redface.gif)
Γίνεται σε χρόνο Ν^2 και χώρο Ν, με λίγες αλλαγές.
Ποστάρω σε λίγο.
![Embarrassed :oops:](./images/smilies/icon_redface.gif)
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Πρόβλημα #2
Τελικά, πῶς;;;
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Re: Πρόβλημα #2
- Spoiler: show
Memory: O(N) (το προφανές είναι O(N2) αλλα μπορεί να γίνει O(N), το αφήνω σαν άσκηση)
Τελευταία επεξεργασία από το μέλος thetrojan01 την Τρί Ιαν 04, 2011 3:03 pm, έχει επεξεργασθεί 2 φορές συνολικά.
Λόγος: Ο(Ν) -> Ο(Ν^2)
Λόγος: Ο(Ν) -> Ο(Ν^2)
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Πρόβλημα #2
Ἰδιοφυές! Δὲν θὰ τὸ ἔβγαζα οὔτε τοῦ χρόνου. Καὶ πάλι μπράβο:D.
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
- kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: Πρόβλημα #2
To «σε λίγο» είναι σχετικό. Όπως τα τέρμινα ![Embarrassed :oops:](./images/smilies/icon_redface.gif)
![Embarrassed :oops:](./images/smilies/icon_redface.gif)
- Συνημμένα
-
- PIXELS2.txt
- Ένα γρήγορο patch, δε ξέρω αν δουλεύει ακριβώς όπως το παλιό pixels.txt
- (2.94 KiB) Μεταφορτώθηκε 590 φορές
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.