Αποστολέας Θέμα: Ίδια στοιχεία και πάνω και κάτω από την κύρια διαγώνιο  (Αναγνώστηκε 1242 φορές)

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 564
  • There can be only one...may it be AEPP.
Υπαρχει δυνατότητα να ελεγχθεί ένας δισδιάστατος πίνακας Π[Ν,Ν] αν περιέχει ίδια στοιχεία πάνω και κάτω από την κύρια διαγώνιο με ενα πέρασμα των στοιχείων του; Δηλαδή με δυο επαναλήψεις
Για ι απο 1 μέχρι Ν
   Για ξ απο 1 μέχρι ι - 1
       ........
Για παράδειγμα ο πίνακας Π[4,4] αν έχει στοιχεία
4  7  8
2  2  3  9
7  4  5  2
8  9  3 7

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

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

apoldem

  • Βετεράνος
  • ****
  • Μηνύματα: 86
Απ: Ίδια στοιχεία και πάνω και κάτω από την κύρια διαγώνιο
« Απάντηση #1 στις: 02 Μάρ 2014, 01:21:23 πμ »
Θα πρέπει όλα τα στοιχεία [i-1, i] να είναι ίσα με τα [i+1, i]. Το πρώτο και το τελευταίο στοιχείο εξαιρούνται, οπότε μια επανάληψη είναι αρκετή
Κώδικας: [Επιλογή]
σωστό <- Αληθής
Για i από 2 μέχρι Ν-1
  σωστό <- Α[i-1, i] = Α[i+1, i]
Τέλος_επανάληψης

Λίγο καλύτερα θα μπορούσαμε να το κάνουμε να σταματά μόλις βρει ψευδές
Κώδικας: [Επιλογή]
i <- 2
Όσο i < Ν και Α[i-1, i] = Α[i+1, i]  ! short-circuit evaluation
  i <- i+1
Τέλος_επανάληψης
σωστό <- i = Ν  ! αν ξεπέρασε το Ν-1 τότε όλα ήταν συμμετρικά

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 564
  • There can be only one...may it be AEPP.
Απ: Ίδια στοιχεία και πάνω και κάτω από την κύρια διαγώνιο
« Απάντηση #2 στις: 03 Μάρ 2014, 09:27:59 μμ »
Θα πρέπει όλα τα στοιχεία [i-1, i] να είναι ίσα με τα [i+1, i]. Το πρώτο και το τελευταίο στοιχείο εξαιρούνται, οπότε μια επανάληψη είναι αρκετή
Κώδικας: [Επιλογή]
σωστό <- Αληθής
Για i από 2 μέχρι Ν-1
  σωστό <- Α[i-1, i] = Α[i+1, i]
Τέλος_επανάληψης

Λίγο καλύτερα θα μπορούσαμε να το κάνουμε να σταματά μόλις βρει ψευδές
Κώδικας: [Επιλογή]
i <- 2
Όσο i < Ν και Α[i-1, i] = Α[i+1, i]  ! short-circuit evaluation
  i <- i+1
Τέλος_επανάληψης
σωστό <- i = Ν  ! αν ξεπέρασε το Ν-1 τότε όλα ήταν συμμετρικά

Νομίζω πως το παραπάνω δεν δουλεύει.
Για παράδειγμα στον πίνακα

1  2  3  5
4  1  4  7
5  3  1  6
7  6  2  1

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

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 429
  • Real stupidity beats ΑΙ any time
Απ: Ίδια στοιχεία και πάνω και κάτω από την κύρια διαγώνιο
« Απάντηση #3 στις: 04 Μάρ 2014, 01:49:28 μμ »
Νομίζω πως το παραπάνω δεν δουλεύει.
Για παράδειγμα στον πίνακα

1  2  3  5
4  1  4  7
5  3  1  6
7  6  2  1

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


Ξανάγραψα την απάντηση για να είναι πιο ορθή.

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

Ο ΑΠΛΟΣ ΤΡΟΠΟΣ
O πιο απλός τρόπος είναι να χρησιμοποιήσεις bubble sort. Μπορείς να βάλεις τα δύο τριγωνικά κομμάτια σε δύο πίνακες, να τους κάνεις sort και να τους συγκρίνεις. Αυτό έχει την πολυπλοκότητα που θες (αφού η bubblesort έχει πολυπλοκότητα Ο(n2) και η σύγκριση Ο(n) ) και επειδή η bubblesort είναι stable, έχεις εξασφαλισμένα σωστό αποτέλεσμα.

O ΙΔΙΩΜΑΤΙΚΟΣ ΤΡΟΠΟΣ
Μπορείς να υπολογίσεις για κάθε κομμάτι τον πίνακα συχνοτήτων για τα περιεχόμενα του και να συγκρίνεις τους δύο πίνακες. Αν είναι οι ίδιοι τότε ισχύει η ιδιότητα που θες αλλιώς όχι.

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

ΕΝΑΣ ΘΕΩΡΗΤΙΚΑ ΣΩΣΤΟΣ( Υποθέτωντας φραγμένους ακέραιους)
Άμα έχεις φραγμένους ακέραιους, υποθέτωντας πχ upper bound το 232 , μπορείς να κάνεις και το εξής. Θα κατασκευάσεις έναν πίνακα F, μήκους upper bound. Θα μηδενίσεις τον πίνακα.
Μπορείς να χρησιμοποιήσεις αυτόν τον πίνακα για dictionary. Για κάθε enty i στο πρώτο κομμάτι θα αυξάνεις το F(i) κατα ένα. Για το δεύτερο κομμάτι θα το μειώνεις. Στο τέλος θα εξετάσεις αν ο πίνακας έχει παντού μηδένικα. Ο μηδενισμός του πίνακα είναι Ο(1) πολυπλοκότητας, η διαδικασία αυξομείωσης Ο(n) όπως και η σύγκριση.

Αυτός ο τρόπος μπορεί να υλοποιηθεί και στα πλαίσια του ΑΕΠΠ, αφού ο πίνακας F έχει δεδομένο μέγεθος. Υποθέτω όμως ότι επειδή δεν ορίζεται όριο στο μέγεθος του ακέραιου στο βιβλίο δεν μπορεί να θεωρηθεί απολύτως σωστός.
« Τελευταία τροποποίηση: 04 Μάρ 2014, 05:16:48 μμ από itt »