Βοήθεια/Απορίες στην ΑΕΠΠ - Ασκήσεις

[Chris1993]

Έλα βρε Χmod10. Το ακέραιο υπόλοιπο ενός αριθμού διαιρουμενος με το 10.

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[manolis_98]

Καλημερα ,
Μπορει καποιος να γραψει τους αλγοριθμους ταξινομησης(κατα γραμμη, κατα στηλη, ολικο) ενος δισδιαστατου πινακα ΝχΜ θεσεων
Ευχαριστω

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[Vold]

Γραμμής-Στήλης-Ολικός
Φαντάζομαι είναι σωστοί οι αλγόριθμοι αλλά δεν τους testαρα.
Υπάρχουν και πολύ πιο αποδοτικοί αλλά δεν νομίζω ότι σας απασχολεί η απόδοση.

Spoiler

Για κ απο 1 μεχρι Ν
	Για ι απο 1 μέχρι Μ
	  Για ξ απο 1 μέχρι Μ
	      Αν Π[κ][ξ] < Π[κ][ι] τότε
	           Αντιμετάθεσε Π[κ][ξ], Π[κ][ι]
	      Τέλος_αν
	  Τέλος_επανάληψης
	Τέλος_επανάληψης
Τέλος_επανάληψης

Για κ απο 1 μεχρι Μ
	Για ι απο 1 μέχρι Ν
	  Για ξ απο 1 μέχρι Ν
	      Αν Π[ξ][κ] < Π[ι][κ] τότε
	           Αντιμετάθεσε Π[ξ][κ], Π[ι][κ]
	      Τέλος_αν
	  Τέλος_επανάληψης
	Τέλος_επανάληψης
Τέλος_επανάληψης

Για λ απο 1 μεχρι Ν
	Για κ απο 1 μεχρι Μ
		Για ι απο 1 μέχρι Ν
		  Για ξ απο 1 μέχρι Μ
		      Αν Π[λ][κ] < Π[ι][ξ] τότε
		           Αντιμετάθεσε Π[λ][κ], Π[ι][ξ]
		      Τέλος_αν
		  Τέλος_επανάληψης
		Τέλος_επανάληψης
	Τέλος_επανάληψης
Τέλος_επανάληψης

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[manolis_98]

Vold οπου πχ Π[κ][ξ] τι εννοεις ;(Π[κ,ξ]; )

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[Vold]

Vold οπου πχ Π[κ][ξ] τι εννοεις ;(Π[κ,ξ]; )

Ναι, με συγχωρείς.

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[manolis_98]

Καλησπέρα ,
ο παρακάτω αλγόριθμος "έξυπνης" ταξινόμησης είναι ελλιπής ως προς την περατότητα;

Ι<--2
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
flag<--ΨΕΥΔΗΣ
!ΕΣΤΩ 5 ΣΤΟΙΧΕΙΑ
ΓΙΑ Ξ ΑΠΟ 5 ΜΕΧΡΙ Ι ΜΕ ΒΗΜΑ -1
ΑΝ Π[Ξ-1]<Π[Ξ] ΤΟΤΕ
ΑΝΤ<--Π[Ξ-1]
Π[Ξ-1]<--Π[Ξ]
Π[Ξ]<--ΑΝΤ
flag<--ΑΛΗΘΗΣ
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Ι<--Ι+1
ΜΕΧΡΙΣ_ΟΤΟΥ flag=ΨΕΥΔΗΣ

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[Vold]

Δεν νομίζω ότι είναι ελλιπής. Δεν βλέπω κάτι "λάθος" αυτή τη στιγμή.

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[manolis_98]

Με την προσθήκη ποιας επιπλέον συνθήκης στην Μεχρις_οτου θα εξασφαλίζονταν ο τερματισμός;
Πχ μεχρις_οτου( flag=Ψευδης) ή ( ι>ν)
*ν στοιχεια

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[Chris1993]

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

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

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[manolis_98]

Παιδιά σε περίπτωση που ζητηθεί ταξινόμηση , ποια μέθοδο προτείνετε να ακολουθήσω;(πχ για πινακα με στοιχεια≥20)

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[leobakagian]

Παιδιά σε περίπτωση που ζητηθεί ταξινόμηση , ποια μέθοδο προτείνετε να ακολουθήσω;(πχ για πινακα με στοιχεια≥20)

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

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[tebelis13]

Παιδιά σε περίπτωση που ζητηθεί ταξινόμηση , ποια μέθοδο προτείνετε να ακολουθήσω;(πχ για πινακα με στοιχεια≥20)

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

Εκτός αν σου πει να διαλέξεις την αποδοτικότερη από τις παραπάνω, τότε επιλέγεις την εισαγωγής διότι οι παραπάνω έχουν τάξη .

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[manolis_98]

Ευχαριστώ για τις απαντήσεις.
Η ταξινόμηση με εισαγωγή ποια είναι ;

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[tebelis13]

Ευχαριστώ για τις απαντήσεις.
Η ταξινόμηση με εισαγωγή ποια είναι ;

Ουσιαστικά την περιγράφει στο τετράδιο του μαθητή, κεφάλαιο 3, η ΔΣ3.


https://el.wikipedia.org/wiki/Ταξινόμηση_με_εισαγωγή

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[Vold]

Εκτός αν σου πει να διαλέξεις την αποδοτικότερη από τις παραπάνω, τότε επιλέγεις την εισαγωγής διότι οι παραπάνω έχουν τάξη .

Αν και δεν έχει σημασία μιας και δεν παίζει να ζητηθεί κάτι τέτοιο, και η insertion sort έχει την ίδια χρονική πολυπλοκότητα στην χείριστη περίπτωση, με τις υπόλοιπες..

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[tebelis13]

Αν και δεν έχει σημασία μιας και δεν παίζει να ζητηθεί κάτι τέτοιο, και η insertion sort έχει την ίδια χρονική πολυπλοκότητα στην χείριστη περίπτωση, με τις υπόλοιπες..

Τάξη πολυπλοκότητας του αλγορίθμου θα εννοείς και όχι χρονική.

Κανονικά ναι, αλλά σύμφωνα με το σχολικό βιβλίο ΟΧΙ.

Μπούσουλας του μαθητή είναι το σχολικό βιβλίο το οποίο αναφέρει ότι έχει .

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[Vold]

Τάξη πολυπλοκότητας του αλγορίθμου θα εννοείς και όχι χρονική.

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

Μπούσουλας του μαθητή είναι το σχολικό βιβλίο

Δεν γνωρίζω τι λέει το βιβλίο αλλά αφού το λέει τότε ασφαλώς αυτό ακολουθεί για "τα μάτια του κόσμου" βέβαια

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[tebelis13]

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

Η χρονική πολυπλοκότητα του αλγορίθμου εξαρτάται και από πλήθος άλλων παραγόντων.

Η απόδειξη της τάξης πολυπλοκότητας (big-O complexity) του αλγορίθμου μας καλύπτει.

Δεν γνωρίζω τι λέει το βιβλίο αλλά αφού το λέει τότε ασφαλώς αυτό ακολουθεί για "τα μάτια του κόσμου" βέβαια

Σωστά , αν και βγήκαμε εκτός.

Οτιδήποτε άλλο θες, σε ΠΜ.

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[Chris1993]

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

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

[vassilis498]

πάντως το ότι λέμε να επιλέγεις τα πιο γνωστά γιατί ο διορθωτής μπορεί να ξέρει μόνο bubblesort κι όχι insertion sort πχ και να σου κόψει με ξεπερνά... γράψτε merge sort με αναδρομικό για τη τρολιά έχω περιέργια να δω τι θα δώσουν.

 

Σημείωση: Το μήνυμα αυτό γράφτηκε 8 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.