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になるか、インデックスがちょうどi番目の項であるため、両方が同等であるため、Bが値を見つけるインデックスである可能性があります。彼らが会わない場合、それは非終了プログラムであることに気づきます。このシナリオは気にしません。

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)」と呼びます。これは の成長率の単純な推定と考えてください。もちろん、それはほぼ確実に間違っていますが、ここで目指しているのは、用語をスキップする方法だけです。それが後で最適化されるものです。 1707-169215B
  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)新しいデルタとして計算) に進むことができます。(B(6)-B(2))/4ステップ 3 (新しいデルタとして計算) に直接進むことができます。(の可能な関数を特徴付けずに、何が最善かを本当に知ることはできませんB。)
    2. より大きい場合は1764、戻る必要があります。繰り返しますが、多くの方法があります。二分探索は、実際には単純で合理的な方法です。と の間にB(4)直接あるため、計算します。未満の場合は、 を試してください。より大きい場合は、 を試してください。どちらかが一致しない場合は、 から始めます。二分探索では、せいぜい計算を行うだけです。B(2)B(6)1764B(5)1764B(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 に答える