Ίδια στοιχεία και πάνω και κάτω από την κύρια διαγώνιο

Ξεκίνησε από nikolasmer, 01 Μαρ 2014, 10:14:20 ΜΜ

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

nikolasmer

Υπαρχει δυνατότητα να ελεγχθεί ένας δισδιάστατος πίνακας Π[Ν,Ν] αν περιέχει ίδια στοιχεία πάνω και κάτω από την κύρια διαγώνιο με ενα πέρασμα των στοιχείων του; Δηλαδή με δυο επαναλήψεις
Για ι απο 1 μέχρι Ν
   Για ξ απο 1 μέχρι ι - 1
       ........
Για παράδειγμα ο πίνακας Π[4,4] αν έχει στοιχεία
4  7  8
2  2  3  9
7  4  5  2
8  9  3 7

τότε έχει τα ίδια στοιχεία και πάνω και κάτω από την κύρια διαγώνιο.
Μερεντίτης Νικόλαος
Πληροφορικός

apoldem

Θα πρέπει όλα τα στοιχεία [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

Παράθεση από: apoldem στις 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 τότε όλα ήταν συμμετρικά


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

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

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

itt

#3
Παράθεση από: nikolasmer στις 03 Μαρ 2014, 09:27:59 ΜΜ
Νομίζω πως το παραπάνω δεν δουλεύει.
Για παράδειγμα στον πίνακα

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 έχει δεδομένο μέγεθος. Υποθέτω όμως ότι επειδή δεν ορίζεται όριο στο μέγεθος του ακέραιου στο βιβλίο δεν μπορεί να θεωρηθεί απολύτως σωστός.