rand() για γεμισμα πινακα

[παπι]

@παπί

 

Είναι πολύ επικίνδυνο να περνάς rand() ως συνάρτηση σύγκρισης σε κάποιο sort για το οποίο δεν ξέρεις όλες τις λεπτομέρειες, μπορεί να γίνουν διάφορα περίεργα (π.χ. infinite loop). Αυτό δεν είναι πρόβλημα στην ίδια την quicksort αλλά είναι κακό σαν παράδειγμα και επιπλέον technically δεν ξέρεις αν η qsort κάνει quicksort. Η ενδεδειγμένη προσέγγιση όταν θες να κάνεις κάτι τέτοιο τόσο για πρακτικούς όσο και για διδακτικούς σκοπούς είναι Fisher-Yates.

 

 

Οντως. Τωρα βεβαια μου μπηκε το μικροβιο για να τη κανω out of the box 

[christodoulos]

ουσιαστικα για να γινει πιο απλο αυτο που με μπερδευει ειναι...
εχουμε εναν πινακα Α τριων θεσεων και θελουμε να τον γεμισουμε με αριθμους απο το 0 εως το 10 που να εχουν διαφορα ΤΟΥΛΑΧΙΣΤΟΝ 2...
δηλαδη αν γεμισουμε τον πινακα μας ετσι: Α[0]=2 A[1]=9  A[2]=6 τοτε τον γεμισαμε σωστα.δεν με ενδιαφερει απαραιτητα να μπουν κατα αυξουσα σειρα ,αφου αυτο μπορω να το πετυχω με μια φυσαλιδα μετα..

ευχαριστω

[παπι]

Αρα θες εναν (τυχαιο απο 0 εως 5) * 2

[migf1]

Αρα θες εναν (τυχαιο απο 0 εως 5) * 2

 

Αυτό δεν βγάζει μόνο ζυγά αποτελέσματα;

[Timonkaipumpa]

Βγάζει αλλά η λογική του είναι, νομίζω, αρκετά κοντά σε αυτό που εγώ πιστεύω ότι είναι η λύση στο last post του TS.

 

Μία ομαδοποίηση ενός rand stream σε bins εύρους 2 αριθμών θέλει η άσκηση. 

[migf1]

Όπως το διάβασα στα πεταχτά, εγώ θα το έκανα με τη λογική που περιγράφει ο defacer. Δεν το βλέπω να θέλει πάνω από 4-5 γραμμές κώδικα.

 

ΥΓ. Καλά που η άσκηση ζητάει έλεγχο μόνο με τον προηγούμενο αριθμό (και όχι με όλους τους προηγούμενους).

[PC_MAGAS]

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

 

• Βάλε ένα τυχαίο Στοιχείο στην θέση  0 πίνακα t
• Από i=1 ως i= το τέλος του πίνακα  κάνε
• Βάλε ένα τυχαίο αριθμό  από εσύ t[i-1]+n μέχρι όσο θες

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

[Timonkaipumpa]

Όπως το διάβασα στα πεταχτά, εγώ θα το έκανα με τη λογική που περιγράφει ο defacer. Δεν το βλέπω να θέλει πάνω από 4-5 γραμμές κώδικα.

 

ΥΓ. Καλά που η άσκηση ζητάει έλεγχο μόνο με τον προηγούμενο αριθμό (και όχι με όλους τους προηγούμενους).

 

Άσκηση; Ούτε καν... μόνο αυτή την σελίδα είδα

 

Οπότε μάλλον άκυρο είναι το μήνυμά μου

 

[Directx]

Θεωρώ και εγώ ότι η λύση του defacer είναι ικανοποιητική.

 

Από περιέργεια όμως ακολούθησα την εξής στρατηγική. Δημιούργησα έναν πίνακα (ας τον πούμε bucket) πχ. 4 θέσεων (όσες περισσότερες θέσεις - τόσο μεγαλύτερη ποικιλία / τυχαιότητα) τον οποίο γέμισα με αριθμούς που πληρούν την απαίτηση κάθε ένας από αυτούς να διαφέρει κατά 2 μονάδες.

 

Ύστερα από τον πίνακα αυτό (bucket), επέλεξα τόσες τυχαίες θέσεις όσες απαιτούνται (πχ. 3) φροντίζοντας να διαγράφω το περιεχόμενο κάθε μιας από το bucket με απλό τρόπο (μηδενίζοντας το περιεχόμενο της θέσης του πίνακα και ορίζοντας ως σύμβαση στο πρόγραμμα πως δεν μπορεί ποτέ να επιλέξει μια τυχαία θέση που περιέχει μηδέν), γεμίζοντας τελικά τον νέο πίνακα με τις απαιτούμενες τιμές.

 

Το μειονέκτημα.. ότι χρειάζομαι δυο πίνακες (μιας και πρέπει να γεμίσω έναν νέο) και χρόνο για την παραγωγή του bucket – το πλεονέκτημα.. ότι ο κώδικας είναι αρκετά απλός.

 

Για παράδειγμα, ένας πίνακας 3 αριθμών με διαφορά τουλάχιστον 2 μονάδων με αυτή την μέθοδο μπορεί να γεμίσει ως εξής: 

1.      4
2.      6
3.      2

Τώρα αν το πρόβλημα έχει κάποια άλλη παράμετρο.. ?

[defacer]

Δεν ξέρω αν υπάρχει περίπτωση να γίνει κάτι λάθος με τον αλγόριθμο που περιγράφεις μιας και δεν έχω καταλάβει τελικά ούτε ποιά είναι η "official" διατύπωση του προβλήματος ούτε και πώς εννοείς το "κάθε ένας να διαφέρει κατα 2 μονάδες" -- εννοείς ότι ο πίνακας δεν έχει διπλές καταχωρήσεις; Γιατί αν έχει (ή γενικότερα αν δεν πρόκειται για μια γνησίως μονότονη ακολουθία) τότε μπορεί να βάλεις τα νούμερα σε κάποια τυχαία σειρά η οποία δεν καλύπτει τις απαιτήσεις της εκφώνησης.

 

Το μεγαλύτερο όμως πρόβλημα είναι ότι η συμπεριφορά του αλγορίθμου δεν είναι ντετερμινιστική (και μάλιστα worst case scenario δεν τερματίζει ποτέ) και δεύτερον ανάλογα τα inputs μπορεί και το average case να είναι τραγικά αργό (π.χ. να γεμίσεις πίνακα 1Κ θέσεων με bucket 1Κ θέσεων).

 

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

 

In the interest of constructive criticism έτσι;

[Directx]

Yup.

 

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

Από εκεί και πέρα, η Wikipedia εδώ είναι - ας ρίξει μια ματιά αν θέλει κάτι (πράγματι) σωστό (Fisher-Yates)