Θέμα: χρειαζομαι βοηθια για να λυσω εναν αλγοριθμο μπιλιαρδου!!

[koulhs]

Εχουμε εναν δυσδιαστατο πινακα 5Χ10 ας υποθεσουμε οτι εχουμε μια μπαλα του μπιλιαρδου στην θεση Α[1,1] χτυπαμε την μπαλα με μια δυναμη Ν και η μπαλα Ξεκινα να κινειται διαγωνια και οταν η μπαλα χτυπισει μια επιφανεια του πινακα συνεχιζει η μπαλα παλι διαγωνια σχηματιζοντας ορθη γωνια με την προηγουμενη διαγωνιο..Θελουμε λοιπον να βρουμε αναλογα με την δυναμη Ν που θα χτυπισουμε την μπαλα σε πια θεση θα σταματισει..Για παραδειγμα αν Ν=2 ΘΑ ΣΤΑΜΑΤΙΣΕΙ στην θεση Α[2,2] αν Ν=5 στην θεση Α[5,5] αν Ν=6 στην θεση Α[4,6] αν Ν=9 στην θεση Α[1,9] και αν Ν=10 στην θεση Α[2,10] και παει λεγοντας..Ελπιζω να καταλαβατε τι εννοω 

[petrosp13]

Ωραίο πρόβλημα!

[Gnirut]

Εχουμε εναν δυσδιαστατο πινακα 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


[Gnirut]

Ίσως να ήταν καλύτερο να μετακινηθεί στα γενικά του λυκείου.

[noname]

Πολύ ενδιαφέρον πρόβλημα. Παρακάτω παρουσιάζω μια γενική λύση. Δηλαδή, αρχικά ζητούνται οι δύο πρώτες θέσεις τις μπάλας, έτσι ώστε να έχουμε την αρχική θέση αλλά και την κατεύθυνση κατά την οποία αρχικά κινείται η μπάλα, κατόπιν η δύναμη (οι θέσεις που μπορεί να μετακινηθεί) και τέλος παρουσιάζονται οι διαδοχικές θέσεις που θα πάρει στο τραπέζι του μπιλιάρδου (πίνακας 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
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Δεν έχω προσθέσει έλεγχο εγκυρότητας για τις αρχικές θέσεις. Επίσης, οι αρχικές θέσεις μπορούν να δηλωθούν ως σταθερές ή αντί για πρόγραμμα να μετατραπεί σε διαδικασία που θα δέχεται ως παραμέτρους τις αρχικές θέσεις και τη δύναμη.

[Gnirut]

Ακολουθεί μια γενίκευση του αλγόριθμου που έστειλα παραπάνω βασισμένη στην γενίκευση του αρχικού προβλήματος που έθεσε ο 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


[meteo_xampos]

Καλημέρα σας... Μια λύση και από μένα για το ωραιότατο πρόβλημα που μας έθεσε ο koulhs...

Αλγόριθμος τάδε
Για ι από 1 μέχρι 5
   Για λ από 1 μεχρι 10
      Α[ι,λ]← "-"
   Τέλος_επανάληψης
Τέλος_επανάληψης !για να υπάρχει ένας πίνακας να έχουμε στοιχεία...
Εμφάνισε "με πόση δύναμη θα χτυπήσεις τη μπάλα?"
Διάβασε Ν
χ← 1
υ← 1! ξεκινάμε από την αρχή... πάνω αριστερά στο μπιλιάρδο...
Για ι από 1 μέχρι Ν
   Αν χ=5 τότε !αν φτάσει η μπάλα στο κάτω άκρο, τότε αρχίζει να ανεβαίνει προς τα πάνω(μειώνεται το χ)
      κάτω← ψευδής
   Τέλος_Αν
   Αν χ=1 τότε !αν φτάσει η μπάλα στο πάνω άκρο, τότε αρχίζει να κατεβαίνει προς τα κάτω(αυξάνεται το χ)
      κάτω← αληθής
   Τέλος_Αν
   Αν υ=10 τότε !αν φτάσει η μπάλα στο δεξί άκρο, τότε αρχίζει να κατευθύνεται προς τα αριστερά(μειώνεται το υ)
      δεξιά← ψευδής
   Τέλος_Αν
   Αν υ=1 τότε !αν φτάσει η μπάλα στο αριστέρο άκρο, τότε αρχίζει να κατευθύνεται προς τα δεξιά(αυξάνεται το υ)
      δεξιά← αληθής
   Τέλος_Αν
   Αν δεξιά=αληθής τότε
      υ← υ+1
   Αλλιώς
      υ← υ-1
   τέλος_αν
   Αν κάτω=αληθής τότε
      χ← χ+1
   Αλλιώς
      χ← χ-1
   Τέλος_Αν
Τέλος_επανάληψης
Εμφάνισε χ," ", υ
Τέλος τάδε

[gpapargi]

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

Το πρόβλημα αυτό απλοποιείται αν δεις τις 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.

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