Meglio usare un esempio per descrivere il problema. Diciamo che ho un valore decimale 100.227273.Dato un numero decimale, trova il moltiplicatore intero più piccolo che dà un risultato intero
100,227273 * X = Y
ho bisogno di trovare il più piccolo intero X positivo che dà intero Y.
Se il 100.227273 è solo un'approssimazione e si desidera ottenere la migliore approssimazione razionale, utilizzare continued fractions.
Prendere 100.227273 come esempio.
in modo da ottenere
1
100.227273 = 100 + —————————
1
4 + —————
1
2 + —
2
semplificare questo espressione per ottenere 2205/22.
+1 per cercare di superare ciò che l'interlocutore ha chiesto, a ciò che probabilmente stanno tentando di fare. –
+1 per le frazioni continue. IIRC c'è un semplice algoritmo che usa solo 3 variabili di stato per andare arbitrariamente in profondità. – phkahler
1000000/gcd(1000000,227273). Conosciuto anche come lcm(1000000,227273)/227273. In questo caso, 1 milione.
Quello che si vuole fare è trasformare 0.227273 in una frazione nella forma più semplice. Il numero che stai cercando è quindi il denominatore di quella frazione. Dal momento che 227273/1000000 è già nella forma più semplice, il gioco è fatto. Ma se il tuo input era 100.075, allora il 75/1000 non è nella forma più semplice. La forma più semplice è 3/40, quindi la soluzione per X è 40.
Come ottimizzazione, puoi semplificare il calcolo perché sai che il denominatore iniziale è una potenza di 10, quindi i suoi unici fattori primi sono 2 e 5. Quindi tutto ciò che devi cercare nel numeratore è divisibilità per 2 e 5, che è più facile dell'algoritmo di Euclide. Naturalmente se hai già un'implementazione di gcd e/o lcm, allora questo è uno sforzo maggiore da parte tua, non di meno.
Tenere presente quando si ottiene il risultato, che i numeri in virgola mobile non possono in generale rappresentare le frazioni decimali con precisione. Quindi, una volta ottenuta la risposta matematicamente corretta, non sarà necessariamente fornire una risposta intera quando si effettua una moltiplicazione a virgola mobile. Il rovescio della medaglia è che ovviamente la domanda si applica solo se esiste un'espressione decimale finita del numero che ti interessa.
Se hai il numero come quoziente in primo luogo, allora devi trova il denominatore della sua forma più semplice direttamente, non convertendolo in decimale e troncandolo. Ad esempio, per risolvere questo problema per il numero "6 e un terzo", la risposta è 3, non una potenza di 10. Se l'input è "la radice quadrata di 2", non c'è soluzione per X.
Beh, in realtà, il più piccolo intero X con la proprietà che si richiede è 0, ma suppongo che non vuol dire che ;-)
e OP significa intero positivo. –
Ovviamente. Dare la risposta "giusta ma sbagliata" è solo il mio piccolo modo di sottolineare l'imprecisione nella domanda. –
No, -10.000.000.000 è molto più piccolo di 0.;) – kennytm
Se il valore decimale positivo D ha n cifre a destra del punto decimale , quindi D * 10^n è un numero intero e X = 10^n/gcf (10^n, D * 10^n) = lcm (10^n, D * 10^n) è il più piccolo intero positivo X.
Tranne che sembra che non sappia quante cifre la parte frazionaria sia in anticipo. –
Suppongo che il decimale di input r sia un numero razionale positivo r con una rappresentazione decimale terminante.
Sia d il numero di cifre dopo il punto decimale (presupporre che abbiamo eliminato tutti gli zeri estranei dalla rappresentazione decimale di r). Quindi notare che 10^d * r è un numero intero m. Let g = gcd(10^d, m). Quindi 10^d/g * r = m/g è un numero intero p. Lasciare q = 10^d/g. Io sostengo che q è il più piccolo di tali numeri interi positivi.
Ho una sensazione che realmente dire questo:
How to convert floats to human-readable fractions?
Dopo un esame penso che questo sia esattamente quello che userò :) – Davorin
Vuoi davvero dire decimale, o in virgola mobile? –
La rappresentanza non ha importanza, almeno non per me. – Davorin