如何检查整数是否是数组中元素的线性组合? [英] How to check if an integer is linear combination of elements in an array?

问题描述

如何检查整数是否可以表示为长度为n的给定数组中元素的线性组合?目前，当n = 2时，我可以为特定情况编写代码，但是当n未知时，我不知道如何编码.

How to check if an integer can be expressed as linear combination of elements in a given array of length n? Currently I can code for the specific case when n=2, but I don't know how to code when n is unknown.

这是n = 2时的功能(当数组中只有两个元素时):

This is the function when n=2 (when there are only two elements in the array):

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

推荐答案

从第一年的离散数学课程中我记得，当且仅当n为a时，n是x和y的线性组合. gcd(x,y)的倍数(即value % gcd(x,y) == 0)

I remember from my first-year discrete math courses that n is a linear combination of x and y if and only if n is a multiple of the gcd(x,y) (i.e. if value % gcd(x,y) == 0)

您可以将此概念用作代码中的强大资产.

you can use this notion as a powerful asset in your code.

这里的目的是计算集合中所有元素之间的gcd，并继续检查value是否可被gcd(x,y)整除.如果是，则返回1，否则返回0.

The moral here is to calculate the gcd between all the elements in your set and keep checking if value is divisible by the gcd(x,y). If it is, then return 1, else 0.

我将gcd()函数的实现留给您(在线有很多示例)，但是这是将其合并到现有代码中的方法:

I'll leave the implementation of the gcd() function to you (there are many examples of it online), but here is how you can incorporate it in your existing code:

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

这篇关于如何检查整数是否是数组中元素的线性组合?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！