Cómo encontrar el menor número entero X en el que el Resto de X / Y = 0

Question

Estoy escribiendo un programa de compra de alimentos.

Quiero calcular el menor número de artículos que tengo que comprar para alcanzar la menor cantidad de dólares enteros.

Por ejemplo:

Los caramelos cuestan 0,11. Necesitas 100 caramelos para llegar a la cantidad de dólares enteros más cercana 11

( 100 * 0.11) = 11.0

Las manzanas cuestan 0,5 cada una. se necesitan 2 manzanas para llegar a la cantidad más cercana de 1 dólar

( 2 * 0.5) = 1.0

El helado cuesta 4,82 Necesitas 50 helados para llegar a la cantidad de dólares enteros más cercana 241

( 50 * 4.82) = 241.0

Creo que estoy tratando de resolver la ecuación X % Y = 0 para X. X debe ser un número entero. Y puede ser cualquier número racional positivo.

Puedo forzar la respuesta ejecutando un simple bucle:

var result : Number = ITEM_COST;

while(result % 1 != 0)
{
     result += ITEM_COST

}
return result / ITEM_COST;

Sin embargo, me gustaría tener un cálculo más elegante, si es posible.

Answer 1

Si $Y$ no es racional, no hay ningún número $X$ que funcione. Si $Y$ es racional, escríbalo en términos mínimos y $X$ es el denominador. Así que para sus ejemplos $0.11=\frac {11}{100}$ y $X=100$ , $0.5=\frac 12$

Answer 2

Estás buscando el mínimo común múltiplo de $100$ y otro número el precio en céntimos. El número $100$ no tiene factores primos excepto $2$ y $5$ : $$ 100 = 2\times2\times5\times5. $$

Digamos que el precio en céntimos es $3080$ (es decir, es $\$ 30.80 $). Look at how many $ 2 $s and $ 5 $s you can pull out of that. $$ 3080 = 2 veces1540= 2 veces2veces770 = 2 veces2veces385 = 2 veces2veces2veces5veces77 $$ Three $ 2 $s and one $ 5 $. To get a multiple of $ 100 $ you need at least two $ 2 $s, and you've got those in this case, and at least two $ 5 $s, and you have only one. So you need another $ 5 $. So it takes five items to get an integer number of dollars: $$ 5\N-tiempos \$30.80 = \$ 154.00

Sólo hay que multiplicar por tantos $2$ y $5$ s que se necesitan para conseguir al menos dos $2$ s y al menos dos $5$ . Si el precio en céntimos no es divisible por $2$ o $5$ entonces necesitarás dos de cada uno, así que multiplicarás por $2\times2\times5\times5$ o $100$ .

Así que en cada caso el número de elementos necesarios es: \begin{align} \text{either } & 1 & & = 1 \\ \text{or } & 2 & & =2 \\ \text{or } & 2\times 2 & & = 4 \\ \text{or } & 5 & & = 5 \\ \text{or } & 2\times 5 & & = 10 \\ \text{or } & 2\times2\times5 & & = 20 \\ \text{or } & 5\times5 & & =25 \\ \text{or } & 2\times5\times5 & & =50 \\ \text{or } & 2\times2\times5\times5 & & =100 \end{align}

Answer 3

Suponiendo que la parte fraccionaria de $Y$ tiene como máximo $2$ dígitos decimales, el valor de $X$ es $\frac{100}{\gcd(100Y,100)}$

Este es el pseudocódigo para calcular el GCD de dos enteros positivos:

Function GCD(a,b):
    If a > b return gcd(a,b)
    Otherwise return gcd(b,a)

Function gcd(a,b):
    Set c = a mod b
    If c = 0 return b
    Otherwise return gcd(b,c)