Gray Codes

[Cue]

Δε ξέρω πόσοι από εσάς τους γνωρίζουν.

 

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

 

Για παράδειγμα,

 

0=0000

1=0001

2=0011

3=0010

4=0110

5=0111

6=0101

7=0100

8=1100

9=1101

10=1111

11=1110

12=1010

13=1011

14=1001

15=1000

 

Το πρόβλημα είναι να βρεθεί ένα ελάχιστο σύνολο μοντέλων (patterns) το όποιο θα ταιριάζει σε μια τυχαία σειρά αριθμών οι οποίοι θα είναι σε μορφή Gray Codes.

 

Στο παράδειγμα απο πάνω π.χ. έχουμε:

 

Το μοντέλο: (0XXX) ταιριάζει στην σειρά 0-7.

Το μοντέλο: (0110 ή 01X1) ταιριάζει στην σειρά 4-6.

Το μοντέλο: (0X10 ή X100 ή X1X1) ταιριάζει στην σειρά 3-10.

 

Το Χ υποδηλώνει πως μπορεί να έχει οποιαδήποτε τιμή.

 

Αλλά αυτός είναι ο ποιο απλός αλγόριθμος φυσικά.

Μπορείτε να σκευτείτε κάποιον άλλο που να υπάρχουν λιγότερα Το μοντέλα?

 

<small>[ 01-03-2002, 18:43: Το μήνυμα επεξεργάστηκε από: Cue ]</small>

[Mihos_Gr]

file mou o parapanos kwdikas anaparista to 16 systhma? an nai soory alla einai la8os...

[Teoulas]

Όχι, αυτός λέγεται κώδικας του Gray και δεν είναι η δυαδική αναπαράσταση των δεκαδικών αριθμών 0-15. Όμως δεν κατάλαβα τι ακριβώς ζητάει ο φίλος cue.

 

<small>[ 02-03-2002, 02:26: Το μήνυμα επεξεργάστηκε από: Teoulas ]</small>

[bandito]

Απο βιβλιογραφία δεν βρήκα τίποτα γι'αυτο που λές.

Απ'οτι καταλαβαίνω, αυτο που ζητάς είναι την βέλτιστη καλύτερη αναπαράσταση n δυαδικών αριθμών με k μοντέλα.

Υπάρχει μαθηματικός τύπος (πιστεύω) και επιφυλάσσομαι.

[Cue]

Ακριβώς αυτό που λέει ο Teoulas,

Και συμπληρώνει ο bandito.

<img border="0" title="" alt="[big Grin]" src="images/icons/grin.gif" />