我想找出递推方程的N个数。
T(n)=T(n-1)+3T(n-2)+3T(n-3)+(n-4),T(1)=T(4)=1,T(2)=T(3)=3因此,假设输入2,5,9作为输入,则输出应为T(2)=3,T(5)=20,T(9)=695
我所做的是创建一个大小等于所有输入值最大值的数组,并在索引i.Then中存储T(i)的解决方案,查找特定索引的数组。例如T(3)的array3,T(5)的array5等等。
该代码工作良好,直到最大值不大于最大整数值系统所能容纳的范围。
Integer.MAXValue.由于数组的索引只能是整数,那么如果数字是n=1855656959555656,那么寻找T(1855656959555656)解的最好方法是什么?很明显,我不能创建一个size=1855656959555656..数组
我甚至尝试过来自BigInteger的java.Math,但没有成功。我要找一些其他的approach.please建议一些想法。
谢谢
发布于 2014-11-03 09:49:14
您不需要存储每个T(i),您只需要存储3个值T(i-1)、T(i-2)、T(i-3)。在循环i时,检查当前的I是否应该是输出的一部分,如果是这样,请立即将其输出,或者将其保存到" output "-array中。
编辑:这个部分效率很低。您签入每一个小值,每一个需要的输出。
for (int k = 0; k < arr.length; ++k) {
if (count == arr[k])
T[k] = temp[i];
else if (arr[k] == 1)
T[k] = 1;
else if (arr[k] == 2)
T[k] = 3;
else if (arr[k] == 3)
T[k] = 3;
else if (arr[k] == 4)
T[k] = 1;
}因此,您的代码运行在时间(max*arr.length),您可以减少到只有(最大)。在arr中使用HashMap和key=neededPosition (=count) value=position
在地图上是这样的:
Map<Long, Integer> map = new HashMap<Long, Integer>();
for (int i = 0; i < arr.length; i++) {
map.put(arr[i], i);
}
if (map.containsKey(count)) {
T[map.get(count)] = temp[i]
}在整件事情发生后,只检查一次值1-4!
发布于 2014-11-03 09:38:40
不可能。数组大小可以是最大的Integer.MAX_VALUE (减去一些东西通常是5或8,这取决于JVM的功能)。为什么?。数组的索引应该是一个整数,这是一个限制。
发布于 2014-11-03 09:41:26
那是做不到的。所以你需要通过引入切分机制来解决这个问题。最简单的方法是只有固定长度的数组。
https://stackoverflow.com/questions/26711407
复制相似问题