몇 가지 제약 조건이 주어지면 거리를 최소화하십시오

Question

시작점이 x-y 평면상의 원점이라고합니다.

나는 특정 방식으로 만 이동할 수 있습니다. 에서와 같이 누군가 내 옆으로 움직이는 것은 단지 2 개의 좌표 지점의 선형 조합 일 수 있다고 알려줍니다.

내 목표는 내가 얻을 수있는 출발점에 가장 가까운 지점을 찾기 위해 최대한 많은 움직임이 있습니다 (물론 출발점 제외).

예를 들어, 2 점이 = (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 및 m = -3)하여 선형 조합의 계수라고하자. 또한, = (x1, y1) 및 b = (x2, y2)이라고합시다.

는 그런 다음, 당신이 을 찾을 필요가 있음을 보여 매우 쉽게 기능 s = sign(x1*x2 + y1*y2)f(l,m) = slm을 최소화 나.

또한 비선형 해석기에 액세스 할 수 있거나 (간단한 함수이므로 사용자 고유의 알고리즘을 작성할 수 있음) 반복적으로 솔루션을 찾을 수 있습니다.

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))); 

나는 꽤입니다 이 두 변수는 동일해야합니다 (아마 한 번 계산되어 변수에 저장 될 수도 있습니다).

또한 정수 변수에 (부동 소수점) 결과 sqrt()이 할당 된 것으로 의심됩니다. 거리의 사각형으로 작업하고 sqrt()을 완전히 피하는 것이 좋습니다.

마지막으로, 첫 번째 계수가 양수이고 두 번째 계수가 음수 인 선형 조합 만 고려하고 있습니다. 계수 중 하나가 0 인 경우를 포함하여 다른 가능성을 고려해야합니다.