Algorytm euklidesa

0

Cześć,
Zrobiłem algorytm euklidesa niestety jest on za wolny. Co mogę poprawićw swoim kodzi. Algorytm ma działać dla liczb zerowych . Czyli dla liczb 0 2 ma wyswiatlić dwójkę. Zrobiłem tą funkcję ale mój algorytm jest za wolny.
#include<iostream>
using namespace std;

int main()
{

while (!std::cin.eof()){
	unsigned long long a, b;

	

	cin >> a >> b;
	if (a == 0 || b == 0) {
		cout << "0" << endl;
	}
		 else if (a > 0 && b == 0 )
		{
			cout << "a" << endl;
		}
		 if (b > 0 && a == 0)
	{
		cout << "b";
	}
	
	else {
		while (a != b)
			if (a < b) b -= a; else a -= b;
		cout << a << endl; }
	
	



}
return 0;

}

0

No ale źle ci działa ten algorytm. Dla 2 i 0 wypisze ci 0.

0

Można to zakodować prościej, używając algorytmu rekurencyjnego.

int gcd(int a, int b)
{
    return (a==0)?b:gcd(b%a,a);
}

Jego złożoność jest rzędu O( Log(min(a, b)) ).

0

Trochę Żeś namieszał, prościej to zrobić w funkcji:

using ull = unsigned long long int;

ull gcd(ull a, ull b) {
	ull m;
	while (0 != b) {
		m = b;
		b = a % b;
		a = m;
	}
	return a;
}
0

Na zajęciach jeszcze nie mieliśmy funkcji. Próbowałem tak zrobić ale czas wykonywania był dłuższy. Zmieniłem trochę algorytm. Teraz brakuje mi jednej setnej sekundy do zalicznia zadnia. Może wiecie jak to zoptymalizować przy uzuciu podstawowych operacji w c++.

#include<iostream>
#include<cstdlib>
using namespace std;
int main()
{
while (!std::cin.eof())
{
unsigned long long a, b;
cin >> a >> b;
if (a == 0) {
cout <<b << endl;
}
if (b == 0)
{
cout <<a << endl;
}
else {
while (a != b)
if (a < b) b -= a; else a -= b;
cout << a << endl;
}

	}
}
0

Mogleś przepisać tą funkcję do maina:

int main(int argc, char **argv)
{
	while (!std::cin.eof()){
		unsigned long long a, b;
		cin >> a >> b;
		unsigned long long m;
		while (b != 0){
			m = b;
			b = a % b;
			a = m;
		}
		cout << a << endl;
	}
	return 0;
}

Jak teraz nie przejdzie, to wydaje mi się, że ciężko będzie poprawić złożoność.

0
int main()
{
   for(unsigned long long a,b;cin>>a>>b;cout<<a<<endl) for(unsigned long long r;b;r=a%b,a=b,b=r) {}
   return 0;
}
2
ulxoriffh Sdfv napisał(a):

Na zajęciach jeszcze nie mieliśmy funkcji.

To znaczy, że nauczyciel nie ma pojęcia o kodowaniu.
Używanie i definiowanie funkcji jest chyba najistotniejszą funkcjonalnością każdego języka programowania.
IMO zaraz po wypisaniu "hello word" powinno się uczyć definiowania funkcji (jeszcze przed for if itp).

A już na pewno nie powinno się zadawać zadań do rozwiązania, jeśli ktoś jeszcze nie umie definiować funkcji.

0

Podstawowy problem z punktu widzenia wydajności, to niezauważenie, że zamiast wielokrotnego odejmowania lepiej użyć reszty z dzielenia (a%b).

1 użytkowników online, w tym zalogowanych: 0, gości: 1