Αποστολέας Θέμα: Ταξινόμηση  (Αναγνώστηκε 2550 φορές)

Δημήτριος Πηλός

  • Επισκέπτης
Ταξινόμηση
« στις: 27 Μαρ 2003, 09:44:42 πμ »
Να δοθεί αλγόριθμος που θα λαμβάνει τα δεδομένα που ανήκουν σε έναν μονοδιάστατο πίνακα Α[Ι] και θα τοποθετεί σε έναν πίνακα Β[Ι] αλλάζοντας ΜΟΝΟ τα μηδενικά και βάζοντας τα στο τέλος.
(η άσκηση είναι αντιγραμμένη από σχολικό διαγώνισμα)

bugman

  • Επισκέπτης
Re: Ταξινόμηση
« Απάντηση #1 στις: 13 Ιουν 2003, 11:25:12 πμ »
Τρόπος επίλυσης αλγορίθμων!
1. Μιλάμε για μονοδιάστατους πίνακες! Εξ ορισμού λέμε ότι οι αρχικές τιμές των πινάκων Α[] και Β[] είναι τοποθετημένες. Ο Α[] 'εχει μερικές μηδενικές τιμές σε τυχαία θέση και ο Β έχει σε όλες τις θέσεις τιμή μηδέν.
2. Για να περπατάς σε εναν πίνακα Α θες μια μεταβλητή Χ από 1 μεχρι Ι. Έτσι για κάθε Χ θα έχεις και το Α[Χ]
3. Για να τοποθετείς τιμές σε έναν πίνακα Β θες μια μεταβλητή Υ ώστε να βάζεις τιμές στο Β[Υ], με αρχική τιμή το 1
4. Για κάθε Α[Χ]<>0 θα βάζεις στο Β[Υ] την Α[Χ] και αμέσως θα αυξάνεις την τιμή του Υ
5. Στο τέλος θα έχουμε διατρέξει όλον τον πίνακα Α, θα έχουμε μεταφέρει τις τιμές στον Β, και η μεταβλητή Υ θα δείχνει στην πρώτη θέση του Β όπου υπάρχει τιμή μηδέν.
6. Απόδειξη λειτουργίας δια τον οριακών καταστάσεων! Οριακή περίπτωση 1: Να μην υπάρχουν μηδενικά στον Α οπότε το Υ θα είναι Ι+1. Οριακή περίπτωση 2: Να υπάρχουν μόνο μηδενικά στον Α οπότε το Υ θα είναι 1, σε κάθε περίπτωση τα μηδενικά στον Α θα είναι Ι+1-Υ
Γιώργος Καρράς
λάτρης του προγραματισμού
Υ.Γ.
Προγραμματισμός: Η εφαρμογή εντολών με τις ανάλογες παραμέτρους αυτών, σε αυτόματη μηχανή,  φτιαγμένη να ακολουθεί αυτές τις εντολές!
Πρόγραμμα: Το σύνολο των εντολών μετά των παραμέτρων τους για μια συγκεκριμένη λειτουργία, σε ένα συγκεκριμένο αυτόματο μηχάνημα!
Αλγόριθμος: Ο περιγραφή του τρόπου λύσης δοσμένου προβλήματος.
Συμπεράσματα - προτάσεις:
1. Ο αλγόριθμος δεν είναι πρόγραμμα.
2. Ο αλγόριθμος χρειάζεται θεωρητική απόδειξη!
3. Το πρόγραμμα έχει διακριτά βήματα, τις εντολές, οι οποίες μπορούν να χρονομετρηθούν και έτσι μπορούμε να υπολγίσουμε τον χρόνο εκτέλεσης.
4. Ο αλγόριθμος, δεν έχει διακριτά βήματα σε επίπεδο εντολής. Έχει όμως βήματα που περιγράφουν συγκεκριμένη ενέργεια! Απλά η ενέργεια μπορεί να διαφέρει στην υλοποίησή της από μια γλώσσα σε μια άλλη.
5. Σε κάθε περίπτωση (Αλγόριθμου ή Προγράμματος), πρέπει να  γνωρίζουμε τις αρχικές τιμές των μεταβλητών μας.
6. Δεν είναι αναγκαίο να υπάρχει αλγόριθμος (σε χαρτί) για να γραφτεί ένα πρόγραμμα. Μπορεί να γίνει στον αέρα (on the fly).
7. Ένας αλγόριθμος δίνει υποθετικά μια λύση. διότι δεν μπορεί να τρέξει παρά μόνο στο μυαλό του ανθρώπου. Αφού γίνει πρόγραμμα τότε μπορούμε να πούμε ότι ο αλγόριθμος έγινε ουσία δηλαδή πρόγραμμα!
8. Αν σε ενδιαφέρει η ουσία (ο προγραμματισμός, αυτό δηλαδή που δίνει προγράμματα) τότε πρέπει να μάθεις το λεξιλόγιο εντολών και την σύνταξη αυτών για μια συγκεκριμένη μηχανή. Δηλαδή δεν μπορείς να φτιάξεις πρόγραμμα με υποθετικές εντολές, αυτό που θα κάνεις είναι να φτιάξεις πάλι έναν αλγόριθμο με κώδικα αντί με φυσική γλώσσα.
9. Κάποιοι μπερδεύουν το προγραμματιστικό τρικ με τον αλγόριθμο. Π.χ. το να κάνω αλλαγή τιμών δυο μεταβλητών με μια τρίτη είναι ένα τρικ, διότι μπορώ να αλλάξω έμμεσα τις τιμές με αντιγραφή σε προσωρινό χώρο (η τρίτη μεταβλητή που λέγαμε) ή έμμεσα αλλάζοντας τους δείκτες που δείχνουν στις τιμές των μεταβλητών (πάλι θα χρησιμοποιήσω έναν προσωρινό χώρο αλλά για δείκτη όχι για τιμή!). Για τον αλγόριθμο αυτό που μας ενδιαφέρει είναι η αλλαγή τιμών, το πως θα γίνει δεν μας νοιάζει!








« Τελευταία τροποποίηση: 13 Ιουν 2003, 11:46:06 πμ από bugman »