首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >实大数大于整数最大值时求递推关系的最佳方法是什么?

问实大数大于整数最大值时求递推关系的最佳方法是什么?
EN

Stack Overflow用户
提问于 2014-11-03 09:37:35
回答 6查看 432关注 0票数 4

我想找出递推方程的N个数。

代码语言:javascript
复制
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等等。

该代码工作良好,直到最大值不大于最大整数值系统所能容纳的范围。

代码语言:javascript
复制
Integer.MAXValue.

由于数组的索引只能是整数,那么如果数字是n=1855656959555656,那么寻找T(1855656959555656)解的最好方法是什么?很明显,我不能创建一个size=1855656959555656..数组

我甚至尝试过来自BigInteger的java.Math,但没有成功。我要找一些其他的approach.please建议一些想法。

谢谢

EN

回答 6

Stack Overflow用户

发布于 2014-11-03 09:49:14

您不需要存储每个T(i),您只需要存储3个值T(i-1)、T(i-2)、T(i-3)。在循环i时,检查当前的I是否应该是输出的一部分,如果是这样,请立即将其输出,或者将其保存到" output "-array中。

编辑:这个部分效率很低。您签入每一个小值,每一个需要的输出。

代码语言:javascript
复制
        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

在地图上是这样的:

代码语言:javascript
复制
 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!

票数 4
EN

Stack Overflow用户

发布于 2014-11-03 09:38:40

不可能。数组大小可以是最大的Integer.MAX_VALUE (减去一些东西通常是5或8,这取决于JVM的功能)。为什么?。数组的索引应该是一个整数,这是一个限制。

票数 1
EN

Stack Overflow用户

发布于 2014-11-03 09:41:26

那是做不到的。所以你需要通过引入切分机制来解决这个问题。最简单的方法是只有固定长度的数组。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/26711407

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档