Résolution de l'équation avec division entière sans force brute

Récemment, une question a été posée sur le grille - pain , ce qui m'a beaucoup touché. Il est enraciné dans une tâche que je donnerai ici dans une interprétation légèrement différente:

Une fois que les programmeurs ont réussi le projet à temps et ont reçu des prix. Pour fêter ça, ils se sont jetés à Mon et ont acheté de la bière avec tout l'argent. Ils ont tout bu le même jour, et chez BT ont décidé de continuer, mais il n'y avait plus d'argent. Ensuite, ils ont remis les bouteilles, ajouté le changement d'hier, et encore une fois, ils ont tout mis en stock, comme hier. La même chose a été faite dans SR et Chet. Et en argent PT était exactement une bouteille. Réflexion - se souvenait du prix d'une bouteille, combien ils prenaient des conteneurs (les prix étaient sans cents), et personne ne pouvait nommer combien d'argent était à l'origine. Le projet était à grande échelle, de gros bonus - donc ça ne vaut pas le coup. Quel était le budget minimum de PN pour que les événements se développent de cette façon?

Raisonner sur elle comme suit


Je suis arrivé à une équation qui dans l'abstrait ressemble à ceci (1):

$$

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

En essayant de trouver une approche sans recherche exhaustive pour résoudre de telles équations, j'ai passé plus d'une heure, mais au final j'ai trouvé une solution vraiment merveilleuse , mais les marges du livre sont trop étroites ;)

Sans illusions sur la supériorité dans ce domaine, je veux juste partager le plaisir reçu dans le processus. Si quelqu'un connaît une méthode ou un nom alternatif pour cela, éclairez-moi; J'invite ceux comme moi à discuter, et les impatients, je vous invite sous cat.

Considérez l'équation résultante sous cette forme (2):

$$

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

comme le côté droit ne peut prendre que des valeurs entières, l'expression entière n'a de sens que lorsque le numérateur est un multiple du dénominateur du côté gauche. De là, il est évident que x pourrait avoir des valeurs à partir de c puis avec une étape a .

Ensuite, j'ai considéré l'équation (1) comme deux fonctions $$$y1 = x$ et $$$y2 = a (x // b) + c$ . À quel argument ils se croisent, c'est la solution. Par exemple, j'ai choisi de petites valeurs des paramètres de manière à afficher l'image le mieux possible. Soit donc a = 3, b = 7, c = 9.


En raison de la nature pas à pas de la deuxième fonction, les graphiques y1 et y2 se coupent en deux points: pour x1 = 12 et x2 = 15, mais selon la condition, nous nous intéressons à la première valeur, comme la plus petite. Donc, afin de déterminer la zone d'intersection sans recherche exhaustive, j'ai introduit une troisième fonction - c'est juste une ligne droite qui limite la fonction y2 par le bas et a l'équation $$$y3 = a / b (x - (b-1)) + c$ .

Reste maintenant à trouver le point d'intersection des deux droites ( y1 et y3 ) et à ajuster la réponse à partir de la restriction sur le x souhaité. En effet, sur la base de la condition, il ne peut prendre que les valeurs auxquelles la condition du multiplicateur du numérateur est satisfaite pour le dénominateur dans l'équation (2), c'est-à-dire $$$x = c + na$ , où n est un certain facteur naturel. Pour ce faire, nous résolvons une équation simple $$$x = a / b (x - (b-1)) + c$ et si la racine résultante ne répond pas à nos exigences, nous la déplacerons vers la racine appropriée la plus proche. Étant donné que la fonction auxiliaire y3 a une pente positive et que toutes les valeurs de y2 sont au-dessus, la racine doit toujours être ajustée vers le haut. Donc, dans notre cas, les lignes se coupent à x = 11,25 (point noir sur le graphique), et la grande valeur la plus proche satisfaisant à la condition est 12 (point rouge), ce qui est la réponse.

Puisqu'il y avait une balise Python dans la question sur le grille-pain, je donnerai ci-dessous un script pour résoudre ce problème en utilisant la fonction, pour trouver le budget de la journée en cours en fonction du budget du lendemain. Nous appliquons la fonction le nombre de fois requis et, voila, nous obtenons la réponse!

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) 

Au lieu d'une conclusion:

la tâche dans cet exemple a été déterminée en tant que valeurs de paramètre $$$a <b <c <x$ et l'équation elle-même $$$x = a (x // b) + c$ ; l'approche proposée avec des changements mineurs est applicable dans d'autres cas similaires - le but de la publication était seulement de décrire le principe sans dériver une solution universelle pour le cas général - donc, ne jugez pas strictement (code Python, incl.), et passez un bon vendredi!