13
在工作中和在游戏中的某个点上工作的游戏中，玩家将被投入到奖励游戏中。他们需要赢得的金额是预先确定的，但是我们想要提出一种算法，使用加法，乘法和除法以x步数量达到该数量。步骤的数量也会提前知道，所以算法只需要弄清楚如何使用这个步骤来达到这个数字。仅使用加法，除法和乘法以固定数量的步骤达到数字的算法
您可以使用的唯一计算方式是+1到+15，x2，x4，/ 2，/ 4。 您可以在步骤中超出目标编号，但必须以最后一步中的目标编号结束。步骤数量通常在15到30之间，您始终从0开始。
例如： 数量：100，步骤：10 == +10，+ 2，x2，+ 4，x4，+10，/2，+ 15，+ 15，+ 9
Amount：40，Steps：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
);
}
}
}
你就不能垫X2的步骤，/ 2，一旦你到达目标很快？还有其他限制吗？ – 2011-02-15 21:36:00
我认为你想要的路线是“有趣”，而不是一个可预见的行为模式。我认为现在不会有真正的解决方案，因为算法解决方案往往完全围绕速度/内存而不是“兴趣”。 – 2011-02-15 21:45:42
@Moron - 是的，我们可以像Ronnyo @El指出的那样，我们希望它很有趣。用户不知道他们将赢得什么，所以我们希望它随着它的进展而变得情绪化/令人兴奋。如果这有道理？ – WesleyJohnson 2011-02-15 21:54:13