Ασκηση προγραμματισμου

[V.I.Smirnov]

Δες στο http://en.wikipedia.org/wiki/Knight's_tour. Προσωπικά (και σε C++/STL) μου φάνηκε ευκολότερη η υλοποίηση του "Warnsdorff’s algorithm".

 

 

Η αναδρομική συνάρτηση όντως είναι δύσκολο να σχεδιαστεί σωστά.

Καλή η υλοποίησή σου, θα την μελετήσω με πρώτη ευκαιρία...

 

 

Ξέχασες να γράψεις και αυτό.

 

Λάθος κάνεις, δεν το ξέχασα. Απλώς κουράστηκα και δεν θέλω να ασχοληθώ περισσότερο.

Παρατήρησε ότι το πρόγραμμά μου μετράει το πλήθος των αναδρομικών κλήσεων και τις αποδίδει

τόσο σε κάθε εύρεση λύσης όσο και συνολικά στο τέλος.

Το πλήθος των πράξεων σε κάθε κλήση είναι γνωστό με απλή εποπτεία του κώδικα.

Πολλαπλασιάζοντάς το με το πλήθος των αναδρομικών κλήσεων που μετρήθηκαν μπορεί να βρεθεί το

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

[bxenos]

@V.I.S...: πολλές γραμμές δεν είναι για αναδρομή; Η αναδρομή έχει τη λογική να λύσει πρόβλημα με ελάχιστο κώδικα.

[GRAPS]

V.I.Smirnov ευχαρηστω για την λυση..δεν το ειχα σκεφτει ετσι...δεν προκειτε να την παραδωσω ετσι...γιατι δεν την καταλαβαινω..δεν ζητησα λυση..ιδεες μονο..θα την μελετησω και θα γραψω τις ερωτησεις μου..συγνωμη για τα ορθογραφικα...

[V.I.Smirnov]

@V.I.S...: πολλές γραμμές δεν είναι για αναδρομή; Η αναδρομή έχει τη λογική να λύσει πρόβλημα με ελάχιστο κώδικα.

 

Αν την παρατηρήσεις προσεκτικά θα δεις ότι δεν είναι πολλές.

Ως κώδικας είναι απλούστατη και χρησιμοποιεί μόνο έναν 2D πίνακα. Ούτε STL, ούτε κλάσεις, ούτε τίποτε άλλο.

Δυο συναρτήσεις είναι όλο κι όλο. Η αναδρομική είναι η moveKnight που κάνει τις 8 δυνατές κινήσεις του ίππου.

Και υπάρχει και μια βοηθητική, η isLegalMove, που ελέγχει ότι το τεράγωνο είναι μέσα στη σκακιέρα και δεν έχει σαρωθεί.

Τα υπόλοιπα είναι βοηθητικά και συνολικά είναι λιγότερα απ' ότι στην επαναληπτική που δίνει ο DirectX.

Η λύση του DirectX ίσως να είναι πιο εύκολο να την συλλάβεις αλλά χρησιμοποιεί περισσότερα παρελκόμενα.

[bxenos]

Αν την παρατηρήσεις προσεκτικά θα δεις ότι δεν είναι πολλές....

ο topic starter δεν ξέρω αν το παρατήρησες αλλά έσβησε το αρχικό μήνυμα και εξαφανίστηκε (θα εμφανιστεί με άλλο username στην επόμενη άσκηση για να βρεί λύση).

 

Δεν έχω compiler εδω που είμαι για να δοκιμάσω το παρακάτω, αλλά θα σου δώσω ένα δείγμα αναδρομικής συνάρτησης σαν παράδειγμα μόνο γιατι δεν σκοπεύω να μοιράζω λύσεις σε τεμπέληδες (σαν τον topic starter)

 

>
struct point { 
coord x, y; 	//valid coordinates in [1,N]
point() { 
	x = y = 0; 		//invalid checkboard point
}
point(coord xx,coord yy);
int operator(const point& a) const;
bool valid(void) const {
	return (x>0 && y>0 && x<=N && y<=N);
}
};

static bool _try(point Start,point *moves,size_t level){
bool test = true;	//επιτυχία=TRUE,αποτυχία=FALSE
if(level<N*N){
	{//is the position in test valid?
		if(!Start.valid())
			test = false;
		for(size_t i=0 ; i<level && test ; i++)
			if(moves[i] == Start)
				test = false;	//dead end: this box, have been used again
	}
	if(test){
		moves[level++] = Start;	//σημείωσε την τρέχουσα κίνηση
		test = false;//υποθέτουμε ότι δεν έχει λύση και αρχίζουμε το ψάξιμο
		for(unsigned short mask=0;mask <8 && !test; mask++){//δοκίμασε όλες τις κινήσεις
			short 	dx = (mask&1?1:-1)*((mask & 4)?1:2), 
				dy = (mask&2?1:-1)*(((~mask) & 4)?2:1);//undocumented!
			if(_try(point(Start.x+dx,Start.y+dy),moves,level))
				test = true;	//βρέθηκε λύση. Μην συνεχίσεις το ψάξιμο
		}
		if(!test)//sorry, αδιέξοδο, ακύρωσε τη διαδρομή απο εδω και κάτω
			moves[--level] = point();
	}
}//else: checkboard completed
return test;
}

void solve(void){
moves = new poiny[N*N];//πίνακας με κινήσεις, γεμίζει προς 
if(moves){
	if(_try(point(0,0),moves,0))
		for(size_t i=0,k=N*N;i<k && moves[i].valid();i++)
			printf("%u: x=%u y=%u\n",(unsigned)i,(unsigned)moves[i].x,(unsigned)moves[i].y);
	//else: δεν βρέθηκε λύση
	delete []moves;
}
}

[V.I.Smirnov]

ο topic starter δεν ξέρω αν το παρατήρησες αλλά έσβησε το αρχικό μήνυμα και εξαφανίστηκε (θα εμφανιστεί με άλλο username στην επόμενη άσκηση για να βρεί λύση).

 

Δεν έχω compiler εδω που είμαι για να δοκιμάσω το παρακάτω, αλλά θα σου δώσω ένα δείγμα αναδρομικής συνάρτησης σαν παράδειγμα μόνο γιατι δεν σκοπεύω να μοιράζω λύσεις σε τεμπέληδες (σαν τον topic starter)

 

Σε περίπτωση που την γράψεις ολόκληρη θυμήσου να μου στείλεις όλο τον κώδικα με pm για να έχω και την εκδοχή της με stack.

Επειδή το πρόβλημα είναι ενδιαφέρον και ασχοληθήκαμε προτείνω να μεταφερθεί σε ειδικό thread ή tutorial.

Kαιν μην ανησυχείς για το κλεψιμέικο της ιστορίας, το είπε και ο ίδιος ο topic-starter ότι δεν καταλαβαίνει τις λύσεις μας...

[javavall]

V.I.Smirnov από διεξοδική ανάλυση προβλημάτων τα πας καλά.

Από προγραμματισμό χρειάζεσαι εξάσκηση.

 

Χαρακτηριστικά να αναφερθώ σε 2 σημεία.

- Δεν χρειάζεται να τα κάνεις όλα unsigned. Ειδικά τους μετρητές σε for loops. Κάνεις πιο αργό το πρόγραμμα. Στους σημερινούς επεξεργαστές είναι λάθος να το κάνεις αυτό, γιατί δουλεύουν με 32/64bit .

- Γράφεις πολύπλοκο κώδικα. πχ η isLegalMove και moveKnight είναι κακογραμμένες.

 

Ενδεικτικά: για την isLegalMove

>int isLegal(x,y){
return((0 <= x) && (x < m) && (0 <= y) && (y < m));
}

 

για το moveKnight:

Με έναν απλό πίνακα που περιέχει ολές της δυνατές κινήσεις μπορείς απλά να αυξάνεις έναν counter και να παίρνεις τις συντεταγμένς για την επόμενη πιθανή κίνηση.

>
int Move[] = {-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};
χ=Move[counter++];
y=Move[counter++];

 

Επειδή το πρόβλημα είναι ενδιαφέρον και ασχοληθήκαμε προτείνω να μεταφερθεί σε ειδικό thread ή tutorial.

Δεν νομίζω ότι είναι και κάτι το φοβερό. Είναι μια τετριμμένη άσκηση φοιτητών πληροφορικής σε πολλά πανεπιστήμια ανά τον κόσμο. Με αποτέλεσμα να υπάρχει αρκετό υλικό στο διαδίκτυο με αναλύσεις, παραδείγματα, παιχνίδια και πηγαίος κώδικας σε java/c/c++ κλτ

[V.I.Smirnov]

@javaval

 

1) Φίλε μου εγώ σπουδάζω άλλο πράγμα - όχι πληροφορική - και δεν έχω συστηματική εκπαίδευση στον προγραμματισμό.

Ότι γράφω είναι από την σκοπιά ενός ερασιτέχνη μόνον.

Αυτά που ξέρω είναι ήδη πολύ περισσότερα από όσο αρμόζει σε έναν μη ειδικό.

Και από αυτή την άποψη, κανένα κακκεντρεχές σχόλιο δεν μπορεί να μειώσει την εμπιστοσύνη στον εαυτό μου.

 

2) Έγραψα το πρόγραμμα μέσα σε μια νύχτα.

Ο κώδικας είναι quick & dirty, δεν έκανα ραφινάρισμα αλλά θα το κάνω στο μέλλον αφού

μπήκα στον κόπο να ασχοληθώ. Οι παρατηρήσεις σου για τις βελτιώσεις είναι δεκτές.

 

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

Οι φοιτητές πληροφορικής προφανώς την ξέρουν.

 

4) Το πρόβλημα δείχνει απλό όπως είναι τώρα.

Για δοκίμασε να το γράψεις στο openMP ώστε να εκτελείται παράλληλα... ή ακόμη χειρότερα στο MPI...

 

Συνεπώς, λόγω των 3) και 4) θα μπορούσε να γίνει αρκετή συζήτηση από τους ειδήμονες.

Εξάλλου, πολύ περισσότερο τετριμένα είναι κάποια tutorials που έχουν παρατεθεί από μέλη του forum και μάλιστα όχι όλα γραμμένα με καλό τρόπο.

Παραταύτα κανείς δεν τα απαξίωσε, οι περισσότεροι που τα διάβασαν τα επαινούν λες και πρόκειται για κάτι εξαιρετικό.

Εγώ, για όσα δεν μου άρεσαν ή δεν βρήκα χρήσιμα, χαμογελώ μόνον και δεν σχολιάζω επικριτικά την προσπάθεια των άλλων.

Κάνε λοιπόν κι΄εσύ το ίδιο τώρα.

[javavall]

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

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

Τέλος να επαναλάβω ότι δεν είχα σκοπό ούτε με το ύφος μου , ούτε με τα λεγομενά μου να σε απαξιώσω.

 

Για δοκίμασε να το γράψεις στο openMP ώστε να εκτελείται παράλληλα... ή ακόμη χειρότερα στο MPI...

 

Ευχαρίστως! Μάθημα του εξαμήνου μου η παράλληλη επεξεργασία. Pthread, openMP..

[C6WGMN]

Ευχαρίστως! Μάθημα του εξαμήνου μου η παράλληλη επεξεργασία. Pthread, openMP..

 

Σιγά τα ωά με το openMP, πολύ απλό στην χρήση! Άσχετο, αλλά για pthreads προτείνω σε όλους το βιβλίο του Butenhof.

[V.I.Smirnov]

Δεν είχα κακές προθέσεις προς θεού, ούτε να σε επικρίνω, ούτε να μειώσω την προσπαθειά σου.

Αντιθέτως, βλέπω έναν άνθρωπο που θέλει να μάθει και προσπάθησα να βοηθήσω.

Βέβαια αλλάζει το θέμα, εφόσον δεν είναι το αντικείμενό σου η πληροφορική, μπορείς να παραβλέψεις όλα αυτά που είπα.

Εκπλήσσομαι που είναι έτσι τα πράγματα, γιατί οι γνώσεις σου επί του θέματος άλλο έδειξαν.

Μακάρι να ήταν στο επιπεδό σου πολλά άτομα που σπουδάζουν το αντικείμενο και δεν ξέρουν τι τους γίνεται.

Τέλος να επαναλάβω ότι δεν είχα σκοπό ούτε με το ύφος μου , ούτε με τα λεγομενά μου να σε απαξιώσω.

 

Ευχαρίστως! Μάθημα του εξαμήνου μου η παράλληλη επεξεργασία. Pthread, openMP..

 

Καλά, δεν επρόκειτο να μαλώσουμε. Μερικές φορές μπορεί να έχουμε εριστικό ύφος άθελά μας.

 

Όσο για την παράλληλη επεξεργασία, πριν δυο-τρία χρόνια είχα ασχοληθεί αρκετά.

Το openMP το μελέτησα πολύ καλά διότι μπορούσε να χρησιμοποιηθεί εύκολα και στην Fortran όπου δουλεύω περισσότερο.

Και ακριβώς γι αυτό δεν ασχολήθηκα με τα posix threads.

Το MPI ήταν κόλαση. Για να γράψω μια ρουτίνα για LU παραγοντοποίηση πίνακα, μου πήρε πάνω από 2 εβδομάδες.

Τελικά τα κατάφερα και δούλεψε όπως ήθελα αλλά έκτοτε το παράτησα.

(Επ΄αυτού θα επανέλθω κάποια στιγμή διότι θέλω να ρωτήσω κάποια πράγματα).

 

Το συγκεκριμένο πρόβλημα στο openMP, θα μπορούσε να εκμεταλευτεί τις νέες εντολές task & taskwait που έχει το openMP 3.0

με τις οποίες δυστυχώς δεν είμαι εξοικοιωμένος διότι όταν το μελετούσα υπήρχε μόνον η έκδοση 2.5 και δεν υφίσταντο.

Ισως κάποια στιγμή στο μέλλον βρω χρόνο να τις ασχοληθώ...