C : 정수가 배열 요소의 선형 조합인지 확인하십시오.

Question

길이가 n 인 주어진 배열에서 정수를 요소의 선형 조합으로 표현할 수 있는지 확인하는 방법은 무엇입니까? 현재 n = 2 일 때 특정 경우에 대해 코드를 작성할 수 있지만 n을 알 수없는 코드를 작성하는 방법을 알지 못합니다.

이

가 함수 인 경우, N = 2 (배열의 두 요소가있는 경우)

bool check(int array[], int n, int value){//n values in the array //  

    for (int i=1; i<array[0]; i++){ 
    for (int j=1; j<array[1]; j++){ 
     if ((i*array[0]+j*array[1])%value==0){ 
      printf("x=%d, y=%d, i=%d, j=%d\n", array[0], array[1], i, j); 
      return 1; 
     } 
    } 
    } 
return 0; 
} 

어떤 도움을 받고있다.

Answer 1

나는 및 n은으로이 개념을 사용할 수있는 gcd(x,y) (즉, 경우 gcd(x,y) % value == 0)

의 배수 인 경우에만 경우 n는 선형 x의 조합 y 것을 내 첫 해 이산 수학 과정에서 기억 코드에서 강력한 자산.

도덕적 인 것은 세트의 모든 요소들 사이의 gcd를 계산하고 value이 gcd(x,y)으로 나눌 수 있는지 계속 확인하는 것입니다. 그럴 경우 1, 그렇지 않으면 0을 반환하십시오.

내가 여기에 gcd() 함수의 구현 (그것의 많은 예 온라인있다)를두고,하지만 것이다 당신이 기존 코드를 통합 할 수있는 방법입니다 ...

bool check(int array[], int n, int value){ 
    for (int i = 0; i < n - 1; i++) {   // notice we only iterate up to n - 1 
     for (int j = i + 1; j < n; j++) { 
      if (value % gcd(array[i], array[j]) == 0) { 
       printf("x=%d, y=%d, i=%d, j=%d\n", array[0], array[1], i, j); 
       return 1; 
      } 
     } 
    } 
    return 0; 
}