Θέμα: Για δυνατούς λύτες

[epsilonXi]

Στο Ποδοσφαιρικό Κύπελλο Ελλάδος συμμετέχουν 64 ομάδες. Στον πρώτο γύρο οι 64 ομάδες χωρίζονται σε 32 ζευγάρια και κάθε ζευγάρι παίζει έναν αγώνα. Όποια ομάδα πετύχει περισσότερα γκολ στον αγώνα προκρίνεται στον επόμενο γύρο του Κυπέλλου. Στον επόμενο γύρο συμμετέχουν 32 ομάδες, οι οποίες χωρίζονται σε 16 ζευγάρια κ.ο.κ. ώσπου στον τελικό γύρο έχουν απομείνει 2 μόνο ομάδες, και από τον μεταξύ τους αγώνα προκύπτει ο νικητής του Κυπέλλου. Από τις ομάδες που συμμετέχουν στον κάθε γύρο, θεωρήστε ότι η 1η ομάδα αγωνίζεται με αντίπαλο τη 2η, η 3η με την 4η, η 5η με την 6η κ.ο.κ. Να γράψετε αλγόριθμο με τον οποίο:
   1. Να καταγράφονται σε έναν πίνακα τα ονόματα των ομάδων, και σε παράλληλο πίνακα το όνομα της πόλης από την οποία προέρχεται η αντίστοιχη ομάδα. Θεωρήστε ότι τα ονόματα όλων των ομάδων θα είναι διαφορετικά μεταξύ τους. (Μονάδες 03/20)
   2. Για κάθε γύρο και για κάθε ζευγάρι αντιπάλων μέχρι και τον τελικό θα εμφανίζει ένα μήνυμα με τα ονόματα των δύο αντιπάλων και μετά θα ρωτά πόσα γκολ έβαλε η κάθε μία, με τον περιορισμό το σκορ να μην είναι ισόπαλο. Όταν δίνεται ισόπαλο σκορ, να εμφανίζεται κατάλληλο μήνυμα. Η ομάδα με τα περισσότερα γκολ πρέπει να προκρίνεται στον επόμενο γύρο.  (Μονάδες 10/20)
   3. Όταν ολοκληρώνεται η διοργάνωση, ο αλγόριθμος θα πρέπει να ανακοινώνει:
       α. ποιά ομάδα είναι κυπελλούχος. (Μονάδες 01/20)
       β. πόσοι αγώνες έγιναν στη διοργάνωση μεταξύ ομάδων της ίδιας πόλης. (Μονάδες 02/20)
       γ. από ποιά πόλη προέρχονται οι περισσότερες ομάδες. (Μονάδες 05/20)

[panastros]

Μια λύση που μου φαίνεται οτι κανει τη δουλειά της, αλλά "χαλάει" τους αρχικούς πίνακες για να μη "βαρύνει" τον αλγόριθμο. Βέβαια το (3.γ) πρέπει να υλοποιηθεί πριν χαλάσουν οι πίνακες.

Αλγόριθμος ταδε
Δεδομένα // ομ, ΟΝ, Π //
! ερώημα (3.γ)
! γίνεται να φτιαχτούν οι ΔΠ και ΣΟΜΠ και χωρίς ταξινόμηση με διαρκείς
! σειριακές αναζητήσεις αλλά μπλέκει με πολλόυς δείκτες η λύση και μπερδεύει.
! έτσι νομίζω ειναι ευκολότερα κατανοητό για τα παιδιά...
! Σίγουρα θα υπάρχει κ λύση που υπολογίζει το (3.γ) παράλληλα με τις υπόλοιπες
! επεξεργασίες, ας την ποστάρει κάποιος που "την κατέχει"...
Για κ από 1 μέχρι ομ
  ΠΤ[κ] ← Π[κ]
Τέλος_επανάληψης
Για λ από 2 μέχρι ομ
  Για κ από ομ μέχρι λ με_βήμα -1
    Αν ΠΤ[κ - 1] > ΠΤ[κ] τότε
      Αντιμετάθεσε ΠΤ[κ - 1], ΠΤ[κ]
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης
ξ ← 1
ΔΠ[ξ] ← ΠΤ[1]
ΣΟΜΠ[ξ] ← 1
Για κ από 2 μέχρι ομ
  Αν ΠΤ[κ - 1] = ΠΤ[κ] τότε
    ΣΟΜΠ[ξ] ← ΣΟΜΠ[ξ] + 1
  αλλιώς
    ξ ← ξ + 1
    ΔΠ[ξ] ← ΠΤ[κ]
    ΣΟΜΠ[ξ] ← 1
  Τέλος_αν
Τέλος_επανάληψης
μεγ ← 0
Για κ από 1 μέχρι ξ
  Αν ΣΟΜΠ[κ] > μεγ τότε
    μεγ ← ΣΟΜΠ[κ]
    θ ← κ
  Τέλος_αν
Τέλος_επανάληψης

! υπόλοιπη άσκηση

! ομ ← 64
πλ ← 0
Αρχή_επανάληψης

  Για λ από 1 μέχρι (ομ div 2)
    α ← 2*λ - 1
    β ← 2*λ
    Εμφάνισε " παίζει η ομάδα :", ΟΝ[α], " με την ομάδα : ", ΟΝ[β]
    Εμφάνισε " Δώσε ...."
    Διάβασε γ, δ
    Όσο (γ = δ) επανάλαβε
      Εμφάνισε " λαθος... ξαναδώσε"
      Διάβασε γ, δ
    Τέλος_επανάληψης
    Αν (γ > δ) τότε
      νικ ← ΟΝ[α]
      ποληνικ ← Π[α]
    αλλιώς
      νικ ← ΟΝ[β]
      ποληνικ ← Π[β]
    Τέλος_αν
    Αν (Π[α] = Π[β]) τότε πλ ← πλ + 1
    ΟΝ[λ] ← νικ
    Π[λ] ← ποληνικ
  Τέλος_επανάληψης

  ομ ← ομ div 2
  Αν ομ = 1 τότε τελνικ ← νικ
Μέχρις_ότου ομ = 1

Εμφάνισε " αγωνες ιδιας πόλης ", πλ
Εμφάνισε " τελικός νικητής: ", τελνικ
Εμφάνισε " οι περισσότερες ομάδες προέρχονται από την πόλη: ", ΔΠ[θ]
Τέλος ταδε

[epsilonXi]

αλγόριθμος θέμα3

για ομ από 1 μέχρι 64
  εμφάνισε “Όνομα ομάδας:”
  διάβασε ΟΝ[ομ]
  εμφάνισε “Πόλη που εδρεύει:”
  διάβασε ΠΟΛΗ[ομ]
  ΠΑΙΖΕΙ[ομ] ← αληθής ! Εξτρα πίνακας που θα παίρνει την τιμή ψευδής όταν η ομάδα αποκλείεται
τέλος_επανάληψης

π ← 0 ! μετρητής για το πόσοι αγώνες έγιναν μεταξύ ομάδων από την ίδια πόλη
για γύρο από 5 μέχρι 0 με βήμα -1 ! γίνονται 6 γύροι συνολικά, αλλά βολεύει από 5 μέχρι 0
  β ← 0
  για αγώνα από 1 μέχρι 2^γύρο ! για να βγαίνει εύκολα ο αριθμός αγώνων ανά γύρο (32,16,8,4,2,1)
    α ← β  ! αναζητώ σειριακά να βρω ομάδα που να μην έχει αποκλειστεί
    αρχή_επανάληψης
      α ← α + 1
    μέχρις_ότου ΠΑΙΖΕΙ[α] = αληθής
    β ← α ! αναζητώ σειριακά να βρω την επόμενη ομάδα που να μην έχει αποκλειστεί
    αρχή_επανάληψης
      β ← β + 1
    μέχρις_ότου ΠΑΙΖΕΙ[β] = αληθής
    αν ΠΟΛΗ[α] = ΠΟΛΗ[β] τότε ! για την καταμέτρηση των αγώνων μεταξύ ομάδων απ'την ίδια πόλη
      π ← π + 1
    τέλος_αν
    εμφάνισε “Αγώνας μεταξύ:”ΟΝ[α], “-”, ΟΝ[β]
    αρχή_επανάληψης ! Έλεγχος εγκυρότητας για να μη δοθεί ισόπαλο σκορ
      εμφάνισε “Σκορ αγώνα:”
      διάβασε γκολ_α, γκολ_β
      αν γκολ_α = γκολ_β τότε
        εμφάνισε “Δεν επιτρέπεται ισόπαλο σκορ.”
      τέλος_αν
    μέχρις_ότου γκολ_α <> γκολ_β
    αν γκολ_α > γκολ_β τότε ! όποια ομάδα έχει τα λιγότερα γκολ, δεν παίζει άλλο
      ΠΑΙΖΕΙ[β] ← ψευδής
    αλλιώς
      ΠΑΙΖΕΙ[α] ← ψευδής
    τέλος_αν
  τέλος_επανάληψης
τέλος_επανάληψης

αν γκολ_α > γκολ_β τότε ! Ο νικητής του τελευταίου αγώνα είναι ο κυπελλούχος
   εμφάνισε “Κυπελλούχος ομάδα:”, ΟΝ[α]
αλλιώς
  εμφάνισε “Κυπελλούχος ομάδα:”, ΟΝ[β]
τέλος_αν

εμφάνισε π, “αγώνες έγιναν μεταξύ ομάδων της ίδιας πόλης.”

δ ← 1 ! για να μετρήσω το πλήθος των διαφορετικών πόλεων, και σίγουρα υπάρχει 1 πόλη
CITY[1] ← ΠΟΛΗ[1] ! Στον πίνακα city θέλω να βάλω τα ονόματα των διαφορετικών πόλεων
ΠΛΗΘ[1] ← 1 ! για να μετρήσω το πλήθος των ομάδων που εδρεύουν σε κάθα διαφορετική πόλη
για ομ από 2 μέχρι 64 ! για κάθε άλλη ομάδα
  κ ← 0
  αρχή_επανάληψης  !αναζητώ σειριακά μήπως την έχω βάλει ήδη στον πίνακα city
    κ ← κ + 1
  μέχρις_ότου ΠΟΛΗ[ομ] = CITY[κ] ή κ = δ
  αν ΠΟΛΗ[ομ] = CITY[κ] τότε ! Αν την έχω βάλει ήδη, απλά μετράω ότι βρήκα άλλη μια ομάδα
    ΠΛΗΘ[δ] ← ΠΛΗΘ[δ] + 1   ! από την ίδια πόλη
  αλλιώς
    δ ← δ + 1  ! μετράω ότι βρήκα άλλη μια διαφορετική πόλη
    CITY[δ] ← ΠΟΛΗ[ομ] ! Την αντιγράφω στον πίνακα city
    ΠΛΗΘ[δ] ← 1 ! και σημειώνω ότι έχω βρει 1 ομάδα από αυτήν την πόλη
  τέλος_αν
τέλος_επανάληψης

μαξ ← 0  ! άρα μετά το μόνο που μένει είναι να βρεθεί το μεγαλύτερο ΠΛΗΘ
για χ από 1 μέχρι δ
  αν ΠΛΗΘ[χ] > μαξ τότε
    μαξ ← ΠΛΗΘ[χ]
    θ ← CITY[χ]
  τέλος_αν
τέλος_επανάληψης
εμφάνισε “Οι περισσότερες ομάδες έχουν ως έδρα την πόλη”, θ

τέλος θέμα3

[epsilonXi]

Άλλη σκέψη εντελώς
Στον 1ο γύρο νικήτρια του ζευγαριού 1-2, μπαίνει στη θέση 1, του ζευγαριού 3-4 στη θέση 3, του ζευγαριού 5-6 στη θέση 5 κ.ο.κ.
Έτσι, στο 2ο γύρο θα παίξει ζευγάρι 1-3, με τον νικητή να μπαίνει στη θέση 1, ζευγάρι 5-7, με τον νικητή να μπαίνει στη θέση 5, 9-11 με το νικητή να μπαίνει στη θέση 9 κ.ο.κ.
Έτσι στον 3ο γύρο θα παίξει ζευγάρι 1-5 με το νικητή να μπαίνει στη θέση 1, ζευγάρι 9-13 με το νικητή να μπαίνει στη θέση 9, κ.ο.κ.
Έτσι μπορώ με «μαθηματικό» τρόπο να λέω ποιός είναι αντίπαλος με ποιον, και να μη χρειάζομαι τις σειριακές αναζητήσεις... επιπλέον, έτσι, ο κυπελλούχος θα καταλήξει στη θέση 1 σίγουρα


αλγόριθμος θέμα3

για ομ από 1 μέχρι 64
  εμφάνισε “Όνομα ομάδας:”
  διάβασε ΟΝ[ομ]
  εμφάνισε “Πόλη που εδρεύει:”
  διάβασε ΠΟΛΗ[ομ]
τέλος_επανάληψης


π ← 0
για γύρο από 1 μέχρι 6
  για α από 1 μέχρι 64 με βήμα 2^γύρο
    β ← α+2^(γύρο-1)
    αν ΠΟΛΗ[α] = ΠΟΛΗ[β] τότε ! για την καταμέτρηση των αγώνων μεταξύ ομάδων απ'την ίδια πόλη
      π ← π + 1
    τέλος_αν
    εμφάνισε “Αγώνας μεταξύ:”ΟΝ[α], “-”, ΟΝ[β]
    αρχή_επανάληψης ! Έλεγχος εγκυρότητας για να μη δοθεί ισόπαλο σκορ
      εμφάνισε “Σκορ αγώνα:”
      διάβασε γκολ_α, γκολ_β
      αν γκολ_α = γκολ_β τότε
        εμφάνισε “Δεν επιτρέπεται ισόπαλο σκορ.”
      τέλος_αν
    μέχρις_ότου γκολ_α <> γκολ_β
    αν γκολ_α < γκολ_β τότε !
      αντιμετάθεσε ΟΝ[α], ΟΝ[β]
      αντιμετάθεσε ΠΟΛΗ[α], ΠΟΛΗ[β]
    τέλος_αν
  τέλος_επανάληψης
τέλος_επανάληψης

εμφάνισε “Κυπελλούχος ομάδα:”, ΟΝ[1]

εμφάνισε π, “αγώνες έγιναν μεταξύ ομάδων της ίδιας πόλης.”

δ ← 1 ! για να μετρήσω το πλήθος των διαφορετικών πόλεων, και σίγουρα υπάρχει 1 πόλη
CITY[1] ← ΠΟΛΗ[1] ! Στον πίνακα city θέλω να βάλω τα ονόματα των διαφορετικών πόλεων
ΠΛΗΘ[1] ← 1 ! για να μετρήσω το πλήθος των ομάδων που εδρεύουν σε κάθε διαφορετική πόλη
για ομ από 2 μέχρι 64 ! για κάθε άλλη ομάδα
  κ ← 0
  αρχή_επανάληψης  ! αναζητώ σειριακά μήπως έχω βάλει ήδη στον πίνακα city την πόλη της
    κ ← κ + 1
  μέχρις_ότου ΠΟΛΗ[ομ] = CITY[κ] ή κ = δ
  αν ΠΟΛΗ[ομ] = CITY[κ] τότε ! Αν την έχω βάλει ήδη, απλά μετράω ότι βρήκα άλλη μια ομάδα
    ΠΛΗΘ[δ] ← ΠΛΗΘ[δ] + 1   ! από την ίδια πόλη
  αλλιώς
    δ ← δ + 1  ! μετράω ότι βρήκα άλλη μια διαφορετική πόλη
    CITY[δ] ← ΠΟΛΗ[ομ] ! Την αντιγράφω στον πίνακα city
    ΠΛΗΘ[δ] ← 1 ! και σημειώνω ότι έχω βρει 1 ομάδα από αυτήν την πόλη
  τέλος_αν
τέλος_επανάληψης

μαξ ← 0  ! άρα μετά το μόνο που μένει είναι να βρεθεί το μεγαλύτερο ΠΛΗΘ
για χ από 1 μέχρι δ
  αν ΠΛΗΘ[χ] > μαξ τότε
    μαξ ← ΠΛΗΘ[χ]
    θ ← CITY[χ]
  τέλος_αν
τέλος_επανάληψης
εμφάνισε “Οι περισσότερες ομάδες έχουν ως έδρα την πόλη”, θ

τέλος θέμα3

[epsilonXi]

Εδώ η μεταβλητή α παίρνει τις τιμές 1,3,5,7... και η μεταβλητή β παίρνει αντίστοιχα τις τιμές 2,4,6,8... δηλαδή κάθε ομάδα σε περιττή θέση θα παίζει με την ομάδα στην ακόλουθη άρτια θέση...

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


αλγόριθμος θέμα3

για ομ από 1 μέχρι 64
  εμφάνισε “Όνομα ομάδας:”
  διάβασε ΟΝ[ομ]
  εμφάνισε “Πόλη που εδρεύει:”
  διάβασε ΠΟΛΗ[ομ]
  COPY[ομ] ← ΠΟΛΗ[ομ] !αντιγραφο γιατί το ένα από τα δύο το καταστρέφω
τέλος_επανάληψης


π ← 0
για γύρο από 6 μέχρι 1 με βήμα -1
  προκ ← 0
  για α από 1 μέχρι 2^γύρο με βήμα 2
    β ← α+1
    αν COPY[α] = COPY[β] τότε ! για την καταμέτρηση των αγώνων μεταξύ ομάδων απ'την ίδια πόλη
      π ← π + 1
    τέλος_αν
    εμφάνισε “Αγώνας μεταξύ:”ΟΝ[α], “-”, ΟΝ[β]
    αρχή_επανάληψης ! Έλεγχος εγκυρότητας για να μη δοθεί ισόπαλο σκορ
      εμφάνισε “Σκορ αγώνα:”
      διάβασε γκολ_α, γκολ_β
      αν γκολ_α = γκολ_β τότε
        εμφάνισε “Δεν επιτρέπεται ισόπαλο σκορ.”
      τέλος_αν
    μέχρις_ότου γκολ_α <> γκολ_β
    προκ <-- προκ + 1
    αν γκολ_α > γκολ_β τότε !
      ΟΝ[προκ] ← ΟΝ[α]
      CITY[προκ] ← CITY[α]
    αλλιώς
      ΟΝ[προκ] ← ΟΝ[β]
      CITY[προκ] ← CITY[β]
    τέλος_αν
  τέλος_επανάληψης
τέλος_επανάληψης

εμφάνισε “Κυπελλούχος ομάδα:”, ΟΝ[1]

εμφάνισε π, “αγώνες έγιναν μεταξύ ομάδων της ίδιας πόλης.”

δ ← 1 ! για να μετρήσω το πλήθος των διαφορετικών πόλεων, και σίγουρα υπάρχει 1 πόλη
CITY[1] ← ΠΟΛΗ[1] ! Στον πίνακα city θέλω να βάλω τα ονόματα των διαφορετικών πόλεων
ΠΛΗΘ[1] ← 1 ! για να μετρήσω το πλήθος των ομάδων που εδρεύουν σε κάθε διαφορετική πόλη
για ομ από 2 μέχρι 64 ! για κάθε άλλη ομάδα
  κ ← 0
  αρχή_επανάληψης  ! αναζητώ σειριακά μήπως έχω βάλει ήδη στον πίνακα city την πόλη της
    κ ← κ + 1
  μέχρις_ότου ΠΟΛΗ[ομ] = CITY[κ] ή κ = δ
  αν ΠΟΛΗ[ομ] = CITY[κ] τότε ! Αν την έχω βάλει ήδη, απλά μετράω ότι βρήκα άλλη μια ομάδα
    ΠΛΗΘ[δ] ← ΠΛΗΘ[δ] + 1   ! από την ίδια πόλη
  αλλιώς
    δ ← δ + 1  ! μετράω ότι βρήκα άλλη μια διαφορετική πόλη
    CITY[δ] ← ΠΟΛΗ[ομ] ! Την αντιγράφω στον πίνακα city
    ΠΛΗΘ[δ] ← 1 ! και σημειώνω ότι έχω βρει 1 ομάδα από αυτήν την πόλη
  τέλος_αν
τέλος_επανάληψης

μαξ ← 0  ! άρα μετά το μόνο που μένει είναι να βρεθεί το μεγαλύτερο ΠΛΗΘ
για χ από 1 μέχρι δ
  αν ΠΛΗΘ[χ] > μαξ τότε
    μαξ ← ΠΛΗΘ[χ]
    θ ← CITY[χ]
  τέλος_αν
τέλος_επανάληψης
εμφάνισε “Οι περισσότερες ομάδες έχουν ως έδρα την πόλη”, θ

τέλος θέμα3