快速計算兩個算術級數的交點

Question

級數A遵循以下規則：
每個值是所有奇數值的總和，包括N sub i。

N個子4. 1+3+5+7 = 16

進展乙如下此規則。 取平方根的上限乘以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項。如果他們不見面，我會意識到這是一個非終止節目。這個場景我不在乎。

Answer 1

僅供參考，您的第一個序列就是方塊。

應該清楚的是，兩個序列都是單調遞增的。因此，您需要做的就是在每個序列中保留一個索引，並重復將指數指向較小的數字，直到兩個指數指向相同的數字。

請注意，如果序列沒有共同的數字，這將永遠運行。

Answer 2

算法的僞代碼：

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都在增加功能，因此很難進一步優化該算法。

Answer 3

我會在這裏總結我的評論，所以對新訪客來說更容易理解。

正如其他人指出的，序列A僅僅是一個正方形序列;而且正如OP通過他的評論澄清的，Sequence B將會不斷變化。

OP的問題的重述可能是

是否有快速的方法來確定在遞增序列的第一方陣，不是計算序列的每個學期？

的確，有。顯而易見的想法是設計一種方法，根據對平方的增長率和序列的瞭解，「跳過」某些術語的計算。但是，以編程方式很難推導出關於任意序列的見解。

一個更強大的解決方案可能是重新制定的問題，因爲找到的最小零：

B(x) - x^2 = 0 

就因爲這一點，可能存在root-finding algorithms，可以幫助。如果您不需要找到最小的零，那麼更容易：實現任何根查找算法，觀察算法收斂到零，添加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必須總是增加，所以這個算法只會擊敗「線性搜索」（計算每個項）），一個序列究竟有多複雜？）關鍵是要找到一個符合你所有序列的，並利用找到一個特定於其的優化。

我仍然不知道你的應用程序是什麼，但在這一點上，你可能只是嘗試它並在實際數據集上進行基準測試（與線性搜索相比）。這會立即告訴您是否有任何實際收益，以及是否應該投入更多時間進行優化。這將比嘗試完成所有理論數學，表徵序列和其他內容更快。