Tag: algorithm
需要可预测的随机生成器
我是一个networking游戏开发者，我遇到了一个随机数的问题。 假设一名玩家有20％的几率用他的剑命中。 这意味着，五分之一的命中应该是至关重要的。 问题是我得到了非常糟糕的现实生活中的结果 – 有时玩家会在5次命中中得到3次暴击，有时候15次都没有。 战斗时间相当短（3-10次），所以获得良好的随机分配很重要。 目前我使用PHP mt_rand() ，但是我们只是把我们的代码移到C ++中，所以我想在我们游戏的新引擎中解决这个问题。 我不知道解决scheme是一些统一的随机生成器，或者也许记住以前的随机状态来强制适当的分配。
跳过列表与二进制树
我最近遇到了称为跳过列表的数据结构。 他们似乎有非常相似的行为二叉search树…我的问题是 – 为什么你会想在二叉search树上使用跳过列表？
什么是dynamic编程？
什么是dynamic编程 ？ 与recursion，记忆等有什么不同？ 我已经阅读了维基百科的文章 ，但是我还是不太明白。
recursion地生成列表的所有可能的排列
我试图recursion地生成列表中的所有项目。 我已经看到了类似的问题的一些解决scheme，但我一直无法让我的代码工作。 有人可以指出我可以如何解决我的代码？ 这对所有的S / O'er都是开放的，而不仅仅是Java人。 （另外我应该注意，它与SO例外崩溃）。 示例input：[1，2，3] 输出：[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] //allPossibleItems is an AL of all items //this is called with generatePerm(null, new ArrayList<Item>); private void generatePerm(Item i, ArrayList<Item> a) { if(i != null) { a.add(i); } if (a.size() == DESIRED_SIZE){ permutations.add(a); return; } for(int j = 0; j < allPossibleItems.size(); […]
Math.Pow（等等）实际上是如何工作的
所以我在Google上search了很长时间，几乎找不到任何东西。 我从这个URL中发现了一些关于Math.Pow可能实现的信息，但是它们是不准确的，例如这个代码 public static double PowerA(double a, double b) { int tmp = (int)(BitConverter.DoubleToInt64Bits(a) >> 32); int tmp2 = (int)(b * (tmp – 1072632447) + 1072632447); return BitConverter.Int64BitsToDouble(((long)tmp2) << 32); } static void Main(string[] args) { double x = 12.53, y = 16.45; Console.WriteLine(Math.Pow(x, y)); Console.WriteLine(PowerA(x, y)); } 提供输出： 1,15158266266297E+18 8,9966384455562E+17 所以不准确 我在想，它是一个系列的总和，但我不知道肯定。
如何比较两个形状？
有没有办法比较两个几何形状（或任何两个更通用的数据结构），而不是在涉及容差时使用暴力？ 蛮力（比较每个对象的每个值与另一个对象的每个值）是有效的，但速度很慢，我不能使用它。 我试着对数据进行sorting并比较两个已sorting的集合。 速度很快，但它只适用于零容忍。 一旦我添加容忍，我迷路了。 问题是，当我比较时，两个值可能是相同的，而当我sorting时，这两个值是不同的。 这里是我的问题的一些细节。 在我的Excel VBA加载项中，我有一个Shape对象集合，它们由两个Point对象构成的Line对象集合构成。 该加载项通过COM扫描CADgraphics并创buildShape对象的集合。 一个简化的版本可以产生这个： Shape 1 Shape 2 Point 1 0.0 5.0 0.0 4.9 Point 2 4.9 0.0 5.1 0.0 Point 3 5.0 5.0 5.0 5.0 我需要找出哪些形状与哪些形状相同，其中相同的手段具有相同的形状，大小和方向，但不是相同的位置（到目前为止，这是微不足道的）加上或减去一个宽容（现在不是很微不足道）！ Point.IsIdenticalTo(OtherPoint)被定义为： Function IsIdenticalTo(OtherPoint As Point) As Boolean IsIdenticalTo = Abs(X – OtherPoint.X) < Tolerance And Abs(Y – OtherPoint.Y) < Tolerance End […]
移动窗口的最小值/最大值是否可以达到O（N）？
我有input数组A. A[0], A[1], … , A[N-1] 我想要返回B的函数Max（T，A）代表A的大小在上一个大小为T的移动窗口上的最大值 B[i+T] = Max(A[i], A[i+T]) 通过使用最大堆来跟踪当前移动窗口A [i]到A [i + T]的最大值，该algorithm产生O（N log（T））最坏的情况。 我想知道有没有更好的algorithm？ 也许是一个O（N）algorithm
欧拉项目问题14（Collatz问题）
以下迭代序列是为正整数集定义的： n – > n / 2（n是偶数）n – > 3n + 1（n是奇数） 使用上面的规则并从13开始，我们生成以下序列： 13 40 20 10 5 16 8 4 2 1可以看出，这个序列（13开始，1结束）包含10个项。 虽然还没有被certificate（Collatz问题），但是所有的起始数字都被认为是1。 哪个起始数字低于一百万，会产生最长的连锁？ 注意：一旦链条开始，条款被允许超过一百万。 我尝试使用bruteforce方法在C编码解决scheme。 但是，似乎我的程序在尝试计算113383时停顿。请指教:) #include <stdio.h> #define LIMIT 1000000 int iteration(int value) { if(value%2==0) return (value/2); else return (3*value+1); } int count_iterations(int value) { int count=1; //printf("%d\n", value); while(value!=1) { value=iteration(value); […]
计算两点之间的最短路线
过去几周，我一直在使用nodejs和websockets在多人游戏上进行HTML5游戏。 我一直陷在这个问题上。 想象一下，我有一个数组（ 如下所示 ）实现这个tileheet映射。 1或棕色的瓷砖 – 有一个障碍，玩家不能通过它。 0或绿色瓷砖 – 是允许玩家移动的自由path。 通过以下方式访问地图上的任何图块： array[x][y] 我想创build最快的algorithm来找出地图两点之间的最短路线（如果有的话）。 你将如何解决这个问题？ 我知道这是常见的问题。 例如 ： 在位置（1,7）的玩家用一些AI来发射子弹，这个AI会在位置（6,0）向敌方玩家发射。 子弹必须计算两个玩家之间的最短路线，如果没有，就会爆炸在墙上。 问题 ： 如何有效地find两点之间的最短路线？
如何find给定数组的所有可能的子集？
我想在C＃或C ++中提取一个数组的所有可能的子集，然后计算所有子集数组各自元素的总和，以检查它们中有多less个与给定数相等。 我正在寻找的是algorithm。 我理解这里的逻辑，但是现在我还没能实现这个逻辑。
