IPC

Al hacer momento de dar un "vuelto" o "cambio", lo más probable es que desee minimizar la cantidad de monedas que está dando a cada cliente, no sea que se acaben (¡y esto molestará al cliente!). Afortunadamente, la informática les ha dado a los cajeros de todo el mundo formas de minimizar el número de monedas para dar, por medio de algo conocido como: algoritmo voraz.

Según el Instituto Nacional de Estándares y Tecnología (NIST por sus siglas en inglés), un algoritmo voraz es uno que “siempre toma la mejor solución inmediata o local mientras encuentra una respuesta. Los algoritmos voraces encuentran la solución óptima general o global para algunos problemas, pero pueden encontrar soluciones menos óptimas para algunos casos en otros problemas ".

¿Qué significa todo eso? Bueno, supongamos que un cajero le debe un vuelto a un cliente y en el cajero hay monedas de 25 centavos, 10 centavos, 5 centavos y 1 centavo. El problema a resolver es decidir qué monedas y cuántas de cada una hay que entregar al cliente. Piense en un cajero "codicioso" como uno que quiere sacar el mayor provecho posible de este problema con cada moneda que saca. Por ejemplo, si a algún cliente se le deben 41 centavos, la primera opción (es decir, el mejor inmediato o local) que se puede tomar es utilizar monedas de 25 centavos. (Ese camino es "mejor" en la medida en que nos acerca a los 0 centavos más rápido que cualquier otra moneda). Tenga en cuenta que tomar una moneda de este tamaño reduciría lo que era un problema de 41 centavos a un problema de 16 centavos, ya que 41 - 25 = 16. Es decir, el resto es un problema similar pero menor. No hace falta decir que otra moneda de 25 centavos sería demasiado grande (suponiendo que el cajero prefiera no perder dinero), por lo que nuestro codicioso cajero pasaría a tomar la opción de la moneda de 10 centavos, dejándolo con un problema de 6 centavos. En ese punto, para satisfacer la codicia del cajero se requiere una moneda de 5 centavos, seguido de una moneda de 1 centavo, momento en el que el problema se resuelve. El cliente recibe una moneda de 25 centavos, una moneda de 10 centavos, una moneda de 5 centavos y una moneda de 1 centavo: 4 monedas en total.

Resulta que este enfoque (es decir, el tipo de algoritmo) no solo es óptimo a nivel local, sino también a nivel global, para muchos tipos de monedas de diferentes países. Es decir, siempre y cuando un cajero tenga suficiente de cada moneda (25, 10, 5 y 1 centavos), esta solución de mayor a menor producirá la menor cantidad de monedas posible para devolver. ¿Cuán pocas? Bueno, ¡cuéntanos tú!

Detalles de la Implementación:

En un archivo llamado cash.c en la carpeta ~/pset1/cash, escriba un programa que primero pregunte al usuario cuánto cambio se le debe y luego que imprima el número mínimo de monedas con las que se puede realizar ese cambio.

Utilice la función get_float para obtener la entrada del usuario y printf para mostrar la respuesta. Asuma que solo hay disponible monedas de 50 centavos, 25 centavos, 10 centavos, 5 centavos y 1 centavo.
- Se le pide que utilice la función get_float para que se puedan manejar quetzales y centavos aunque sin el signo de quetzal (Q.). En otras palabras si a un cliente se le deben Q 9.75 (como en el caso que un cliente compre un chicle de 25 centavos pero paga con un billete de Q.10) Suponga que la entrada del programa será 9.75 y no Q 9.75 o 975. Sin embargo si a un cliente se le deben exactamente Q 9, entonces la entrada del programa será 9.00 o sólo 9 pero no Q9 ó 900 así mismo no necesita preocuparse por comprobar si la entrada del usuario está "formateada" como debería ser un valor para definir dinero.
No es necesario que intente verificar si la entrada de un usuario es demasiado grande para caber en un float. Al usar get_float se garantizará que la entrada del usuario sea de hecho un valor de tipo foat (o integral), pero no se podrá garantizar que no sea un valor negativo.
Si el usuario proporciona un valor negativo, el programa debe volver a solicitar al usuario una cantidad válida una y otra vez hasta que el usuario ingrese un valor no negativo.
Para ayudar a la calificación del programa, por favor asegúrese de que la última línea de salida de su programa sea solo el número mínimo de monedas posible: un número entero seguido de un \\n (salto de linea).
Tenga cuidado con la imprecisión inherente de los valores de tipo float. Recuerde lo visto en clase con el archivo floats.c donde, si x es 2 y y es 10, entonces x / y no es exactamente 0.20. Por lo tanto, antes de calcular el cambio, es probable que desee convertir los valores ingresados en quetzales por el usuario a centavos. (es decir, de un valor tipo float a un int) para evitar pequeños errores.
Tenga cuidado al momento de redondear sus quetzales al centavo más cercano, para esto puede utilizar round, que se declara en math.h. Por ejemplo, si los quetzales son un valor tipo float con la entrada del usuario (p. Ej. 0.20), puede programar de la siguiente manera:

int centavos = round(quetzales * 100);

Su programa debería tener un comportamiento como el que se ve en los siguiente ejemplos.

$ ./cash
Cambio: 0.41
4

$ ./cash
Cambio: -0.41
Cambio: 
Cambio: 0.41
4

Tutorial

Cash.mp4

¿Cómo probar el código?

¿Su programa tiene el comportamiento deseado cuando se ingresa?

-1.00 (o algún otro número negativo)
0.00
0.01 (o alǵun otro numero negativo)
Letras o palabras
Ninguna entrada, cuando solo se presiona Enter

Cómo enviar

Envíe este formulario.