时间戳

首页 > 解决方案 > 没有递归的 C# 计数项目

c# - 没有递归的 C# 计数项目

问题描述

我需要解决一个测试问题，要求计算总共可以吃多少个苹果，当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.
 */

标签： c#recursion

解决方案

不确定您是否在答案中受到限制，但是通过一些数学运算，您可以提出以下方法：

public int CheatEatenApples(int startingApples, int newEvery)
{
    var firstGuess = (double)startingApples*newEvery/(newEvery-1);

    if (firstGuess%1==0) // Checks if firstGuess is a whole number
    {
        return (int)firstGuess-1;
    }
    else
    {
        return (int)firstGuess;
    }
}

第一个猜测是根据我们不断获得新苹果的事实计算得出的，因此对于newEvery我们吃过的每个苹果，其中一个是免费的！当然，如果第一个猜测是一个整数，这实际上会失效。这需要提供免费的苹果才能让我们吃。令人困惑的是，让我们看一个例子。

如果我们有 3 个苹果并且每两个得到一个新苹果，那么我们的第一个猜测是 6 个苹果。然而，那是三个免费的苹果，我们在吃完 6 个之后才能得到第三个，这依赖于三个免费的苹果！所以在这种情况下，我们需要取下一个。剩下的时间我们可以四舍五入去掉小数部分，它代表我们离一个免费苹果有多近。

这只是表明您在学校学习的数学可以在现实世界中使用。以上是一些简单的计算，可能会比大多数迭代/递归计算方法更快。

附加说明：在现已删除的评论中指出，使用整数算术进行firstGuess计算可以更好地完成。这将节省需要将返回值转换回 int。之所以写成现在这样，部分是因为这是我在编写它时考虑的方式，部分是因为当我迭代正确答案时，我在调试时查看了那个小数部分（确认它只是在firstGuess很完整，我需要做一些特别的事情）。

如果您确实更改为整数数学，则需要更改 if 条件（因为它不再按原样工作），然后您将得到 Sefe 的答案。

最后注：

如果您确实想要执行迭代技术，那么以下方法符合规范：

public int CalculateEatenApples(int startingApples, int newEvery)
{
    int applesEaten = 0;
    int apples = startingApples;
    while (apples>0)
    {
        applesEaten++;
        apples--;
        if (applesEaten%newEvery==0)
        {
            apples++;
        }
    }
    return applesEaten;
}

它非常简单。当你有苹果时，它会增加你吃过的数量并减少你剩下的数量。然后，如果您吃的数字是倍数，newEvery则它会增加一个。

推荐阅读