Αποστολέας Θέμα: Προτεινόμενη λύση  (Αναγνώστηκε 2664 φορές)

oratios

  • Νέος
  • *
  • Μηνύματα: 6
Προτεινόμενη λύση
« στις: 21 Οκτ 2014, 04:09:00 μμ »
Στο παιχνίδι Darts (βελάκια) τα επιτρεπτά σκορ με ένα βέλος είναι: 7, 15, 19, 23, 29 και 37. Στόχος του παιχνιδιού είναι να συγκεντρωθούν 100 βαθμοί ακριβώς με 6 βολές. Ποιοι είναι οι δυνατοί συνδυασμοί για να επιτευχθεί αυτό;
(Θεωρήστε ότι τα 6 διαφορετικά επιτρεπτά σκορ βρίσκονται σε πίνακα ακεραίων Ρ[6]).

Λύση 6 εμφωλευμένες επαναλήψεις για να παρεις ολους τους διακριτούς συνδυασμούς. Καποια αλλη?


petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2212
Απ: Προτεινόμενη λύση
« Απάντηση #1 στις: 21 Οκτ 2014, 04:42:17 μμ »
Από ότι καταλαβαίνω, επιτρέπεται να ρίξει 2 φορές το ίδιο σκορ;
Μια ιδέα που μειώνει τις απαιτούμενες επαναλήψεις είναι ότι αν το άθροισμα φτάνει πάνω από ένα επιτρεπτό όριο, δεν χρειάζεται να ελεγχθούν και οι 6 πιθανοί βαθμοί
Πχ, πάνω από 73 δεν χρειάζεται η τελευταία, πάνω από 81, οι 4 τελευταίες
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

oratios

  • Νέος
  • *
  • Μηνύματα: 6
Απ: Προτεινόμενη λύση
« Απάντηση #2 στις: 21 Οκτ 2014, 04:53:25 μμ »
Φυσικά και επιτρέπεται να ριξεις 2 φορες το ιδιο αφου εαν ηταν διακτιτες οι ριψεις θα επρεπε: 7+15+19+23+29+37(=130) να κανει 100!

Οποτε λες 6 εμφωλευμενες με ΜΕΧΡΙΣ_ΟΤΟΥ και να σπαω τα 2 τελευταια με τις συνθηκες που ειπες. Μου φαινεται πολυ μανουρα και μικρο το κερδος απο το να τα κανεις απλα με 6 εμφωλευμενα ΓΙΑ. Οι επαναληψεις που θα κανουμε θα ειναι 6!


evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: Προτεινόμενη λύση
« Απάντηση #3 στις: 21 Οκτ 2014, 04:55:36 μμ »
Και με εξαπλή επανάληψη πάλι δεν είναι σωστό, διότι θα εμφανίσεις κάποιους συνδυασμούς πολλές φορές, αφού η σειρά δεν έχει σημασία.
Σκέψου ότι οι διαφορετικές μεταθέσεις 6 διαφορετικών αριθμών είναι 6! = 720. Εσύ φυσικά θα έχεις κάποιους ίδιους.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

oratios

  • Νέος
  • *
  • Μηνύματα: 6
Απ: Προτεινόμενη λύση
« Απάντηση #4 στις: 21 Οκτ 2014, 04:59:41 μμ »
Μα ναι, θεωρω διαφορετικη παιξιά την 1,2,3 απο την 1,3,2. Δεν ξερω εαν ειναι σωστο! Στην περιπτωση μου δεν μας ενδιαφερει η σειρα ειναι πιο δυσκολο!

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 983
  • Program or be Programmed
    • pseudoglossa.gr
Απ: Προτεινόμενη λύση
« Απάντηση #5 στις: 21 Οκτ 2014, 05:51:14 μμ »
Το πρόβλημα αυτό έχει ωραία αναδρομική λύση.

Μόλις το καταφέρω να τρέξει στον νέο διερμηνευτή θα την αναρτήσω!
Στάθης Στέργου - sstergouATgmailDOTcom - http://www.pseudoglossa.gr

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 983
  • Program or be Programmed
    • pseudoglossa.gr
Απ: Προτεινόμενη λύση
« Απάντηση #6 στις: 21 Οκτ 2014, 07:57:12 μμ »
Η ψευδογλώσσα θα αργήσει λίγο   ::)


Κώδικας: Python
  1. elements = [7, 15, 19, 23, 29, 37]
  2. l = len(elements)
  3.  
  4. def c100(pos, acc):
  5.     s = sum(acc)
  6.     if s == 100 and len(acc) == 6:
  7.         return [acc]
  8.     elif s > 100 or pos == l:
  9.         return []
  10.     else:
  11.         return c100(0, acc + [elements[pos]]) + c100(pos + 1, acc)
  12.  
  13. permutations = c100(0, [])
  14. combinations = set(map(tuple, map(sorted, permutations)))
  15.  
  16. print len(permutations)
  17. # 840
  18. print len(combinations)
  19. # 5
  20. print combinations
  21. # set([(7, 7, 15, 19, 23, 29), (7, 15, 15, 15, 19, 29), (7, 7, 19, 19, 19, 29), (7, 7, 7, 19, 23, 37), (7, 7, 15, 15, 19, 37)])
  22.  
  23.  
Στάθης Στέργου - sstergouATgmailDOTcom - http://www.pseudoglossa.gr

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 983
  • Program or be Programmed
    • pseudoglossa.gr
Απ: Προτεινόμενη λύση
« Απάντηση #7 στις: 21 Οκτ 2014, 08:37:03 μμ »
Και κάτι παρόμοιο. Αναρωτήθηκα με πόσες γραμμές μπορεί άραγε να το λύσει κανείς. Αυτό δίνει κατευθείαν τους συνδυασμούς.

Κώδικας: Clojure
  1. (defn c100 [elements acc]
  2.   (let [s (reduce + acc)]
  3.     (cond (and (= s 100) (= (count acc) 6)) (conj '() acc)
  4.           (or (> s 100) (empty? elements)) '()
  5.           :else (concat (c100 elements (conj acc (first elements))) (c100 (rest elements) acc)))))
  6.  
  7. ;; user> (c100 elements '())
  8. ;; ((37 23 19 7 7 7) (37 19 15 15 7 7) (29 23 19 15 7 7) (29 19 19 19 7 7) (29 19 15 15 15 7))
  9.  

Κώδικας: Python
  1. def c100(elements, acc):
  2.     if sum(acc) == 100 and len(acc) == 6:
  3.         return [acc]
  4.     elif sum(acc) > 100 or not elements:
  5.         return []
  6.     else:
  7.         return c100(elements, acc + [elements[0]]) + c100(elements[1:], acc)
  8.  
  9. # ή με δύο γραμμές:
  10.  
  11. def c100(elements, acc):
  12.         return [acc] if sum(acc) == 100 and len(acc) == 6 else [] if sum(acc) > 100 or not elements else c100(elements, acc + [elements[0]]) + c100(elements[1:], acc)
  13.  
« Τελευταία τροποποίηση: 21 Οκτ 2014, 11:04:43 μμ από sstergou »
Στάθης Στέργου - sstergouATgmailDOTcom - http://www.pseudoglossa.gr

ether

  • Επισκέπτης
Απ: Προτεινόμενη λύση
« Απάντηση #8 στις: 22 Οκτ 2014, 12:05:47 πμ »

ssimaiof

  • Πληροφορικοί Δυτικής Μακεδονίας
  • *
  • Μηνύματα: 23
Απ: Προτεινόμενη λύση
« Απάντηση #9 στις: 22 Οκτ 2014, 08:39:28 μμ »
Με πίνακα Δεικτών υλοποιείται με 2 εμφωλευμένες επαναλήψεις.
Έχει το πλεονέκτημα ότι λειτουργεί ανεξάρτητα του μεγέθους του πίνακα.
(Με εμφωλευμένες ΓΙΑ θα πρέπει να χρησιμοποιείσουμε τόσες ΓΙΑ όσες και οι ρίψεις,
δηλαδή αν αλλάξω τον αριθμό των ρίψεων θα πρέπει να αλλάξω και τον κώδικα!!)

Κώδικας: [Επιλογή]
ΠΡΟΓΡΑΜΜΑ Darts
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Ρ[6], Δ[6], i, Άθρ, Πλ
ΑΡΧΗ
  Ρ[1] <- 7
  Ρ[2] <- 15
  Ρ[3] <- 19
  Ρ[4] <- 23
  Ρ[5] <- 29
  Ρ[6] <- 37

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 6
    Δ[i] <- 1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  Πλ <- 0
  ΟΣΟ Δ[1] <= 6 ΕΠΑΝΑΛΑΒΕ
    Άθρ <- 0
    ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 6
      Άθρ <- Άθρ + Ρ[Δ[i]]
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΑΝ Άθρ = 100 ΤΟΤΕ
      Πλ <- Πλ + 1
      ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 6
        ΓΡΑΨΕ Ρ[Δ[i]], "  "
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
      ΓΡΑΨΕ
    ΤΕΛΟΣ_ΑΝ
    Δ[6] <- Δ[6] + 1
    ΓΙΑ i ΑΠΟ 6 ΜΕΧΡΙ 2 ΜΕ_ΒΗΜΑ -1
      ΑΝ Δ[i] > 6 ΤΟΤΕ
        Δ[i] <- 1
        Δ[i - 1] <- Δ[i - 1] + 1
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ "Πλήθος : ", Πλ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ Darts

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 983
  • Program or be Programmed
    • pseudoglossa.gr
Απ: Προτεινόμενη λύση
« Απάντηση #10 στις: 23 Οκτ 2014, 12:13:30 μμ »
Ωραία λύση.
Στάθης Στέργου - sstergouATgmailDOTcom - http://www.pseudoglossa.gr

ether

  • Επισκέπτης
Απ: Προτεινόμενη λύση
« Απάντηση #11 στις: 23 Οκτ 2014, 03:44:53 μμ »
Μια μικρή τροποποίηση στον κώδικα του ssimaiof ώστε να υπολογίζει, όπως και ο κώδικας του sstergou, συνδυασμούς (αντί για μεταθέσεις)
http://pastebin.com/WcWHbRUK

Με πίνακα Δεικτών υλοποιείται με 2 εμφωλευμένες επαναλήψεις.
Έχει το πλεονέκτημα ότι λειτουργεί ανεξάρτητα του μεγέθους του πίνακα.
(Με εμφωλευμένες ΓΙΑ θα πρέπει να χρησιμοποιείσουμε τόσες ΓΙΑ όσες και οι ρίψεις,
δηλαδή αν αλλάξω τον αριθμό των ρίψεων θα πρέπει να αλλάξω και τον κώδικα!!)

Κώδικας: [Επιλογή]
ΠΡΟΓΡΑΜΜΑ Darts
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Ρ[6], Δ[6], i, Άθρ, Πλ
ΑΡΧΗ
  Ρ[1] <- 7
  Ρ[2] <- 15
  Ρ[3] <- 19
  Ρ[4] <- 23
  Ρ[5] <- 29
  Ρ[6] <- 37

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 6
    Δ[i] <- 1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  Πλ <- 0
  ΟΣΟ Δ[1] <= 6 ΕΠΑΝΑΛΑΒΕ
    Άθρ <- 0
    ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 6
      Άθρ <- Άθρ + Ρ[Δ[i]]
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΑΝ Άθρ = 100 ΤΟΤΕ
      Πλ <- Πλ + 1
      ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 6
        ΓΡΑΨΕ Ρ[Δ[i]], "  "
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
      ΓΡΑΨΕ
    ΤΕΛΟΣ_ΑΝ
    Δ[6] <- Δ[6] + 1
    ΓΙΑ i ΑΠΟ 6 ΜΕΧΡΙ 2 ΜΕ_ΒΗΜΑ -1
      ΑΝ Δ[i] > 6 ΤΟΤΕ
        Δ[i] <- 1
        Δ[i - 1] <- Δ[i - 1] + 1
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ "Πλήθος : ", Πλ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ Darts