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 является линейной комбинацией x а также y тогда и только тогда, когда n кратно gcd(x,y) (т.е. если gcd(x,y) % value == 0)

Вы можете использовать это понятие как мощный актив в своем коде.

Мораль здесь заключается в том, чтобы вычислить 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;
}