c - 具有更多解的线性方程的算法

Question

谁能帮我解决在模块化算术 (!) 中求解线性方程的算法。我只需要“最小”的解决方案。最小意味着字典序在前。

让我们拥有这个系统:
3x1+2x2=3
4x1+3x2+1x3+2x4=4
x 旁边的数字是索引。

我们使用模 5(0<=x<=p，其中 p 是我们的模)的这个系统的矩阵是
3 2 0 0 0 | 3
4 3 1 2 0 | 4

最小的解决方案是 (0,4,0,1,0)。我必须编写一个算法来为我提供该解决方案。我在考虑暴力破解，因为 p<1000。但我不知道该怎么做，因为在这种情况下，第一行我必须 x1=0 ... p-1，然后求解 x2，在第二行我必须选择 x3= 0 ... p-1。并解决 x4。我必须这样做，直到方程组成立。如果我从 0 .. p-1 开始，那么我得到的第一个解决方案将是最小的。

PS:矩阵可以有很多种形式，比如:
3 2 4 0 0 | 3
4 3 1 2 1 | 4

1 2 0 0 0 | 3
3 0 3 0 0 | 3
4 3 1 2 3 | 4
等

抱歉我的英语不好，我来自亚洲。

编辑:我在考虑如何确定哪些变量是参数。但是想不通....

Answer 1

好吧，这到底是怎么回事，为什么不呢，给你

#include <stdio.h>

#define L 2
#define N 5
#define MOD 5

static int M[L][N] =
{       { 3, 2, 0, 0, 0 }
,       { 4, 3, 1, 2, 0 }
};

static int S[L] =
{       3, 4
};

static void init(int * s)
{
        int     i;
        for (i = 0; i < N; i++)
        {
                s[i] = 0;
        }
}

static int next(int * s)
{
        int     i, c;
        c = 1;
        for (i = N-1; i >= 0 && c > 0; i--)
        if ( (++s[i]) == MOD)
        {
                s[i] = 0;
        }
        else
        {
                c = 0;
        }
        return c == 0;
}

static int is_solution(int * s)
{
        int     i, j, sum;

        for (i = 0; i < L; i++)
        {
                sum = 0;
                for (j = 0; j < N; j++)
                {
                        sum += M[i][j]*s[j];
                }
                if (sum % MOD != S[i])
                {
                        return 0;
                }
        }
        return 1;
}

int main(void)
{
        int     s[N];

        init(s);
        do
        {
                if (is_solution(s))
                {
                        int     i;
                        for (i = 0; i < N; i++)
                        {
                                printf(" %d", s[i]);
                        }
                        printf("\n");
                        break;
                }
        } while (next(s));
        return 0;
}