Linearna diofantska enačba

[Math Freak]

Pozdravljeni,

rad bi napisal program, ki ugotovi ali obstaja rešitev za linearno diofantsko enačbo (za dane a,b,c) oblike \(ax + by = c; \ \ \ a,b,c,x,y \in \mathbb{Z^+}\).

Za klasično linearno diofantsko enačbo obstajajo celoštevilske rešitve tedaj, ko \(c|D(a,b)\). Kaj pa, če iščemo nenegativne celoštevilske rešitve - je potrebno iti skozi tisti razširjen Evklidov algoritem ali obstaja kaka krajša pot?

[Math Freak]

Kaj pa če bi spremenil nalogo v iskanje vsaj enega para pozitivnih celoštevilskih koordinat x in y za linearno funkcijo by = -ax + c ... obstajajo kake metode za to?

Diofantske enačbe je simpl za razrešit ročno, ampak se mi zdi ful komplicirano da bi to sprogrameru ...

[derik]

V Excelu je to zelo enostavno. Enačbo ax + by = c rešiš takole. Označiš stolpce z "a", "b", "c", "x", "y", in "ax+by-c" ter v zadnjega napišeš ustrezno formulo. Potem odpreš Solver in nastaviš za Objective "ax+by-c" = 0, s spreminjanjem vrednosti v celicah x in y, ob dveh pogojih in sicer, da je x integer in y integer.

[Math Freak]

Na žalost bi rad napisal program v c#, tako da ne gre tako preprosto.

V bistvu je največ dela z razširjenem Evklidovim algoritmom - po tem dobiš partikularno rešitev, nato splošno rešitev za x in y, za kateri razrešiš sistem dveh neenačb \(x \geqslant 0\) in \(y \geqslant 0\).

Sem mislil, če obstaja kakšna hitrejša pot, ker za razliko od običajnega postopka imam v enačbi sama pozitivna števila a,b,c,x,y in ne zanimajo me rešitve te enačbe ampak samo to, če rešitev obstaja.

[derik]

Potem ti pa zadostuje preveriti, če je c mnogokratnik od GCD(a, b). Če ni, potem ni rešitve.

[Math Freak]

To pa ne bo držalo ...

a = 8, b = 6, c = 10
D(6,8) = 2; c%2 = 0

Nenegativni rešitvi za x in y za enačbo 8x + 6y = 10 sta ?

[Math Freak]

Zaenkrat izgleda koda tako (z optimizacijo se bom kasneje ukvarjal, trenutno rabim delujočo rešitev)

Koda: Izberi vse

            // imamo enačbo ax + by = c
            int a = 12;
            int b = 130;
            int c = 5260;

            if (c == 0 || (a > c && b > c))
            {
                Console.WriteLine("nesmiselni podatki");
            }

            // ali lahko sestavimo rezultat samo z enim parametrom
            if (c % a == 0 || c % b == 0)
            {
                Console.WriteLine(true);
            }

            // nastavi, da je a manjši ali enak b
            if (a > b)
            {
                int temp = a;
                a = b;
                b = temp;
            }

            List<int> bList = new List<int>() { };
            List<int> aList = new List<int>() { };
            List<int> pList = new List<int>() { };
            List<int> qList = new List<int>() { };

            // če je b večkratnik števila a, potem vrnemo false, saj z a-jem ne moremo sestaviti rezultata
            if (b % a == 0)
            {
                if (c % a != 0)
                {
                    Console.WriteLine(false);
                }
            }

            // poženemo razširjen Evklidov algoritem
            else
            {
                // osnovni izrek o deljenju: b = p*a + q 
                bList.Add(b);
                aList.Add(a);
                pList.Add(b / a);
                qList.Add(b % a);

                // dokler ostanek ni enak 0, nadaljujemo ta algoritem
                while (qList[qList.Count - 1] != 0)
                {
                    bList.Add(aList[aList.Count - 1]);
                    aList.Add(qList[aList.Count - 1]);
                    pList.Add(bList[aList.Count - 1] / aList[aList.Count - 1]);
                    qList.Add(bList[aList.Count - 1] % aList[aList.Count - 1]);
                }
            }

            // testiranje - primerjava z ročnim pregledom
            Console.Write("b': ");
            foreach (int i in bList)
            {
                Console.Write(i + " ");
            }
            Console.Write("\np': ");

            foreach (int j in pList)
            {
                Console.Write(j + " ");
            }
            Console.Write("\na': ");
            foreach (int k in aList)
            {
                Console.Write(k + " ");
            }
            Console.Write("\nq': ");
            foreach (int l in qList)
            {
                Console.Write(l + " ");
            }
            // konec testiranja

            Console.WriteLine();
            Console.WriteLine("\nGCD(a,b) = " + qList[aList.Count - 2]);

            // GCD(a,b) se nahaja v predzadnji vrstici med ostanki, tu lahko preverimo rešitev, ki vključuje negativna števila
            if (c % qList[aList.Count - 2] != 0)
            {
                Console.WriteLine(false);
            }

Ta algoritem deluje sedaj - to je navaden Evklidov algoritem s katerem dobimo GCD(a,b).

Je kaka ideja kako bi reversal sedaj ta algoritem, da bi dobil razširjen Evklidov algoritem?

[Math Freak]

Nevermind, sem že našel odgovor na Wiki-ju: http://en.wikipedia.org/wiki/Extended_E ... _algorithm