Προτεινόμενη λύση

Ξεκίνησε από oratios, 21 Οκτ 2014, 04:09:00 ΜΜ

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

oratios

Στο παιχνίδι Darts (βελάκια) τα επιτρεπτά σκορ με ένα βέλος είναι: 7, 15, 19, 23, 29 και 37. Στόχος του παιχνιδιού είναι να συγκεντρωθούν 100 βαθμοί ακριβώς με 6 βολές. Ποιοι είναι οι δυνατοί συνδυασμοί για να επιτευχθεί αυτό;
(Θεωρήστε ότι τα 6 διαφορετικά επιτρεπτά σκορ βρίσκονται σε πίνακα ακεραίων Ρ[6]).

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


petrosp13

Από ότι καταλαβαίνω, επιτρέπεται να ρίξει 2 φορές το ίδιο σκορ;
Μια ιδέα που μειώνει τις απαιτούμενες επαναλήψεις είναι ότι αν το άθροισμα φτάνει πάνω από ένα επιτρεπτό όριο, δεν χρειάζεται να ελεγχθούν και οι 6 πιθανοί βαθμοί
Πχ, πάνω από 73 δεν χρειάζεται η τελευταία, πάνω από 81, οι 4 τελευταίες
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

oratios

Φυσικά και επιτρέπεται να ριξεις 2 φορες το ιδιο αφου εαν ηταν διακτιτες οι ριψεις θα επρεπε: 7+15+19+23+29+37(=130) να κανει 100!

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


evry

Και με εξαπλή επανάληψη πάλι δεν είναι σωστό, διότι θα εμφανίσεις κάποιους συνδυασμούς πολλές φορές, αφού η σειρά δεν έχει σημασία.
Σκέψου ότι οι διαφορετικές μεταθέσεις 6 διαφορετικών αριθμών είναι 6! = 720. Εσύ φυσικά θα έχεις κάποιους ίδιους.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

oratios

Μα ναι, θεωρω διαφορετικη παιξιά την 1,2,3 απο την 1,3,2. Δεν ξερω εαν ειναι σωστο! Στην περιπτωση μου δεν μας ενδιαφερει η σειρα ειναι πιο δυσκολο!

sstergou

Το πρόβλημα αυτό έχει ωραία αναδρομική λύση.

Μόλις το καταφέρω να τρέξει στον νέο διερμηνευτή θα την αναρτήσω!

sstergou

Η ψευδογλώσσα θα αργήσει λίγο   ::)


Κώδικας: python
elements = [7, 15, 19, 23, 29, 37]
l = len(elements)

def c100(pos, acc):
    s = sum(acc)
    if s == 100 and len(acc) == 6:
        return [acc]
    elif s > 100 or pos == l:
        return []
    else:
        return c100(0, acc + [elements[pos]]) + c100(pos + 1, acc)

permutations = c100(0, [])
combinations = set(map(tuple, map(sorted, permutations)))

print len(permutations) 
# 840
print len(combinations)
# 5
print combinations
# 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)])

sstergou

#7
Και κάτι παρόμοιο. Αναρωτήθηκα με πόσες γραμμές μπορεί άραγε να το λύσει κανείς. Αυτό δίνει κατευθείαν τους συνδυασμούς.

Κώδικας: clojure
(defn c100 [elements acc]
  (let [s (reduce + acc)]
    (cond (and (= s 100) (= (count acc) 6)) (conj '() acc)
          (or (> s 100) (empty? elements)) '()
          :else (concat (c100 elements (conj acc (first elements))) (c100 (rest elements) acc)))))

;; user> (c100 elements '())
;; ((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))


Κώδικας: python
def c100(elements, acc):
    if sum(acc) == 100 and len(acc) == 6:
        return [acc]
    elif sum(acc) > 100 or not elements:
        return []
    else:
        return c100(elements, acc + [elements[0]]) + c100(elements[1:], acc)

# ή με δύο γραμμές:

def c100(elements, acc):
        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)


ssimaiof

Με πίνακα Δεικτών υλοποιείται με 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


ether

Μια μικρή τροποποίηση στον κώδικα του ssimaiof ώστε να υπολογίζει, όπως και ο κώδικας του sstergou, συνδυασμούς (αντί για μεταθέσεις)
http://pastebin.com/WcWHbRUK

Παράθεση από: ssimaiof στις 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