Πίνακας με στοιχεία ίδια με τις θέσεις του αλλά ανακατεμένη σειρά

Ξεκίνησε από nikolasmer, 10 Μαΐου 2015, 07:14:26 ΜΜ

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

nikolasmer

Έστω οτι έχουμε ενα πίνακα μονοδιάστατο 10 θέσεων με τα εξης στοιχεία

10 , 6 , 4 , 8 , 1 , 5 , 2 , 7 , 9, 3 στις αντίστοιχες θέσεις 1-10

και θέλουμε με μια επανάληψη να ελέγξουμε αν περιέχονται μοναδικά όλα τα στοιχεία από το 1 μέχρι και το 10.

Ένας τρόπος να το πετύχουμε είναι ο παρακάτω, με την τιμή του πλ να βγάζει 10 αν όλα τα στοιχεία υπάρχουν και είναι μοναδικά. 
ΠΡΟΓΡΑΜΜΑ ΤΕΣΤ
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Ι, Π[10], ΠΛ, Τ
ΑΡΧΗ
  ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 10
    ΔΙΑΒΑΣΕ Π[Ι] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΠΛ <- 1
  Ι <- 1
  ΟΣΟ Π[Ι] <> 0 ΕΠΑΝΑΛΑΒΕ
    Τ <- Π[Ι] 
    Π[Ι] <- 0
    Ι <- Τ
    ΠΛ <- ΠΛ + 1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ ΠΛ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ


Και τώρα οι ερωτήσεις μου:
1. Υπάρχει τρόπος να υλοποιηθεί το παραπάνω με αναδρομή; (Εκτός ύλης για το μάθημα της ΑΕΠΠ)
2. Στον παραπάνω τρόπο, αν ο πίνακας έχει τιμή εκτός ορίων του πίνακα, το σφάλμα που προκύπτει είναι λογικό; Δεν πληρείται πιο κριτήριο; Πώς θα το αποφύγω. Βάζοντας flag στη συνθήκη, κάνοντας μερική αποτίμηση των λογικών τελεστών;
2. Αν είχαμε εναν Διασδιάστατο Πίνακα γίνεται να ελέγξουμε το παραπάνω που ζητείται, με 2 και μόνο επαναλήψεις, δηλαδή σαρώνοντας μια φορά τα στοιχεία του πίνακα;
Σκέφτηκα το παρακάτω αλλά και πάλι θα πρέπει να δημιουργήσουμε καινούριο πίνακα Κ[25] για τον πίνακα Π[5,5] πράγμα που ξεφεύγει από τη φιλοσοφία του πρώτου κώδικα με τον μονοδιάστατο πίνακα.
ΠΡΟΓΡΑΜΜΑ ΤΕΣΤ
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Ι, Ξ, Π[5, 5], Κ[25], ΠΛ
ΑΡΧΗ
  ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 5
    ΓΙΑ Ξ ΑΠΟ 1 ΜΕΧΡΙ 5
      ΔΙΑΒΑΣΕ Π[Ι, Ξ] 
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 25
    Κ[Ι] <- Ι
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΠΛ <- 0
  ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 5
    ΓΙΑ Ξ ΑΠΟ 1 ΜΕΧΡΙ 5
      ΑΝ Κ[Π[Ι, Ξ]] <> 0 ΤΟΤΕ
        ΠΛ <- ΠΛ + 1
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ ΠΛ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ


Υ.Γ. Οι πίνακες έχουν δεδομένα.
Μερεντίτης Νικόλαος
Πληροφορικός

ssimaiof

Κατ' αρχήν μια παρατήρηση για τον αλγόριθμο:
Λειτουργεί εφ' όσον το περιεχόμενο οποιασδήποτε θέσης του πίνακα είναι διαφορετικό από την ίδια τη θέση.
Π[i]<>i

Τώρα μία αναδρομική επίλυση θα μπορούσε να είναι η
ΠΡΟΓΡΑΜΜΑ ΤΕΣΤ
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Ι, Π[10], ΠΛ
ΑΡΧΗ
  ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 10
    ΔΙΑΒΑΣΕ Π[Ι] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΠΛ <- 0
  ΚΑΛΕΣΕ ΤΘ(Π, 1, ΠΛ) 
  ΓΡΑΨΕ ΠΛ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

ΔΙΑΔΙΚΑΣΙΑ ΤΘ(Π, θ, Μ) 
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Π[10], θ, Μ, Τ
ΑΡΧΗ
  ΑΝ Π[θ] <> 0 ΤΟΤΕ
    Μ <- Μ + 1
    Τ <- Π[θ] 
    Π[θ] <- 0
    ΚΑΛΕΣΕ ΤΘ(Π, Τ, Μ) 
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ


Όσον αφορά το λογικό (προφανώς) λάθος πρέπει να παραβιάζεται το κριτήριο της καθοριστικότητας.
Για να αποφευχθεί ένας απλός έλεγχος της μορφής
ΑΝ Π[Ι]>10 ΤΟΤΕ
   ...

Όπου 10 το μέγεθος του πίνακα.

Προσωπικά μ' αρέσει και η παρακάτω λύση η οποία λειτουργεί αν το μέγεθος του πίνακα είναι μικρότερο ή ίσο με την ακρίβεια υπολογισμού των πραγματικών αριθμών
ΠΡΟΓΡΑΜΜΑ ΤΕΣΤ
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Ι, Π[10], ΠΛ, Τ
  ΠΡΑΓΜΑΤΙΚΕΣ: Σ
ΑΡΧΗ
  ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 10
    ΔΙΑΒΑΣΕ Π[Ι] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  Σ <- 0
  ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 10
    Σ <- Σ + 10^(Π[Ι] - 1) 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ Σ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Όπου πρέπει να μας βγάλει τόσους άσσους όσο το μέγεθος του πίνακα.
Σταύρος Σημαιοφορίδης

ssimaiof

Τώρα που ξαναείδα τον αλγόριθμό σου πιστεύω ότι δεν θα δουλέψει αν υπάρχει κλειστός κύκλος μέσα στον πίνακα. Δηλαδή
Α[1]=2
Α[2]=1
... Τα υπόλοιπα αδιάφορα

Πάντως όσον αφορά δισδιάστατο και δεν έχουμε προβλήματα με τις περιπτώσεις που ανέφερα μία λύση θα ήταν η μετατροπή του αριθμού σε γραμμή και στήλη. Για παράδειγμα σε πίνακα 4x3 με δεδομένα 12,6,4,8,1,5,2,7,9,3,10,11 θα μπορούσαμε να έχουμε
ΠΡΟΓΡΑΜΜΑ ΤΕΣΤ
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Ι1, Ι2, Π[4, 3], ΠΛ, Τ
ΑΡΧΗ
  ΓΙΑ Ι1 ΑΠΟ 1 ΜΕΧΡΙ 4
    ΓΙΑ Ι2 ΑΠΟ 1 ΜΕΧΡΙ 3
      ΔΙΑΒΑΣΕ Π[Ι1, Ι2] 
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΠΛ <- 0
  Ι1 <- 1
  Ι2 <- 1
  ΟΣΟ Π[Ι1, Ι2] <> 0 ΕΠΑΝΑΛΑΒΕ
    ΑΝ Π[Ι1, Ι2] <= 12 ΤΟΤΕ
      Τ <- Π[Ι1, Ι2] 
      Π[Ι1, Ι2] <- 0
      Ι1 <- (Τ + 2) div 3
      Ι2 <- Τ - ((Ι1 - 1)*3) 
      ΠΛ <- ΠΛ + 1
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ ΠΛ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
Σταύρος Σημαιοφορίδης

nikolasmer

Φοβερό το μήνυμα του ssimaiof.
Έχω εντυπωσιαστεί!!!!! :D

Κλειστός κύκλος...μμμ
Δεν το είχα σκεφτεί.

Ωραία μου ακούγεται και ο έλεγχος εγκυρότητας για το να μην υπάρχουν κλειστοί κύκλοι μέσα στα στοιχεία ενός πίνακα.!!!

Μερεντίτης Νικόλαος
Πληροφορικός

ολγα

Δε δουλεύει και στην περίπτωση π.χ.:
10 , 6 , 4 , 8 , 1 , 5 , 2 , 7 , 7, 3
(Εμφανίζει 10, ενώ δεν θα έπρεπε)

ssimaiof

Η ολγα βρήκε και λάθος παράβλεψης! Προφανώς πρέπει
ΠΛ <- 0

οπότε και ο αλγόριθμος θα εμφάνιζε με βάση τα αρχικά δεδομένα ως αποτέλεσμα το 9 που είναι σωστό!
Αν και το ανέφερα δεν παρατήρησα ότι στην 9η θέση υπάρχει το 9 !!
Οπότε ακόμη και αν αλλάξει τιμή η 9η θέση του πίνακα δεν επηρεάζει το αποτέλεσμα. Έχουμε κλειστό κύκλο 9 στοιχείων !!

Υ.Γ. Διόρθωσα και τους αντίστοιχους δικούς μου κώδικες.
Σταύρος Σημαιοφορίδης