Algorytm euklidesa

Odpowiedz Nowy wątek
2019-10-10 20:45
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;

}

Pozostało 580 znaków

2019-10-10 20:54
0

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

nie, wypisze: a <- źle, czytaj niżej. - _13th_Dragon 2019-10-11 12:15
Przecież załapie się na pierwszy if. - szweszwe 2019-10-11 12:17
Ups, racja, nie zobaczyłem dokładnie i przyjąłem że tam stoi sensowny operand, czyli: && - _13th_Dragon 2019-10-11 12:19
No nie, w tym kodzie niewiele jest sensownego :) - szweszwe 2019-10-11 12:19

Pozostało 580 znaków

2019-10-10 21:07
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)) ).

edytowany 1x, ostatnio: TomaszLiMoon, 2019-10-10 21:08

Pozostało 580 znaków

2019-10-10 21:18
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;
}

Pozostało 580 znaków

2019-10-10 21:56
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;
}

    }
}

Pozostało 580 znaków

2019-10-10 22:10
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ść.


edytowany 1x, ostatnio: lion137, 2019-10-10 22:11
Ale można pozbyć się wolnego cin/cout ;) - Shalom 2019-10-10 22:42
std::cin.eof() oraz cin >> a >> b - coś tu nie pasuję - _13th_Dragon 2019-10-11 01:18

Pozostało 580 znaków

2019-10-11 01:28
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;
}

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2019-10-11 11:24
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.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 1x, ostatnio: MarekR22, 2019-10-11 11:25
Właśnie, algorytm, bardzo prosty, ale nie banalny, a tu funkcji nie znamy! - lion137 2019-10-11 11:37

Pozostało 580 znaków

2019-10-11 11:32
0

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

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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