Resolviendo la ecuación con división entera sin fuerza bruta

Recientemente, se planteó una pregunta sobre la tostadora , que me conmovió seriamente. Está enraizado en una tarea que daré aquí en una interpretación ligeramente diferente:

Una vez que los programadores aprobaron el proyecto a tiempo y recibieron premios. Para celebrar, se arrojaron directamente a Mon y compraron cerveza con todo el dinero. Bebieron todo el mismo día, y en BT decidieron continuar, pero no quedaba más dinero. Luego entregaron las botellas, agregaron el cambio de ayer, y nuevamente pusieron todo en stock, como ayer. Lo mismo se hizo en SR y Chet. Y en PT el dinero era exactamente una botella. Pensamiento: recordaba el precio de una botella, cuánto tomaban los contenedores (los precios no tenían centavos), y nadie podía nombrar cuánto dinero originalmente. El proyecto fue a gran escala, grandes bonificaciones, por lo que no vale la pena. ¿Cuál fue el presupuesto mínimo en PN para que los eventos se desarrollen de esta manera?

Razonando sobre ella de la siguiente manera


Llegué a una ecuación que en resumen se ve así (1):

$$

$$x = a (x // b) + c$$

Tratando de encontrar un enfoque sin una búsqueda exhaustiva para resolver tales ecuaciones, pasé más de una hora, pero al final encontré una solución realmente maravillosa , pero los márgenes del libro son demasiado estrechos ;)

Sin ilusiones sobre la superioridad en este asunto, solo quiero compartir el placer recibido en el proceso. Si alguien conoce un método o nombre alternativo para esto, ilumíneme; Insto a aquellos como yo a discutir, y los impacientes, los invito bajo el gato.

Considere la ecuación resultante en esta forma (2):

$$

$$(x-c) / a = x // b$$

Como el lado derecho solo puede tomar valores enteros, toda la expresión tiene sentido solo cuando el numerador es un múltiplo del denominador en el lado izquierdo. A partir de esto, es obvio que x podría tener valores a partir de c y luego con un paso a .

Entonces consideré la ecuación (1) como dos funciones $$$y1 = x$y $$$y2 = a (x // b) + c$. Con qué argumento se cruzan, esa es la solución. Por ejemplo, elegí valores pequeños de los parámetros para mostrar la imagen lo mejor posible. Entonces, sea a = 3, b = 7, c = 9.


Debido a la naturaleza gradual de la segunda función, las gráficas y1 e y2 se cruzan en dos puntos: para x1 = 12 y x2 = 15, pero de acuerdo con la condición, nos interesa el primer valor, como el más pequeño. Entonces, para determinar el área de intersección sin una búsqueda exhaustiva, introduje una tercera función: es solo una línea recta que limita la función y2 desde abajo y tiene la ecuación $$$y3 = a / b (x - (b-1)) + c$.

Ahora queda por encontrar el punto de intersección de las dos líneas ( y1 e y3 ) y ajustar la respuesta de la restricción en la x deseada. De hecho, sobre la base de la condición, puede tomar solo aquellos valores en los que se cumple la condición del multiplicador del numerador para el denominador en la ecuación (2), es decir. $$$x = c + na$, donde n es un cierto factor natural. Para hacer esto, resolvemos una ecuación simple $$$x = a / b (x - (b-1)) + c$y si la raíz resultante no cumple con nuestros requisitos, la trasladaremos a la más adecuada. Dado que la función auxiliar y3 tiene una pendiente positiva, y todos los valores de y2 están por encima de ella, la raíz siempre debe ajustarse hacia arriba. Entonces, en nuestro caso, las líneas se cruzan en x = 11.25 (punto negro en el gráfico), y el valor grande más cercano que satisface la condición es 12 (punto rojo), que es la respuesta.

Como había una etiqueta de Python en la pregunta sobre el Tostador, a continuación le daré un script para resolver este problema usando la función, para encontrar el presupuesto del día actual en función del presupuesto del día siguiente. Aplicamos la función el número requerido de veces y, ¡voila, obtenemos la respuesta!

def this_day_budget(next_day_budget): a = bottle_price - tare_return_price b = bottle_price c = next_day_budget x = (a - a*b + b*c)/(b - a) if (x - c) % a: # value does not match the increment x = ((xc)//a + 1) * a + c return x bottle_price = 7 tare_return_price = 4 party_duration_days = 5 last_day_budget = bottle_price for days_to_party_end in range(party_duration_days): if days_to_party_end == 0: current_budget = last_day_budget else: current_budget = this_day_budget(current_budget) print('first day budget was - %d' % current_budget) 

En lugar de una conclusión:

la tarea en este ejemplo se determinó como valores de parámetros $$$a <b <c <x$y la ecuación misma $$$x = a (x // b) + c$; el enfoque propuesto con cambios menores es aplicable en otros casos similares: el propósito de la publicación fue solo describir el principio sin derivar una solución universal para el caso general, por lo tanto, no juzgue estrictamente (código Python, incl.), ¡y tenga un buen viernes!