Towers of Hanoi

Συζητήσεις για την γλώσσα C και C++

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
Άβαταρ μέλους
Connor MacLeod
Honorary Member
Δημοσιεύσεις: 13372
Εγγραφή: 07 Φεβ 2005 13:36
Τοποθεσία: Κοζάνη
Επικοινωνία:

Towers of Hanoi

Δημοσίευση από Connor MacLeod » 25 Απρ 2012 09:56

Γεια μαααςςς. Τι κανουμε? Χρονια πολλα και για το Πασχα.
:P
Στο λοιπόν. Φαντάζομαι ξερεται το Towers of Hanoi.
Ειναι ενα παζλ που εχει 3 στιλες, στη πρώτη δίσκους στοιβαγμένους αποτον μικρότερο προς το μεγαλύτερο (Απο πανω προς τα κατω) και πρεπει να τους πας στην τελευταία στήλη μετακινώντας τους χωρις να επιτρέπετε να βαζεις εναν μεγαλύτερο (διαμετρικά) κύλινδρο
επάνω απο εναν μικρότερο του

http://en.wikipedia.org/wiki/Tower_of_Hanoi

Εχω φτιαξει αυτο το πραγμα που δουλεύει μια χαρα (Σε C):

Κώδικας: Επιλογή όλων

#include "stdio.h"

void towers(int,char,char,char);

main()
	{ int n;
	  printf("Dose ena noumero : ");
	  scanf("%d",&n);
	  printf("Lisi: :\n\n");
	  towers(n,'A','C','B');
	  return 0;
	}


void towers(int n,char from,char top,char aux)
	{
	  if(n==1)
	    { printf("\nMetakinise to disko 1 apo ton stilo %c ston %c",from,top);
	      return;
	    }
	  towers(n-1,from,aux,top);
	  printf("\nMetakinise to disko %d apo to stilo %c sto %c",n,from,top);
	  towers(n-1,aux,top,from);
	}
Τωρα εγω θελω να ρωτήσω το εξεις:
Οταν βαζεις στο pc ενα σχετικά μικρο νούμερο κανει σχετικά λιγο χρόνο να βγαλει το αποτέλεσμα..
Αν του δώσω όμως 300 δισκους να μετακινήσει, θα κανει 300 χρόνια. Ασχετα αν εχεις 80386 ή intel i9 με 96 cores...

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

Κατι που σκέφτηκα ειναι το έξεις:

Οταν του δίνω για πρώτη φορα τον αριθμό πχ 30, αυτο βγάζει ενα αποτέλεσμα και λεει οτι μετακινήθηκαν αυτοι οι δίσκοι, απο εδω εδω... Θα μπορούσε το πρόγραμμα να κραταει την λυση αυτη και όταν εγω του καναδίνω το 30, απλα να κανει load το αποθηκευμένο κοματι και απλα να το print-άρει?
Meizu MX5(5.5"/8Core/3GB/32GB/Sony IMX220 20.7MP)
PC 27'' (3770@3.4/16GB/560SE/500GB SATA3/650W S12G)
Mac mini (2.5GHz/8GB/6630/90GB GorsairGT)

Άβαταρ μέλους
c0d3punk
Honorary Member
Δημοσιεύσεις: 1076
Εγγραφή: 15 Σεπ 2008 22:32
Τοποθεσία: Puerto pollo
Επικοινωνία:

Towers of Hanoi

Δημοσίευση από c0d3punk » 25 Απρ 2012 17:04

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

Τρόπους επίλυσης θα βρεις πολλούς. Το θέμα είναι ποιός είναι ο πιο αποδοτικός σε ταχύτητα και χρήση μνήμης (πέραν του σωστού αποτελέσματος για n στοιχεία, αν το θεωρήσουμε δεδομένο).

Η υπολογιστική δύναμη παίζει σημαντικό ρόλο στην επίλυση, οπότε δεν μπορεί να συγκρίνεις τους χρόνους του 386 με έναν i7 απλά σε μεγάλα προβλήματα που θα κάνουν να λυθούν 50 αιώνες, με πιο σύγχρονο pc θα τα λύσεις σε... 49 αιώνες :-)

Αν θέλεις την γνώμη μου βιάζεσαι να μάθεις (καλό από άποψης ενδιαφέροντος). Διάβασε αυτά που έχεις αυτό το εξάμηνο και σε επόμενα εξάμηνα θα μάθεις να τεκμηριώνεις την ορθότητα/πολυπλοκότητα του αλγόριθμου που έχεις αναπτύξει.
like ants in a colony we do our share
but there's so many other f****' insects out there || Ανανεωμένα Παρτάλια || biZfind.gr

Άβαταρ μέλους
Connor MacLeod
Honorary Member
Δημοσιεύσεις: 13372
Εγγραφή: 07 Φεβ 2005 13:36
Τοποθεσία: Κοζάνη
Επικοινωνία:

Towers of Hanoi

Δημοσίευση από Connor MacLeod » 25 Απρ 2012 17:54

Η υπολογιστική δύναμη παίζει σημαντικό ρόλο στην επίλυση, οπότε δεν μπορεί να συγκρίνεις τους χρόνους του 386 με έναν i7 απλά σε μεγάλα προβλήματα που θα κάνουν να λυθούν 50 αιώνες, με πιο σύγχρονο pc θα τα λύσεις σε... 49 αιώνες
Δε νομίζω, τουλαχιστο στο συγκεκριμένο...
To εκανα το προγραμμα το πασχα λογο βαρεμάρας, στην Κοζανη σε ενα PC P4-2.66GHz και το δοκίμασα με 14 κυλίνδρους και το ιδιο εκανα και στον AMD X4, και με καναν πανω κατω και οι δυο 15-20 δευτερόλεπτα αν θυμαμαι καλα...
:think:

Το θεμα ειναι οτι ειναι υπερβολικά αργό. Δε ξερω τι ακριβός κανει η cpu (με ποιο τροπο δουλευει) και αργει στο συγκεκριμένο πρόγραμμα ετσι. Αν θες δοκιμαστο να δεις..

ΥΓ.

Σκεψου δηλαδή οτι αν του βαλεις 20, θα κανει πανω απο 1 λεπτο αν στα 14 κανει 15-20secs
Meizu MX5(5.5"/8Core/3GB/32GB/Sony IMX220 20.7MP)
PC 27'' (3770@3.4/16GB/560SE/500GB SATA3/650W S12G)
Mac mini (2.5GHz/8GB/6630/90GB GorsairGT)

Άβαταρ μέλους
c0d3punk
Honorary Member
Δημοσιεύσεις: 1076
Εγγραφή: 15 Σεπ 2008 22:32
Τοποθεσία: Puerto pollo
Επικοινωνία:

Towers of Hanoi

Δημοσίευση από c0d3punk » 25 Απρ 2012 18:11

Και άμα του βάλεις 500 θα κάνει μήνες.

Αυτό σου εξηγώ. ότι αν π.χ. αυξάνοντας το πλήθος των στοιχείων έχεις υπερδιπλάσια αύξηση του χρόνου επίλυσης από κάποιο σημείο και μετά θα είναι αδύνατη η λύση γιατί απλά θα θέλει πάρα πολύ καιρό να λυθεί. Υπάρχουν άλυτα τέτοια υπολογιστικά προβλήματα, γιατί απλά ο υπολογίσιμος χρόνος επίλυσης δεν φτάνει ούτε για δύο ζωές.
like ants in a colony we do our share
but there's so many other f****' insects out there || Ανανεωμένα Παρτάλια || biZfind.gr

Άβαταρ μέλους
Connor MacLeod
Honorary Member
Δημοσιεύσεις: 13372
Εγγραφή: 07 Φεβ 2005 13:36
Τοποθεσία: Κοζάνη
Επικοινωνία:

Towers of Hanoi

Δημοσίευση από Connor MacLeod » 25 Απρ 2012 18:16

:(
Εμενα με αρεσει να σκέφτομαι διαφορετικά και να λεω οτι πολυ απλα κανεις δεν εχει φτιαξει εναν αποδοτικό αλγόριθμο για την λύση τετοιων προβλημάτων, οπως πχ των Bubble sort and Quick sort που κανουν την ίδια δουλεια αλλα ο ενας ειναι πολυ πιο αποδοτικος απο τον αλλο.
:P
Meizu MX5(5.5"/8Core/3GB/32GB/Sony IMX220 20.7MP)
PC 27'' (3770@3.4/16GB/560SE/500GB SATA3/650W S12G)
Mac mini (2.5GHz/8GB/6630/90GB GorsairGT)

Άβαταρ μέλους
dva_dev
Script Master
Δημοσιεύσεις: 3790
Εγγραφή: 16 Σεπ 2005 01:32
Επικοινωνία:

Towers of Hanoi

Δημοσίευση από dva_dev » 25 Απρ 2012 19:39

Connor MacLeod έγραψε:Δε νομίζω, τουλαχιστο στο συγκεκριμένο...
To εκανα το προγραμμα το πασχα λογο βαρεμάρας, στην Κοζανη σε ενα PC P4-2.66GHz και το δοκίμασα με 14 κυλίνδρους και το ιδιο εκανα και στον AMD X4, και με καναν πανω κατω και οι δυο 15-20 δευτερόλεπτα αν θυμαμαι καλα...
Δοκίμασε με 25 για να δεις τη διαφορά.

Άβαταρ μέλους
cherouvim
Script Master
Δημοσιεύσεις: 3137
Εγγραφή: 13 Ιούλ 2005 22:56
Τοποθεσία: Athens, Greece
Επικοινωνία:

Towers of Hanoi

Δημοσίευση από cherouvim » 26 Απρ 2012 11:55

Στο πρόγραμμα αυτό το πιο αργό πράγμα είναι το print.
Δοκίμασε να το τρέξεις στέλνοντας το output σε ένα αρχείο και πες μας αν κάνει την ίδια ώρα.

mariosal
Honorary Member
Δημοσιεύσεις: 1473
Εγγραφή: 09 Νοέμ 2007 23:55

Towers of Hanoi

Δημοσίευση από mariosal » 26 Απρ 2012 16:11

Η γνωστότερη trivial υλοποίηση των Towers of Hanoi είναι αυτή ακριβώς που έχεις κάνει. Μπορεί να μετατραπεί σε επαναληπτική χωρίς να γλυτώνεις κάτι. Από εκεί και πέρα η τεχνική της αποθήκευσης παλαιότερων αποτελεσμάτων ονομάζεται Memoization και μειώνει τρομερά την πολυπλοκότητα όταν έχεις επικαλυπτόμενα προβλήματα, όπως οι αριθμοί Fibonacci.

Αλλά στη συγκεκριμένη περίπτωση τα επικαλυπτόμενα προβλήματά σου εξαρτώνται από 3 πράγματα( κύλινδροι, αφετηρία, προορισμός ) που κάνει το memoization ανούσιο, διότι θα χάσεις από πλευράς readability και ΠΟΛΛΗΣ μνήμης. Επίσης ένα θέμα είναι πώς θα αποθηκεύσεις παλαιότερα states μιας και δεν είναι απλά ένα νούμερο σαν τους Fibonacci.

Όσον αφορά το χρόνο εκτέλεσης η πολυπλοκότητα του αλγορίθμου είναι O( 2^n ) αν δεν κάνω λάθος, οπότε μη σε ξαφνιάζει. Μπορείς να διαβάσεις τις διαφάνειες από το περσινό camp του Διαγωνισμού Πληροφορικής για πολυπλοκότητα: http://www.softlab.ntua.gr/~nickie/tmp/ ... lexity.pdf

Ένας μπακαλίστικος τρόπος να δεις πόσο γρήγορα τρέχει το πρόγραμμά σου είναι να διαιρείς ότι έχει μέσα ως όρισμα το Big O Notation με το 10^8 που είναι οι πράξεις που εκτελεί ένας σύγχρονος επεξεργαστής, όπως ο 2 GHz Intel Core i7 μου, το δευτερόλεπτο. Σε παλαιότερους υπολογιστές η δύναμη του 10 μειώνεται, από 10^8 μπορεί να είναι 10^6.

Π.χ.
  • Αν η πολυπλοκότητα του αλγορίθμου είναι O( n^2 ), τότε θα τρέξει σε n^2/10^8 δευτερόλεπτα.
    Αν η πολυπλοκότητα του αλγορίθμου είναι O( n ), τότε θα τρέξει σε n/10^8 δευτερόλεπτα.
    Αν η πολυπλοκότητα του αλγορίθμου είναι O( 2^n ), όπως στους Towers of Hanoi, τότε θα τρέξει σε 2^n/10^8 δευτερόλεπτα.
Όπου n είναι το μέγεθος της εισόδος. Σε εσένα τώρα είναι το πλήθος των κυλίνδρων.

Άβαταρ μέλους
Connor MacLeod
Honorary Member
Δημοσιεύσεις: 13372
Εγγραφή: 07 Φεβ 2005 13:36
Τοποθεσία: Κοζάνη
Επικοινωνία:

Towers of Hanoi

Δημοσίευση από Connor MacLeod » 26 Απρ 2012 22:46

Καλα το ότι θα με μαθαινε προγραματισμο ο Μαριος δε το περιμενα!
Αντε και μια μερα να περασεις και τον cherouvim σε ευχομαι

Μπραβο ρε Μαριε! Keep Going. και thanks for the info.
:P
Η γνωστότερη trivial υλοποίηση των Towers of Hanoi είναι αυτή ακριβώς που έχεις κάνει.
:(
Και νομιζα οτι ειμαι και εφευρετικός...
Meizu MX5(5.5"/8Core/3GB/32GB/Sony IMX220 20.7MP)
PC 27'' (3770@3.4/16GB/560SE/500GB SATA3/650W S12G)
Mac mini (2.5GHz/8GB/6630/90GB GorsairGT)

nkast
Δημοσιεύσεις: 137
Εγγραφή: 15 Νοέμ 2009 20:31
Επικοινωνία:

Towers of Hanoi

Δημοσίευση από nkast » 04 Μάιος 2012 01:41

Η απάντηση του mariosal είναι to the point.
Επεσες στην περιπτωση!


Oι ερωτήσεις που κάνεις είναι πολυ ευστοχες (αν δηλαδή υπάρχει υλοποίηση που τρέχει σε γραμικό χρόνο ή οχι)

Αυτα τα ερωτήματα απαντα η θεωρία της πολυπλοκότητας.

Η ιδέα είναι πως αν αποδείξεις πως το πρόβλημα σου είναι ισοδύναμο με άλλο γνωστό 'δύσκολο' πρόβλημα όπως για παράδειγμα το γνωστό πρόβλημα του πλανόδιου πωλητή, τότε και το πρόβλημα που εξετάζεις είναι 'δύσκολο' και δεν υπάρχει λόγος να προσπαθείς να βρεις εναλλακτικό αλγόριθμο!


Εκτός και αν κάποιος αποδείξει πως P=NP δηλαδή πως ολα τα 'δύσκολα' προβλήματα ήταν στην πραγματικότητα 'εύκολα'!
Αλλα... ολα δείχνουν πως P!=NP αν και αυτο δεν εχει αποδειχτεί ακομα...
(Πολλοί πιστεύουν πως μια απόδειξη για το P!=NP βρίσκεται πέρα απο τις δυνατότητες των μαθηματικών. :hammer: )


Ο συλλογισμός που χρησιμοποιείται για την απόδειξη ειναι εξαιρετικά ευφυής αλλα οι λεπτομέρειες είναι πολλές και δεν τις θυμάμαι.
Με κάθε επιφύλαξη:
Δείχνεις πως το engine που εχεις για να λυνεις το TOH θα μπορούσε να χρησιμοποιηθεί για να λύσει και το πρόβλημα του Πλανόδιου Πωλητή. (η λεπτομέρειες της υλοποίησης του αλγοριθμου δεν μας αφορούν, μονο οι μετασχηματισμοί στα δεδομένα εισόδου και εξόδου απο το ενα προβλημα στο αλλο)
Αν το engine σου ετρεχε σε γραμικό χρόνο, τοτε θα μπορουσε να χρησιμοποιηθεί για να λυνει και το προβλημα του πωλητή σε γραμικό χρόνο.
Το πρόβλημα του πωλητή είναι γνωστό 'δύσκολο' πρόβλημα! :o που σημαίνει πως δεν υπάρχει -με καμια παναγια - τρόπος να λύθεί σε γραμικό χρόνο.
Αρα το TOH δεν μπορει παρα να είναι και αυτο 'Δυσκολο' πρόβλημα.
QED

Απάντηση

Επιστροφή στο “C, C++”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες