Θέμα: Άσκηση με Ταξινόμηση σε ΝxΝ της κύριας Διαγωνίου

[nikolasmer]

Μπορεί να έχει ξανά υπωθεί το θέμα.
Να ταξινομήσετε τα στοιχεία της κ.δ κατά αύξουσα(ή φθίνουσα σειρά) σε δισδιάστατο πίνακα Π[Ν,Ν].

Αλγόριθμος Ταξινόμηση_κύριας_διαγωνίου
Για i από 1 μέχρι Ν
  Για j από 1 μέχρι Ν
    Εμφάνισε "Δώσε το ", i, ",", j, " στοιχείο"
    Διάβασε Π[i, j]
  Τέλος_επανάληψης
Τέλος_επανάληψης
Για k από 2 μέχρι Ν
  Για i από Ν μέχρι k με_βήμα -1
    Για j από Ν μέχρι k με_βήμα -1
      Αν i = j τότε
        Αν Π[i - 1, j - 1] > Π[i, j] τότε
          προσ ← Π[i - 1, j - 1]
          Π[i - 1, j - 1] ← Π[i, j]
          Π[i, j] ← προσ
        Τέλος_αν
      Τέλος_αν
    Τέλος_επανάληψης
  Τέλος_επανάληψης
Τέλος_επανάληψης
Εμφάνισε "Τα στοιχεία της Κύριας Διαγωνίου είναι:"
Για i από 1 μέχρι Ν
  Εμφάνισε Π[i, i]
Τέλος_επανάληψης
Τέλος Ταξινόμηση_κύριας_διαγωνίου

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

[odysseas]

Δεν είναι ανάγκη να διατρέχεις όλον τον πίνακα (διπλή ΓΙΑ με i, j) μόνο και μόνο για να αντιμεταθέτεις τα στοιχεία της κύριας διαγωνίου. Εφόσον το περιεχόμενο της διπλής ΓΙΑ ενεργοποιείται μόνο όταν i=j, αρκεί μόνο μια εσωτερική ΓΙΑ:

Κώδικας: [Επιλογή]

  Για i από Ν μέχρι k με_βήμα -1
        Αν Π[i - 1, i - 1] > Π[i, i] τότε
          προσ ← Π[i - 1, i - 1]
          Π[i - 1, i - 1] ← Π[i, i]
          Π[i, i] ← προσ
        Τέλος_αν
      Τέλος_αν
  Τέλος_επανάληψης

Από κει και πέρα ομολογώ οτι δεν αντιλαμβάνομαι την σκοπιμότητα μιας τέτοιας άσκησης.

[nikolasmer]

Σωστή η παρατήρηση.
Σκέφτόμουνα το Θέμα Δ 2011 και θέλησα να την κάνω λίγο πιο δύσκολη μήπως τα παιδιά τριφτούν περισσότερο.

"Στο διαγώνισμα που έβαλε ο καθηγητής στην ΑΕΠΠ έδωσε για διόρθωση τα γραπτά σε κάθε εναν μαθητή για να τα διορθώσει και να αποθηκεύσει τη βαθμολογία τους[0-100]. Να γίνει αλγόριθμος ο οποίος σε ενα πίνακα 20 θέσεων να διαβάζει τα ονόματα μαθητών και στη συνέχεια σε πίνακα 20χ20 να διαβάζει τη βαθμολογία που θα έδινε ο κάθε ενας τους, στους υπόλοιπους συμμαθητές έτσι ώστε στο στοιχείο Β[i,i] να περιέχει τη βαθμολογία που έδωσε ο μαθητής στον εαυτό του. Να υπολογίζει και να εμφανίζει ταξινομημένα τα ονόματα των μαθητών ανάλογα με τη βαθμολογία που έδωσαν στους εαυτούς τους. Υποθέτουμε πως δεν υπάρχουν ισοβαθμίες. Σε περίπτωση που η σειρά των ονομάτων έχει απόκλιση μεγαλύτερη του 20% χαμηλότερη από το μέσο όρο των βαθμών που πήραν από τους συμαθητές τους, να εμφανίζεται το μήνυμα "οχι σωστή κατάταξη" και τα ονόματα των μαθητών που αξιολόγησαν τον εαυτό τους πολύ υψηλότερα από το μέσο όρο των συμαθητών τους. Να χρησιμοποιήσετε μόνο τους πίνακες που δίνονται."

Σε αυτή τη φάση μόνο αυτό τον τρόπο μπόρεσα να σκεφτώ για απάντηση.

[odysseas]

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

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

Κώδικας: [Επιλογή]

ΓΙΑ κ ΑΠΟ 1 ΜΕΧΡΙ Ν
  αθρ <-- 0
  ΓΙΑ λ ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΑΝ λ <> κ ΤΟΤΕ
      ΔΙΑΒΑΣΕ β
      αθρ <-- αθρ+β
    ΑΛΛΙΩΣ
      ΔΙΑΒΑΣΕ ΒΑΘ[κ]
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  Μ[κ] <-- αθρ/Ν
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

'Η αν ο μαθητής είναι λίγο πιο νίντζα:

Κώδικας: [Επιλογή]

ΓΙΑ κ ΑΠΟ 1 ΜΕΧΡΙ Ν
  αθρ <-- 0
  ΓΙΑ λ ΑΠΟ 1 ΜΕΧΡΙ κ-1
    ΔΙΑΒΑΣΕ β
    αθρ <-- αθρ+β
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΔΙΑΒΑΣΕ ΒΑΘ[κ]
  ΓΙΑ λ ΑΠΟ κ+1 ΜΕΧΡΙ Ν
    ΔΙΑΒΑΣΕ β
    αθρ <-- αθρ+β
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  Μ[κ] <-- αθρ/Ν
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ


[nikolasmer]

Ναι ναι πολύ ωραίο. 
Θα τους το πώ. Έχω μερικά χελωνονιτζάκια. Φοβερό. Θα δώ τις αναντήσεις τους και θα τους πώ και το δεύτερο τρόπο. Θα χαρούν πολύ.
Ευχαριστώ Οδυσσέα.