仅使用加法、除法和乘法，在固定步数内达到一个数字的算法

Question

在工作中开发一个游戏，在游戏的某个点上，玩家会被投入到一个奖励游戏中。他们需要赢得一定金额，然而我们希望设计一个算法，使用加法、乘法和除法来在x步内达到该金额。步数也会事先确定，因此算法只需找出如何使用这些步数来达到目标数字。

你可以使用的计算方式仅限于+1至+15、x2、x4、/2和/4。在步骤中你可以超过目标数字，但必须在最后一步到达目标数字。步数通常在15到30之间，且你总是从0开始。

例如： 金额：100，步数：10 == +10，+2，x2，+4，x4，+10，/2，+15，+15，+9

金额：40，步数：12 == +15，+1，+5，+2，+1，/2，*4，+6，+6，/4，+5，*2

我想知道是否已经存在这样的算法？我相信我们可以想出一些方法，但如果已经有普遍适用的算法可以处理这个问题，那么我就不想重复造轮子了。

更新：对@FryGuy的代码进行了一些微小的更改，使其达到目标数字的路径略微随机化。他的解决方案非常好，但在看到它工作并考虑了@Argote和@Moron的评论后，我意识到它需要一定程度的随机性，以使我们的玩家感兴趣。在10步内加1达到目标数字为10非常好，但从我们将要使用它的角度来看，这种方式有些“无聊”。非常感谢所有发表评论和回答的人。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CR
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                int targetNumber = 20;
                int steps = 13;
                int[] route = null;
                Boolean routeAcceptable = false;

                // Continue choosing routes until we find one that is acceptable (doesn't average above or target win, but does exceed it at least once)
                while(!routeAcceptable)
                {
                    routeAcceptable = CalculateRoute(targetNumber, steps, out route) && route.Average() < targetNumber && route.Max() > targetNumber;
                }

                foreach (int i in route.Reverse())
                {
                    Console.WriteLine(i);
                }
                Console.WriteLine("-----------------------");
                Console.ReadLine();
            }
        }

        static Boolean CalculateRoute(int targetNumber, int numSteps, out int[] route)
        {
            int maxValue = targetNumber * 16;
            bool[,] reachable = new bool[numSteps + 1, maxValue];

            // build up the map
            reachable[0, 0] = true;
            for (int step = 0; step < numSteps; step++)
            {
                for (int n = 0; n < maxValue; n++)
                {
                    if (reachable[step, n])
                    {
                        foreach (int nextNum in ReachableNumbersFrom(n))
                        {
                            if (nextNum < maxValue && nextNum > 0)
                            {
                                reachable[step + 1, nextNum] = true;
                            }
                        }
                    }
                }
            }

            // figure out how we got there
            int[] routeTaken = new int[numSteps + 1];
            int current = targetNumber;
            for (int step = numSteps; step >= 0; step--)
            {
                routeTaken[step] = current;
                bool good = false;

                // Randomize the reachable numbers enumeration to make the route 'interesting'
                foreach (int prev in RandomizedIEnumerbale(ReachableNumbersFromReverse(current)))
                {
                    if (prev < targetNumber * 8)
                    {
                        if (reachable[step, prev])
                        {
                            current = prev;
                            good = true;

                            // Avoid hitting the same number twice, again to make the route 'interesting'
                            for (int c = numSteps; c >= 0; c--)
                            {
                                reachable[c, prev] = false;
                            }
                            break;
                        }
                    }
                }

                if (!good)
                {
                    route = routeTaken;
                    return false;
                }
            }

            route = routeTaken;
            return true;
        }

        static IEnumerable<int> ReachableNumbersFrom(int n)
        {
            // additions
            for (int i = 1; i <= 15; i++)
            {
                yield return n + i;
            }

            // mults/divides
            yield return n / 2;
            yield return n / 4;
            yield return n * 2;
            yield return n * 4;
        }

        static IEnumerable<int> ReachableNumbersFromReverse(int n)
        {
            // additions
            for (int i = 1; i <= 15; i++)
            {
                if (n - i >= 0)
                    yield return n - i;
            }

            // mults/divides
            if (n % 2 == 0)
                yield return n / 2;
            if (n % 4 == 0)
                yield return n / 4;
            yield return n * 2;
            yield return n * 4;
        }

        static IEnumerable<int> RandomizedIEnumerbale(IEnumerable<int> enumerbale)
        {
            Random random = new Random(System.DateTime.Now.Millisecond);
            return (
                from r in
                    (
                        from num in enumerbale
                        select new { Num = num, Order = random.Next() }
                    )
                orderby r.Order
                select r.Num
                );
        }
    }
}

- WesleyJohnson

---

@Moron - 是的，我们可以这样做，但正如@El Ronnoco所指出的那样，我们希望它具有趣味性。用户不知道他们将会赢得什么，因此我们希望在进展过程中具有情感/激动人心的元素。如果这有意义的话？ - WesleyJohnson

@Wesley：有趣是主观的词语。根据你认为有趣的标准，你可以添加限制条件（这就是我问你是否有任何限制条件的原因）。例如，一个限制条件可以是不能重复使用数字。因此，你不能立即执行x2再跟上/2等操作。简单地说，你需要决定什么是有趣的，并添加相应的限制条件。 - Aryabhatta

@Morno - 这是真的，你说得很有道理。我想我没有考虑到最初列出的以外的约束类型。我感谢你的见解，这让我思考更深入，这是一件好事。 - WesleyJohnson

只是出于好奇，是否有可能反过来做，即计算一系列步骤（给定某些边界），然后将该数字呈现为人们必须达到的数字？那么你已经知道如何到达那个数字了。 - FryGuy

@FryGuy：那是一种更简单的方法，尽管有多种方法可以到达一个给定的数字。 - Argote

Answer 1

我会使用动态规划。首先，建立一个从每个步骤可以到达哪些数字的映射表，然后回溯以找出你是如何到达那里的：

void CalculateRoute(int targetNumber, int numSteps)
{
    int maxValue = targetNumber * 16;
    bool[,] reachable = new bool[numSteps + 1, maxValue];

    // build up the map
    reachable[0, 0] = true;
    for (int step = 0; step < numSteps; step++)
    {
        for (int n = 0; n < maxValue; n++)
        {
            if (reachable[step, n])
            {
                foreach (int nextNum in ReachableNumbersFrom(n))
                {
                    if (nextNum < maxValue && nextNum >= 0)
                        reachable[step + 1, nextNum] = true;
                }
            }
        }
    }

    // figure out how we got there
    int current = targetNumber;
    for (int step = numSteps; step >= 0; step--)
    {
        Console.WriteLine(current);

        bool good = false;
        foreach (int prev in ReachableNumbersFromReverse(current))
        {
            if (reachable[step, prev])
            {
                current = prev;
                good = true;
                break;
            }
        }

        if (!good)
        {
            Console.WriteLine("Unable to proceed");
            break;
        }
    }
}

IEnumerable<int> ReachableNumbersFrom(int n)
{
    // additions
    for (int i = 1; i <= 15; i++)
        yield return n + i;

    // mults/divides
    yield return n / 2;
    yield return n / 4;
    yield return n * 2;
    yield return n * 4;
}

IEnumerable<int> ReachableNumbersFromReverse(int n)
{
    // additions
    for (int i = 1; i <= 15; i++)
        yield return n - i;

    // mults/divides
    if (n % 2 == 0)
        yield return n / 2;
    if (n % 4 == 0)
        yield return n / 4;
    yield return n * 2;
    yield return n * 4;
}

- FryGuy

---

+1 我很菜数学，但这是一个对我来说有点模糊的问题的绝佳答案 :) - Tom

Answer 2

从所需的解决方案开始往回推导。由于只涉及2和4的除法和乘法，因此你可以轻松知道何时可以或不能执行这些操作。最后的4-5步可以随意返回0。此外，你可以在初始阶段使用随机操作，检查是否执行了非法操作，并应包括范围检查。不要以400这样的数字结束，然后不得不进行多次除以4的操作才能回到0。

- Jean-Bernard Pellerin

Answer 3

您可以使用搜索树进行暴力破解，其深度为N级，其中N是步数。这将是O(m^n)，其中m是允许的操作次数。

可能有更好的算法，但对于较小的N值，这应该可以工作。

例如，使用{广度，深度}优先搜索或A*算法。

- Argote

---

@David：好的例子，我还应该指出，这可以返回从数字X到数字Y的所有可能路径，给定N步上的M个运算符。 - Argote

@David：你在这里会使用什么作为A*的可接受启发式算法？ - Matthew Slattery

@Matthew：“最接近所需分数（但不超过）的算术运算。” - David Weiser

@David：嗯，一个人可以使用除法运算符来进行计算，但是适当的启发式定义并不容易。 - Argote

我同意你的观点。启发式算法很难定义。在问题的限制条件下，我提出了我能想到的最简单的方法。 - David Weiser