غاوسي القضاء مودولو ص

Question

أحاول إعادة كتابة رمز في جافا حل مجموعة من المعادلات الخطية القيام القضاء غاوس على العوامات ، للعمل على المعادلات مودولو رئيس الوزراء.المشكلة هي أنه لا يعمل ، ولا يمكنني معرفة ما هو الخطأ.يبدو أنه يعمل على مجموعات صغيرة من المعادلات ، ولكن ليس على مجموعات كبيرة ، مما يجعل التصحيح صعبا.

تأخذ الخوارزمية الخاصة بي الصف الأول ، وتطبيع هذا من خلال إيجاد معكوس العنصر الأول ، وتضاعف كل عنصر في الصف بهذا المعكوس.ثم يطرح هذا الصف من الصفوف الأخرى مرات كافية لجعل العنصر الأول صفرا.في التكرار التالي ، ينتقل إلى الصف التالي ويفعل نفس الإجراء ، حتى يكون العنصر المحوري للصف الأول في العمود الأول.وأخيرا فإنه يطرح كل صف من الصفوف السابقة لجعل عنصر واحد فقط غير الصفر من كل عمود (باستثناء آخر واحد).(اعتبارا من الآن يمكنني استخدام الزوجي ، وهو ليس ضروريا ، ولكن هذا لا ينبغي أن يكون مشكلة).وهنا رمز بلدي:

// Transforms A so that the leftmost square matrix has at most one 1 per row,
    // and no other nonzero elements.
    // O(n^3)
 public static void gauss(int[][] A, int num_columns) {
        int n = A.length;
        int m = A[0].length;

        for (int i = 0; i < num_columns; i++) {
            // Finding row with nonzero element at column i, swap this to row i
            for(int k = i; k < num_columns; k++){
                if(A[k][i] != 0){
                    int t[] = A[i];
                    A[i] = A[k];
                    A[k] = t;
                }
            }
            // Normalize the i-th row.
            int inverse = (int)inverse((long)A[i][i], prime);
            for (int k = i ; k < m; k++) A[i][k] = (A[i][k]*inverse) % prime;

            // Combine the i-th row with the following rows.
            for (int j = 0; j < n; j++) {
                if(j == i) continue;
                int c = A[j][i];
                A[j][i] = 0;
                for (int k = i + 1; k < m; k++){
                    A[j][k] = (A[j][k] - c * A[i][k] + c * prime) % prime;
                }
            }
        }
    }

    public static void gauss(int[][] A) {
        gauss(A, Math.min(A.length, A[0].length));
    }
    public static long gcd(long a, long b){
        if(a < b){
            long temp = a;
            a = b;
            b = temp;
        }
        if(b == 0) return a;
        return gcd(b, a % b);
     }
    public static Pair ext_euclid(long a, long b){
        if(a < b){
            Pair r = ext_euclid(b,a);
            return new Pair(r.second, r.first);
        }
        if(b == 0) return new Pair(1, 0);
        long q = a / b;
        long rem = a - b * q;
        Pair r = ext_euclid(b, rem);
        Pair ret = new Pair(r.second, r.first - q * r.second);
        return ret;
    }

    public static  long inverse(long num, long modulo){
        num = num%modulo;
        Pair p = ext_euclid(num, modulo);
        long ret = p.first;
        if(ret < 0) return (modulo + ret) % modulo;
        return ret % modulo;
    }

    static class Pair{
        public long first;
        public long second;
        public Pair(long frst, long scnd){
            first = frst;
            second = scnd;
        }
    }

هذا يعمل على أمثلة صغيرة (وزارة الدفاع 29):

matrix = {{1.0, 1.0, 1.0, 1.0}, {1.0, 2.0, 1.0, 2.0},{1.0, 0.0, 0.0‚ 3.0}};
answer= {{1.0, 0.0, 0.0, 0.0},{0.0, 1.0, 0.0, 1.0}, {0.0, 0.0, 1.0, 0.0}};

وهو الصحيح (المتغير الأول = 0 ، الثاني = 1.0 ، الثالث = 0) ، كما يمكن التحقق من قبل ولفرام ألفا ل 0*ك^0 + 1*ك^1 + 0*ك^2 ل ك = 1..3.

على سبيل المثال ، وجود 10 متغيرات ، والمعادلات أ * ك ^ 0 + ب * ك^1 + ج*ك^2...(وزارة الدفاع 29) لك = 1..11 ، لدي هذه المصفوفة:

1 1 1 1 1 1 1 1 1 1 1 8 
1 2 4 8 16 3 6 12 24 19 9 5 
1 3 9 27 23 11 4 12 7 21 5 12 
1 4 16 6 24 9 7 28 25 13 23 12 
1 5 25 9 16 22 23 28 24 4 20 15 
1 6 7 13 20 4 24 28 23 22 16 0 
1 7 20 24 23 16 25 1 7 20 24 5 
1 8 6 19 7 27 13 17 20 15 4 1 
1 9 23 4 7 5 16 28 20 6 7 18 
1 10 13 14 24 8 22 17 25 18 7 20 
1 11 5 26 25 14 9 12 16 7 7 8  

باستخدام خوارزمية بلدي أحصل على الجواب:

1 0 0 0 0 0 0 0 0 0 0 18 
0 1 0 0 0 0 0 0 0 0 0 8 
0 0 1 0 0 0 0 0 0 0 0 15 
0 0 0 1 0 0 0 0 0 0 0 11 
0 0 0 0 1 0 0 0 0 0 0 28 
0 0 0 0 0 1 0 0 0 0 0 27 
0 0 0 0 0 0 1 0 0 0 0 7 
0 0 0 0 0 0 0 1 0 0 0 21 
0 0 0 0 0 0 0 0 1 0 0 9 
0 0 0 0 0 0 0 0 0 1 0 24 
0 0 0 0 0 0 0 0 0 0 1 14  

لكن هذا خطأ!(يمكن التحقق مع ولفرام ألفا).يجب أن تكون الإجابة الصحيحة (أ ب ج ...) = (8 13 9 13 4 27 18 10 12 24 15).

يمكن لأي شخص بقعة خطأي?أو لقد أساءت فهم كيفية القيام غاوس وزارة الدفاع ص?

Answer 1

لا يبدو أنك تجد صف مع غير صفري في المركز الأول خلال المرحلة الأولى.وبالنظر إلى ذلك ، وحقيقة أنني لا أعرف كيف لديك inverse تعمل الوظيفة ، قد تواجه أو لا تواجه مشكلة هناك.

لا أفهم لماذا تبحث عن" محاور " في المرحلة الثانية.أنت تعرف أين هم من المرحلة الأولى.في الواقع ، لا أرى لماذا لديك مرحلة ثانية على الإطلاق.هل كل من القضاء في المرحلة الأولى بدلا من ذلك.هذا سوف يوضح التعليمات البرمجية الخاصة بك إلى حد كبير.

أنا لا أفهم لماذا كنت تستخدم doubleالصورة في المصفوفة الخاصة بك.أنا أيضا لا أفهم لماذا تستخدم Math.abs في كل مكان;مقارنات المساواة مناسبة هنا.

أخيرا ، أنت تحل نظام فاندرموند.إذا كان هذا هو التطبيق الخاص بك ، وليس مجرد حالة اختبار ، يجب عليك على الأرجح استخدام الاستيفاء لاغرانج بدلا من ذلك.