2

私はこのウェブサイトとCの両方に不慣れです。すべてのポイントからの平均的な「ジャンプ」を見つけるためのプログラムが必要です。

ここに画像の説明を入力してください

アイデアはこれです：1から2、1から3、1から4 ... 1から9までの「ジャンプ」距離を見つけるか、2から1、2から3、2から42から5などを見つけます。

最初の行でそれらを行うのは簡単で、（2-1）または（3-1）だけで、正しい番号が得られます。しかし、1から4または1から8の間の距離を見つけたい場合は、まったくわかりません。マトリックスの次元は潜在的に変更可能である必要があります。しかし、私は3x3マトリックスの助けが欲しいだけです。

誰でも私にそれを見つける方法を教えてもらえますか？

ジャンプとは、あるポイントから別のポイントへの垂直または水平の移動を意味します。1から2=1、1から9 = 4（最短パスのみ）

4

4 に答える 4

6

この種の問題の「距離」の定義は常に注意が必要です。

ポイントがフィールド上のマークであり、自由にその中を歩くことができると想像してください。次に、あるポイントから別のポイントへの任意のパスを取ることができます。その場合、最短ルートは直線になります。その長さは、ポイントを結合するベクトルの長さになります。これは、たまたま2つのポイントの位置間の差ベクトルです。この長さは、ピタゴラスの定理を使用して計算できますdist = sqrt((x2-x1)^2 + (y2-y1)^2)。これは、ポイント間のユークリッド距離として知られています。

今、あなたが都市にいて、各ポイントが建物であると想像してください。建物の上を歩くことはできないので、上/下または左/右に行くしかありません。次に、最短距離は、差ベクトルの成分の合計によって与えられます。これは、「2ブロック下がってから、左に1ブロック下がる」という数学的な言い方で、3ブロックの距離を歩くことを意味しますdist = abs(x2-x1) + abs(y2-y1)。これは、ポイント間のマンハッタン距離として知られています。

ただし、あなたの問題では、対角線が許可されている場合、単一のステップで隣接するポイントにジャンプすることが唯一の可能な移動であるように見えます。次に、パスが非常に不規則であるため、問題は少し複雑になります。ここにはいくつかのグラフ理論が必要です。これは、リンクされた要素、つまり「ノード」に関する問題をモデル化するときに非常に役立ちます。各ポイントは隣接ノードに接続されたノードであり、問​​題は別の特定のポイントへの最短パスを見つけることです。ジャンプの重みが異なる場合（たとえば、対角線でのジャンプが難しい場合）、これを解決する簡単な方法は、ダイクストラのアルゴリズムを使用することです。ウィキペディアでの実装の詳細。

コストが常に同じである場合、問題は、ソースからの宛先ポイントの幅優先探索でのジャンプの数をカウントすることになります。

于 2013-03-02T21:31:38.077 に答える
3

Let's define the 'jump' distance : "the number of hops required to reach from Point A [Ax,Ay] to Point B [Bx,By]."

Now there can be two ways in which the hops are allowed :

  1. Horizontally/Vertically
    In this case, you can go up/down or left/right. As you have to travel X axis and Y axis independently, your ans is:
    jumpDistance = abs(Bx - Ax) + abs(By - Ay);

  2. Horizontally/Vertically and also Diagonally
    In this case, you can go up/down or left/right and diagonally as well. How it differs from Case 1 is that now you have the ability to change your X axis and Y axis together at the cost of only one jump . Your answer now is:
    jumpDistance = Max(abs(Bx - Ax),abs(By - Ay));

于 2015-10-20T19:30:31.523 に答える
2

「ジャンプ距離」の定義は何ですか？

男性が正方形のMからNにジャンプする必要がある回数を意味する場合、垂直方向と水平方向にしかジャンプできない場合、1つの可能性があります。

dist = abs(x2 - x1) + abs(y2 - y1);

たとえば、1と9の間のジャンプ距離は次のとおりです。|3-1|+|3-1| = 4

于 2013-03-02T21:20:48.333 に答える
0

ジャンプ距離を計算する方法は2つあります。1）水平方向と垂直方向の移動のみが許可されている場合、その場合は、2つのポイントの間に長方形を形成し、隣接する2つの辺の長さを計算するだけです。たとえば、1から9に移動したい場合は、最初に1から3に移動し、次に3から9に移動します。（コードに変換）2）8方向すべての移動が許可されている場合、状況は複雑になります。1から6に移動したい場合のように仮定します。あなたがする必要があるのはあなたが1から5までもっとしなければならないということですそしてそれから5から6まで。コードでそれをする方法はxとy座標の違いの間の最大値を見つけることです。この例では、x座標では差は2（3-1）であり、y座標では差は1（2-1）です。したがって、これの最大値は2です。これが答えです。（コードに変換）

于 2020-03-24T07:04:27.757 に答える