Algoritmo ID univoco

Question

Algoritmo ID univoco

#1 da (3 voti)
#2 da (2 voti)
#3 da (1 voti)

0

Ho una rotta che contiene oggetti. Ognuno ha valore 0 o 1. Ho bisogno di un ID percorso univoco che identificherà qualsiasi ordine di oggetti. Attualmente lo sto facendo usando il numero binario che viene convertito in decimale (vedi immagine).

Il problema è che la quantità di oggetti nel percorso è fino a 15. Quindi il numero decimale sarà molto grande (fino a 32767) con molti valori, che non saranno mai usati.
Come convertire quel numero, in un altro valore univoco, ma molto più piccolo (< 255)? Ho bisogno di farlo, solo usando semplici operatori aritmetici (+, -, *, div).

algorithms math

posta Djent 08.05.2014 - 09:33

fonte

3 risposte

Leggi altre domande sui tag algorithms math

Quando si ottiene un elenco di file da elaborare, è necessario memorizzarli in un elenco di stringhe o in un elenco di Stream? [chiuso] Codice lingua per i segnaposti di traduzione e il contesto di traduzione?

score 3 · Answer 1

Hai l'equivalente di 15 bit di informazioni che devi salvare. Il numero binario più grande rappresentato da 15 bit è 32767 e non è affatto un caso che questo sia anche il numero massimo di combinazioni possibili (-1).

Non è possibile ridurre questo numero senza prima fornire una sorta di regola di semplificazione (ovvero il numero deve essere un numero dispari, il numero deve essere un palindromo, ecc.). Altrimenti è consentita la combinazione qualsiasi dei 15 bit.

Sebbene sia possibile eseguire operazioni matematiche per semplificare questo numero allo stesso modo, si perderebbero le informazioni nel processo e quindi sarebbe unidirezionale (non si riusciva a capire il numero originale invertendo l'operazione matematica ( s)).

score 2 · Answer 2

Supposto, viaggeremo solo su un determinato sottoinsieme di tutte le possibili rotte di sempre.

In tal caso, è possibile utilizzare una mappatura tra i percorsi e un ID numerico incrementato. Dovrai memorizzare tale mappatura da qualche parte, ma in questo modo ogni percorso utilizzato ottiene un ID univoco assegnato, che può essere usato per riferirlo successivamente.

Non sono così sicuro che questo sia un modo efficace per farlo, ma non hai chiesto questo aspetto.

score 1 · Answer 3

È impossibile perché ogni via può essere raggiunta (o no?). Hai tanti percorsi quanti 2 ^ 15

Forse devi considerare il fatto che alcuni di loro non appariranno mai (è vero?). Quindi puoi numerare solo questo di loro che può essere raggiunto. Questo diminuirà il numero di modi.

Per ridurre il numero di rotte da 0 a 255, devi eliminare circa 2 ^ 7 rotte. Ciò può significare che sette oggetti avranno sempre lo stesso valore (0 o 1).

Ad esempio

ffff1101fff10111
ffff0101fff00101
ffff0111fff10100

ecc ...