ασκηση στην c

[vaggos_ece]

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

Epan3(1).pdf

[Technology fan]

Ωραίο, σίγουρα δεν σαν είπαν για το πως να κατασκευάσετε τέτοια ακολουθία? μου φαίνεται λίγο δυσκολάκι για απλή εξοικείωση

 

Η δική μου λύση θα ήταν ως εξής:

 

Έστω ότι έχουμε Ν αριθμούς και κάθε αριθμός συμβολίζεται με x: 

 

1) Θα έφτιαχνα τον 2d πίνακα (NxN) D(i,j)=x(i)-x(j)

2) Μετά θα έφτιαχνα έναν μονοδίασταο πίνακα (N^2) με τα πίνακα του D ταξινομημένα αλλά να ξέρω σε κάθε θέση του πίνακα η διαφορά ποιων αριθμών αντιστοιχεί

3) Μετά κάποιου είδους αναδρομή στον πίνακα κρατώντας πάντα τα στοιχεία των αριθμών που έχεις επισκευφτεί αλλά δεν είναι τόσο απλό.

 

Ίσως να υπάρχει και κάποια απλή λύση 

[vaggos_ece]

ναι καλη ιδέα  και το 2 γινεται απο την στιγμη που τα i,j δηλωνουν τους αριθμους που αφερεις... οσο για το 3 θα είναι μεγάλο μπλεξιμο.

[albNik]

Παρε μηδεν εως Ν στοιχεια ταξινομισε τα σε αυξουσα σειρα, τα υπολοιπα σε φθινουσα και "κόλλα" τις δυο ακολουθίες. Μετα ελεγξε αν ειναι αυξουσες οι διαφορες.

 

π.χ. 

10,7,4,2 οχι

7|10,4,2 οχι

4|10,7,2 ΟΚ

2|10,7,4  οχι

2,7|10, 4 ΟΚ

 

Η τελικη ακολουθια θα αποτελειται απο δυο υπο-ακολουθιες, μια αυξουσα και η αλλη φθινουσα (μπορει καποια απο τις δυο να ειναι κενή). Θα εχει μια κορυφή, χωρις σκαμπανεβασματα.

[vaggos_ece]

θα το δοκιμάσω... τώρα έχω βάλει τις διαφορές σε δισδιάστατο 15x15 ταξινομω οριζόντια μετα καθετα και παράλληλα εχω δισδιάστατο πινακα που κρατάω τις θέσεις που άλλαξα και μάλλον πρέπει να παίξω φιδακι για να βρω την ακολουθιά .... λετε να βγαίνει ετσι?

[albNik]

Αν το μεγαλυτερο στοιχειο ειναι πχ. 100 πρεπει ολα στα αριστερα του (αν υπαρχουν) να ειναι ταξινομημένα σε αυξουσα , και ολα στα δεξια του σε φθινουσα.

Αυτο ειναι απαραίτητο αλλα οχι ικανο (γιαυτο πρεπει να εξεταστουν οι διαφορες) αλλα περιοριζει πολυ τους συνδυασμούς.

[AlexHello]

Περιεργη ασκηση. Ενω προσπαθουσα να κωδικοποιησω τον αλγοριθμο που προτεινε ο albNik επεσα πανω στους αριθμους

42, 23, 79, 19 οι οποιοι δεν νομιζω οτι μπορουν να ταξινομηθουν οπως ζηταει η ασκηση. Ή απλα ειμαι πολυ κουρασμενος και δεν ξερω τι μου γινεται. Μεχρι και ολα τα permutations εβγαλα και δεν μπορεσα να βρω καποια αυξουσα σειρα βασει των διαφορων

[albNik]

Ναι δεν υπαρχει παντα λυση...

 

Εγω θα ελεγχα μονο τους παρακατω απο τους 24 συνδυασμους

Στα αριστερά του 79 ειναι σε αυξουσα, στα δεξια σε φθινουσα

 

19,23,42,79

19,23,79,42

19,42,79,23

23,42,79,19

19,79,42,23

23,79,42,19

42,79,23,19

79,42,23,19

[vaggos_ece]

συγκεκριμενα εχω 15 αριθμους, αρχικα εχω 2 αριθμους αριστερα πρεπει εκει να βάλω ολους τους δυνατους συνδιασμους, μετα για 3 κτλπ... πως γίνεται?

[albNik]

βαζεις το μεγαλυτερο πρωτο ολα μετα απ αυτον σε φθινουσα,

μεγαλυτερο δευτερο, 1 πριν απο αυτο και ολα τα αλλα μετά (14 φορες)

μεγαλυτερο τριτο, 2 πριν απο αυτο και ολα τα αλλα μετά (14*13/2 φορες)

μεγαλυτερο τεταρτο, 3 πριν απο αυτο και ολα τα αλλα μετά (14*13*12/6 φορες)

...

μεγαλυτερο τελευταίο 

 

αντι για 15!=1307674368000 συνδυασμους θα κανεις 1+14+14*13/2+14*13*12/6+....=.2¹⁴=16384

 

Για combinations google

π.χ.

http://stackoverflow.com/questions/5095407/all-combinations-of-k-elements-out-of-n

[Technology fan]

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

 

α) Φαντάσου τους αριθμούς οτι είναι κόμβοι σε ένα γράφημα,

β) όλοι ενώνονται με όλους και κάθε ακμή συμβολίζει την διαφορά τους  (τον πίνακα D που έλεγα πιο πριν). 

 

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

 

Τέλος, πιστεύω μια DFS διάσχυση του γράφου είναι ότι πρέπει.. 

[vaggos_ece]

Να σου πω την αληθεια λίγα κατάλαβα.σε πινακα ΝxN βάζω τις διαφορές τους και ξεκινάω απο στήλη καταληγω σε μια γραμμη μετα συναχιζω στην ίδια γραμμη και ψαχνω την επομενη στηλη με συνθηκη να βρω μεγαλητερη διαφορα.καθε φορα που δεν βρησκει παω ενα βήμα πισω . κατι τετοιο δεν λες?

[Technology fan]

Να σου πω την αληθεια λίγα κατάλαβα.σε πινακα ΝxN βάζω τις διαφορές τους και ξεκινάω απο στήλη καταληγω σε μια γραμμη μετα συναχιζω στην ίδια γραμμη και ψαχνω την επομενη στηλη με συνθηκη να βρω μεγαλητερη διαφορα.καθε φορα που δεν βρησκει παω ενα βήμα πισω . κατι τετοιο δεν λες?

 

Σωστά...κάθε φορά που δεν βρίσκει πάει ένα βήμα πίσω, αυτό κάνει η διάσχιση DFS. υπόψιν οτι ο κόμβος από τον οποίο ξεκινάς ενδέχεται να μην είναι σωστός οπότε θα πρέπει να συμπεριλάβεις και τον πρώτο κόμβο στην έυρεση του μονοπατιού. Σίγουρα πάντως ο πιο εύκολος δρόμος είναι αυτός που ξέρεις οπότε αν δεν σε βοηθάει η αντιστοιχία/σκέψη με το γράφημα δεν είναι ανάγκη να την ακολουθήσεις, η λύση που προτάθηκε από τον @albNik είναι παρόμοια, απλά είναι σχετικά δύσκολη η παραγωγή των πιθανών συνδυασμών, ενώ η αναδρομή στο DFS αναλαμβάνει σχεδόν από μόνη της να βρει έναν συνδυασμό. 

[albNik]

Μια απλοποίηση στην δικια μου προσέγγιση :

ο μικροτερος αριθμος μπορει να ειναι μονο στην πρωτη ή τελευταία θεση

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

κλπ

 

κώδικας σε C#  (πατα execute)

 

http://goo.gl/BdzG5R

[vaggos_ece]

Σωστά...κάθε φορά που δεν βρίσκει πάει ένα βήμα πίσω, αυτό κάνει η διάσχιση DFS. υπόψιν οτι ο κόμβος από τον οποίο ξεκινάς ενδέχεται να μην είναι σωστός οπότε θα πρέπει να συμπεριλάβεις και τον πρώτο κόμβο στην έυρεση του μονοπατιού. Σίγουρα πάντως ο πιο εύκολος δρόμος είναι αυτός που ξέρεις οπότε αν δεν σε βοηθάει η αντιστοιχία/σκέψη με το γράφημα δεν είναι ανάγκη να την ακολουθήσεις, η λύση που προτάθηκε από τον @albNik είναι παρόμοια, απλά είναι σχετικά δύσκολη η παραγωγή των πιθανών συνδυασμών, ενώ η αναδρομή στο DFS αναλαμβάνει σχεδόν από μόνη της να βρει έναν συνδυασμό. 

δυστηχος είμαι 1ο ετος στους ηλ/μηχ και δεν έχω ασχοληθει με γραφήματα .Εργασία για να λύσεις/φτιάξεις λαβυρινθο είναι οχι 3ο εργαστηριο.