算法使用加法，除法和乘法达到数步固定金额仅 [英] Algorithm to reach a number in a fixed amount of steps using addition, division and multiplication only
问题描述
工作在一个游戏在工作和游戏中的一个点上的球员被扔进一个奖金游戏。他们需要赢得的金额pdetermined $ P $，但我们希望拿出一个算法，使用加法，乘法和除法，以获得该金额的步骤X量。步骤的数量会提前知道一样，所以算法将只需要弄清楚如何使用的步骤量达到多少。
您可以使用的唯一计算是+1到+15，X2，X4，/ 2/4。 你可以超过在步骤目标数，但最终必须在在最后步骤中的目标数。步骤量通常介于15和30以及你总是从0开始。
例如： 金额：100，步骤：10 == 10，2，×2，4，4倍，10，/ 2，15，15，9
金额：40，步骤：12 == 15，1，5，2，1，/ 2，* 4，6，6，/ 4，5，* 2
我很好奇，如果有这样的事情可能已经存在？我相信我们能拿出的东西，但我不想重新发明轮子，如果有一个共同的算法，可以完成这项工作。
更新：做了一些小的改动@ FryGuy的code，使其才能达到目标人数有些随机的路线。他的解决方案工作太棒了原来的样子，但看到后工作，并考虑到@Argote和@Moron提出的意见，我意识到它需要有随机性在里面的水平，使之吸引我们的球员。添加+1超过10个步骤才能到10的伟大工程的目标数，但无聊中，我们将如何使用它条款。许多感谢大家谁评论和回答。
使用系统;
使用System.Collections.Generic;
使用System.Linq的;
使用System.Text;
命名空间CR
{
类节目
{
静态无效的主要（字串[] args）
{
而（真）
{
INT targetNumber = 20;
诠释步骤= 13;
INT []途径= NULL;
布尔routeAcceptable = FALSE;
//继续选择的路线，直到我们找到一个可以接受的（不高于平均水平或目标的胜利，但超过它至少一次）
而（！routeAcceptable）
{
routeAcceptable = CalculateRoute（targetNumber，步骤，放线）及和放大器; route.Average（）＆其中; targetNumber＆功放;＆安培; route.Max（）＆GT; targetNumber;
}
的foreach（诠释我在route.Reverse（））
{
Console.WriteLine（ⅰ）;
}
Console.WriteLine（-----------------------）;
到Console.ReadLine（）;
}
}
静态布尔CalculateRoute（INT targetNumber，诠释numSteps，OUT INT []路线）
{
INT包括maxValue = targetNumber * 16;
布尔[，]可达=新布尔[numSteps + 1，maxValue（最大值）];
//建立地图
到达[0,0] =真;
对于（INT步= 0;步骤LT; numSteps;步++）
{
对于（INT N = 0; N＆LT; maxValue（最大值）; N ++）
{
如果（可达[工序，N]）
{
的foreach（INT nextNum在ReachableNumbersFrom（N））
{
如果（nextNum＆其中;包括maxValue＆安培;＆安培; nextNum大于0）
{
到达[步+ 1，nextNum] = TRUE;
}
}
}
}
}
//弄清楚我们如何到达那里
INT [] routeTaken =新INT [numSteps + 1];
INT当前= targetNumber;
为（中间体步骤= numSteps;步骤＆gt; = 0; step--）
{
routeTaken [步骤] =电流;
布尔好= FALSE;
//随机化可达数枚举使路由有趣
的foreach（INT $ P $的PV RandomizedIEnumerbale（ReachableNumbersFromReverse（电流）））
{
如果（preV＆LT; targetNumber * 8）
{
如果（可达[工序，preV]）
{
电流= preV;
好= TRUE;
//避免碰到相同数量的两倍，再次使路由有趣
对于（INT C = numSteps; C＆GT; = 0; C--）
{
到达[C，$ P $光伏] = FALSE;
}
打破;
}
}
}
如果（好！）
{
路线= routeTaken;
返回false;
}
}
路线= routeTaken;
返回true;
}
静态的IEnumerable＆LT; INT＆GT; ReachableNumbersFrom（INT N）
{
//添加
的for（int i = 1; I＆LT; = 15;我++）
{
收益回报N + I;
}
// mults /鸿沟
收益回报N / 2;
收益回报N / 4;
收益回报N * 2;
收益回报N * 4;
}
静态的IEnumerable＆LT; INT＆GT; ReachableNumbersFromReverse（INT N）
{
//添加
的for（int i = 1; I＆LT; = 15;我++）
{
如果（N - I＆GT; = 0）
得到的回报N - 我;
}
// mults /鸿沟
如果（N％2 == 0）
收益回报N / 2;
如果（N％4 == 0）
收益回报N / 4;
收益回报N * 2;
收益回报N * 4;
}
静态的IEnumerable＆LT; INT＆GT; RandomizedIEnumerbale（IEnumerable的＆LT; INT＆GT; enumerbale）
{
随机随机=新的随机（System.DateTime.Now.Millisecond）;
返回 （
从R中
（
从NUM在enumerbale
选择新的{民= NUM，令= random.Next（）}
）
排序依据r.Order
选择r.Num
）;
}
}
}
我会用动态规划。首先，建立一个地图，其中数字是从可达每一步，再原路返回，找出你如何能已经得到有：
无效CalculateRoute（INT targetNumber，INT numSteps）
{
INT包括maxValue = targetNumber * 16;
布尔[，]可达=新布尔[numSteps + 1，maxValue（最大值）];
//建立地图
到达[0,0] =真;
对于（INT步= 0;步骤LT; numSteps;步++）
{
对于（INT N = 0; N＆LT; maxValue（最大值）; N ++）
{
如果（可达[工序，N]）
{
的foreach（INT nextNum在ReachableNumbersFrom（N））
{
如果（nextNum＆其中;包括maxValue＆安培;＆安培; nextNum＆GT; = 0）
到达[步+ 1，nextNum] = TRUE;
}
}
}
}
//弄清楚我们如何到达那里
INT当前= targetNumber;
为（中间体步骤= numSteps;步骤＆gt; = 0; step--）
{
Console.WriteLine（电流）;
布尔好= FALSE;
的foreach（INT $ P $的PV ReachableNumbersFromReverse（电流））
{
如果（可达[工序，preV]）
{
电流= preV;
好= TRUE;
打破;
}
}
如果（好！）
{
Console.WriteLine（无法继续）;
打破;
}
}
}
IEnumerable的＆LT; INT＆GT; ReachableNumbersFrom（INT N）
{
//添加
的for（int i = 1; I＆LT; = 15;我++）
收益回报N + I;
// mults /鸿沟
收益回报N / 2;
收益回报N / 4;
收益回报N * 2;
收益回报N * 4;
}
IEnumerable的＆LT; INT＆GT; ReachableNumbersFromReverse（INT N）
{
//添加
的for（int i = 1; I＆LT; = 15;我++）
得到的回报N - 我;
// mults /鸿沟
如果（N％2 == 0）
收益回报N / 2;
如果（N％4 == 0）
收益回报N / 4;
收益回报N * 2;
收益回报N * 4;
}
Working on a game at work and at one point in the game the player is tossed into a bonus game. The amount they need to win is predetermined, however we'd like to come up with an algorithm which uses addition, multiplication and division to get to that amount in x amount of steps. The amount of steps would be known ahead of time as well, so the algorithm would just need to figure out how to use that amount of steps to reach the number.
The only computations you can use are +1 through +15, x2, x4, /2, /4. You can exceed the target number during the steps, but must end up at the target number on the last step. The step amount is typically between 15 and 30 and you always start at 0.
For example: Amount: 100, Steps: 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
I'm curious if there something like this might already exist? I'm sure we can come up with something, but I didn't want to re-invent the wheel if there is a common algorithm that could handle the job.
Update: Made a few minor changes to @FryGuy's code to make it the route it takes to reach the target number somewhat random. His solution worked great as-is, but after seeing it working and taking into consideration comments by @Argote and @Moron, I realized it needed to have a level of randomization in it to make it appealing to our players. Added +1 over 10 steps to get to a target number of 10 works great, but is 'boring' in terms of how we would be using it. Much thanks to everyone who commented and answered.
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
);
}
}
}
I would use dynamic programming. First, build a map of which numbers are reachable from each step, then backtrack to find out how you could've gotten there:
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;
}
这篇关于算法使用加法，除法和乘法达到数步固定金额仅的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
