将while循环转换为数学公式

Question

我将循环作为内循环,并试图通过将其转换为数学公式来摆脱它:

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

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

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

我完全坚持这个问题.我试图简化循环条件,但由于unsignedness约束而失败.

至于结果,我只是想获得的价值a取决于b,c,d.

Answer 1

更换aux用a*b在每一个点,你会得到:

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

如果d大于c,则第二个条件将为false,因此循环将永远不会终止.所以我们只能考虑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);