いくつかの制約を指定して距離を最小化する

Question

出発点がx-y平面の原点であるとします。

私は特定の方法で移動することのみ許可されています。 のように、私の次の動きは、2つの座標点の線形結合でしかないということを誰かに教えてくれます。

私の目標は、できるだけ多くの動きで、私が得ることができる出発点に最も近いポイントを見つけることです（コースの原点を除く）。

例えば、2点がa =（13,4）およびb =（17,5）であると言われたとします。

したがって、私が原点から得ることができる最も近いものは（1,1）です。 4a-3bから得られたものです。

私はそれのためのプログラムを書いています。しかし、私によれば、ロジックには完全な欠陥があります。

しかし、私が試したいくつかのテストケースの正解を出力します。

はここ

#include<math.h> 
int sq(int a) 
{ 
    return a*a; 
} 

int main(void) 
{ 
    int a,b,c,d,min=200000,i,j,n=100; 
    scanf("%d %d %d %d",&a,&b,&c,&d); 
    for(i=-100;i<n;i++) 
    { 
     for(j=-100;j<n;j++) 
     { 
      if(sq((i*a)-(j*c))+sq((i*b)-(j*d))<min) 
      { 
       min=sqrt(sq((i*a)-(j*c)))+sqrt(sq((i*b)-(j*d))); 
      } 
     } 
    } 
    printf("%d\n",min); 
    return(0); 
} 

があなたの入力を与えると、問題に取り組むためのより良い方法があればお気軽に私のコードです。

プログラムで出力されている回答は、| x | + | y |です。

Answer 1

数学を行うと、網羅的な検索を簡単に行うことができます。

はリットル、Mは（リットルあなたの例では= 4とメートル= -3）あなたの線形結合の係数をとします。また、をa =（x1、y1）およびb =（x2、y2）とする。

その後、それはあなたがs = sign(x1*x2 + y1*y2)機能f(l,m) = slmを最小限に抑えることが B、見つける必要があることを示すためには非常に簡単です。

また、非線形ソルバーにアクセスできる場合（または単純な関数なので独自のアルゴリズムを記述することもできます）、解を繰り返し見つけることができます。

Answer 2

私は詳細にあなたのコードを解析しようとしましたが、どのような私に飛び出しことmin割り当て内での発現が前if内での発現が異なるということですされていない：私はかなりだ

if(sq((i*a)-(j*c))+sq((i*b)-(j*d))<min) 
{ 
    min=sqrt(sq((i*a)-(j*c)))+sqrt(sq((i*b)-(j*d))); 

これらの2つは同じでなければなりません（おそらく一度だけ計算され、変数に格納されます）。

また、sqrt()の（浮動小数点）結果の整数変数への代入は疑わしいと思われます。距離の正方形で作業すると、sqrt()を完全に避けることができます。

最後に、最初の係数が正、2番目が負の線形結合のみを検討しています。係数の1つがゼロであるものを含めて、他の可能性を考慮する必要があります。