C# 无递归计数项目

Question

我需要解决一个测试问题，该问题要求计算以X苹果为起始量，Y每次吃苹果，每次吃苹果时添加苹果时总共可以吃多少个苹果1。我当前的解决方案使用递归函数，因此如果Y小于X或给定X太大，则会导致无限循环。public class Apples{    // Counts iterations. If we eat less than we add new every, it'll loop infinetely!    private static int _recursions;    private static int _applesRemaining;    private static int _applesEaten;    public static int CountApples(int startingAmount, int newEvery)    {        if (newEvery > startingAmount) newEvery = startingAmount;        Console.WriteLine("startingAmount: " + startingAmount + ", newEvery: " + newEvery);        _applesRemaining = startingAmount;        /* Eat 'newEvery' amount */        _applesRemaining -= newEvery;        _applesEaten += newEvery;        Console.WriteLine("Eat: " + newEvery + ", remaining: " + _applesRemaining);        /* Get one additional candy */        _applesRemaining += 1;        Console.WriteLine("Added 1.");        if (_applesRemaining > 1 && _recursions++ < 1000)        {            CountApples(_applesRemaining, newEvery);        }        else        {            if (_recursions > 1000) Console.WriteLine("ABORTED!");            /* Eat the one we've just added last. */            _applesEaten += 1;        }        return _applesEaten;    }    public static void Main(string[] args)    {        Console.WriteLine(CountApples(10, 2) + "\n");    }}我怎样才能使这更有效？可能有一种更优雅的方法可以做到这一点，但我无法弄清楚。编辑：原始测试问题文本：/** * You are given startingAmount of Apples. Whenever you eat a certain number of * apples (newEvery), you get an additional apple. * * What is the maximum number of apples you can eat? * * For example, if startingAmount equals 3 and newEvery equals 2, you can eat 5 apples in total: *  * Eat 2. Get 1. Remaining 2. * Eat 2. Get 1. Remaining 1. * Eat 1. */

Answer 1

这个问题的递归似乎有点矫枉过正，所以我建议另一种数学方法。

让我们从我们总是至少吃 X 个苹果的事实开始。真正的问题是在所有东西都吃完后总共会添加多少苹果。

假设 ni 将是 i “吃”后剩余的苹果数量。然后：

n0 = X

n1 = X - Y + 1

n2 = X - 2Y + 2

...

ni = X - i(Y - 1)

求解 ni = 0 将得到 i - 吃掉所有东西所需的“进食”次数：

ni = 0 = X - i(Y - 1) => i = X / (Y - 1)

现在我们知道要吃多少次了，所以要吃掉的苹果总数是原来的 X 加上吃掉 Y 个苹果的次数（因为每次这样做时我们都会得到一个额外的苹果）：

tot = X + roundDown(i) = X * roundDown(X / (Y - 1))

我们将结果四舍五入，因为设置 ni = 0 捕获了部分“吃”，然后导致部分苹果。

例子：

X = 7, Y = 3 => tot = 7 + roundDown(7 / (3 - 1)) = 7 + roundDown(3.5) = 10

starting with 7:

0 eaten, 7 remain

3 eaten, 1 gained, 5 remain

3 eaten, 1 gained, 3 remain

3 eaten, 1 gained, 1 remains

1 eaten, nothing gained, nothing remains

--

10 eaten in total