java – 对于真正大于整数最大值的巨大数,求解递归关系的最佳方法应该是什么

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – 对于真正大于整数最大值的巨大数,求解递归关系的最佳方法应该是什么，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1355字，纯文字阅读大概需要2分钟。

内容图文

我想找到递归方程的第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处存储T(i)的解.然后查找数组中的特定索引.例如,T [3]的数组[3],T(5)的数组[5]等

代码工作正常,直到最大数量不大于系统可以容纳的最大整数值,即

Integer.MAXValue.

因为数组的索引只能是整数
如果数字是n = 1855656959555656应该是找到解决方案的最佳方法
T(1855656959555656)？
显然我不能创建一个大小= 1855656959555656的数组..

我甚至尝试过java.Math中的BigInteger但没有成功.
我必须找到一些其他的方法.请提出一些想法..

谢谢

解决方法:

你不需要存储每个T(i),你只需要存储3个值T(i-1),T(i-2),T(i-3).在循环i时,检查当前i是否应该是输出的一部分,如果是,请立即将其输出或将其保存到“输出”-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中使用带有key = neededPosition(= count)value = position的HashMap

像这样初始化地图：

 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！

内容总结

以上是互联网集市为您收集整理的java – 对于真正大于整数最大值的巨大数,求解递归关系的最佳方法应该是什么全部内容，希望文章能够帮你解决java – 对于真正大于整数最大值的巨大数,求解递归关系的最佳方法应该是什么所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端