ソフトウェア開発技術者平成19年春期 午前問4

問4

四つの整数を引数とする関数d(X1,Y1,X2,Y2)を,次のとおりに定義する。

 d(X1,Y1,X2,Y2)=|X1−X2|+|Y1−Y2|

この関数は,2点(X1,Y1)と(X2,Y2)との間の2次元正方格子上の最短経路長を求めるものである。その性質に関する記述のうち,適切なものはどれか。
04.gif/image-size:421×141
  • 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
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop