Descrivi una pendenza (N / M), approssimativamente come un piccolo numero di frazioni (n / m)

Question

Descrivi una pendenza (N / M), approssimativamente come un piccolo numero di frazioni (n / m)

#1 da (-1 voti)
#2 da (-1 voti)

-1

Quale algoritmo posso usare per descrivere un gradiente specificato (N / M) approssimativamente come la somma di un insieme di frazioni razionali {(n1 / m1) + (n2 / m2) ...}?

Limiti di design:

L'algoritmo prende come input (N, M) , descrivendo il vero gradiente N / M.
- N e M sono numeri interi.
- Se è importante: M è in genere intorno a 100-1000.
- Se è importante: N varia ampiamente, da bassa (1, gradiente superficiale) fino a dimensioni arbitrariamente grandi (quintilioni, gradiente estremamente ripido che si avvicina alla verticale).
L'algoritmo produce come output un piccolo set di tuple, { (n1, m1), (n2, m2), …} .
- La combinazione di tuple (n, m), quando combinate come frazioni, si avvicina molto al gradiente N / M.
- Il numero di tuple dovrebbe essere piccolo (mi aspetterei meno di 3).
- Ogni n e m è un numero intero.
- Ogni m è il più piccolo possibile, ma non inferiore al minimo per M (ad esempio 100).

Esempio

Dato l'input (50001, 1000)
- l'algoritmo può generare il set { (5000, 100), (1, 1000) }
- perché (50001/1000) == ((5000/100) + (1/1000)).
- L'output è buono perché è un piccolo set e i denominatori sono bassi, pur rimanendo al di sopra del minimo.
Dato l'input (14, 1000)
- l'algoritmo può generare il set { (1, 100), (1, 250) }
- perché (14/1000) == (1/100) + (1/250).
- L'output è buono perché è un piccolo set e i denominatori sono bassi, pur rimanendo al di sopra del minimo.
Dato l'input (5.07e+30, 1000)
- l'algoritmo può generare il set { (5.07e+29, 100) }
- perché (5.07e + 30/1000) == (5.07e + 29/100).
- L'output è buono perché è un piccolo set e i denominatori sono bassi, pur rimanendo al di sopra del minimo.

Non so per certo che quelle siano le migliori uscite; ma soddisferebbero i criteri.

Le formule matematiche sono apprezzate ma non sono un math-literate

La mia algebra non è abbastanza strong per descrivere questo in generale. Allo stesso modo, non sono in grado di guardare una descrizione in linguaggio matematico e sapere quale algoritmo descrive; né sono in grado di dire se effettivamente risponde a questa domanda.

Grazie per riferimenti come

ecc., ma non posso tradurlo in pseudo-codice per un algoritmo. Per favore suggerisci qualche pseudo-codice in una risposta, così posso capire se sta facendo quello che ho descritto.

algorithms arithmetic

posta bignose 09.01.2018 - 00:46

fonte

2 risposte

Leggi altre domande sui tag algorithms arithmetic

Considerazioni sulla progettazione del database per volumi di dati estremamente grandi Giudicatore di programmazione con sistema contro [chiuso]

score -1 · Answer 1

Questo è l'algoritmo corrente che ho; è un po 'esagerato, perché sto cercando di esprimere le parti in modo da poter capire come si forma il risultato.

Given 'step_max' is 1000
Given 'step_min' is 100

Function 'describe_gradient_as_fractions' with inputs 'N', 'M'

    Let 'fractions' be an empty set

    If 'N' <= 0:
        Return 'fractions'

    Let 'step_min_per_max' be ('step_max' / 'step_min')

    Let 'n' be the integer part of ('N' / 'step_min_per_max')
    Let 'm' be 'step_min'
    If 'n' > 0:
        Add a tuple ('n', 'm') to 'fractions'

    Let 'n_remain' be ('N' − ('n' * 'step_min_per_max'))
    Let 'step_remain' be the integer part of ('m_max' / 'm_remain')
    Let 'n' be the ceiling of ('n_remain' / ('m_max' / 'step_remain'))
    Let 'm' be 'step_remain'
    If 'n' > 0:
        Add a tuple ('n', 'm') to 'fractions'

    Return 'fractions'

score -1 · Answer 2

Nonostante non sia del tutto chiaro quali sono i requisiti, penso che potrei avere una bella risposta.

Inizia dividendo M nei suoi fattori primi. Ad esempio, se M = 5100 , puoi scrivere M come 2^2 * 3 * 5^2 * 17 .

Prendi il più grande di questi fattori primi che è minore o uguale a N e chiama questo q . Quindi, puoi riscrivere N come a * q + b . a può essere trovato dividendo N di q e arrotondando per difetto. b è il resto.

Usando lo stesso esempio, se N = 53 , allora q sarebbe 5^2 = 25 . N può essere riscritto come 2 * 25 + 3 .

Successivamente, dividi la frazione come segue.

N/M = a*q/M + b/M

Poiché q divide M, la frazione diventa

N/M = a/M' + b/M

Il risultato dell'esempio sarebbe

53/5100 = 2/204 + 3/5100

Puoi ripetere questo processo un paio di volte sul restante b/M . Il risultato finale sarebbe

53/5100 = 2/204 + 1/1700

(Se vuoi avere il minor numero possibile di divisioni, dovresti cercare di trovare la più grande combinazione di fattori primi più piccola o uguale a N e usare quel risultato come q .)