Rozszerzony algorytm Euklidesa bez stosu czy rekurencji

Question

using System;

public class Test
{
	public static void Main()
	{
		// your code goes here
		int a,b,d,x,y;
		string str;
		str=Console.ReadLine();
		int.TryParse(str,out a);
		str=Console.ReadLine();
		int.TryParse(str,out b);
		d = gcdex(a,b,out x,out y);
		Console.WriteLine("NWD({0},{1})={2}",a,b,d);
		Console.WriteLine("Wspolczynniki przy a oraz b to: {0} {1}",x,y);
	}
	public static int gcdex(int a,int b,out int x,out int y)
	{
		int c,temp;
		int top = -1;
		int[] S = new int[10];
		x = 1;
		y = 0;
		while(b != 0)
		{
			top++;
			if(top == S.Length)
				Array.Resize(ref S,2*S.Length);
			S[top] = a/b;
			temp = a;
			a = b;
			b = temp % b;
		}
		while(top != -1)
		{
			c = S[top];
			top--;
			temp = x;
			x = y;
			y = temp - c * y;
		}
		if(a < 0)
		{
			x *= -1;
			y *= -1;
			return -a;
		}
		else
			return a;
	}
}

 

 

Jak przepisać tę funkcję tak aby stos nie był potrzebny

Funkcja licząca NWD działa jednak przez to użycie stosu funkcja nie jest optymalna pamięciowo

 

Comments

https://cp-algorithms.com/algebra/extended-euclid-algorithm.html#iterative-version

---

Widziałem to jednak te make tuple

Kiedyś znalazłem też funkcję zapisaną w Pascalu ale już nie mam kodu na dysku

---

Ale można się przecież łatwo pozbyć tuple.

---

To pokaż

Na youtube jeden rozpisał obliczenia w tabelce i stąd napisałem ten kod a

wcześniej widziałem funkcję iteracyjną zapisaną w Pascalu
więc napisałem że można bez stosu

---

Poza tym lepiej byłoby dojść do tego jak wyrugować stos analizując kod a nie wyszukując gotowców

---

make_tuple służy wyłącznie uproszczeniu zapisu. To:

tie(x, x1) = make_tuple(x1, x - q * x1);

to jest to samo co to:

int temp_x = x1;
x1 = x - q * x1;
x = temp_x;

A jeśli chcesz zrozumieć dlaczego to działa to na tej stronie co podlinkowałem wszystko jest napisane.

---

To czy to uproszczenie zapisu to już kwestia względna
Otóż okazało się że ten algorytm co widziałem zapisany w Pascalu
przepisałem na jednym z forów matematycznych

Jak dla mnie ta wersja z tuple może i jest krótsza za to mniej czytelna

Answer 1

int gcdex(int a,int b, int &x,int &y){
    int xa = 1, ya = 0, xb = 0, yb=1;
    int a0 = a, b0 = b;
     int q;
    while(a0 != 0 && b0 != 0)  
   {
            if(abs(a0) > abs(b0))
            {
                  q = a0/b0;
                   a0 = a0 % b0;
                   xa -= q*xb;
                   ya -= q*yb;
            }
            else
            {
                   q = b0/a0;
                   b0 = b0 % a0;
                    xb -= q*xa;
                    yb -= q*ya;
            }
   } 
if(b0 == 0)
{
     x = xa;
     y = ya;
}
else
{
    x = xb;
    y = yb;
}
if(a*x+b*y < 0)
{
   x = -x;
   y = -y
}
return a*x+b*y;
}

 

Jakiś czas temu widziałem u Mateusza Kowalskiego algorytm przedstawiony w ten sposób że łatwo było napisać następującą funkcję

 

Jak widać Mateusz Kowalski lepiej przedstawił algorytm niż Oskar Skibski