Ερώτηση πάνω σε Πίνακα

Ξεκίνησε από pmouz, 16 Μαΐου 2010, 12:47:10 ΜΜ

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

pmouz

Θέμα 3ο (Εξετάσεις 2001)
Δίνεται πίνακας Π δύο διαστάσεων, που τα στοιχεία του είναι ακέραιοι αριθμοί με Ν γραμμές και Μ στήλες. Να αναπτύξετε αλγόριθμο που να υπολογίζει το ελάχιστο στοιχείο του πίνακα.

Ερώτηση: Πως θα μπορούσαμε να γράψουμε το παραπάνω θέμα σε Πρόγραμμα και όχι σε αλγόριθμο;

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

ΠΡΟΓΡΑΜΜΑ Θέμα3
ΣΤΑΘΕΡΕΣ
  Ν = 3
  M = 3
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: i, j, Π[Ν, M], min
ΑΡΧΗ
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ M
      ΔΙΑΒΑΣΕ Π[i, j] 
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  
  min <- Π[1, 1] 
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ M
      ΑΝ min > Π[i, j] ΤΟΤΕ
        min <- Π[i, j] 
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ min
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ Θέμα3


Ποιά είναι η γνώμη σας;

sstergou

Οι τιμές των Μ, Ν πρέπει να είναι γνωστές κατά την στιγμή της μεταγλώττισης. Ο πίνακας είναι στατική δομή και ο μεταγλωττιστής πρέπει να ξέρει πόση μνήμη πρέπει να δεσμεύσει. Για αυτό το λόγο δεν γίνεται τα Μ, Ν να διαβαστούν.

Προσεγγιστική λύση είναι να γίνει αυτό που ήδη έκανες στην λύση σου, δηλαδή να δηλώσεις τα Μ, Ν σαν σταθερές.

pmouz

Αυτό είχα και έγω εντύπωση, αλλά ήθελα να πάρω μια δεύτερη γνώμη. Είναι ένα από τα μειονεκτήματα της ΓΛΩΣΣΑΣ.

meteo_xampos

Βασικά είναι ένα από τα μειονεκτήματα του μαθήματος... Η ΓΛΩΣΣΑ απλώς υλοποιεί το διδακτικό πακέτο...

pmouz

Σωστός. Αλλά αλγοριθμικά με βάση το βιβλίο το πρόβλημα λύνεται. Στη ΓΛΩΣΣΑ δεν λύνεται.

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

Παράθεση από: meteo_xampos στις 16 Μαΐου 2010, 01:06:28 ΜΜ
Βασικά είναι ένα από τα μειονεκτήματα του μαθήματος... Η ΓΛΩΣΣΑ απλώς υλοποιεί το διδακτικό πακέτο...

Γιατί θεωρούμε ότι είναι μειονέκτημα αυτό; Κατ' επέκταση μειονέκτημα θα θεωρούσαμε και ότι η υπολογιστική μηχανή έχει πεπερασμένη μνήμη, αλλά αφού αυτή είναι η πραγματικότητα τότε πρέπει να λειτουργήσουμε μέσα σε αυτήν...

pgrontas

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

Σχετικά με το αν είναι μειονέκτημα ή όχι, θεωρώ ότι η απάντηση είναι σχετική. Ενα σχετικό παράδειγμα έχουμε στους ακέραιους. Παλιότερα οι ακέραιοι ήταν μέχρι το 32767 (ή 8 δεν θυμάμαι). Τώρα έχουμε φτάσει σε ακέραιους που είναι όσο μεγάλοι θέλουμε (BigInteger). Αυτό σε κάποιες περιπτώσεις βοηθάει σε κάποιες όχι. Στην διδασκαλία, η μια γνώμη λέει ότι οι περιορισμοί οδηγούν σε πειθαρχία και κατά συνέπεια σε καλύτερους προγραμματιστές, ενώ άλλη ότι σε αρχικό στάδιο καλύτερα να μην έχουμε τόσους περιορισμούς. Το ίδιο ισχύει και για τους στατικούς πίνακες, νομίζω.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

evry

Το μειονέκτημα αυτής της στατικότητας κατά τη γνώμη μου έχει να κάνει με τον τύπο του πίνακα. Φτιάχνεις για παράδειγμα ένα υποπρόγραμμα για την εύρεση μεγίστου σε πίνακα 100 στοιχείων και θέλεις να βρεις το μέγιστο σε έναν πίνακα 99 στοιχείων. Θα πρέπει να κάνεις άλλο υποπρόγραμμα!!!!
Το πρόβλημα είναι ότι το πλήθος των στοιχείων ενός πίνακα καθορίζει τον τύπο του.
Δηλαδή δεν υπάρχει πίνακας ακέραιων αριθμών αλλά πίνακας 100 ακέραιων αριθμών. Αυτό θεωρώ ότι είναι το μεγάλο πρόβλημα της στατικότητας γιατί έτσι καταργεί αρκετά από  τα πλεονεκτήματα του τμηματικού προγραμματισμού

Παράθεση από: Νίκος Αδαμόπουλος στις 16 Μαΐου 2010, 01:29:15 ΜΜ
Γιατί θεωρούμε ότι είναι μειονέκτημα αυτό;
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

pmouz

Παναγιώτη συμφωνώ και για το 2ο μπάλωμα. Το χρησιμοποιούσα στη σχολή όταν μαθαίναμε προγραμματισμό και κάναμε pascal.
Επίσης συμφωνώ και με τον ευριπίδη για τη στατικότητα των πινάκων. Είναι αρκετά δεσμευτικό όταν παίζεις με πίνακες.
Στον αλγόριθμο δεν έχουμε πρόβλημα. Λέμε //Δεδομένα Ν, Μ, Πίνακα// και μετά χρησιμοποιούμε κατευθείαν τον Πίνακα[Ν,Μ].

Καρκαμάνης Γεώργιος

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

evry

Αυτό που έχει πραγματικά ενδιαφέρον είναι τι θα γινόταν αν κάποιος το έλυνε με ΓΛΩΣΣΑ και όριζε τα Ν, Μ σταθερές ενώ ζητάει ψευδογλώσσα, θα ήταν σωστός?
Διότι κάποιοι καθηγητές κάνουν μόνο ΓΛΩΣΣΑ για να βγάλουν άνετα την ύλη με το σκεπτικό ότι οποιοσδήποτε αλγόριθμος ζητηθεί μπορεί να δοθεί ως πρόγραμμα.
Σε αυτή την περίπτωση ισχύει αυτό? Τι λέτε?
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

sstergou

Οπωσδήποτε σωστός.

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

evry

Ναι, οκ δεν εννοώ να κόψεις μονάδες αλλά επιστημονικά είναι σωστός?
Για παράδειγμα αν δώσω σε ψευδογλώσσα τον αλγόριθμο εύρεσης μεγίστου σε έναν πίνακα δεν φαίνεται ο πίνακας τι τύπου στοιχεία έχει. Οπότε ο αλγόριθμός μου είναι ο ίδιος και για ακέραιους και για πραγματικούς και για χαρακτήρες. Αν όμως δώσω πρόγραμμα θα πρέπει να επιλέξω ένα από αυτά
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

sstergou

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

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

pmouz

Παράθεση από: Καρκαμάνης Γεώργιος στις 16 Μαΐου 2010, 10:12:34 ΜΜ
Έτσι όπως διατυπωμένη η συγκεκριμένη εκφώνηση, δεν πρέπει να επιχειρήσουμε να την λύσουμε με ΓΛΩΣΣΑ για τους λόγους που αναφέρατε παραπάνω.
και δεν βλέπω τον λόγο για να γίνει αυτό.

Το ξέρω ότι η άσκηση ζητάει να αναπτύξουμε αλγόριθμο. Εγώ απλά αρχικά ρώτησα τι γίνεται στην περίπτωση που προσπαθήσουμε να το κάνουμε σε ΓΛΩΣΣΑ. Αλγοριθμικά όπως προείπα είναι πολυ εύκολο να λυθεί. Στη ΓΛΩΣΣΑ όμως υπάρχουν περιορισμοί, λόγω του ότι οι διαστάσεις του πίνακα πρέπει να οριστούν στο τμήμα δηλώσεων, ενώ εμείς θέλουμε να τις δίνει ο χρήστης, όταν εκτελεί το πρόγραμμα.
Μια (λύση) είναι αυτή που είπε ο pgrontas, να ορίσουμε τις διαστάσεις του πίνακα με το μέγιστο δυνατό πλήθος στοιχείων και στη συνέχεια μέσα στο πρόγραμμα να χρησιμοποιούμε όσα στοιχεία θέλουμε, αλλά και πάλι ουσιαστικά το πρόβλημα δεν έχει λυθεί, επειδή σπαταλάμε επιπλέον μνήμη.

Ζήτημα 2ο
Το Υπουργείο λέει ότι οι ασκήσεις μπορούν να λυθούν είτε σε Ψευδογλώσσα, είτε σε ΓΛΩΣΣΑ. Αυτό ισχύει στην περίπτωση που σου λέει να κατασκευαστεί αλγόριθμος ή να κατασκευαστεί πρόγραμμα;
Κάποιος που το κάνει με τον άλλο τρόπο, θα μειωθεί ο βαθμός του, επειδή δεν ακολούθησε πιστά την εκφώνηση;