Θέμα: Τελικό Επαναληπτικό Διαγώνισμα 2014-2015 από το Στέκι

[Αθανάσιος Πέρδος]

Μιας και ασχοληθήκα με τον Πάπα πρωτύτερα παραθέτω μία ενδεικτική λύση. Απλά για να υπάρχει η δυνατότητα να γίνει παρακολούθηση μεταβλητών θεωρώ τους υποψήφιους 5 και τους καρδινάλιους 10.

Κώδικας: [Επιλογή]

Αλγόριθμος ΘΓ

Για i από 1 μέχρι 5
  Διάβασε ΥΠΟΨ[i]
  ΦΑΒ[i] ← Αληθής
Τέλος_επανάληψης


Αρχή_επανάληψης

  Για i από 1 μέχρι 5
    ΣΨ[i] ← 0
  Τέλος_επανάληψης

  Για i από 1 μέχρι 10
    Διάβασε ον
    j ← 1
    done ← Ψευδής
    Όσο done = Ψευδής και j ≤ 5 επανάλαβε
      Αν ΥΠΟΨ[j] = ον τότε
        ΣΨ[j] ← ΣΨ[j] + 1
        done ← Αληθής
      αλλιώς
        j ← j + 1
      Τέλος_αν
    Τέλος_επανάληψης
  Τέλος_επανάληψης

  μεγ ← ΣΨ[1]
  θμεγ ← 1
  Για j από 2 μέχρι 5
    Αν μεγ < ΣΨ[j] τότε
      μεγ ← ΣΨ[j]
      θμεγ ← j
    Τέλος_αν
  Τέλος_επανάληψης

  Αν μεγ ≥ 2/3* 10 τότε
    Εμφάνισε "Λευκός καπνός"
  αλλιώς
    Εμφάνισε "Μαύρος καπνός"
  Τέλος_αν

  Για j από 1 μέχρι 5
    Αν ΣΨ[j] ≠ μεγ τότε
      ΦΑΒ[j] ← Ψευδής
    Τέλος_αν
  Τέλος_επανάληψης

Μέχρις_ότου μεγ ≥ 2/3* 10

Εμφάνισε ΥΠΟΨ[θμεγ]
Αν ΦΑΒ[θμεγ] = Αληθής τότε
  Εμφάνισε "Φαβορί"
αλλιώς
  Εμφάνισε "Αουτσάιντερ"
Τέλος_αν


Τέλος ΘΓ


[noname]

Ας γράψω και εγώ με τη σειρά μου μια προτεινόμενη λύση για το Θέμα Γ.

Κώδικας: [Επιλογή]

Αλγόριθμος ΘέμαΓ
Για ι από 1 μέχρι 18
Διάβασε ΥΠΟΨ[ι]
ΠΡΩΤΙΕΣ[ι] <- 0
Τέλος_επανάληψης
ΨΗΦΟΦΟΡΙΕΣ <- 0
Αρχή_επανάληψης
ΨΗΦΟΦΟΡΙΕΣ <- ΨΗΦΟΦΟΡΙΕΣ + 1
Για ι από 1 μέχρι 18
Ψ[ι] <- 0
Τέλος_επανάληψης
Για ι από 1 μέχρι 115
Διάβασε ΟΝ
ξ <- 0
Αρχή_επανάληψης
ξ <- ξ + 1
Μέχρις_ότου ΥΠΟΨ[ξ] = ΟΝ
Ψ[ξ] <- Ψ[ξ] + 1
Τέλος_επανάληψης
θ <- 1
Για ξ από 2 μέχρι 18
Αν Ψ[ξ]>Ψ[θ] τότε θ <- ξ
Τέλος_επανάληψης
ΠΡΩΤΙΕΣ[θ] <- ΠΡΩΤΙΕΣ[θ] + 1
Αν Ψ[θ] < 2/3*115 τότε
Εμφάνισε "Μαύρος καπνός"
Τέλος_αν
Μέχρις_ότου Ψ[θ] >= 2/3*115
Εμφάνισε "Λευκός καπνός"
Εμφάνισε ΥΠΟΨ[θ]
Αν ΨΗΦΟΦΟΡΙΕΣ = ΠΡΩΤΙΕΣ[θ] τότε
Εμφάνισε "Ο Πάπας ήταν φαβορί"
αλλιώς
Εμφάνισε "Αουτσάιντερ"
Τέλος_αν
Τέλος ΘέμαΓ


[noname]

Να και μια βιαστική λύση για το θέμα Δ.

Κώδικας: [Επιλογή]

ΠΡΟΓΡΑΜΜΑ ΘΕΜΑΔ
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ:Ι, Κ, Μ
ΠΡΑΓΜΑΤΙΚΕΣ:Τ, ΘΤ, Σ, ΜΟ, Θ[1000,1000], Π[1000,1000]
ΛΟΓΙΚΕΣ: ΙΣΧΥΕΙ
ΑΡΧΗ
ΔΙΑΒΑΣΕ Τ
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 1000
ΓΙΑ Κ ΑΠΟ 1 ΜΕΧΡΙ 1000
Θ[Ι,Κ] <- Τ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΔΙΑΒΑΣΕ ΘΤ
ΜΕΧΡΙΣ_ΟΤΟΥ ΘΤ >= Τ+50
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 1000
Θ[Ι,1] <- ΘΤ
Θ[Ι,1000] <- ΘΤ
Θ[1,Ι] <- ΘΤ
Θ[1000,Ι] <- ΘΤ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Μ <- 0
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ Ι ΑΠΟ 2 ΜΕΧΡΙ 999
ΓΙΑ Κ ΑΠΟ 2 ΜΕΧΡΙ 999
Π[Ι,Κ] <- Φ(Θ, Ι, Κ)
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Σ <- 0
ΓΙΑ Ι ΑΠΟ 2 ΜΕΧΡΙ 999
ΓΙΑ Κ ΑΠΟ 2 ΜΕΧΡΙ 999
Θ[Ι,Κ] <- Π[Ι,Κ]
Σ <- Σ + Θ[Ι,Κ]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΜΟ <- Σ/998^2
Μ <- Μ + 1
ΜΕΧΡΙΣ_ΟΤΟΥ ΘΤ-ΜΟ<0.5
ΓΡΑΨΕ Μ
ΙΣΧΥΕΙ <- ΑΛΗΘΗΣ
Ι <- 2
ΟΣΟ Ι <= 500 ΚΑΙ ΙΣΧΥΕΙ ΕΠΑΝΑΛΑΒΕ
ΑΝ Θ[Ι,Ι]>Θ[Ι-1,Ι-1] Ή Θ[500+Ι,500+Ι]<Θ[500+Ι-1,500+Ι-1] ΤΟΤΕ
ΙΣΧΥΕΙ <- ΨΕΥΔΗΣ
ΑΛΛΙΩΣ
Ι <- Ι + 1
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝ ΙΣΧΥΕΙ ΤΟΤΕ
ΓΡΑΨΕ 'ΙΣΧΥΕΙ'
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'ΔΕΝ ΙΣΧΥΕΙ'
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

ΣΥΝΑΡΤΗΣΗ Φ(Θ, Ι, Κ):ΠΡΑΓΜΑΤΙΚΗ
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ:Ι, Κ, Μ, Ν
ΠΡΑΓΜΑΤΙΚΕΣ:Σ, Θ[1000,1000]
ΑΡΧΗ
Σ <- 0
ΓΙΑ Μ ΑΠΟ Ι-1 ΜΕΧΡΙ Ι+1
ΓΙΑ Ν ΑΠΟ Κ-1 ΜΕΧΡΙ Κ+1
Σ <- Σ + Θ[Μ,Ν]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Σ <- Σ + Θ[Ι,Κ]
Φ <- Σ/10
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ


[Αθανάσιος Πέρδος]

Ας γράψω και εγώ με τη σειρά μου μια προτεινόμενη λύση για το Θέμα Γ.

Κώδικας: [Επιλογή]

Αλγόριθμος ΘέμαΓ
Για ι από 1 μέχρι 18
Διάβασε ΥΠΟΨ[ι]
ΠΡΩΤΙΕΣ[ι] <- 0
Τέλος_επανάληψης
ΨΗΦΟΦΟΡΙΕΣ <- 0
Αρχή_επανάληψης
ΨΗΦΟΦΟΡΙΕΣ <- ΨΗΦΟΦΟΡΙΕΣ + 1
Για ι από 1 μέχρι 18
Ψ[ι] <- 0
Τέλος_επανάληψης
Για ι από 1 μέχρι 115
Διάβασε ΟΝ
ξ <- 0
Αρχή_επανάληψης
ξ <- ξ + 1
Μέχρις_ότου ΥΠΟΨ[ξ] = ΟΝ
Ψ[ξ] <- Ψ[ξ] + 1
Τέλος_επανάληψης
θ <- 1
Για ξ από 2 μέχρι 18
Αν Ψ[ξ]>Ψ[θ] τότε θ <- ξ
Τέλος_επανάληψης
ΠΡΩΤΙΕΣ[θ] <- ΠΡΩΤΙΕΣ[θ] + 1
Αν Ψ[θ] < 2/3*115 τότε
Εμφάνισε "Μαύρος καπνός"
Τέλος_αν
Μέχρις_ότου Ψ[θ] >= 2/3*115
Εμφάνισε "Λευκός καπνός"
Εμφάνισε ΥΠΟΨ[θ]
Αν ΨΗΦΟΦΟΡΙΕΣ = ΠΡΩΤΙΕΣ[θ] τότε
Εμφάνισε "Ο Πάπας ήταν φαβορί"
αλλιώς
Εμφάνισε "Αουτσάιντερ"
Τέλος_αν
Τέλος ΘέμαΓ


Αν υπάρχει ισοβαθμία πριν από την εκλογή αυξάνεται μόνο ο αριθμός των πρωτιών του πρώτου υποψηφίου που έχει τις περισσότερες ψήφους. Μία τροποποίηση εύρεσης μεγίστου πολλές φορές, λύνει το πρόβλημα

[Λαμπράκης Μανώλης]

Καλησπέρα

ήθελα την γμώμη σας για δύο θέματα ... επιτρέψτε μου και μία ανάλυση ώστε 1) να εξηγήσω εγώ στους μαθητές και 2) εσείς σε εμένα αν έχω λάθος   

Α.3
Για i από N-1 μέχρι  1 με_βήμα -1   
     Για j από 1 μέχρι i με_βήμα +1 
         Αν A[ j ] > A[j + 1] τότε
             Αντιμετάθεσε A[ j ], A[ j+1 ]
       Τέλος_αν
    Τέλος_επανάληψης
Τέλος_επανάληψης

Α.5

α) --> Εμφανίζοναται 4 χαρακτήρες * (υποθέτω η εύκολη μονάδα, βρίσκεται μόνο στην επανάληψη Για i από 1 μέχρι 4)
β) --> Η εντολή Για j από 1 μέχρι i έχει μεταβλητή τιμή "μέχρι" οπότε θα εκτελέσει τις εξής επαναλήψεις

Για j από 1 μέχρι 1  --> 1 εμφάνισε
Για j από 1 μέχρι 2  --> 2 εμφάνισε
Για j από 1 μέχρι 3  --> 3 εμφάνισε
Για j από 1 μέχρι 4  --> 4 εμφάνισε

σύνολο το άθροισμά τους, δηλαδή 10 χαρακτήρες "+"

γ) η εντολή εμφάνισε "#" θα εκτελεστεί

--> 4 φορές στον βρόγχο του i
--> 10 φορές στον βρόγχο του j (η παραπάνω ανάλυση)
--> ο τριτος εμφωλευμένος βρόγχος του κ θα εκτελεστεί 101 φορές (από 101 μέχρο 200 θα ήταν 100) επί 10 φορές οι δύο προγούμενες που είναι εμφωλευμένος

άρα σύνολο 101*10  +  4 + 10  επαναλήψεις  (ελπίζω να μην χάθηκα στην μετάφραση...    ) 

περιμένω τα σχόλιά σας

ευχαριστώ

[Νίκος Αδαμόπουλος]

Καλησπέρα

ήθελα την γμώμη σας για δύο θέματα ... επιτρέψτε μου και μία ανάλυση ώστε 1) να εξηγήσω εγώ στους μαθητές και 2) εσείς σε εμένα αν έχω λάθος   

Ok και τα δύο!

Όσο για το:
101*10  +  4 + 10 = 1024 ...  Τυχαίο;   

[Λαμπράκης Μανώλης]

οκ ευχαριστώ ...

1024  ε ?? όντως δεν έκανα την πράξη .... 2^10 έχουν και κρυφά μηνύματα τα θέματα λίγο εδώ, λίγο το θέμα με τον πάπα,βατικανό,  πολύ μυστήριο φέτος .... 

[tdiam]

Εξαιρετικά θέματα, μπράβο στην ομάδα για τη φαντασία και το χρόνο που αφιέρωσε!

EDIT: Όπως επισημάνθηκε ήδη, σε μία ψηφοφορία μπορεί να υπάρχουν περισσότεροι από ένας νικητές, λόγω ισοβαθμίας.
Άρα η παρακάτω λογική είναι λανθασμένη, αφού απαιτεί ο εκλεχθείς Πάπας να ήταν ο (μοναδικός) νικητής σε κάθε ψηφοφορία.

Μία εναλλακτική ματιά στο Γ' Θέμα, χωρίς αποθήκευση των νικών κάθε υποψηφίου:
Αν ο εκλεχθείς Πάπας ήταν φαβορί, τότε όλες οι ψηφοφορίες θα είχαν αυτόν νικητή.
Άρα, αν σε οποιαδήποτε ψηφοφορία βρούμε νικητή διαφορετικό από τον νικητή της 1ης ψηφοφορίας, δεν υπάρχει φαβορί.

Κώδικας: [Επιλογή]

Αλγόριθμος Θέμα_Γ

      ! εισαγωγή υποψηφίων
      Για i από 1 μέχρι 18
            Διάβασε ΥΠΟΨ[i]
      Τέλος_επανάληψης

      φαβορί <-- Αληθής    ! κρατάει αν στο τέλος της ψηφοφορίας ο εκλεχθείς πάπας ήταν φαβορί
      λευκός_καπνός <-- Ψευδής
      ψηφοφορία <-- 0
      Αρχή_επανάληψης
            ψηφοφορία <-- ψηφοφορία + 1
            max <-- 0     ! για την εύρεση του νικητή *αυτής* της ψηφοφορίας

            ! μηδενισμός ψήφων κάθε υποψηφίου
            Για i από 1 μέχρι 18   
                  ΨΗΦ[i] <-- 0
            Τέλος_επανάληψης

            ! διεξαγωγή ψηφοφορίας
            Για κ από 1 μέχρι 115
                  Διάβασε όνομα
                  ! σειριακή αναζήτηση στον πίνακα ΥΠΟΨ
                  i <-- 1
                  θέση <-- 0
                  Όσο i <= 18 και θέση = 0 επανάλαβε
                        Αν ΥΠΟΨ[i] = όνομα τότε
                              θέση <-- i
                        Αλλιώς
                              i <-- i + 1
                        Τέλος_αν
                  Τέλος_επανάληψης
                  ΨΗΦ[θέση] <-- ΨΗΦ[θέση] + 1    ! προσθήκη ψήφου στον αντίστοιχο υποψήφιο
            Τέλος_επανάληψης

            Για i από 1 μέχρι 18
                  Αν ΨΗΦ[i] > max τότε
                        max <-- ΨΗΦ[i]
                        max_i <-- i
                  Τέλος_αν
                  Αν ΨΗΦ[i] >= (2/3) * 115 τότε
                        λευκός_καπνός <-- Αληθής    ! εκλέχθηκε πάπας
                        πάπας <-- i                 ! θέση του εκλεχθέντα πάπα στον πίνακα ΥΠΟΨ
                  Τέλος_αν
            Τέλος_επανάληψης

            Αν ψηφοφορία = 1 τότε
                  πρώτος_νικητής <-- max_i              ! κρατάει τη θέση του υποψήφιου που κέρδισε την πρώτη ψηφοφορία
            Αλλιώς_αν max_i <> πρώτος_νικητής τότε      ! o τρέχων νικητής είναι διαφορετικός από τον νικητή της πρώτης ψηφοφορίας
                  φαβορί <-- Ψευδής                     ! άρα δεν υπάρχει φαβορί
            Τέλος_αν

            Αν λευκός_καπνός = Αληθής τότε
                  Γράψε "Λευκός καπνός"
            Αλλιώς
                  Γράψε "Μαύρος καπνός"
            Τέλος_αν
      Μέχρις_ότου λευκός_καπνός = Αληθής

      Γράψε "Ο νέος Πάπας είναι ο", ΥΠΟΨ[πάπας]
      Αν φαβορί = Αληθής τότε
            Γράψε "Ο Πάπας ήταν το φαβορί"
      Αλλιώς
            Γράψε "Αουτσάιντερ"
      Τέλος_αν

Τέλος Θέμα_Γ


[Νίκος Αδαμόπουλος]

Προστέθηκε το αρχείο λύσεων στο αρχικό μήνυμα.

[Νίκος Αδαμόπουλος]

Μία εναλλακτική ματιά στο Γ' Θέμα, χωρίς αποθήκευση των νικών κάθε υποψηφίου:
Αν ο εκλεχθείς Πάπας ήταν φαβορί, τότε όλες οι ψηφοφορίες θα είχαν αυτόν νικητή.
Άρα, αν σε οποιαδήποτε ψηφοφορία βρούμε νικητή διαφορετικό από τον νικητή της 1ης ψηφοφορίας, δεν υπάρχει φαβορί.

Όπως προαναφέρθηκε από άλλους συναδέλφους, το πρόβλημα δημιουργείται από το γεγονός ότι μπορεί σε κάποιες ψηφοφορίες (εκτός φυσικά από την τελευταία) να έχουμε ισοψηφίες στην 1η θέση...

[tdiam]

Ναι, έχεις δίκιο! Άρα φάουλ η απάντηση.

[vistrian]

για το Α3 μπορούσε να είναι :
1)1
2)N-1
3)1
4)N-1
5)1
6)j
7)j
8)j+1

σελίδα 49 τετράδιο μαθητή
βέβαια κάνει πολλές περιττές συγκρίσεις. Για μένα σωστή είναι η λύση που δώσατε αλλά... τι θα γινόταν εάν ένας μαθητής έδινε την παραπάνω λύση;

[it0466]

Θα ήθελα την γνώμη σας για μια λύση για το θέμα Α3. Πιστεύω ότι δουλεύει, τι λέτε;

Κώδικας: Pascal

1. Για i από Ν μέχρι 2 με_βήμα -1
2.      Για j από 1 μέχρι i-1 με_βήμα 1
3.              Αν Α(j) > A(j+1) τότε
4.                     Αντιμετάθεσε A(j), A(j+1)
5.              Τέλος_αν
6.      Τέλος_επανάληψης
7. Τέλος_επανάληψης

Συγχαρητήρια για τα θέματα, είναι πάρα πολύ ωραία.

[evry]

και μένα μου φαίνεται ότι δουλεύει, με μια πρώτη ματιά

[mdelhmh]

Τα θέματα ειναι ΕΞΑΙΡΕΤΙΚΑ !!!! Μολις κατεβασα και το αρχειο των λύσεων και ειναι ενδιαφέρουσες και ιδιαίτερα κομψές!!! Ενα τεραστιο ΜΠΡΑΒΟ στην ομάδα !!!!