Realmente estamos haciendo las monedas correctas desde un punto de vista matemático? Es una moneda de un centavo,cinco centavos, diez centavos un trimestre y 1,5,10,20,50 y los billetes de 100 dólares la configuración óptima? O hay una mejor configuración que puede ser más útil? Lo que crees. Se me ocurrió esta pregunta porque yo estaba pensando en el sistema métrico, y de cómo fue mucho más intuitivo y me preguntaba si el mismo es cierto acerca de la moneda.
Respuestas
¿Demasiados anuncios?
Como otros han dicho, depende de cómo se defina "óptima".
Voy a asumir que usted le preguntó: "¿Qué conjunto de las monedas, se minimiza la cantidad de monedas necesarias en una transacción en efectivo, suponiendo que todos los 100 posibles valores de las monedas de diez centavos/centavos lugares son igualmente probables?" (Esta suposición no es del todo cierto, en realidad, debido a cosas como las máquinas expendedoras que no aceptan monedas de un centavo. También hay 99¢ psicológica de precios, pero el impuesto de ventas tiende a cancelar).
Voy a seguir suponga que usted va a utilizar el algoritmo voraz para el cambio.
def num_coins(amount, denominations):
result = 0
for coin in sorted(denominations, reverse=True):
result += amount // coin
amount %= coin
if amount != 0:
raise ValueError('Cannot make change for amount with the given coins')
return result
El promedio de número de monedas por transacción puede ser calculada como:
def avg_num_coins(denominations):
return sum(num_coins(amount, denominations) for amount in range(100)) / 100.0
Aplicando esto a las {1, 5, 10, 25} el conjunto de NOS las monedas, da un promedio de 4.7 monedas por transacción (2 peniques + 0.4 níquel + 0.8 dime + 1.5 cuartos).
¿Cuál es la óptima?
Trivally, 1.0. Tiene un 99 diferentes denominaciones de monedas de 1¢ 99¢. Sin embargo, esto haría que las cajas registradoras bastante difícil de manejar. Así, una mejor pregunta sería, ¿cuál es la óptima dada una restricción en el número de monedas en circulación?
Con 1 denominación
Con el fin de ser capaz de hacer cualquier cantidad 1¢ o superior, la moneda más pequeña tiene que ser de 1¢.
Con una moneda de un centavo-sólo denominación del sistema, el promedio de número de monedas por transacción es de 49.5. Obviamente no es muy eficiente.
Con 2 denominaciones
Encontrar x tal que avg_num_coins({1, x}) se reduce al mínimo. Esto puede ser fácilmente obtenida por la fuerza bruta, tratando de que todos los valores de x entre 2 y 99. Tengo dos soluciones óptimas, ambos de los cuales resultan en un promedio de 9 monedas por transacción:
- 1¢ y 10¢
- 1¢ y 11¢
De estos, es probable que prefiera utilizar 10¢ monedas en lugar de 11¢ monedas, por la facilidad de la aritmética.
Con 3 denominaciones
Dos combinaciones de denominaciones dar el mínimo de 5.26 monedas por transacción:
- 1, 5 y 22¢
- 1, 5 y 23¢
Limitado a los factores de 100
Si usted está dispuesto a tolerar la ineficiencia de 5.5 monedas en lugar de 5.26, usted podría tener uno de los siguientes:
- 1, 4 y 20¢
- 1, 5, y 20¢
- 1, 5 y 25¢
Con 4 denominaciones
Nuestro {1, 5, 10, 25} sistema con un promedio de 4,7 monedas por transacción es, de hecho, no son las óptimas. En su lugar, podríamos utilizar uno de los siguientes conjuntos de denominaciones, con un promedio de sólo 4.1 monedas por transacción:
- 1, 3, 11 y 37¢
- 1, 3, 11 y 38¢
Limitado a los factores de 100
Desafortunadamente, los sistemas antes mencionados, hacen que sea difícil hacer el cambio por un dólar. En lugar de un bonito y fácil 2 medio de dólares, 4 cuartos, o de 5 a 20 céntimos, tendrías que romper un dólar en 37 + 37 + 11 + 11 + 3 + 1 o 38 + 38 + 11 + 11 + 1 + 1.
Una alternativa con un promedio de 4.6 monedas por transacción (un poco mejor que el status quo) sería tener un {1, 4, 10, 25} sistema (es decir, reemplazar el níquel con un 4 centavos).
Con 5 denominaciones
Un promedio de 3.46 monedas por transacción puede ser obtenida con cualquiera de las combinaciones:
- 1, 3, 7, 16, 40¢
- 1, 3, 7, 16, 41¢
- 1, 3, 7, 18, 44¢
- 1, 3, 7, 18, 45¢
- 1, 3, 8, 20, 44¢
- 1, 3, 8, 20, 45¢
Limitado a los factores de 100
Un promedio de 3.76 monedas por transacción puede ser obtenido con el conjunto de {1, 4, 10, 25, 50}.
Con 6 denominaciones
Un promedio de 3.13 monedas por transacción puede ser obtenida con cualquiera de las siguientes:
- 1, 2, 5, 11, 25, 62¢
- 1, 2, 5, 11, 25, 63¢
- 1, 2, 5, 13, 29, 64¢
- 1, 2, 5, 13, 29, 65¢
Limitado a los factores de 100
Un promedio de 3.36 monedas por transacción puede ser obtenido con el conjunto de {1, 2, 4, 10, 25, 50}.
El Euro céntimos de {1, 2, 5, 10, 20, 50} apenas se echa de menos la optimalidad, con 3.4 monedas por transacción.
En general
Un conjunto de denominaciones es "óptima" si hace que las relaciones entre consecutivos denominaciones tan iguales como sea posible. Por ejemplo, {1, 5, 22} el conjunto de las relaciones de 5¢/1¢ = 5, 22¢/5¢ = 4.4, y $1/22¢ = 4.545454... Esto puede ser visto como un entero aproximación a {1, 100^(1/3), 100^(2/3)} = {1, 4.641588833612778, 21.544346900318832}.
La vida Real de las monedas sacrificio "optimalidad" con el fin de hacer las denominaciones de niza ronda los números en base diez. Efectivamente, este hecho limita las relaciones entre las denominaciones para el conjunto de {2, 2.5, 4, 5}.
El conjunto de NOS denominaciones de monedas son óptimas porque de espaciado desigual: En particular, hay una proporción de 5 entre la moneda y el níquel, pero sólo 2 entre el níquel y moneda de diez centavos.
Preguntas Abiertas
Los billetes
El análisis anterior asume una distribución uniforme de los dimes+centavos de dólar de los dígitos de los precios. Pero esto no iba a funcionar para grandes denominaciones: estoy mucho más probable que pase un billete de cinco libras de Ben. Sería una distribución exponencial de trabajo mejor?
No decimales de la moneda
Hizo Jefferson comete un error cuando alegó para 100 centavos de un dólar? Hubiera sido "mejor" mejor utilizar el viejo Británico £sd sistema con 240 peniques a un libra? Adoptar base-doce sistema con 144 centavos a un dólar? O pegado con el histórico de divisiones binarias (1/2, 1/4, 1/8, 1/16, etc.) de un dólar, como la BOLSA de nueva york hizo hasta el año 2001?
Austin Mohr
Puntos
16266
Una agradable propiedad sobre nuestra moneda es la que posee la subestructura óptima con respecto a hacer el cambio. Es decir, si usted desea dar a alguien, digamos, $0.57 utilizando la menor cantidad de monedas, usted puede hacerlo por siempre dar el máximo de monedas en cada paso. En este ejemplo, dos cuartos, una de níquel, y dos monedas de diez centavos.
No todas las denominaciones tienen esta propiedad. Por ejemplo, supongamos que nuestro monedas fueron sólo cuatro centavos y cinco centavos. Es posible hacer 0,08 dólares, pero el algoritmo voraz de "dar siempre la moneda más grande" puede inducir a error.
Rod Carvalho
Puntos
1939
Deje $\mathcal{B} := \{1,5,10,20,50,100,1000\}$ ser un conjunto de proyectos de ley. Para cada entero positivo $n$ existe un entero positivo $m$ y facturas de $b_1, b_2, \dots, b_m \in \mathcal{B}$ tal que
$$b_1 + b_2 + \dots + b_m = n$$
Por supuesto, en general, una "descomposición" no va a ser único. Por ejemplo, si $n = 10$, tenemos tres admisible descomposiciones:
- $m = 1$, $b_1 = 10$: tenemos el caso trivial $10 = 10$. En otras palabras, podemos pagar un 10, un dólar con un 10, un dólar.
- $m = 2$, $b_1 = b_2 = 5$: tenemos $10 = 5 + 5$, es decir, podemos pagar un 10 dólar con dos 5 billetes de un dólar.
- $m = 10$, $b_1 = \dots = b_{10} = 1$: tenemos $10 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1$, lo que es lo mismo que decir que podemos pagar un 10, un dólar con diez 1 de billetes de un dólar.
Si hay varios admisible descomposiciones, uno puede empezar a hablar de la óptima . Si su objetivo es minimizar el número de facturas que mano a la caja, a continuación, elige la descomposición con $m = 1$ y un 10 dólar con un 10, un dólar.
Lo que puedes hacer es inventar varios conjuntos de cuentas y, a continuación, calcular el promedio de la longitud de la descomposición al $n \in \{1,2,\dots,100\}$. Averiguar qué conjunto de proyectos de ley de los rendimientos de la menor longitud media.
