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 = Xn1 = X - Y + 1n2 = 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) = 10starting with 7:0 eaten, 7 remain3 eaten, 1 gained, 5 remain3 eaten, 1 gained, 3 remain3 eaten, 1 gained, 1 remains1 eaten, nothing gained, nothing remains--10 eaten in total