切饼问题

切 3 刀最多可以得到 11 块.

切 \(n\) 刀可以得到 \(\frac{2 \cdot (n + 1) + n \cdot (n - 1)}{2} \ (n \ge 0)\)

1 刀不切,最多可以得到 1 块;

切 1 刀,最多可以得到 2 块;

切 2 刀,最多可以得到 4 块;

切 3 刀,最多可以得到 7 块;

切 4 刀,最多可以得到 11 块;

可以得到 2 个数列: \(0\;1\;2\;3\;4\;\ldots\) 和 \(1\;2\;4\;7\;11\;\ldots\).

在仔细观察后对它们进行错位,可以发现一个规律:

\(\;0\;1\;2\;3\;4\;\ldots\)

\(1\;2\;4\;7\;11\;\ldots\)

切第 \(n\) 刀时得到的块数比切第 \(n - 1\) 刀多 \(n\) 块.

也就是说切第 \(n\) 刀得到的块数为 \(e = 1 + 1 + 2 + 3 + \ldots + (n - 2) + (n - 1) + n\).

这已经是答案,不过,这个公式不太方便计算,所以还是要找一个效率更加高的算法.

\(e_{1} = 1 + \overbrace{1 + 2 + 3 + \ldots + (n - 2) + (n - 1)}^{n - 1 个} + n\)

\(e_{2} = n + \underbrace{(n - 1) + (n - 2) + \ldots + 3 + 2 + 1}_{n - 1 个} + 1\)

\(e_{2}\) 只是 \(e_{1}\) 的倒序写法,两者是相等的: \(e_{1} = e_{2} = e\).

可以发现被括号包含的两个部分相加为 \([1 + (n - 1)] + [2 + (n - 2)] + [3 + (n - 3)] + \ldots + [(n - 3) + 3] + [(n - 2) + 2] + [(n - 1) + 1] = n \cdot (n - 1)\),

所以 \(e_{1} + e_{2} = 2 \cdot (n + 1) + n \cdot (n - 1)\).

从而可以得出: \(e = \frac{2e}{2} = \frac{e_{1} + e_{2}}{2} = \frac{2 \cdot (n + 1) + n \cdot (n - 1)}{2} \ (n \ge 0)\).