Αντιμεταθέσεις στοιχείων

Ξεκίνησε από Anastasis13, 01 Νοε 2022, 10:49:32 ΜΜ

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

Anastasis13

Ποια η διαφορά των παρακάτω ;


Για i από 1 μέχρι n

  Αν a[i] ≠ i τότε Αντιμετάθεσε a[i],a[a[i]]

Τέλος_επανάληψης



Για i από 1 μέχρι n

  Αν a[i] ≠ i τότε Αντιμετάθεσε a[a[i]],a[i]

Τέλος_επανάληψης



Για i από 1 μέχρι n

  Αν a[i] ≠ i τότε

    pos ← i

    Αντιμετάθεσε a[i],a[pos]

  Τέλος_αν

Τέλος_επανάληψης

alkisg

Θεωρούμε τον παρακάτω αλγόριθμο:

Κώδικας: Ψευδογλώσσα
Αλγόριθμος Πρόβλημα_αντιμετάθεσης
Για ι από 1 μέχρι 5
  Π[ι] ← 2*ι
Τέλος_επανάληψης
Αντιμετάθεσε Π[Π[1]], Π[1] 
Αποτελέσματα // Π //
Τέλος

Ο πίνακας λοιπόν αρχικοποιείται σε:
2, 4, 6, 8, 10.

1) Η εντολή `Αντιμετάθεσε Π[Π[1]], Π[1]` ισοδυναμεί με `Αντιμετάθεσε Π[2], Π[1]` και κάνει τον πίνακα: 4, 2, 6, 8, 10.

2) Αλλάζουμε την Αντιμετάθεσε σε `Αντιμετάθεσε Π[1], Π[Π[1]]` που νομίζουμε ότι αντιστοιχεί σε `Αντιμετάθεσε Π[1], Π[2]` και περιμένουμε το ίδιο αποτέλεσμα. Τότε όμως παίρνουμε το εξής περίεργο:
4, 4, 6, 2, 10.

Αυτό γίνεται επειδή η εντολή Αντιμετάθεσε αντιστοιχεί στις παρακάτω 3 εντολές:

Κώδικας: Ψευδογλώσσα
προσωρινή <- Π[1]     ! Άρα προσωρινή <- 2
Π[1] <- Π[Π[1]]       ! Άρα Π[1] <- Π[2], δηλαδή Π[1] <- 4
Π[Π[1]] <- προσωρινή  ! Άρα Π[4] <- 2

Το πρόβλημα δηλαδή είναι ότι το Π[1] έχει ήδη αλλάξει όταν το διαβάζουμε για να το βάλουμε μέσα στο Π[Π[1]].

Foto

Αυτό το βλέπω ως πρόβλημα υλοποίησης. Λογικά η Αντιμετάθεσε πρέπει να βρίσκει τις δύο θέσεις πίνακα, 1 και 2, εκτελώντας τις αριθμητικές εκφράσεις των δεικτών, δηλαδή το 1 και το Π[1] που δίνει το 2 και μετά να κάνει τις αλλαγές μέσω μιας τρίτης βοηθητικής.

alkisg

Η υλοποίηση που προτείνεις θα ήταν προτιμητέα σε compilers γλωσσών που είναι by reference, όχι όμως σε Διερμηνευτή της ΓΛΩΣΣΑΣ που είναι by copy restore (και θεωρούμε κατά προέκταση ότι το ίδιο ισχύει και στην Ψευδογλώσσα).

Ας θεωρήσουμε το αντίστοιχο πρόγραμμα σε ΓΛΩΣΣΑ:

Κώδικας: ΓΛΩΣΣΑ
ΠΡΟΓΡΑΜΜΑ Πρόβλημα_αντιμετάθεσης
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ι, Π[5] 
ΑΡΧΗ
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ 5
    Π[ι] <- 2*ι
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΚΑΛΕΣΕ Αντιμετάθεσε(Π[Π[1]], Π[1]) 
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ 5
    ΓΡΑΨΕ Π[ι], ',  '
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

ΔΙΑΔΙΚΑΣΙΑ Αντιμετάθεσε(α, β) 
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: α, β, τ
ΑΡΧΗ
  τ <- α
  α <- β
  β <- τ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ


Αυτό λοιπόν έχει το ίδιο "πρόβλημα" και τυπώνει: 4, 4, 6, 2, 10.
Τι συμβαίνει;
Κατά την κλήση, με βάση το by-copy-restore, δημιουργούνται αντίγραφα των πραγματικών παραμέτρων.
Αντιμετατίθενται σωστότατα εντός της Διαδικασίας.
Όταν όμως έρχεται η ώρα να αντιγραφούν πίσω στο κυρίως πρόγραμμα, τι θεωρούμε ότι πρέπει να γίνει;

Π[1] <- β
Π[Π[1]] <- α

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

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

Foto

Όπως καταλαβαίνω αν δεν χρησιμοποιηθεί ως δείκτης στο Π[] έκφραση με στοιχείο του πίνακα, δηλαδή γράψουμε σε ένα Α το Π[1] και κάνουμε αντιμετάθεση Π[1], Π[Α]  δεν θα υπάρξει πρόβλημα. 

alkisg

#5
Ακριβώς. Το ίδιο δηλαδή όπως θα το κάναμε για να αποφύγουμε το πρόβλημα αν δεν υπήρχε η εντολή Αντιμετάθεσε.
Π.χ. έστω ότι σε πιο δύσκολη περίπτωση θέλαμε να αντιμεταθέσουμε το Π[Π[1]] και το Π[Π[2]]:

Κώδικας: Ψευδογλώσσα
θ1 <- Π[1]
θ2 <- Π[2]
τ <- Π[θ1]
Π[θ1] <- Π[θ2]
Π[θ2] <- τ