About the author

asynadak

Η ακαδημαϊκή μου ιδιότητα είναι πτυχιούχος του τμήματος Μαθηματικών του Α.Π.Θ.. Ωστόσο, πέρα από τα μαθηματικά και τις εφαρμοσμένες επιστήμες, θα με δείτε να ασχολούμαι με web development και διαδικτυακό προγραμματισμό ! Το newsfilter.gr προέκυψε στις αρχές του 2007 (01 Ιανουαρίου για την ακρίβεια) και από τότε φροντίζουμε να προσφέρουμε καθημερινές στιγμές ενημέρωσης και ψυχαγωγίας! Εμένα θα με δείτε να γράφω, μεταξύ άλλων, περισσότερο για κινητά τηλέφωνα, gadgets, Formula 1, ίσως Lost και για περίεργα πράγματα που συμβαίνουν στον κόσμο (τα περισσότερα τυγχάνουν στην Κίνα, δεν ξέρω αν έχουν κάτι και τα τραβάνε!)!

15 Comments

  1. 1

    AA

    Σε αυτή την έκδοση το παιχνίδι ονομάζεται Anaconda!

    Reply
  2. 2

    V.P.

    Kai egw klaigomai pou den mporw na kanw tin ergasia sti matlab…!! 😛

    Reply
  3. 3

    chzigkol

    Ωπ, άκουσα MatLab ή με γελούν τα αυτιά μου; V.P. τι εργασία έχεις στο MatLab?

    Reply
  4. 4

    V.P.

    Des edw http://en.wikipedia.org/wiki/Knight's_tour !
    Alla ftanw se kapoio simeio pou to alogo exei kalupsei oles tis pithanes metavaseis kai den mporei na paei pouthena allou. (den prepei na paei 2 fores stin idia thesi).
    Kai meta vlepw videos san to parapanw kai aisthonomai entelws xazi!!

    Reply
  5. 5

    V.P.

    Einai kai to «‘s_tour» sto link.

    Reply
  6. 6

    asynadak

    Καλή φάση αυτό το πρόβλημα! Το έχει για την σχολή ή ασχολείσαι μόνη σου?

    Reply
  7. 7

    AA

    V.P και τι έγινε που φτάνεις σε ένα σημείο και δεν μπορείς να συνεχίσεις; Δεν υπάρχει λύση απο όλα τα σημεία.

    Πιθανότατα έχετε καλύψει ήδη το Depth First Search (DFS). Αν στην αναζήτηση έχεις επιστρέψει στο root καλύπτοντας όλες τις πιθανές οδούς σε κάθε επίπεδο τότε δεν υπάρχει λύση.

    Παρ’ όλα αυτά ίσως χρειαστεί να μετατρέψεις το DFS απο Recursive σε Non-Recursive αν έχεις μεγάλο board ή να αλλάξεις το recursion limit του MATLAB.

    Reply
  8. 8

    asynadak

    @ΑΑ: Κανονικά, υπάρχει λύση από όποιο σημείο της σκακιέρας και αν ξεκινήσεις. Αλλά δεν υπάρχει λύση για κάθε δεδομένη διαδρομή.

    Reply
  9. 9

    AA

    Δεν θα ήθελα να επιμείνω αλλά νομίζω οτι έτσι όπως το θέτεις, το συμπέρασμα αναιρεί τη πρόταση. (Εκτός και αν το εννοείς έτσι 😕 )

    Για τον εξής λόγο: Κάθε θέση εκκίνησης (κάθε κόμβος στο graph) είναι και πιθανό σημείο μιας διαδρομής που διέρχεται απο αυτό (και έχει ξεκινήσει απο άλλο). Αν λοιπόν υπάρχει μια διαδρομή που «αστοχεί» τότε υπάρχει και ένα σημείο εκκίνησης για το οποίο δεν υπάρχει λύση.

    Λεπτομέρειες…το θέμα είναι οτι είναι καταπληκτική σπαζοκεφαλιά και ίσως η απεικόνιση των διαδρομών στο χρόνο να έκανε και ωραίο σχήμα απάνω στο κτήριο 😀

    Reply
  10. 10

    asynadak

    Βασικά έκανα ένα μικρό λαθάκι! Νόμιζα ότι έπρεπε να τελειώσει το άλογο οπωσδήποτε εκεί που ξεκίνησε. Κατά συνέπεια έκανε έναν κύκλο. Άρα από όποιο σημείο και αν ξεκινούσε θα μπορούσε να κάνει αυτό το κύκλο.

    Βέβαια, στην γενική του περίπτωση, εφόσον υπάρχει έστω και μία τέτοια λύση (για την ακρίβεια υπάρχουν 26,534,728,821,064 σύμφωνα με την wikipedia), άρα από που και να ξεκινήσουμε το αλογάκι, θα μπορεί να κάνει αυτόν τον κύκλο.

    Άρα κάθε θέση εκκίνησης δίνει λύση!

    Reply
  11. 11

    V.P.

    @ asynadak: to exw gia ti sxoli. Anti gia grapti eksetasi stin eksetastiki prepei na dwsw tin ergasia!

    @ AA + asynadak: prepei na to ftiaksw me tetoio tropo wste na uparxei lusi apo opoiodipote simeio enarksis. Apo tis 8 pithanes metavaseis mono oi «x» epitrepontai kai me ti xrisi tou «rand» dialegw mia metavasi. Otan den exw alles kiniseis x=0. Opote, sto telos twn metavasewn mpainei «if x==0» kai me kapoio tropo prepei na to stelnw ksana stin arxi kai me idio simeio enarksis kai ti xrisi tou «rand(‘state’,sum(100*clock))» na akolouthei alli poreia. Ekei uparxei to provlima!

    Reply
  12. 12

    asynadak

    @V.P. τι πρόβλημα υπάρχει εκεί? Να μην παίρνει και πάλι την ίδια διαδρομή?

    Reply
  13. 13

    V.P.

    Den kserw ti entoles na valw mesa sto «if x==0»! Me to «rand(’state’,sum(100*clock))» tha akolouthei kathe fora alli diadromi mexri na vrei tin «idaniki» kai na paei se ola ta tetragwna. Eixa vrei ena tropo alla itan lathos kai kollouse kai to pc. Logika einai polu eukolotero apo olo to upoloipo pou exw kanei mexri twra alla exw kollisei!

    Reply
  14. 14

    AA

    @asynadak: 😀 ξανασκέψου το, στο 8×8 board, είναι πολύ πιθανό όλες οι θέσεις να δίνουν διαδρομές που επιστρέφουν στο ίδιο σημείο (δεν το θυμάμαι αν όντως έτσι είναι) αλλά αυτή δεν είναι η γενική περίπτωση.

    @V.P: Ρίξε μια ματιά http://en.wikipedia.org/wiki/Depth-first_search

    Reply
  15. Pingback: Newsfilter » Τα καλύτερα του newsfilter για το 2008!

Πείτε την γνώμη σας

Powered by Social Mind