Aσκήσεις σε στοίβα και ουρά σε ΓΛΩΣΣΑ

Ξεκίνησε από Πέτρος Κ., 22 Ιουν 2015, 08:53:23 ΜΜ

« προηγούμενο - επόμενο »

bugman

Ευτυχώς υπάρχουν κάποια σχολεία που φτιάχνουν και καμιά ρομποτική εφαρμογή, κάτι να δείξουν ότι δεν πάνε χαμένες οι γνώσεις, ή δεν γίνονται για να πιστεύει κάποιος ότι είναι "ξερόλας"...ή το κέντρο του κόσμου (που τις βρήκε αυτές τις εκφράσεις ο ether...μου θυμίζει λύκειο...)

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

Παράθεση από: bugman στις 05 Αυγ 2015, 05:04:13 ΜΜ
- Δεν διδάσκω ΑΕΠΠ (ευτυχώς).

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

bugman

Σωστά, η συζήτηση πρέπει να περιστρέφεται γύρω από τις ασκήσεις σε στοίβα και ουρά. Αλλά νομίζω ότι πάνω σε αυτά συζητώ και μάλιστα ως προς την χρησιμότητα της εξάσκησης πάνω σε αυτές. Νομίζω ότι είναι το Στέκι των Πληροφορικών και όχι το http://www.sch.gr/. Σε καμία περίπτωση δεν θα έγραφα στο τελευταίο.
Οπωσδήποτε το να έχει κάποιος την άποψή του για το θέμα δεν αλλάζει το θέμα. Δεν αλλάζει ότι ο μαθητής θα γράψει εξετάσεις και ότι θα πρέπει να μάθει δέκα ασκήσεις. Για την εξεταστική διαδικασία ασφαλώς λοιπόν και έχει νόημα η εμπέδωση ασκήσεων. Εξέφρασα το παράπονό μου για την ύλη αυτή η οποία εμφανίζεται αναγκαία όταν δεν υπάρχει διαφαινόμενη αναγκαιότητα να έχει η γλώσσα στοιχεία εισόδου εξόδου από και προς την οθόνη και προς αρχεία, να μην έχει γραφικά και άλλα ωραία πράγματα, που θα δίνουν "δουλειά" και όχι τεστ ευφυίας...(πιστεύω ότι το θέμα των ουρών είναι πολύ προχωρημένο για το λύκειο).
Θέλω να ευχαριστήσω για την υπομονή σας. Και όποιος ενδιαφέρεται για την Μ2000..διαθέτω τον κώδικά της ανοιχτό εδώ:
https://www.dropbox.com/sh/xq8j8t7kbj37ms0/AABKIv4d9qXTLbEFPvfjPLb0a?dl=0
για Vb6 Enterprise Edition.
Εδώ είναι ένα παράδειγμα με κλάσεις  (Η διάβασε διαβάζει πάντα από σωρό...όπως τον εννοώ εγώ..Stack, με στοιχεία διάφορα, πίνακες, ομάδες - έτσι λέγονται τα αντικείμενα στη Μ2000-, με πέρασμα με τιμή αλλά και με αναφορά. Το πώς γίνεται στο σωρό να περνάει κανείς και με τιμή και με αναφορά...θέλει διάβασμα ο κώδικας)
Φόρμα 40,25 \\40Χ25
Κλάση Αλφα {
      Χ=10, Υ, Α$="Όνομα"
      Τμήμα Αλφα {
            Αν ταύτιση("NN") Τότε Διάβασε .Χ , .Υ
      }
      Τμήμα Νέο.Όνομα {
            Διάβασε .Α$
      }
      Συνάρτηση Νέο.Όνομα$ {
            =.Α$
      }
      Συνάρτηση Ένα { = .Χ**2+.Υ}
}
Κάπα=Αλφα()   \\ κατασκευάζουμε το αντικείμενο χωρίς παραμέτρους
Κάπα.Υ=20
Τύπωσε Κάπα.Ένα()
Βήτα=Αλφα(10,20)  \\ εδώ με παραμέτρους
Τύπωσε Βήτα.Ενα()
Για Βήτα {
      Τύπωσε .Χ, .Υ, .Α$, .Ενα()
}
Λάμδα=Κάπα  \\ αντιγραφή αντικειμένου
Για Λάμδα {
      .Χ-=5
      .Νέο.Όνομα "Λάμδα"
      Τύπωσε .Νέο.Όνομα$(), .Ένα()
}

alkisg

bugman, για να διαφημίζεις τη γλώσσα σου, νομίζω θα ήταν καλύτερα να μην συμμετέχεις στους πίνακες συζητήσεων για τα μαθήματα της δευτεροβάθμιας, αφού δεν εμπλέκεσαι στη διδακτική διαδικασία, και καταλήγεις να κάνεις παραπληροφόρηση, να χαλάς τις συζητήσεις των άμεσα ενδιαφερόμενων κ.α.
Νομίζω ότι θα ήταν καλύτερα να συνεχίσεις στο θέμα που ήδη άνοιξες: https://alkisg.mysch.gr/steki/index.php?topic=6318.0

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

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

Ως επαγγελματίας φωτογράφος θα ήσουν πολύ πιο χρήσιμος σε ένα φόρουμ φωτογράφων, όπου θα έδινες τις γνώσεις σου στους ερασιτέχνες φωτογράφους...

bugman


papaluk


Οι κώδικες για εξαγωγή και εισαγωγή σε ουρά όπως  τους είχα "φανταστεί" με βάση περιγραφή σχολικού και χωρίς να χρησιμοποιώ δυναμικές δομές αλλά πίνακα με Ν θέσεις

Αλγόριθμος Εξαγωγή_από_Ουρά
Δεδομένα // rear, front, queue, N //
Αν rear > front τότε
  Itemout ← queue[front]
  front ← front+1
  done ← Αληθής
αλλιώς_αν rear=front και rear ≠ 0 τότε
  Itemout← queue[front]
  front ← 0
  rear ← 0
  done ← Αληθής
αλλιώς
  done ← Ψευδής
Τέλος_αν
Αποτελέσματα // itemout, rear, front, done //
Τέλος Εξαγωγή_από_Ουρά   

Αλγόριθμος Εισαγωγή_σε_Ουρά
Δεδομένα // rear, front, queue, N, itemin //
Αν rear < Ν  τότε
  Αν rear ≠ 0 τότε
    rear← rear+1
    queue[rear]← itemin
    done ← Αληθής
  αλλιώς ! rear=front=0
    rear← rear+1
    front ← front+1
    queue[rear]← itemin
    done ← Αληθής
  τέλος_Αν
αλλιώς
  done ← Ψευδής
Τέλος_αν
Αποτελέσματα // rear, front, done //
Τέλος Εισαγωγή_σε_Ουρά

bugman

Θα μπορούσες να εμπλουτίσεις την δομή σου με δυο αλγόριθμους:
καθαρή_ουρά
γεμάτη_ουρά  (συνάρτηση).
Κατά την άποψή μου δεν εισάγουμε κάτι με πιθανότητα να πάρουμε λάθος, αλλά  πρώτα κοιτάμε αν μπορούμε να εισάγουμε και μετά κάνουμε την ενέργεια. Εντούτοις θα μπορούσε να βγει λάθος αλλά αυτό το λάθος δεν θα είχε να κάνει με την λογική της δομής αλλά με την αδυναμία εγγραφής..δηλαδή την αδυναμία του υλικού ( δεν μπορεί να συμβεί στη ΓΛΩΣΣΑ αλλά θα μπορούσε να συμβεί με μια άλλη γλώσσα που θα είχε τον πίνακα σε αρχείο, οπότε πολλά θα μπορούσαν να συμβούν).
Με απλά λόγια στον "Αλγόριθμος Εισαγωγή_σε_Ουρά" ο έλεγχος των rear and front για την περίπτωση της υπερχείλισης θα έπρεπε να γίνει πριν.
1) Υπερχείλιση; Όχι ->Εισαγωγή
2) Άδειο; Όχι -> Εξαγωγή
Χρησιμοποιείς την front για να εισάγεις και την rear για να εξάγεις. Θα μπορούσε η rear να είναι αριθμητικά μεγαλύτερη από την front.
π.χ. σε πίνακα δέκα θέσεων (1 εως 10) η front δείχνει την 3 θέση (όπου θα μπει ένα νέο στοιχείο), και η rear θα πρέπει λογικά να δείχνει από εκεί που θα πάρουμε και όχι από την προηγούμενη θέση (όπως δείχνεις στο παράδειγμά σου) αλλά ας το δεχτούμε έτσι, άρα αν έχουμε rear 7 θα πάρουμε από το 8. Πόσα στοιχεία έχουμε; Ας το  δούμε από το μάζεμα, έχουμε το ( 8 ),(9),(10),(1),(2) άρα πέντε στοιχεία. Κάθε φορά η ουρά μπορεί να πάρει το πολύ δέκα στοιχεία, για οποιοδήποτε rear...Να γιατί δεν μπορούμε να σκεφτόμαστε το rear ως το "ήδη εξαγόμενο" και να υπολογίζουμε να πάρουμε από το rear+1.
Ο αλγόριθμος papaluk όπως γράφτηκε δεν εξασφαλίζει ότι για οποιοδήποτε rear μπορώ να βάλω N στοιχεία όσο το μέγεθος του πίνακα. (Αυτή είναι η ουσία μιας ουράς, να μπορεί να πάρει σε όλο το άνοιγμα στοιχεία, και να μπαίνουν και να βγαίνουν χωρίς να μετακινούμε τα στοιχεία που δεν σχετίζονται με την εισαγωγή ή εξαγωγή).

petrosp13

Θα πέσει πολύ κλάμα φέτος με ασκήσεις ουράς, αλγορίθμους ταξινόμησης και πολυπλοκότητα..
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

nikolasmer

Σκέφτηκα μια εκφώνηση για ένα φανταστικό παιχνίδι με τράπουλα. Δεν ξέρω αν ευσταθεί ή όχι. (Δεν είμαι καλός σε αυτό το κομμάτι των μαθηματικών). Θα ήθελα μια άποψη για το σενάριο και μια άποψη για το αν ακουμπάει το θέμα της ΣΤΟΙΒΑΣ και θα ήταν προτιμότερο να τη λύσει κάποιος με τη χρήση των λειτουργιών της και όψι με τη χρήση των λειτουργιών των πινάκων. Βέβαια στα πλαίσια του μαθήματος θεωρούμε πως η Στοίβα και η Ουρά υλοποιούνται με πίνακες... Anyway.... η εκφώνηση δεν είναι και τόσο καλή και επιδέχεται πολλές διορθώσεις. Ελπίζω να καταλάβει κάποιος πως παίζεται το παιχνίδι...Πρόγραμμα δεν έχω κάνει ακόμα... :P και δεν την έχω λύσει:

Διαθέτουμε μια τράπουλα με φύλα από το 1 μέχρι το 10 χωρίς βαλέδες , ντάμες και ρηγάδες και με αυτά τα φύλλα (40 στον αριθμό) παίζουμε το παιχνίδι «Stupidity» το οποίο πάει ως εξής. Ρίχνω κάτω χαρτιά μέχρι το άθροισμα του πιο πάνω χαρτιού ή και του αμέσως προηγούμενου κλπ. συμπληρώσει άθροισμα ακριβώς 10. Όταν αυτό συμβεί τότε να αφαιρούνται αυτά τα χαρτιά (που το άθροισμά τους μας κάνει 10) από τη ΣΤΟΙΒΑ φύλλων. Όταν τα φύλλα της Τράπουλας τελειώσουν, να «γυρίζουμε» τη Στοίβα φύλλων ανάποδα και να συνεχίζουμε κατά τον ίδιο τρόπο πάλι ρίχνοντας φύλλα. Στόχος του παιχνιδιού είναι να φύγουν όλα τα φύλλα της τράπουλας, μέχρι και το τελευταίο, σε 10άδες. Να υλοποιηθεί το παραπάνω παιχνίδι με πρόγραμμα σε ΓΛΩΣΣΑ ως εξής:
1.   Θα διαβάζει από το πληκτρολόγιο αριθμούς, οι οποίοι αντιστοιχούν σε φύλλα και θα τους ωθεί σε μια Στοίβα μέχρι να «εξαντληθούν» όλα τα φύλλα της τράπουλας.
2.   Κάθε φορά που το άθροισμα των κορυφαίων φύλλων στη Στοίβα, φτάνει ακριβώς 10, τότε να Απωθεί αυτά τα Φύλλα (ή αυτό το φύλλο) από τη Στοίβα και να συνεχίζει με το διάβασμα των επόμενων φύλλων.
3.   Όταν τελειώσουν τα φύλλα της τράπουλας το πρόγραμμα να αποφαίνεται αν επιτυγχάνεται ο στόχος του παιχνιδιού και να εμφανίζει κατάλληλο μήνυμα σε κάθε περίπτωση. Για το σκοπό αυτό θα πρέπει κάθε φορά που τελειώνουν τα φύλλα, να ξανά εισάγονται οι αριθμοί που έμειναν – φύλλα – σε στοίβα, με την αντίστροφη σειρά. Αν μετά από ένα γύρο (ρίχνουμε όλα τα φύλλα) δεν παρουσιαστεί 10άδα τότε το παιχνίδι «κλείδωσε» και δεν επιτυγχάνεται ο στόχος. Διαφορετικά συνεχίζουμε με επόμενο γύρο.
4.   Στην περίπτωση που ο στόχος επιτυγχάνεται το πρόγραμμα να εμφανίζει τον αριθμό των ολοκληρωμένων 10άδων που δημιουργήθηκαν καθώς και πόσες φορές «ρίχτηκαν» τα φύλλα της τράπουλας από την αρχή.
Μερεντίτης Νικόλαος
Πληροφορικός

nikolasmer

(1)Έστω ότι έχουμε μια ακολουθία από Λειτουργίες Ώθησης και Απώθησης στοιχείων σε και από μια Στοίβα.
Η λειτουργία της Ώθησης , ωθεί τα ψηφία 0 - 9 σε σειρά (αύξουσα ή φθίνουσα) στη Στοίβα. Η Απώθηση , απωθεί την τιμή που βρίσκεται στην κορυφή της στοίβας εμφανίζοντάς τη παράλληλα στην οθόνη. Ποια από τις παρακάτω ακολουθίες αριθμών που εμφανίζονται στην οθόνη, ΔΕΝ μπορεί να συμβεί με την παραπάνω διαδικασία;
(a)  4 3 2 1 0 9 8 7 6 5
(b)  4 6 8 7 5 3 2 9 0 1
(c)  2 5 6 7 4 8 9 3 1 0
(d)  4 3 2 1 0 5 6 7 8 9

(2) Δείξτε πώς μπορεί μια ουρά να υλοποιηθεί με τη βοήθεια 2 Στοιβών
(3) Δείξτε πώς μπορεί μια Στοίβα να υλοποιηθεί με τη βοήθεια 2 Ουρών

Για τις (2) και (3) δεν έχω ιδέα πως μπορούν να υλοποιηθούν! :P

Πηγή: http://www.cs.princeton.edu/courses/archive/spring2001/cs126/exercises/adt.html
Μερεντίτης Νικόλαος
Πληροφορικός

Diotima

Από την πρώτη φορά που διάβασα την άσκηση που σκέφτηκες με την τράπουλα μου άρεσε πάρα πολύ σαν εφαρμογή των λειτουργιών της στοίβας αλλά και σαν σενάριο. Επίσης η τράπουλα δίνει μια πραγματική απεικόνιση της στοίβας, πράγμα που επίσης μου αρέσει πολύ. Σκέφτηκα μάλιστα την υλοποίηση με 2 στοίβες, ώστε όταν υπολογίζεται το άθροισμα των πάνω χαρτιών της πρώτης στοίβας και ξεπερνά το 10, να ωθούνται ταυτόχρονα κατά σειρά στη δεύτερη στοίβα, οπότε στον επόμενο γύρο η διαδικασία θα γίνεται σε αυτή, αφού τα χαρτιά θα απωθούνται με αντίστροφη σειρά (κανόνας 3). Και η διαδικασία θα συνεχίζεται εναλλάξ στις δύο στοίβες. Υποθέτω βέβαια ότι κατάλαβα τον κανόνα 2, δηλ. όταν το άθροισμα των πάνω φύλλων είναι ίσο με 10, απωθούνται από τη στοίβα, ενώ όταν βγάζουμε κατά σειρά τα χαρτιά και το άθροισμα τους ξεπεράσει το 10, ξεκινάμε το άθροισμα απ' την αρχή και τα χαρτιά αυτά μένουν στην τράπουλα.

Κάποια στιγμή, όταν είχα χρόνο, σκέφτηκα ότι πρέπει να διερευνήσω από μαθηματική άποψη τις πιθανές λύσεις ώστε να δω αν έχει νόημα το παιχνίδι, πριν προχωρήσω στην υλοποίηση. Υπέθεσα λοιπόν ότι θέλουμε να στήσουμε την τράπουλα ώστε να βγουν όλα τα φύλλα με αθροίσματα του 10.
Τα 10άρια δεν τα υπολογίζω αφού βγαίνουν μόνα τους.
Κατ' αρχήν τα 9άρια μπορούν να βγουν μόνο αν ακολουθεί ή προηγείται άσσος. Άρα θα πρέπει να έχουμε 4 ζεύγη (9,1) ή (1,9) για να φύγουν τα 9άρια.
Τα 8άρια για να φύγουν θα πρέπει να έχουμε άθροισμα 8+2 ή 8+1+1. Αλλά αφού τα 1 τα θέλουμε για τα 9άρια θα πρέπει τα 8άρια να βγουν μόνο με το συνδυασμό 8+2.
Πάνε και τα τέσσερα 2άρια. Όμοια, τα 7άρια που βγαίνουν με αθροίσματα 7+3 ή 7+2+1 ή 7+1+1+1 πρέπει να βγουν μόνο με άθροισμα 7+3 αφού χρειαζόμαστε τα τέσσερα 2άρια και τους τέσσερις άσσους για να βγάλουμε τα 8άρια και τα 9άρια. Και πάει λέγοντας, τα 6άρια πρέπει να βγουν με 4 και τα 5άρια με 5.
Συμπέρασμα:
Για να επιτευχθεί ο στόχος του παιχνιδιού, η λύση του, πρέπει να έχουμε τα ζεύγη
(9,1), (8,2), (7,3), (6,4) 4 φορές το καθένα (ή αντίστροφα οι αριθμοί) και δύο ζέύγη (5,5) με οποιαδήποτε δυνατή διάταξη τους και τα 10άρια ανάμεσα στα ζεύγη ή στην αρχή ή στο τέλος (αρκετές λύσεις-διατάξεις).
Οπότε τα φύλλα θα βγουν από τον πρώτο γύρο και δε χρειάζεται να γίνει δεύτερος γύρος αν ο στόχος είναι να βγουν όλα τα φύλλα. Αν μείνουν φύλλα από τον πρώτο γύρο ξέρουμε ότι το παιχνίδι κλειδώνει, δεν πρόκειται να βγουν όλα. Όπως επίσης ξέρουμε ότι αν σχηματιστεί άθροισμα του 10 με τρία ή περισσότερα φύλλα το παιχνίδι κλειδώνει, δεν επιτυγχάνεται ο στόχος. Όλα κρίνονται στον πρώτο γύρο.
Αυτό είναι απογοητευτικό, αλλά επειδή το σενάριο και η αλγοριθμική υλοποίηση είναι ωραία για στοίβα σκέφτομαι μήπως κάναμε κάποιες αλλαγές ή να αλλάζαμε το στόχο ώστε να έχουν νόημα οι συνεχόμενοι γύροι.

Ωραίο το link με τις ασκήσεις, ευχαριστώ!

apoldem

Μια ουρά μπορεί εύκολα να υλοποιηθεί με 2 στοίβες και το αντίστροφο.

Η ουρά κρατά τα στοιχεία με την σειρά εισαγωγής ενώ η στοίβα με την αντίστροφη σειρά εισαγωγής.

Οπότε, αν μια ουρά την αδειάσουμε σε μια άλλη ουρά ("αδειάζω" σημαίνει εξάγω ένα-ένα τα στοιχεία της μιας δομής και τα εισάγω στην άλλη δομή), τότε η δεύτερη ουρά θα γίνει στοίβα! Το αντίστροφο ισχύει αν έχω δύο στοίβες και αδειάσω την μία στοίβα στην άλλη στοίβα. Η δεύτερη στοίβα θα έχει την ίδια σειρά που θα είχε η αντίστοιχη ουρά.

Π.χ. για να κάνω μια ουρά χρησιμοποιώντας δύο στοίβες (έστω στοίβα Α και Β) τότε:

1) ορίζω ως βασική δομή (δλδ την φανταστική ουρά) την στοίβα Α.
2) κάθε φορά που εισάγεται ένα νέο στοιχείο:
        αδειάζω την στοίβα Α στην Β
        εισάγω το στοιχείο στην Α
        αδειάζω πίσω την Β στην Α
3) κάθε φορά που εξάγω στοιχείο από την δομή (την φανταστική ουρά)
        δίνω το πάνω στοιχείο της στοίβας Α

apoldem

Το παιχνίδι με την τράπουλα είναι πολύ ωραίο! Για να λύνεται πάντα θα πρέπει να επεκταθεί το άθροισμα σε όλα τα πολλαπλάσια του 10 και όχι μόνο στο 10 ακριβώς. Δηλαδή ο παίκτης να παίρνει όλα τα φύλλα που έχουν άθροισμα 10, 20, 30... μέχρι την χειρότερη περίπτωση 140 (χωρίς τα δεκάρια).

P.Tsiotakis

Ετοίμασα ένα φυλλάδιο για τις Δομές Δεδομένων Στοίβα και Ουρά

καθώς και σχετικό βίντεο περιγραφής τους

manpoul

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