Algoritmo ottimizzato per la conversione di una cifra decimale in una frazione "carina"

Question

Invece di convertire un decimale arbitrario in una frazione esatta (qualcosa come 323527/4362363), sto cercando di convertire solo in comune, facilmente distinguibile (in termini di leggibilità) quantità come 1/2, 1/4, 1/8 ecc.

Oltre a utilizzare una serie di confronti if-then, inferiore/uguale a ecc., esistono tecniche più ottimizzate per eseguire questa operazione?

Modifica: Nel mio caso particolare, le approssimazioni sono accettabili. L'idea è che 0.251243 ~ 0.25 = 1/4 - nel mio caso di utilizzo, è "abbastanza buono", con quest'ultimo più preferibile per la leggibilità umana in termini di un indicatore rapido (non usato per il calcolo, usato solo come numeri di visualizzazione).

Answer 1

È possibile utilizzare l'algoritmo euclideo per ottenere il più grande divisore comune tra enumeratore e denominatore e dividerlo per questo.

Answer 2

Cercare "approssimazione della frazione continua". Wikipedia ha una introduzione di base nel suo articolo "continua frazione", ma ci sono algoritmi ottimizzati che generano il valore approssimato durante la generazione della frazione.

Quindi scegliere un certo arresto euristico, una combinazione di dimensioni del denominatore e prossimità di approssimazione, per quando sei "abbastanza vicino".

Answer 3

Nel seguito, assumerò che i nostri decimali cadano tra 0 e 1. Dovrebbe essere semplice adattarlo a numeri più grandi e numeri negativi.

Probabilmente la cosa più semplice da fare sarebbe quella di scegliere il massimo denominatore che si troverà accettabile e quindi creare un elenco di frazioni tra 0 e 1 che hanno quei denominatori minori o uguali a loro. Assicurati di evitare qualsiasi frazione che possa essere semplificata. Ovviamente, una volta elencato 1/2, non è necessario 2/4. Puoi evitare le frazioni che possono essere semplificate controllando che il GCD del numeratore e del denominatore sia 1 che fa riferimento all'algoritmo di Euclide. Una volta che hai la tua lista. Valuta questi come numeri in virgola mobile (probabilmente raddoppia, ma il tipo di dati dipende ovviamente dalla tua scelta del linguaggio di programmazione). Quindi inseriscili in un albero di ricerca binario bilanciato che memorizza sia la frazione originale che la valutazione in virgola mobile della frazione. Dovresti farlo solo una volta per impostare le cose inizialmente, quindi il tempo n * log (n) (dove n è il numero di frazioni) non è molto.

Quindi, ogni volta che ottieni un numero, cerca semplicemente l'albero per trovare il numero più vicino ad esso che si trova nell'albero di ricerca. Nota che questo è leggermente più complicato della ricerca di una corrispondenza esatta perché il nodo che stai cercando potrebbe non essere un nodo foglia. Quindi, mentre attraversi l'albero, tieni un registro del nodo stimato più vicino che hai visitato. Una volta raggiunto un nodo foglia e confrontarlo con il nodo stimato più vicino che hai visitato, hai finito. Qualunque sia la tua persona più vicina, è la tua risposta.

Answer 4

Ecco un suggerimento: Assumendo che il frazione partenza è p/q

1. Calcolare r = p/q come valore razionale (virgola mobile) (ad esempior = float (p)/galleggiante (q))

2. Calcolare il arrotondate decimale x = int (10000 * r)

3. Calcolare MCD (denominatore massimo comune) di x e 10000: s = GCD (x, 10000)

4. rappresentare il risultato come m/n dove m = x/s ed n = y/s (tuo esempio calcola a 371/5000)

Normalmente, tutti i denominatori 1000 sono abbastanza leggibili.

Questo potrebbe non fornire il miglior risultato quando il valore è più vicino a casi più semplici come 1/3. Tuttavia, personalmente trovo 379/1000 molto più leggibile dall'uomo di 47/62 (che è la rappresentazione frazionaria più corta). È possibile aggiungere alcune eccezioni per perfezionare tale processo (ad es. Calcolare il p/GCD (p, q), q/GCD (p, q) e accettarlo se uno di questi è un valore a una cifra prima di procedere con questo metodo)

Answer 5

soluzione abbastanza stupida, solo per "l'anteprima" frazione:

 
factor = 1/decimal 
result = 1/Round(factor) 
mult = 1 

while (result = 1) { 
    mult = mult * 10 
    result = (1 * mult)/(Round(mult * factor)) 
} 

result = simplify_with_GCD(result) 

buona fortuna!