この質問は数学の質問として投稿できますが、これを実装したいので、これがより良い場所だと思いました。
解決しなければならない問題があり、可能な限り最善の方法で解決しようとしています。
私は 2 つのユニットを持っており、これらのユニットが決定されたポイントに到達して出会う時期を予測したいと考えています。これらのユニットは円形/楕円形で移動し、各ユニットがいつポイントに到達するかを予測する方程式は簡単に計算できます。時間は離散的です。つまり、システムはティックで動作するため、時間 = t0、t1、t2、... などになります。
その例がこれです。彼らが出会う点を P としましょう。
ユニット 1 には 2 つの方程式があるため、任意の x について、t はユニット 1 が P にいる時間です。
t = 10x + 1
t = 10x + 9
ユニット 1 は、P の 1、9、11、19、... にあります。
ユニット 2 も同様:
t = 6y + 1
t = 6y + 5
ユニット 1 は、P の 1、5、7、11、17、... にあります。
したがって、t = 11 で、ユニットは P で会合します。会合の時間はさらにある可能性がありますが、発生したのは 1 回だけです。
これらの方程式は無限の数の会合時間を生成する可能性があるため、時間制限が導入されます。この時間制限を L と呼びましょう。したがって、これらの方程式を考えると、ユニットが互いに出会う L 未満のすべての時間 (ティック) を計算したいと思います。 .
方程式のペアごとにソートされたリスト/配列を作成して交点を計算できることに注意してください。ただし、これはよりスマートな方法で解決できると思います。
方程式を使用してこれをどのように解決できますか? それは可能ですか、それともアレイを構築する必要がありますか? この問題の下限は? これは O(1) で実行できますか? 問題にいくつかの制限を追加すると、O(1) で機能させることができるでしょうか? たとえば、最初の会議の時間、またはいずれかの会議の時間を知りたい場合などです。
最大でサイズが L の 2 つの並べ替えられた配列があり、各配列を 1 回通過するだけで交点を取得できるため、これは O(L) になると思います。
モッズ、英語のエラーを自由に修正してください。それは私の主な言語ではありません。