アルゴリズムテスト

アルゴリズムテスト
実験室の大先輩は小さなかまどを開けて、簡単なアルゴリズムの問題を話して私たちに構想を開拓してくれた.今、今回お話ししたいくつかのテスト問題をここに記録します.一つはもう一度印象を深めることです.もう一つは後で見てもいいです.
テスト問題1--判断とsの要素の存在性
テーマ:既知の配列a[0],a[1],...,a[i],a[i+1],...,a[n]および整数s;ここで、nの範囲は10^5、a[i]の範囲は10^9であり、配列a[n]の中にa[i]およびa[j]が存在するか否かを判断し、s=a[i]+a[j]であり、iはjに等しくてもよい.
私の考え:最も早く考えることができるのは当然列挙法で、配列a[n]の中の各2つの要素を加えてsに等しいかどうかを見ることですが、この方法は愚かで、時間の複雑さはo(n^2)です.それはもっと良い方法がありますか?もちろんありますが、実はこのような配列から数を探す問題は、何度も繰り返して問題を解決できない場合は、まずソート処理を行います.ソートプロセスは複雑さを増しますが、ソート後は要素間の関連情報を利用して問題を解くことができます.だからまず数字を並べ替えて、方法はとても多くて、速く並べてo(nlog(n))をします.スタックソート後の配列は両端から遍歴し,i=0からj=nで始まり,このときa[i]が最小,a[j]が最大である.次に、次のルールに従って移動します.

 while(i<=j){
 if a[i]+a[j]==s
 return true;
 else if a[i]+a[j] i++;
 else if a[i]+a[j]>s
 j--;
 }
 return false;
 

この方法は並べ替え後の配列にとって結果を得る時間的複雑さはo(n)である.前のソートの過程を考えると,全体の複雑さはmax(o(nlog(n),o(n)=o(nlog(n))である.
この方法を理解するには、a[i]+a[j]を2次元マトリクスとして想像することができ、縦軸も横軸もa[0]...a[n],形状如:

 --------------------------------->
 | a[0], a[1], a[2],..., a[n]
 | a[0] - - - -
 | a[1] - - - -
 | ...
 | a[n] - - - -
 /
 

マトリクス内の要素の特徴は、矢印の方向に従って、マトリクス内の要素に対応する横縦座標a[i]とa[j]の和が増大することである.もっと明らかなのは

 --------------------------------->
 | a[0], a[1], a[2],..., a[n]
 | a[0]        2
 | a[1]     X  
 | ...
 | a[n]  1  1    
 /
 

です
マトリクス内の各要素の値は、その横長座標a[i]とa[j]の和であり、現在位置がXであり、「小」対応位置の値が「X」対応値より小さく、「大」対応位置の値が「X」対応値より大きく、残りの「未1」と「未2」対応値と「X」の関係は未知である.この問題は,この行列にsの値があるか否かを判断する要素に変換される.現在の値xがsより小さいと仮定し、「小さい」に対応する値がsより小さいことを示します.では、「大きい」、「未1」、「未2」で探し続けます.逆に、現在xがsより大きい場合、「大きい」に対応する値がsより大きいことを説明すると、「小さい」、「未1」、「未2」で探し続けるべきです.このプロセスは,検索領域を簡略化して排除するプロセスである.では、毎回の簡略化で得られる残りの領域は多角形であり、矩形ではなく、矩形テンプレート上で問題を簡略化する目的をうまく実現できないという問題がある.どのようにして簡略化されるたびに残りが矩形になるのでしょうか.開始判断位置として左下または右上を任意に選択して簡略化すれば簡単です.例えば右上から、最初の簡略化時にx>sは最も右の列を排除することができ、xがこの理論をコードに実現すると、上の偽コードのように、最も左と最も右が同時に遍歴する.もちろん他にもこの問題を解く方法はたくさんありますが、この方法は時間の複雑さが最も小さいはずです.もし誰かがもっと良い方法があれば、交流することができます.
試験問題2-三角形面積の計算
テーマ:三角形の3つの定点の座標を与えて、この三角形の面積を計算します.解法:この問題には多くの解法があります.簡単なのは数式で計算することです.例えば、

ヘレン式:sqrt(d(d-a)(d-b)(d-c))は、a,b,cが三角形の三辺長であり、dが三辺和である一般的に、d=(a+b+c)/2である.この解法では,式を用いて3辺の長さを先に計算する必要がある.アルゴリズムの欠点は、コンピュータ計算時に誤差があることです.

は = × /2の式を用い,同様に他の式を用いて計算が高く,辺長もあり,欠点も誤差がある.

ベクトル外積公式を利用する:ベクトルの外積はまだ1つのベクトルで、新しいベクトルのモードは:|AB×AC|=(|AB|×|AC|×sin(θ));三角形面積=(1/2)(AB×AC)=(1/2)(|AB|×|AC|×sin(θ));したがって、ベクトルの外積に基づいて三角形の面積を得ることができる.外積の座標は:(x1,y1,z1)×(x2,y2,z2)=(y1z2-y2z1,z1x2-z2x1,x1y2-x2y1)と表され、ベクトルの外積は3次元空間に確立されており、三角形の面積はそのうちの1次元の座標を0、例えばz 1=z 2=0に位置決めすることができ、(x1,y1,0)×(x2,y2,0)=(0,0,x1y2-x2y1)を得ることができる.3点A(x 1,y 1),B(x 2,y 2),C(x 3,y 3)を仮定すると,AB=(x 2−x 1,y 2−y 1),AC=(x 3−x 1,y 3−y 1);則面積=(1/2)|AB×AC|=(1/2)((x2-x1)×(y3-y1)-(y2-y1)×(x3-x1));

多角形面積式:多角形を複数の三角形に分割し、すべての三角形の総和を求めるので、本質も上のベクトル外積式を利用している.

テスト問題3-最短距離を求める
題目:二次元直角座標系の中に座標と平行な行列があって、この行列の4つの点A、B、C、Dの座標を与えて、および1つの行列の外のP点座標、P点から行列の境界の上で任意の点の距離の中の最短距離を計算します.
私の考え:この問題は最初に矩形の4つの辺を無限に延長することを考えて、このように座標系は8つの領域に分けられて、P点がこの8つの領域の中の正の上下左右の方にある時、最も短い距離はP点の横座標と縦座標とA、B、C、Dの4つの点座標の横座標と縦座標の差の中の最小値です;一方,P点が残りの4つの領域にある場合,最短距離はP点とA,B,C,Dの4つの点距離の最小値である.私のこの考えはもちろん実行可能だが、簡潔ではなく、最良の答えに近いが、本質をつかんでいない.以下、より良い解法を説明します.
最短配線におけるP(p 1,p 2)点を除くもう一つの点がS(s 1,s 2)であると仮定すると、s1=max(min(a1,b1),min(max(a1,b1),p1));s2=max(min(a2,c2),min(max(a2,c2),p2))、それから直接SPの距離を求めればいいです.ここでのs 1はa 1,b 1,p 1の3つの数を並べ替えた後に中間に位置するその数の値であり,s 2はa 2,c 2,p 2の3つの数を並べ替えた後に中間に位置するその数の値である.
...未完待续..