Αποστολέας Θέμα: Άσκηση γεμισματος πίνακα σε σπιράλ μορφή!!  (Αναγνώστηκε 1287 φορές)

Vagnes

  • Θαμώνας
  • ***
  • Μηνύματα: 39
Καλησπέρα σ' όλους.. Πώς σας φαινεται η άσκηση να γεμίσουμε ένα πίνακα 4χ4 με τους αριθμούς απο 1-16, σε σπιράλ μορφή( το 1 στο[1,1], το 2 στο [1,2] κ.ο.κ)???

        1     2    3    4
        12  13  14   5
        11  16  15   6
        10    9    8   7
« Τελευταία τροποποίηση: 20 Μάι 2013, 10:22:05 μμ από Vagnes »

noname

  • Ομάδα διαγωνισμάτων 2013
  • *
  • Μηνύματα: 193
Απ: Help!! Άσκηση γεμισματος πίνακα σε σπιράλ μορφή!!
« Απάντηση #1 στις: 09 Φεβ 2013, 03:29:54 πμ »
Εγώ το σκέφτηκα κάπως έτσι: Το σπιράλ είναι 4 διαφορετικές σαρώσεις (2 οριζόντιες και 2 κατακόρυφες εναλλάξ) με διαφορετικές αρχικές και τελικές τιμές και βήμα.
Δηλαδή, πρώτα σαρώνεις οριζόντια την 1η γραμμή από 1 μέχρι Ν με βήμα 1, έπειτα την Ν στήλη από 2 μέχρι Ν με βήμα 1, έπειτα την Ν γραμμή από Ν-1 μέχρι 1 με βήμα -1 έπειτα την 1η στήλη από Ν-1 μέχρι 2 με βήμα -1 κ.ο.κ. Το θέμα είναι να βρεις το πώς μεταβάλλονται οι αρχικές, οι τελικές τιμές και το βήμα κάθε σάρωσης.
Όλες αυτές οι σαρώσεις θα επαναλαμβάνονται μέχρι να προστεθούν Ν^2 αριθμοί.
Ο αλγόριθμος που έφτιαξα ίσως να είναι λίγο πολύπλοκος αλλά δουλεύει. Μάλλον θα υπάρχει κάτι πολύ πιο απλό αλλά τέτοια ώρα δεν δουλεύει και πολύ το μυαλό. :-)

Κώδικας: [Επιλογή]
αλγόριθμος σπιραλ
ν <- 4
για ι από 1 μέχρι ν
  α[1,ι]<- ι
Τέλος_επανάληψης
αγρ <- 2
αστ <- ν-1
τγρ <- ν
τστ <- 1
Χ <- ν + 1
στ <- ν
Όσο Χ<=ν^2 επανάλαβε
Για γρ από αγρ μέχρι τγρ
α[γρ,στ] <- Χ
Χ <- Χ + 1
Τέλος_επανάληψης
γρ <- τγρ
τγρ <-  αγρ
αγρ <- γρ - 1
Για στ από αστ μέχρι τστ με_βήμα -1
α[γρ,στ] <- Χ
Χ <- Χ + 1
Τέλος_επανάληψης
στ <- τστ
τστ <- αστ
αστ <- στ + 1
Για γρ από αγρ μέχρι τγρ με_βήμα -1
α[γρ,στ] <- Χ
Χ <- Χ + 1
Τέλος_επανάληψης
γρ <- τγρ
τγρ <- αγρ
αγρ <- γρ + 1
Για στ από αστ μέχρι τστ
α[γρ,στ] <- Χ
Χ <- Χ + 1
Τέλος_επανάληψης
στ <- τστ
τστ <- αστ
αστ <- στ - 1
Τέλος_επανάληψης
τέλος σπιραλ


epsilonXi

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 151

έφαγα 2 ώρες απ'τη ζωή μου:

ξεκινώντας από την παρατήρηση ότι για τον εξωτερικό από τους «ομόκεντρους κύκλους» ενός πίνακα ΝχΝ θέλουμε:

πρώτη γραμμή από αριστερά: 1, 2, 3, ... , Ν-1,
τελευταία στήλη από πάνω: 1+(Ν-1), 2+(Ν-1), 3+(Ν-1), ... , Ν-1+(Ν-1),
τελευταία γραμμή από δεξιά: 1+2(Ν-1), 2+2(Ν-1), 3+2(Ν-1), ... , Ν-1+2(Ν-1), 
πρώτη στήλη από κάτω: 1+3(Ν-1), 2+3(Ν-1), 3+3(Ν-1), ... , Ν-1+3(Ν-1),

και παρατηρώντας ότι για κάθε επόμενο «ομόκεντρο κύκλο»:
η «ακτίνα» του είναι κατά 2 μικρότερη από τον αμέσως προηγούμενο
και συνεχίζει το μέτρημα από εκεί που είχε σταματήσει ο αμέσως προηγούμενος
καταλήγω:

ν <-- 10  ! ύψος-πλάτος πίνακα
ψ <-- 0   ! η τιμή που θα προστίθεται σε κάθε κελί του εξωτερικού «ομόκεντρου κύκλου»
χ <-- ν-1 ! πόσα κελιά έχει κάθε «τεταρτημόριο» του εξωτερικού «ομόκεντρου κύκλου»


! επειδή ο υπόλοιπος αλγόριθμος για τις περιπτώσεις όπου ν = 2κ+1 αφήνει πάντα το κεντρικό κελί κενό,
! βάζω ξεχωριστή εντολή γι' αυτό το κελί:

α[(ν+1) div 2 , (ν+1) div 2] <-- ν^2

! για κάθε έναν από τους «ομόκεντρους κύκλους» στον πίνακα
για ι από 1 μέχρι (ν+1) div 2

  ! για κάθε κελί κάθε «τεταρτημορίου» του τρέχοντος «κύκλου»
  για ξ από ι μέχρι ν-ι

    ! δίνω τιμή στο κελί της πάνω γραμμής
    α[ι,ξ] <-- ψ+ξ

    ! δίνω τιμή στο κελί της δεξιάς στήλης
    α[ξ, ν-ι+1] <-- ψ+ξ+χ

    ! δίνω τιμή στο κελί της κάτω γραμμής
    α[ν-ι+1, ν+1-ξ] <-- ψ+ξ+2*χ

    ! δίνω τιμή στο κελί της αριστερής στήλης
    α[ν+1-ξ, ι] <-- ψ+ξ+3*χ

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

  ψ <-- ψ + 4*χ-1 ! η τιμή που θα προστίθεται σε κάθε κελί του επόμενου εσωτερικού «ομόκεντρου κύκλου»
  χ <-- χ - 2 ! πόσα κελιά έχει κάθε «τεταρτημόριο» του επόμενου εσωτερικού «ομόκεντρου κύκλου»
τέλος_επανάληψης




 :)