応用数学(全48問中40問目)

スタディング 応用情報技術者講座
四つの整数を引数とする関数d(X1,Y1,X2,Y2)を,次のとおりに定義する。

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

この関数は,2点(X1,Y1)と(X2,Y2)との間の2次元正方格子上の最短経路長を求めるものである。その性質に関する記述のうち,適切なものはどれか。
04.gif

出典:平成19年春期 問 4

  • 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

Pagetop