0

级数 A 遵循此规则：
每个值是所有奇数加在一起，包括 N sub i 。

N 子 4。 1+3+5+7 = 16

进阶 B 遵循此规则。取平方根乘以 2 加 1 的上限。从天花板尖齿本身中减去 N。继续添加奇数。

N = 33。
天花板（√33）=6。
6*2+1=13。
36-33=3。
3+13 =16。

停止，因为 16 在进程 A 和 B 中。是否有可能快速做到这一点？即最小的 1 或 2 步解决方案？java或通用实现会很方便

*问题*

What is the output you desire? Simply abool saying they do meet? Or do you want the indices at which they do meet, i.e.A[4]=16 andB[17]=16? Or do you just want the number at which they meet, i.e.16? And what if they don't meet exactly? Do you want the indices (or number) before, or after, the intersection? Finally, when or how do you decide to halt, if, say, the two sequences will never meet? (I know in this case they do, but I mean in the general case.)

我期望的输出将是值 16 或者它可能是 B 找到该值的索引，因为两者都是等价的，因为索引只是第 i 项。如果他们不见面，我意识到这是一个非终止程序。这种情况我不在乎。

4

3 回答 3

4

我将在这里总结我的评论，以便新访问者更容易理解。

正如其他人所指出的，序列 A仅仅是一个正方形序列；正如 OP 通过他的评论澄清的那样，序列 B将不断变化。

重述 OP 的问题可能是

有没有比计算序列的每一项更快的方法来确定递增序列中的第一个正方形？

确实，有。显而易见的想法是设计一种方法来“跳过”某些项的计算，基于对平方增长率与序列的洞察力。但是很难以编程方式获得关于任意序列的洞察力。

一个更强大的解决方案可能是将问题重新表述为找到最小的零：

B(x) - x^2 = 0

为此，可能存在可能会有所帮助的寻根算法。如果您不需要找到最小的零，那么更容易：实现任何求根算法，观察算法收敛到零，添加x^2以补偿重新制定，然后就可以了。

编辑

（评论框太有限，无法回复您的。）

当我说“二分法”时，我实际上是指“二分搜索”。这需要一个上限，因此并不真正适用于您的问题。

不过，让我提供一个简单的算法作为开始，尽管您可能已经完全想到了这一点。

  1. 计算B(1)。说它是1692（不是正方形）。
  2. 计算B(2)。说它是1707（不是正方形）。
  3. 计算B(2)-B(1)，称其为“delta”，例如 1707-1692，或15。认为这是对 的增长率的幼稚B估计。当然，这几乎肯定是错误的，但我们在这里的目标是通过某种方式跳过术语。这就是稍后要优化的内容。
  4. 下一个平方大于1707多少？一个公式(floor(sqrt(1707))+1)^2, 产生1764。
  5. 我们应该跳过多少项来尝试到达那个正方形？另一个公式 ,(1764-1707)/15产生3.8，我们可以四舍五入到4。
  6. 计算B(2+4) = B(6)。
    1. 如果小于，1764则需要继续。但是在这种情况下，您已经节省了计算 3 个项的时间。你选择如何继续前进，只是另一种选择。您可以计算B(7)并转到第 3 步（B(7)-B(6)作为新增量计算）。您可以直接进入第 3 步（(B(6)-B(2))/4作为新增量计算）。（如果不描述的可能功能，您将无法真正知道什么是最好的B。）
    2. 如果大于，1764则需要返回。再次，有很多方法。二分查找实际上是一种简单、合理的方法。计算B(4)，因为它直接在B(2)和之间B(6)。如果小于1764，请尝试B(5)。如果大于1764，请尝试B(3)。如果其中一个不匹配，则继续从B(7). 使用二进制搜索，您最多可以进行log(N)计算。

所以这听起来很划算，对吧？你要么跳过一些计算，要么log(N)最多做。（或者，您会发现对此进行更好的优化。）但是，显然，这并不是那么简单，因为您正在做额外的计算来找到这些增量、投影、二分搜索等。由于正方形增长非常缓慢（只有平方之间有这么多整数），我觉得这样的算法只会击败“线性搜索”（计算每个术语），如果你正在处理大整数，或者非常复杂的序列B（但鉴于B必须总是增加，多么复杂一个序列真的可以吗？）关键是找到一个适合你所有序列的特征，

我仍然不知道您的应用程序是什么，但此时您不妨尝试一下并在现实数据集上对其进行基准测试（相对于线性搜索）。这将立即告诉您是否有任何实际收益，以及是否应该在优化上投入更多时间。而且它会比尝试做所有的理论数学、表征序列等等更快。

于 2012-12-25T17:35:20.707 回答
1

仅供参考，您的第一个序列只是正方形。

应该清楚的是，两个序列都是单调递增的。因此，您需要做的就是在每个序列中保留一个索引，并重复递增指向较小数字的索引，直到两个索引都指向相同的数字。

请注意，如果序列没有共同的数字，这将永远运行。

于 2012-12-25T15:45:57.473 回答
0

伪代码中的算法：

int i=1, j=1;
int x=func1(i), y=func2(j);
while x!=y {
  if x<y {i++; x=func1(i)}
  else   {j++; y=func2(j)}
}

假设我们所知道的func1只是func2增加函数，那么很难进一步优化这个算法。

于 2012-12-25T17:11:25.417 回答