在满足特定要求的序列中查找三个数字的组合量

啊啊啊啊啊吖

2019-02-14 阅读量: 696

给定数字D和数量为N的数字序列，找到其中具有最大差值的三个数字的组合的量，其不超过值D.例如：

D = 3, N = 4

Sequence of numbers: 1 2 3 4

Possible combinations: 1 2 3 (3-1 = 2 <= D), 1 2 4 (4 - 1 = 3 <= D), 1 3 4, 2 3 4.

Output: 4

我的概念是：迭代整个数字序列，并在减去当前比较数字时找到超过D值的最小数字。然后，找到这两个数字之间的组合，当前比较的数字是固定值（这意味着n [两个数字之间的数字]组合2）。如果即使用当前比较的数字减去序列中的最大数字也不超过D，则使用取得的全部元素的组合3。

N可以大到10 ^ 5，最小为1，D可以大到10 ^ 9，最小也为1。

我的算法有问题：当我组合第一个元素和10 ^ 5元素时发生溢出。我怎样才能解决这个问题？有没有办法计算大量的组合而不实际进行阶乘？

解决办法：

D在排序列表中查找值范围中的项目并获得索引差异时M，您应该计算C(M,3)。

但对于这样的组合数字，您不需要使用巨大的因子：

C(M,3) = M! / (6 * (M-3)!) = M * (M-1) * (M-2) / 6

更多地减少中间结果：

A = (M - 1) * (M - 2) / 2

A = (A * M) / 3

119.8891

关注作者

发表评论

暂无数据

CDA考试动态

CDA报考指南

推荐帖子