Αποστολέας Θέμα: Δύσκολη Άσκηση από τον Bugman.  (Αναγνώστηκε 443 φορές)

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 367
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Δύσκολη Άσκηση από τον Bugman.
« στις: 28 Οκτ 2018, 12:35:41 πμ »
Δίνεται ένας πίνακας Ν μεγέθους, μεγαλύτερος ή ίσος με 1. Δίνεται ένας αριθμός Μ ομάδων μεγαλύτερος ή ίσος με 1. Για κάθε ομάδα δίνεται ένας αριθμός μήκους. Σκοπός μας είναι να γεμίσουμε τον πίνακα με όλες τις ομάδες, και να το κάνουμε αυτό για όλους τους συνδυασμούς, σύμφωνα με τις παρακάτω οδηγίες. Μια ομάδα με μήκος 2 πιάνει δυο συνεχόμενες θέσεις στο πίνακα, και ως τιμή βάζουμε το 1 σε αυτές τις θέσεις. Οι ομάδες μπαίνουν με τη σειρά που δόθηκαν, και μεταξύ τους υποχρεωτικά θα έχουν μια κενή θέση. Οι κενές θέσεις στο πίνακα είναι με τιμή 0.
Αν δοθεί πίνακας Ν=5 και Μ=2 με Μ(1)=2 και Μ(2)=1 τότε θα πρέπει το πρόγραμμα να δώσει τις παρακάτω σειρές:
1 1 0 1 0
1 1 0 0 1
0 1 1 0 1

Δείξτε με τον κατάλληλο αλγόριθμο το αποτέλεσμα για
Ν=5 Μ=1 Μ(1)=1
Ν=10 Μ=1 Μ(1)=8
Ν=15 Μ=4 Μ(1)=3 Μ(2)=2 Μ(3)=3 Μ(4)=2

Δείξτε με τον ίδιο αλγόριθμο ότι το παρακάτω δεν είναι εφικτό
Ν=5 Μ=2 Μ(1)=2 Μ(2)=3
« Τελευταία τροποποίηση: 28 Οκτ 2018, 10:22:32 πμ από bugman »

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 367
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Απ: Δύσκολη Άσκηση από τον Bugman.
« Απάντηση #1 στις: 29 Οκτ 2018, 09:29:18 μμ »
Η λύση δεν κάνει αναδρομή, και αντί αυτού χρησιμοποιεί  μια μεταβλητή με όνομα ΣΤΟΙΒΑ και δυο πίνακες ΣΠ[] και ΣΚ[] όπου βάζει το Π το τρέχον στοιχείο του ΠΙΝ[] και το Κ το επιλεγμένο στοιχείο από το πίνακα ΜΠΛΟΚ[].
Για ευκολία έχουμε έναν πίνακα ΜΗΚΟΣ[] όπου για το 1 δίνει όλο το μήκος μέχρι το τέλος που πρέπει να έχει ελάχιστο ο πίνακας για να χωρέσει η σειρά. Για κάθε Ι μέχρι το Μ έχουμε το μήκος από το Ι μπλοκ μέχρι το τέλος. Δείτε ότι το τελευταίο μπλοκ το Μ δεν έχει ανάγκη το ένα κενό (ως διαχωριστικό) και έτσι μπαίνει με το μήκος που δόθηκε στο ΜΠΛΟΚ(Μ).

Προστέθηκε η περίπτωση του Μ να είναι 0 (να έχουμε κενά κελιά), το οποίο δεν το ζητάει η άσκηση αλλά μπήκε εδώ!

ΠΡΟΓΡΑΜΜΑ ΑΛΦΑ
ΣΤΑΘΕΡΕΣ
  ΜΕΓΙΣΤΟ_ΠΛΗΘΟΣ_ΚΕΛΙΩΝ = 100
  ΜΕΓΙΣΤΟ_ΠΛΗΘΟΣ_ΜΠΛΟΚ = 50
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ΠΙΝ[ΜΕΓΙΣΤΟ_ΠΛΗΘΟΣ_ΚΕΛΙΩΝ], ΜΠΛΟΚ[ΜΕΓΙΣΤΟ_ΠΛΗΘΟΣ_ΜΠΛΟΚ], Ν, Μ
  ΑΚΕΡΑΙΕΣ: Ι, Π, Κ, Λ, Π1
  ΑΚΕΡΑΙΕΣ: ΣΠ[ΜΕΓΙΣΤΟ_ΠΛΗΘΟΣ_ΜΠΛΟΚ*2], ΣΚ[ΜΕΓΙΣΤΟ_ΠΛΗΘΟΣ_ΜΠΛΟΚ*2], ΣΤΟΙΒΑ
  ΑΚΕΡΑΙΕΣ: ΜΗΚΟΣ[ΜΕΓΙΣΤΟ_ΠΛΗΘΟΣ_ΜΠΛΟΚ]
  ΛΟΓΙΚΕΣ: ΣΗΜΑΙΑ
ΑΡΧΗ
  ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
    ΓΡΑΨΕ "ΔΩΣΕ ΑΡΙΘΜΟ ΚΕΛΙΩΝ:"
    ΔΙΑΒΑΣΕ Ν
  ΜΕΧΡΙΣ_ΟΤΟΥ Ν > 0 ΚΑΙ Ν <= ΜΕΓΙΣΤΟ_ΠΛΗΘΟΣ_ΚΕΛΙΩΝ
  ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
    ΓΡΑΨΕ "ΔΩΣΕ ΑΡΙΘΜΟ ΜΠΛΟΚ"
    ΔΙΑΒΑΣΕ Μ
  ΜΕΧΡΙΣ_ΟΤΟΥ Μ >= 0 ΚΑΙ Μ <= ΜΕΓΙΣΤΟ_ΠΛΗΘΟΣ_ΜΠΛΟΚ
  ΜΗΚΟΣ[1] <- 0
  ΑΝ Μ > 0 ΤΟΤΕ
    ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Μ
      ΓΡΑΨΕ "ΜΕΓΕΘΟΣ ΜΠΛΟΚ:", Ι
      ΔΙΑΒΑΣΕ ΜΠΛΟΚ[Ι]
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΜΗΚΟΣ[Μ] <- ΜΠΛΟΚ[Μ]
    ΑΝ Μ > 1 ΤΟΤΕ
      ΓΙΑ Ι ΑΠΟ Μ - 1 ΜΕΧΡΙ 1 ΜΕ_ΒΗΜΑ -1
        ΜΗΚΟΣ[Ι] <- ΜΠΛΟΚ[Ι] + ΜΗΚΟΣ[Ι + 1] + 1
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΑΝ
  ΑΝ ΜΗΚΟΣ[1] > Ν ΤΟΤΕ
    ΓΡΑΨΕ "ΑΔΥΝΑΤΟΝ"
  ΑΛΛΙΩΣ_ΑΝ Μ = 0 ΤΟΤΕ
    ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν
      ΓΡΑΨΕ 0, "  "
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΓΡΑΨΕ
  ΑΛΛΙΩΣ
    ΣΤΟΙΒΑ <- 0
    Π1 <- 0
    Λ <- 0
    ΟΣΟ Π1 <= (Ν - ΜΗΚΟΣ[1]) ΕΠΑΝΑΛΑΒΕ
      Κ <- 0
      Π <- Π1 + 1
      ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν
        ΠΙΝ[Ι] <- 0
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
     
      ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
        ΟΣΟ Κ < Μ ΕΠΑΝΑΛΑΒΕ
          Κ <- Κ + 1
          Λ <- 0
          ΟΣΟ Λ < ΜΠΛΟΚ[Κ] ΚΑΙ Π <= Ν ΕΠΑΝΑΛΑΒΕ
            Λ <- Λ + 1
            ΠΙΝ[Π] <- 1
            Π <- Π + 1
          ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
          ΑΝ Π < Ν ΤΟΤΕ
            ΠΙΝ[Π] <- 0
            Π <- Π + 1
            ΑΝ Κ < Μ ΤΟΤΕ
              ΑΝ (Π + ΜΗΚΟΣ[Κ + 1]) <= Ν ΤΟΤΕ
                ΣΤΟΙΒΑ <- ΣΤΟΙΒΑ + 1
                ΣΠ[ΣΤΟΙΒΑ] <- Π
                ΣΚ[ΣΤΟΙΒΑ] <- Κ
              ΤΕΛΟΣ_ΑΝ
            ΤΕΛΟΣ_ΑΝ
          ΤΕΛΟΣ_ΑΝ
        ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
       
        ΣΗΜΑΙΑ <- ΑΛΗΘΗΣ
        ΑΝ Λ = ΜΠΛΟΚ[Κ] ΤΟΤΕ
          ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν
            ΓΡΑΨΕ ΠΙΝ[Ι], "  "
          ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
          ΓΡΑΨΕ
          ΑΝ ΣΤΟΙΒΑ > 0 ΤΟΤΕ
            Π <- ΣΠ[ΣΤΟΙΒΑ]
            Κ <- ΣΚ[ΣΤΟΙΒΑ]
            ΣΤΟΙΒΑ <- ΣΤΟΙΒΑ - 1
            ΓΙΑ Ι ΑΠΟ Π ΜΕΧΡΙ Ν
              ΠΙΝ[Ι] <- 0
            ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
            Π <- Π + 1
            ΑΝ Κ < Μ ΤΟΤΕ
              ΑΝ (Π + ΜΗΚΟΣ[Κ + 1]) <= Ν ΤΟΤΕ
                ΣΤΟΙΒΑ <- ΣΤΟΙΒΑ + 1
                ΣΠ[ΣΤΟΙΒΑ] <- Π
                   ! το ΣΚ[ΣΤΟΙΒΑ]<-Κ δεν το βάζουμε είναι ήδη Κ
              ΤΕΛΟΣ_ΑΝ
            ΤΕΛΟΣ_ΑΝ
            ΣΗΜΑΙΑ <- ΨΕΥΔΗΣ
          ΤΕΛΟΣ_ΑΝ
        ΤΕΛΟΣ_ΑΝ
      ΜΕΧΡΙΣ_ΟΤΟΥ ΣΗΜΑΙΑ = ΑΛΗΘΗΣ
      Π1 <- Π1 + 1
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ




ΔΩΣΕ ΑΡΙΘΜΟ ΚΕΛΙΩΝ:
5
ΔΩΣΕ ΑΡΙΘΜΟ ΜΠΛΟΚ
1
ΜΕΓΕΘΟΣ ΜΠΛΟΚ:1
1
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

ΔΩΣΕ ΑΡΙΘΜΟ ΚΕΛΙΩΝ:
10
ΔΩΣΕ ΑΡΙΘΜΟ ΜΠΛΟΚ
1
ΜΕΓΕΘΟΣ ΜΠΛΟΚ:1
8
1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 1 1 1

ΔΩΣΕ ΑΡΙΘΜΟ ΚΕΛΙΩΝ:
15
ΔΩΣΕ ΑΡΙΘΜΟ ΜΠΛΟΚ
4
ΜΕΓΕΘΟΣ ΜΠΛΟΚ:1
3
ΜΕΓΕΘΟΣ ΜΠΛΟΚ:2
2
ΜΕΓΕΘΟΣ ΜΠΛΟΚ:3
3
ΜΕΓΕΘΟΣ ΜΠΛΟΚ:4
2
1 1 1 0 1 1 0 1 1 1 0 1 1 0 0
1 1 1 0 1 1 0 1 1 1 0 0 1 1 0
1 1 1 0 1 1 0 1 1 1 0 0 0 1 1
1 1 1 0 1 1 0 0 1 1 1 0 1 1 0
1 1 1 0 1 1 0 0 1 1 1 0 0 1 1
1 1 1 0 1 1 0 0 0 1 1 1 0 1 1
1 1 1 0 0 1 1 0 1 1 1 0 1 1 0
1 1 1 0 0 1 1 0 1 1 1 0 0 1 1
1 1 1 0 0 1 1 0 0 1 1 1 0 1 1
1 1 1 0 0 0 1 1 0 1 1 1 0 1 1
0 1 1 1 0 1 1 0 1 1 1 0 1 1 0
0 1 1 1 0 1 1 0 1 1 1 0 0 1 1
0 1 1 1 0 1 1 0 0 1 1 1 0 1 1
0 1 1 1 0 0 1 1 0 1 1 1 0 1 1
0 0 1 1 1 0 1 1 0 1 1 1 0 1 1

ΔΩΣΕ ΑΡΙΘΜΟ ΚΕΛΙΩΝ:
5
ΔΩΣΕ ΑΡΙΘΜΟ ΜΠΛΟΚ
2
ΜΕΓΕΘΟΣ ΜΠΛΟΚ:1
2
ΜΕΓΕΘΟΣ ΜΠΛΟΚ:2
3
ΑΔΥΝΑΤΟΝ

ΔΩΣΕ ΑΡΙΘΜΟ ΚΕΛΙΩΝ:
5
ΔΩΣΕ ΑΡΙΘΜΟ ΜΠΛΟΚ
0
0 0 0 0 0
« Τελευταία τροποποίηση: 29 Οκτ 2018, 10:49:39 μμ από bugman »