第12回：木構造

第2回課題解答・解説
 やらせたい仕事：100個の点について，最も近い2点間距
離を求める
p[3][0]ö
æp3x ÷
ö æ
÷
ç
ç
÷
÷
p
=
=
ç
ççp ÷
P3
点が6つの場合…
3
÷
ç
÷
è 3y ÷
ø çèp[3][1]ø
P0
P2
P5
P4
P1
点 P0 と点 P3 の間の距離：dist(p[0], p[3])
1
第2回課題解答・解説
 2つの点の全ての組み合わせの距離を計算して，その中で
最短の距離を求めればよい．つまり，100点から2点を取
る組み合わせを総当たりで探さなくてはならない．
点が6つの場合…
P3
P0
P2
P5
P4
P1
線分で結ぶときの1点目は
0番から4番まで．2点目
は1点目に選んだ点の次の
点から5番までを選択
組み合わせの数：
NUMC2
→ これが距離計算の回数
2
第2回課題解答・解説
 では，これをプログラム上でどのように書けばよいだろう
か？まずはしらみつぶしで距離を計算する．
 二重ループ：「1点目を選ぶループ」があり，その中に
「2点目を選ぶループ」が回っているようにする．
for (i = 0; i < NUM-1; i++) 1点目を選ぶループ
for (j = i+1; j < NUM; j++) 2点目を選ぶループ
距離＝dist(p[i], p[j]);
これで，全ての2点間の距離を計算することはできる．
では次に，最小距離をどうやって求めるか？
3
第2回課題解答・解説
 「今のところの最短距離」を変数として保持しておき，2
点間距離を計算するつどその距離をこの変数と比較して，
計算した距離が変数の値未満であれば更新する．
 注意：初期化を忘れない．変数を宣言した時点では変数に
はでたらめな数が入っている．これを「あり得ないぐらい
大きな値」あるいは1サンプルで初期化する．
min = dist(p[0], p[1]);
minの初期化
for (i = 0; i < NUM-1; i++)
for (j = i+1; j < NUM; j++)
if (min > dist(p[i], p[j])) 比較
min = dist(p[i], p[j]); 更新
4
第2回課題解答・解説
 距離計算関数 dist() の呼出回数を更に減らすには
さっきのやり方だと…
min = dist(p[0], p[1]);
for (i = 0; i < NUM-1; i++)
for (j = i+1; j < NUM; j++)
if (min > dist(p[i], p[j]))
min = dist(p[i], p[j]);
このやり方では，更新が行われる場合，比較時と更新
時で二重に関数を呼び出してしまっている．変数を新
たに使って，これを1回にすることができる．
5
第2回課題解答・解説
 距離計算関数 dist() の呼出回数を更に減らすには
double d; 変数 d の宣言
min = dist(p[0], p[1]);
for (i = 0; i < NUM-1; i++)
for (j = i+1; j < NUM; j++) {
d = dist(p[i], p[j]); まず d に代入
if (min > d) min = d;
比較・更新には
}
d を利用する
6
第2回課題解答・解説
 関数 dist() は平方根の計算などがあり，重い．計算時
間のボトルネックはこの関数となっている．
 変数dを使えば，関数 dist() の呼出回数は，(初期化の1
回)＋(100点から2点を選択する組み合わせの数)と等しく，
100C2 +1 = 100×99÷2 +1＝4951 (回)
 変数dを使わなかった場合，minの更新が起こる回数だけ
余分に呼出をするので，その余分な回数が最低で0回，最
高だと毎回になり4949 (回)．従って全呼出回数は4951回
から9900回になる．
 より一般的に，点の数が n であるときは，
nC2 +1 = n(n-1)/2 + 1 (回)
となる．
7
第2回課題解答・解説
 まとめると…
 「全ての2点間について」 二重ループによる繰返し
 「距離の最小値を」 変数 min の初期化と更新
 この左側が人間に指示するときの言い方，右側がコン
ピュータに対する指示である．
 この授業のミソは，普通の人間にするような指示方法を解
釈できない相手 (コンピュータ) に，アホでも分かるよう
な手順を書いて教えるところにある．
 このような，コンピュータでも分かる手順に書き下す過程
こそが「プログラミング」である．
8

Download Report