Εχουμε εναν δυσδιαστατο πινακα 5Χ10 ας υποθεσουμε οτι εχουμε μια μπαλα του μπιλιαρδου στην θεση Α[1,1] χτυπαμε την μπαλα με μια δυναμη Ν και η μπαλα Ξεκινα να κινειται διαγωνια και οταν η μπαλα χτυπισει μια επιφανεια του πινακα συνεχιζει η μπαλα παλι διαγωνια σχηματιζοντας ορθη γωνια με την προηγουμενη διαγωνιο..Θελουμε λοιπον να βρουμε αναλογα με την δυναμη Ν που θα χτυπισουμε την μπαλα σε πια θεση θα σταματισει..Για παραδειγμα αν Ν=2 ΘΑ ΣΤΑΜΑΤΙΣΕΙ στην θεση Α[2,2] αν Ν=5 στην θεση Α[5,5] αν Ν=6 στην θεση Α[4,6] αν Ν=9 στην θεση Α[1,9] και αν Ν=10 στην θεση Α[2,10] και παει λεγοντας..Ελπιζω να καταλαβατε τι εννοω :)
Ωραίο πρόβλημα!
Παράθεση από: koulhs στις 17 Μαρ 2012, 11:16:34 ΠΜ
Εχουμε εναν δυσδιαστατο πινακα 5Χ10 ας υποθεσουμε οτι εχουμε μια μπαλα του μπιλιαρδου στην θεση Α[1,1] χτυπαμε την μπαλα με μια δυναμη Ν και η μπαλα Ξεκινα να κινειται διαγωνια και οταν η μπαλα χτυπισει μια επιφανεια του πινακα συνεχιζει η μπαλα παλι διαγωνια σχηματιζοντας ορθη γωνια με την προηγουμενη διαγωνιο..Θελουμε λοιπον να βρουμε αναλογα με την δυναμη Ν που θα χτυπισουμε την μπαλα σε πια θεση θα σταματισει..Για παραδειγμα αν Ν=2 ΘΑ ΣΤΑΜΑΤΙΣΕΙ στην θεση Α[2,2] αν Ν=5 στην θεση Α[5,5] αν Ν=6 στην θεση Α[4,6] αν Ν=9 στην θεση Α[1,9] και αν Ν=10 στην θεση Α[2,10] και παει λεγοντας..Ελπιζω να καταλαβατε τι εννοω :)
Ένας τρόπος είναι ο παρακάτω:
Σχηματίζεις τους πίνακες:
ii=[1,2,3,4,5,4,3,2], 8 στοιχείων και
jj=[1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2], 18 στοιχείων.
Από το n=73 και μετά η ακολουθία επαναλαμβάνεται.
ΠΡΟΓΡΑΜΜΑ Billiard
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: ii[8], jj[18], n, m, i, j, imax, jmax, iimax, jjmax
ΑΡΧΗ
imax <- 5
jmax <- 10
iimax <- 2*imax - 2
jjmax <- 2*jmax - 2
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ iimax
ΑΝ i <= imax ΤΟΤΕ
ii[i] <- i
ΑΛΛΙΩΣ
ii[i] <- 2*imax - i
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ jjmax
ΑΝ i <= jmax ΤΟΤΕ
jj[i] <- i
ΑΛΛΙΩΣ
jj[i] <- 2*jmax - i
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ n ΑΠΟ 1 ΜΕΧΡΙ 150 ! όσο θέλουμε
m <- n - 1
i <- ii[m MOD iimax + 1]
j <- jj[m MOD jjmax + 1]
ΓΡΑΨΕ n, ' -> Α[', i, ',', j, ']'
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ Billiard
Ίσως να ήταν καλύτερο να μετακινηθεί στα γενικά του λυκείου.
Πολύ ενδιαφέρον πρόβλημα. Παρακάτω παρουσιάζω μια γενική λύση. Δηλαδή, αρχικά ζητούνται οι δύο πρώτες θέσεις τις μπάλας, έτσι ώστε να έχουμε την αρχική θέση αλλά και την κατεύθυνση κατά την οποία αρχικά κινείται η μπάλα, κατόπιν η δύναμη (οι θέσεις που μπορεί να μετακινηθεί) και τέλος παρουσιάζονται οι διαδοχικές θέσεις που θα πάρει στο τραπέζι του μπιλιάρδου (πίνακας 5x10).
Οποιαδήποτε διόρθωση ή και παρατήρηση είναι ευπρόσδεκτη.
ΠΡΟΓΡΑΜΜΑ Μπιλιάρδο
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: i, j, i_prev, j_prev, i_next, j_next, Κ, Ν
ΑΡΧΗ
ΓΡΑΨΕ 'ΔΩΣΕ ΤΗΝ ΠΡΩΤΗ ΘΕΣΗ ΤΗΣ ΜΠΑΛΑΣ: '
ΔΙΑΒΑΣΕ i_prev, j_prev
ΓΡΑΨΕ 'ΔΩΣΕ ΤΗ ΔΕΥΤΕΡΗ ΘΕΣΗ ΤΗΣ ΜΠΑΛΑΣ: '
ΔΙΑΒΑΣΕ i, j
ΓΡΑΨΕ 'ΔΩΣΕ ΤΗ ΔΥΝΑΜΗ: '
ΔΙΑΒΑΣΕ Ν
ΓΡΑΨΕ i_prev, ' , ', j_prev
ΓΡΑΨΕ i, ' , ', j
ΓΙΑ Κ ΑΠΟ 1 ΜΕΧΡΙ Ν-1
ΑΝ i_prev<i ΚΑΙ i<5 ΤΟΤΕ
i_next <-- i + 1
ΑΛΛΙΩΣ_ΑΝ i>1 ΤΟΤΕ
i_next <-- i - 1
ΑΛΛΙΩΣ
i_next <-- i + 1
ΤΕΛΟΣ_ΑΝ
ΑΝ j_prev<j ΚΑΙ j<10 ΤΟΤΕ
j_next <-- j + 1
ΑΛΛΙΩΣ_ΑΝ j>1 ΤΟΤΕ
j_next <-- j - 1
ΑΛΛΙΩΣ
j_next <-- j + 1
ΤΕΛΟΣ_ΑΝ
i_prev <-- i
j_prev <-- j
i <-- i_next
j <-- j_next
ΓΡΑΨΕ i, ' , ', j
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
Δεν έχω προσθέσει έλεγχο εγκυρότητας για τις αρχικές θέσεις. Επίσης, οι αρχικές θέσεις μπορούν να δηλωθούν ως σταθερές ή αντί για πρόγραμμα να μετατραπεί σε διαδικασία που θα δέχεται ως παραμέτρους τις αρχικές θέσεις και τη δύναμη.
Ακολουθεί μια γενίκευση του αλγόριθμου που έστειλα παραπάνω βασισμένη στην γενίκευση του αρχικού προβλήματος που έθεσε ο noname.
Η αρχική θέση και η επιθυμητή κατεύθυνση κίνησης λαμβάνεται υπόψιν μέσω της κατάλληλης ολίσθησης δεξιά ή αριστερά των πινάκων ii και jj.
Η υλοποίηση των ολισθήσεων θα μπορούσε ίσως να γίνει καλύτερη.
ΠΡΟΓΡΑΜΜΑ Billiard2
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: ii[8], jj[18], iibuf[8], jjbuf[18], n, m, i, j
ΑΚΕΡΑΙΕΣ: iimax, jjmax, i_init, j_init, i_next, j_next
ΑΚΕΡΑΙΕΣ: i_dir, j_dir, imax, jmax, step, i_shift, j_shift
ΑΡΧΗ
!---------------------------------------------------------------
! Αρχικοποιήσεις-εισαγωγή δεδομένων
! (προσοχή στις δεσμεύσεις μνήμης των ii, jj,
! πρέπει να είναι ίσες με iimax, jjmax)
!
! Αρχικοποίηση των πινάκων ii, jj σε:
! [1,2,3,4,5,4,3,2], [1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2]
!---------------------------------------------------------------
imax <- 5
jmax <- 10
iimax <- 2*imax - 2
jjmax <- 2*jmax - 2
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ iimax
ΑΝ i <= imax ΤΟΤΕ
ii[i] <- i
ΑΛΛΙΩΣ
ii[i] <- 2*imax - i
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ jjmax
ΑΝ j <= jmax ΤΟΤΕ
jj[j] <- j
ΑΛΛΙΩΣ
jj[j] <- 2*jmax - j
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ 'Αρχική γραμμή'
ΔΙΑΒΑΣΕ i_init
ΓΡΑΨΕ 'Αρχική στήλη'
ΔΙΑΒΑΣΕ j_init
ΓΡΑΨΕ 'Επόμενη γραμμή'
ΔΙΑΒΑΣΕ i_next
ΓΡΑΨΕ 'Επόμενη στήλη'
ΔΙΑΒΑΣΕ j_next
ΓΡΑΨΕ 'N'
ΔΙΑΒΑΣΕ n
ΓΡΑΨΕ
!---------------------------------------------------------------
!---------------------------------------------------------------
! Ολισθήσεις των πινάκων ii, jj για να λάβουμε υπ'οψιν την αρχική
! θέση και τις επιθυμητές κατευθύνσεις κίνησης
!---------------------------------------------------------------
i_dir <- i_next - i_init
j_dir <- j_next - j_init
i_shift <- i_init - 1
ΑΝ i_dir > 0 ΤΟΤΕ
! Ολίσθησε το ii[] αριστερά (i_init-1) φορές
ΓΙΑ i ΑΠΟ i_init ΜΕΧΡΙ iimax
iibuf[i - i_shift] <- ii[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ i_init - 1
iibuf[iimax - i_shift + i] <- ii[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ iimax
ii[i] <- iibuf[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΛΛΙΩΣ_ΑΝ i_dir < 0 ΤΟΤΕ
! Ολίσθησε το ii[] δεξιά (i_init-1) φορές
ΓΙΑ i ΑΠΟ i_shift + 1 ΜΕΧΡΙ iimax
iibuf[i] <- ii[i - i_shift]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ i_shift
iibuf[i] <- ii[iimax - i_shift + i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ iimax
ii[i] <- iibuf[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΛΛΙΩΣ
! Εαν πρέπει να κινηθούμε κατά μήκος της γραμμής πρέπει το ii[]=i_init
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ iimax
ii[i] <- i_init
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΑΝ
j_shift <- j_init - 1
ΑΝ j_dir > 0 ΤΟΤΕ
! Ολίσθησε το jj[] αριστερά (j_init-1) φορές
ΓΙΑ j ΑΠΟ j_init ΜΕΧΡΙ jjmax
jjbuf[j - j_shift] <- jj[j]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ j_init - 1
jjbuf[jjmax - j_shift + j] <- jj[j]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ jjmax
jj[j] <- jjbuf[j]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΛΛΙΩΣ_ΑΝ j_dir < 0 ΤΟΤΕ
! Ολίσθησε το jj[] δεξιά (j_init-1) φορές
ΓΙΑ j ΑΠΟ j_shift + 1 ΜΕΧΡΙ jjmax
jjbuf[j] <- jj[j - j_shift]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ j_shift
jjbuf[j] <- jj[jjmax - j_shift + j]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ jjmax
jj[j] <- jjbuf[j]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΛΛΙΩΣ
! Εαν πρέπει να κινηθούμε κατά μήκος της στήλης πρέπει το jj[]=j_init
ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ jjmax
jj[j] <- j_init
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΑΝ
!---------------------------------------------------------------
!---------------------------------------------------------------
! Κυρίως αλγόριθμος
!---------------------------------------------------------------
ΓΙΑ step ΑΠΟ 1 ΜΕΧΡΙ n
m <- step - 1
i <- ii[m MOD iimax + 1]
j <- jj[m MOD jjmax + 1]
ΓΡΑΨΕ step, ' -> Α[', i, ',', j, ']'
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
!---------------------------------------------------------------
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ Billiard2
Καλημέρα σας... Μια λύση και από μένα για το ωραιότατο πρόβλημα που μας έθεσε ο koulhs...
Αλγόριθμος τάδε
Για ι από 1 μέχρι 5
Για λ από 1 μεχρι 10
Α[ι,λ]← "-"
Τέλος_επανάληψης
Τέλος_επανάληψης !για να υπάρχει ένας πίνακας να έχουμε στοιχεία...
Εμφάνισε "με πόση δύναμη θα χτυπήσεις τη μπάλα?"
Διάβασε Ν
χ← 1
υ← 1! ξεκινάμε από την αρχή... πάνω αριστερά στο μπιλιάρδο...
Για ι από 1 μέχρι Ν
Αν χ=5 τότε !αν φτάσει η μπάλα στο κάτω άκρο, τότε αρχίζει να ανεβαίνει προς τα πάνω(μειώνεται το χ)
κάτω← ψευδής
Τέλος_Αν
Αν χ=1 τότε !αν φτάσει η μπάλα στο πάνω άκρο, τότε αρχίζει να κατεβαίνει προς τα κάτω(αυξάνεται το χ)
κάτω← αληθής
Τέλος_Αν
Αν υ=10 τότε !αν φτάσει η μπάλα στο δεξί άκρο, τότε αρχίζει να κατευθύνεται προς τα αριστερά(μειώνεται το υ)
δεξιά← ψευδής
Τέλος_Αν
Αν υ=1 τότε !αν φτάσει η μπάλα στο αριστέρο άκρο, τότε αρχίζει να κατευθύνεται προς τα δεξιά(αυξάνεται το υ)
δεξιά← αληθής
Τέλος_Αν
Αν δεξιά=αληθής τότε
υ← υ+1
Αλλιώς
υ← υ-1
τέλος_αν
Αν κάτω=αληθής τότε
χ← χ+1
Αλλιώς
χ← χ-1
Τέλος_Αν
Τέλος_επανάληψης
Εμφάνισε χ," ", υ
Τέλος τάδε
Χωρίς να έχω δει τα όσα έχουν γραφεί πιο πριν, γράφω την άποψή μου για το πρόβλημα και σόρρυ αν επαναλαμβάνω πράγματα.
Το πρόβλημα αυτό απλοποιείται αν δεις τις 2 διαστάσεις ανεξάρτητα (όπως πχ κάνεις και στις βολές στο βαρυτικό πεδίο).
Μόνο για τον οριζόντιο άξονα έχεις μια ακολουθία 12345432123454321...
Που επαναλαμβάνεται συνεχώς με περίοδο 8. Για τα πρώτα 8 (τα διαφορετικά) ισχύει ότι ο όρος είναι α[ν]=5-Α_Τ(5-ν) . Επειδή υπάρχει επαναληψημότητα στους δείκτες (πχ ο α[1]=α[9], α[2]=α[10] κλπ) έχω α[ν]=α[(ν-1) mod 8 +1] . Η απόδειξη παραλείπεται αλλά αν κάποιος θέλει τη γράφω.
Έτσι με σύνθεση των 2 ακολουθιών έχω
α[ν]= 5 - Α_Τ(5 - ((ν - 1) MOD 8 + 1))
όπου α[ν] ο νιοστός όρος της ακολουθίας. (Δεν ανακατεύω πίνακες)
Όμοια στον κατακόρυφο άξονα ισχύει
α[ν]=10 - Α_Τ(10 - ((ν - 1) MOD 18 + 1))
Έτσι τελικά έχω
Γραμμή = 5 - Α_Τ(5 - ((ν - 1) MOD 8 + 1))
Στήλη = 10 - Α_Τ(10 - ((ν - 1) MOD 18 + 1))
Στον οριζόντιο άξονα έχω περίοδο 8 (δηλαδή έχω επανάληψη κάθε 8, 16, 24, 32 κλπ)και στον κατακόρυφο περίοδο 18 (επανάληψη και κάθε πολλαπλάσιο του 18). Άρα το ζευγάρι επαναλαμβάνεται κάθε ελάχιστο κοινό πολλαπλάσιο του 8 και του 18 που είναι το 72. Άρα το φαινόμενο έχει περίοδο 72.
Εύκολα γενικεύεται για κάθε πλήθος γραμμών και στηλών. Μπορεί να ξέφυγε κάτι, αλλά νομίζω ότι η ιδέα φαίνεται.