ソースからデスティネーションまでの最小ステップ

-2

x軸に1からNまでのパスがあります。パスには、ソース、Sおよびデスティネーションの2つのポイントがあります。ソースSから出発して、我々は2つの動きだけを許す。私たちはUステップを前方にジャンプするか、Lステップを後方にジャンプすることができます。ある位置pにいる場合、[1、N]の範囲内にあれば、p + Uまたはp-Lに移動することができます。 Sから目的地Dに到達するために必要な最低限の歩数はいくらですか？ソースからデスティネーションまでの最小ステップ

D - S = x * U - y * L 

y = (Ux + S-D)/L

これは数学である：Sステップと最小限のx+yをしたい - 私たちは、だから我々はDをしなければならない境界線1とN.

出典

2017-10-23 user3223196

...あなたの質問は？ – vish4071

本当に問題をよりよく定義する必要があります。書かれているように、それはほとんど意味がありません。 SからDまでの方向を把握し、必要に応じて適切な方向に多くのステップを実行します。どういうわけか、私は疑問に多くがあると思いますが、あなたの説明は言いません。 –

Sで始まるが、Dが何であるかわからない最適なアルゴリズムが必要なのかもしれません。代わりに試してみる必要があります。それがDに達するときだけ、アルゴリズムはそれが行ったことを知るでしょう。 DはSよりも小さくても大きくてもかまいません。これがあなたの質問であれば、そのように説明しておいたはずですが、これは以前に尋ねられています。 [駐車場検索アルゴリズム]（https://stackoverflow.com/questions/37422823/parking-lot-search-alg）を参照してください。 – trincot

を超えて到達することはできません。

Dを正確に打つには、Ux+S-D % Lを0（％はモジュロ演算子）にする必要があります。

xは賢明な数学またはループです。

私はこれがあなたを始めることを望みます。

私が扱った数学によって、賢さは異なる場合があります。彼らはGCDと剰余を扱う場合：

Let g = gcd(U, L)

はその後何の解決策(D-S) % g != 0はありません。たとえば、L 2とU 4を使用して3〜6に達することはできません。

出典

2017-10-24 13:31:19

ソースからデスティネーションまでの最小ステップ

答えて

関連する問題