将 while 循环转换为数学公式

Question

我有以下 loop 作为内部循环，并尝试通过将其转换为数学公式来摆脱它：

while(!(((aux = a * b) <= c) && (c >= aux + d))) --a;

a、b、c、d 和 aux 都是 size_t 类型，即 unsigned int的

注意： a 在循环体内的每次迭代中递减！

我完全被这个问题困住了。我试图简化循环条件，但由于 unsignedness 约束而失败。

因此我只想根据 b、c、d 获取 a 的值。

Answer 1

在每一点用a*b替换aux，你得到：

    !(a * b <= c && c - a * b >= d)
<=> !(a * b <= c && c >= d + a * b)
<=> !(a * b <= c && d + a * b <= c)

如果d大于c，第二个条件将为假，因此循环永远不会终止。所以我们只能考虑d <= c。第二个条件更严格，所以我们可以只关注它：

<=> !(d + a * b <= c)
<=> !(    a * b <= c - d)
<=> !(    a     <= (c - d)/b) // if integer division is used
<=>  (    a     >  (c - d)/b)

鉴于你只递减a，它要么需要从一开始就满足条件(a <= (c - d)/b)，要么小于等于(c - d)/b。总的来说，我们得到：

a = std::min(a, (c - d)/b);

Answer 2

让我们简化一下：

while(!(((aux = a * b) <= c) && (c - aux >= d))) --a;

放弃 aux，只支持 a*b:

while(!((a*b <= c) && (c - a*b >= d))) --a;

将!(x && y)重写为!x || !y:

while ((a*b > c) || (c - a*b < d)) --a;

翻转第二个表达式的符号：

while ((a*b > c) || (a*b > c - d)) --a;

这只是：

while (a*b > min(c, c-d)) --a;

也就是说，找到最小的a使得a*b <= min(c, c-d)。除非它已经比那个小了。所以：

a = min(a, min(c, c-d) / b);

呃，假设所有的变量都是unsigned，显然是min(c, c-d) == c - d，所以：

a = min(a, (c-d)/b);

Convert while-loop to mathematical formula