HOME»ソフトウェア開発技術者平成19年春期»午前問4
ソフトウェア開発技術者平成19年春期 午前問4
問4
四つの整数を引数とする関数d(X1,Y1,X2,Y2)を，次のとおりに定義する。
d(X1,Y1,X2,Y2)＝|X1－X2|＋|Y1－Y2|
この関数は，2点(X1,Y1)と(X2,Y2)との間の2次元正方格子上の最短経路長を求めるものである。その性質に関する記述のうち，適切なものはどれか。
d(X1,Y1,X2,Y2)＝|X1－X2|＋|Y1－Y2|
この関数は，2点(X1,Y1)と(X2,Y2)との間の2次元正方格子上の最短経路長を求めるものである。その性質に関する記述のうち，適切なものはどれか。
- d(0,0,X2,Y2)≦1を満たす整数の組(X2,Y2)は，全部で四つある。
- d(2X1,2Y1,2X2,2Y2)＝4d(X1,Y1,X2,Y2)である。
- d(X1,Y1,X2,Y2)＝0ならば，X1＝X2＝Y1＝Y2である。
- d(X1,Y1,X2,Y2)＝d(Y2,X2,Y1,X1)である。
分類
テクノロジ系 » 基礎理論 » 応用数学
正解
エ
解説
- 経路長が1になる点は(1,0)(0,1)(-1,0)(0,-1)の4通り、さらに経路長が0となる点(0,0)が加わるため5つ存在します。
- d(-1,-1,1,1)＝4で考えてみると、
d(-2,-2,2,2)＝|-2-2|＋|-2-2|
＝4＋4＝8
したがって d(2X1,2Y1,2X2,2Y2)＝2d(X1,Y1,X2,Y2)です。 - 経路長が0ならば、(X1,Y1)と(X2,Y2)の2点は格子状の同一点に存在することになります。しかし、その点のX座標及びY座標は(3,1)(3,1)のように必ずしも一致するとは限りません。
- 正しい。|X1－X2|＝|X2－X1|、同様に|Y1－Y2|＝|Y2－Y1|なので経路長は等しくなります。
d(-3,1,5,2)＝|-3-5|＋|1-2|
＝8＋1＝9
d(5,2,1,-3)＝|5-1|＋|2-(-3)|
＝4＋5＝9