在没有蛮力的情况下用整数除法求解方程

最近，对烤面包机提出了一个问题，这使我很感动。 它植根于一项任务，在这里我将以稍微不同的解释来给出该任务：

一旦程序员按时通过项目并获得奖赏。 为了庆祝，他们全力以赴，并用所有的钱买了啤酒。 他们在同一天喝了所有东西，在BT决定继续，但是没有钱了。 然后他们交出了瓶子，添加了昨天的零钱，然后又像昨天一样将所有东西都放入了库存。 在SR和Chet中也做过同样的事情。 在PT中，钱正好是一瓶。 思考-记住一瓶的价格，拿了多少容器（价格没有美分），没人能说出最初多少钱。 该项目规模庞大，奖金丰厚-因此不值得。 PN的最低预算是多少，这样事件才能以这种方式发展？

对她的推理如下


我得出一个等式，抽象地看起来像这样（1）：

$$

$$x = a（x // b）+ c$$

试图找到一种无需详尽搜索此类方程式解决方案的方法，我花了一个多小时，但最终我找到了一个真正出色的解决方案 ，但本书的边际太窄了 ；）

在这件事上没有关于优越性的幻想，我只想分享在此过程中获得的快乐。 如果有人知道替代方法或名称，请启发我； 我敦促像我这样的人讨论，不耐烦的人，我请你照看。

考虑以下形式的结果方程式（2）：

$$

$$（x-c）/ a = x // b$$

由于右侧只能取整数值，因此仅当分子是左侧分母的倍数时，整个表达式才有意义。 由此可知， x可能具有从c到步骤a的值 。

然后我认为方程式（1）是两个函数 $$$y1 = x$和 $$$y2 = a（x // b）+ c$。 他们以什么论点相交，就是解决方案。 例如，我选择了较小的参数值，以便尽可能地显示图片。 因此，让a = 3， b = 7， c = 9。


由于第二个函数的逐步性质，图y1和y2在两个点处相交：对于x1 = 12和x2 = 15，但是根据条件，我们对第一个值感兴趣，因为它较小。 因此，为了在不进行详尽搜索的情况下确定相交区域，我引入了第三个函数-它只是一条直线，从下面限制了函数y2并具有等式 $$$y3 = a / b（x-（b-1））+ c$。

现在剩下的工作就是找到两条线（ y1和y3 ）的交点，并根据期望x的限制来调整答案。 实际上，根据该条件，它只能取满足等式（2）中分母分子的乘子的条件的那些值， $$$x = c + na$，其中n是某个自然因素。 为此，我们解决了一个简单的方程式 $$$x = a / b（x-（b-1））+ c$如果生成的根不符合我们的要求，我们会将其移至最接近的合适根。 由于辅助函数y3具有正斜率，并且y2的所有值均在其上方，因此应始终向上调整根。 因此，在我们的情况下，线在x = 11.25（图形上的黑点）处相交，并且满足条件的最接近的大值为12（红点），这就是答案。

由于烤面包机上的问题中有一个Python标记，因此在下面，我将提供一个脚本使用函数来解决此问题，以根据第二天的预算来查找当天的预算。 我们将函数应用所需的次数，瞧，我们得到了答案！

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) 

而不是结论：

本例中的任务被确定为参数值 $$$a <b <c <x$，以及方程本身 $$$x = a（x // b）+ c$; 建议的方法进行较小的更改也适用于其他类似情况-该出版物的目的只是描述原理，而没有为一般情况提供通用解决方案-因此，请勿严格判断（包括Python代码），并祝您星期五愉快！