37421. Posortuj Euklidesa [DDZ6]

[wojdanadam]

Witam.
Mam problem z tym zadaniem: https://pl.spoj.com/problems/DDZ6/

Napisałem już działający kod, który wczytywał liczby i sortował je malejąco na podstawie ich największych dzielników oraz wyświetlał na ekranie. Jak już miałem wszystko dopięte na ostatni guzik to zorientowałem się, że nie przeczytałem dokładnie zadania i zapomniałem o tym, że w przypadku, gdy dzielniki danych liczb są takie same to te liczby względem siebie powinny być posortowane rosnąco.

Dokleiłem do algorytmu sortującego kolejnego if’a, który uwzględnia przypadek, gdy dzielniki są sobie równe.
Niestety kod nie działa. Głowie się nad tym parę dni i nie jestem w stanie zrozumieć co zrobiłem źle.

Cały kod:

Ideone.com

Może na początku opisze jak ten kod działa krok po kroku.

1. Oblicza wszystkie dzielniki liczby 1260 i zapisuje je do tablicy "basic_number_divisors"
2. Wczytuje ilość liczb jaką do programu zamierzamy wprowadzić.
3. Wczytuje owe liczby do tablicy "number"
4. Porównuje liczbę “number” z “basic_number_divisors” i zapisuje ile dzielników powinno sprawdzić (np. jeśli liczba jest większa lub równa 1260 to musi sprawdzić wszystkie 36 dzielników).
5. Zapisuje do tablicy “common_divisors” największe dzielniki tych liczb.
5.5. W tym momencie mam dwie tablice: “number” z liczbami oraz “common_divisors” z ich największymi dzielnikami. Obie tablicę mają te same współrzędne dla numerów i ich dzielników. np. "common_divisors[33] to największy dzielnik liczby number[33].
6. No i zaczyna się sortowanie bąbelkowe.
6a. W pierwszym if’ie algorytm sortuje jednocześnie tablicę “common_divisors” oraz “numbers” na podstawie danych z tablicy “common_divisors”. Tak by posortować dzielniki od największego do najmniejszego oraz analogicznie liczby w tablicy "numbers"
6b. W else if algorytm sortuje dane liczby w tablicy “number” od najmniejszej do największej jeśli dzielniki tych liczb są takie same. Niestety ten fragment nie działa.
7. Program wyświetla już posortowane liczby z tablicy “number”.

Fragment algorytmu do sortowania z podpunktu 6a. i 6b.:

        if (*largest_common_divisors < *(largest_common_divisors + 1))
        {
            // algorithm for sorting tables with the largest common divisors
            temp = *largest_common_divisors;
            *largest_common_divisors = *(largest_common_divisors + 1);
            *(largest_common_divisors + 1) = temp;

            // algorithm for sorting tables with numbers
            temp_number = *number;
            *number = (*number + 1);
            *(number + 1) = temp_number;
        }


        // ----- THE CODE BELOW DOES NOT WORK -----
        // if the divisors have the same value next to each other, the algoritm sorts the corresponding numbers in ascending order

    else if (*largest_common_divisors == *(largest_common_divisors + 1))
    {
        if (*number > (*number + 1))
        {
            temp_number = *number;
            *number = *(number + 1);
            *(number + 1) = temp_number;
        }
    }

Problem polega na tym, że warunek ten pomimo tego, że jest spełniony to w ogóle się nie wykonuje.
Nie mam pojęcia w czym może być problem bo, gdy debuguje mając ustawiony breakpoint na tym if’ie to widać, że pomija cały ten kod.
Najdziwniejsze jest to, że jak podmienię warunki z “if” oraz “else if” w ten sposób:

        if (*largest_common_divisors == *(largest_common_divisors + 1))
        else if (*largest_common_divisors < *(largest_common_divisors + 1))

to dalej wykonuje się pierwszy if. Kolejności też podmieniałem oraz zamiast else if dawałem po prostu if. To jest już absurdalne

Bardzo proszę o pomoc. Według mnie kod jest poprawny i powinien działać tylko z jakiegoś nieznajomego mi i powodu program całkowicie pomija drugi warunek.

PS. Wiem, że część kodu z pkt 4 i 5 dałoby się połączyć. Wiem też, że finalnie w wyjściu mają być wyświetlane tylko liczby oraz bez zbędnych śmieci;).

[wojdanadam]

To jest niesamowite. Głowie się nad tym już parę dni i dopiero gdy napisałem post na tym forum i przeczytałem swój własny post to dostrzegłem strasznie głupią literówkę, która była przyczyną niedziałającego kodu.

miałem w kodzie

if (*number > (*number + 1))

zamiast

if (*number > *(number + 1))

EDIT
Kod już działa ale sędzia ma teraz inne obiekcje: “Przekroczono limit czasu”.
Wie ktoś może dlaczego?

Tutaj mam poprawioną wersje kodu:

Ideone.com

To przez mało wydajne sortowanie bąbelkowe?

[narbej]

To przez mało wydajne sortowanie bąbelkowe?

Tak, ale:
mówiąc oględnie, twoje gcd [greatest common divisor] jest też mało wydajny, a użycie wskaźniów [a także komentarzy] jest nieuzasadnione.

PS
Pochwała, za całościowe i wyczerpujące opisanie problemu oraz piękny [mówiąc oględnie] jak na początkującego kod.

[wojdanadam]

Przerobiłem kod tak, że powinien być bardziej wydajny, krótszy i czystszy.

Ideone.com

Niestety dalej sędzia krzyczy "“Przekroczono limit czasu”.
Nie mam pomysłu jak jeszcze mógłbym to usprawnić.
Używanie bardziej zaawansowanych algorytmów do sortowania nie bardzo mi pasuje do zadania z kategorii łatwe.

@narbej
Dlaczego użycie wskaźników jest nieuzasadnione? Dodałem wskaźniki by przyspieszyć dzięki temu algorytmy działające na tablicach (oraz chciałem przećwiczyć wskaźniki i przesyłanie oryginalnych zmiennych do funkcji, przed którymi do tej pory broniłem się rękami i nogami ).

PS. Dzięki za pochwałę. Ale wcześniej źle opisałem punkt nr 4 działania programu (sam nie do końca rozumiałem co robi void CheckNumber po parodniowym odpoczynku od tego zadania).
A te komentarze dodałem nie dla siebie, tylko dla czytających ten temat(przy okazji ćwicząc moją łamaną angielszczyznę). Myślałem, że poprawie tym czytelność kodu.

[narbej]

Masz trochę racji, ale niestety albo musisz sam napisać lepszy algorytm do sortowania albo użyć gotowej funkcji [algorytmu] sort z biblioteki STL.

To jest moje zdanie: jeżeli dopiero zaczynasz, to użycie wskaźników mogłoby być uzasadnione tylko z tego powodu, że chcesz je poznać i przećwiczyć. Zastosowanie wskaźników zamiast normalnych indeksów w żadnym wypadku nie powoduje przyśpieszenia działania programu - uzyskujemy taki sam. Po co więc stosujemy wskaźniki? Aby skrócić zapis kodu, a przy okazji uczynić go mniej czytelnym i zrozumiałym - przeczytaj początek tego akapitu

Taki przykład - jak bym to ja napisał, jeżeli bym w ogóle tak pisał - patrz początek poprzedniego akapitu.

void showNumbers (int *numbers, int v_how_many) {
    while (v_how_many--)
        cout << *numbers++ << " ";
}

ale pewnie raczej jednak tak:

void showNumbers (int *numbers, int v_how_many) {
    for  (int i = 0; i < v_how_many; ++i)
        cout << *(numbers +i) << " ";
}

Napisałem, że nieuzasadnione, bo jednak najpierw powinieneś napisać działający kod na AC, a dopiero potem baw się wskaźnikami i sam naocznie zobacz czy uzyskany kod będzie dużo szybszy. Nawet jeżeli przypadkiem tak się stanie, to i tak efekt nie będzie wart - gra nie warta świeczki.
Lub może inaczej - tablice do funkcji można przekazać jako adres początku tablicy - czyli masz rację - jako wskaźnik, ale potem bezpośrednie działania na nim - przesuwanie go powodują efekty uboczne.

Komentarze powinny być tylko dla Ciebie w pierwszej kolejności. Jeżeli robiłeś to dla mnie - musiałem myśleć o jeszcze jedne jrzeczy więcej, o twoim komentarzu. To nie moje wymysły - poczytaj np Czysty kod - [Clean kode].
Nadmiar lub zbędne komentarze tylko zaciemniają kod.
Taki przykład:

// determine divisors of 1260 and set them all to variable "all_basic_number_divisors"
    setBasicNumberDivisors(basic_number, basic_number_divisors);
///Jeżeli używasz opisowych nazw zmiennych i funkcji to komentarz staje się zbędny [lub błędny ;-) ]
// determine divisors of 1260 and set them all to variable "basic_number_divisors"
// chyba, że tak bardzo chcesz poćwiczyć angielski.
// podobnie dalej - przy sortowaniu

Mój przykład zbędnego komentarza:

/// teraz będę sortował tablicę A od początku do końca
sort (A.begin(), A.end());  

A znajdowanie gcd, wymyślił już starożytny matematyk Euklides. Tu masz po angielsku: https://en.wikipedia.org/wiki/Euclidean_algorithm, ale to samo zbnajdziesz też po polsku.

[pawoj20]

Nie mam pomysłu jak jeszcze mógłbym to usprawnić

Jest dostepne omowienie zadania pod adresem

Konkurs programistyczny z okazji Dnia Dziecka (SPOJ)

(chyba jest dostepne dla kazdego ??)
Jest tam fragment
W zadaniu tym należało zaimplementować dowolny algorytm sortujący o złożoności O(n log2(n)) albo lepszej.
Nie rozwiazywalem tego zadania, ale wydaje sie po omowieniu że jest to bardzo ważne.
Sortowanie bombelkowe ma zlozonosc wieksza niz omawiana.

[korkirw]

Omówienie jest dostępne dla każdego. Ja to omówienie czytałem

[oscarman28]

Cześć, czy ktoś mógłby mi podpowiedzieć dlaczego Spoj nie akceptuje mi poniższego kodu ?
Testowałem go i według przykładu podając liczby na wejściu otrzymuje podane liczby na wyjściu. Wydaję się, że kod działa poprawnie.

using System;
using System.Linq;

public class Test
{
    public static void Main()
    {

        int n = int.Parse(Console.ReadLine());

        if (n<=1000000)
        { 
        int[] ciag = Console.ReadLine().Split(' ').Take(n).Select(int.Parse).ToArray();

                if (Array.TrueForAll(ciag, element => element >= 2) && Array.TrueForAll(ciag, element => element <= 1000000))
                {

                    int[] val = new int[n];
                    for (int i = 0; i < n; i++)
                    {
                        val[i] = ciag[i];
                    }

                    for (int i = 0; i < n; i++)
                    {
                        int b = 1260;
                        while (ciag[i] != b)
                        {
                            if (ciag[i] < b)

                                b -= ciag[i];

                            else
                                ciag[i] -= b;
                        }

                    }

                    Array.Sort(ciag, val);
                    Array.Reverse(val);    

                for (int k = 0; k < n-1; k++)
                {
                 
                        Console.Write(val[k] + " ");        
                }
                Console.Write(val[n - 1]);
             

            }
           
       }
    }
}

[lordarab]

Cześć, czy jesteś pewien ze zagwarantowałeś:

Jeśli NWD(a, 1260) = NWD(b, 1260), to liczby a i b sortujemy niemalejąco

[manjaro]

Witam serdecznie
Program u mnie jak również na ideone ładnie działa, dla przykładowych testów i znalezionych tutaj dostaję dobre wyniki.
Natomiast spoj wypluwa błąd wykonania NZEC. Program napisany w Python3.

Czym to może być spowodowane?

EDIT:
Poradziłem sobie już sam. Szkoda tylko że autor zadania na koniec danych testowych wrzucił sobie dodatkowo extra SPACJĘ, a ty weź sobie człowieku szukaj przez kilka godzin błędu…
Poza tym jak to w Pythonie, prawidłowo napisany program nie ma szans zmieścić się w czasie, trzeba stosować różne sztuczki typu fast I/O.