Problem z zadankiem ze SPOJ

Question

Hej. Mam problem z pewnym zadaniem ze spoja: http://pl.spoj.com/problems/NWW/.

Za nic nie mogę znaleźć błędu w moim kodzie, dlatego proszę was o pomoc. Wynik nie zawsze się zgadza. 

#include <iostream>

using namespace std;


int main()
{
    int n;
    int liczby[100000];
    int najwieksza=0;
    int wspolny_dz;
    int mnoznik = 2;   

    cin >> n;
    for (int j = 0; j < n; j++)
    {
        cin >> liczby[j];
    }


    for (int j = 0; j < n; j++)
    {
        if (liczby[j] > najwieksza)
        {
            najwieksza = liczby[j];
        }
    }
    wspolny_dz = najwieksza;

        
    for (int j = 0; j < n; j++)
    {
        if ((wspolny_dz%liczby[j]) != 0)
        {
            wspolny_dz = najwieksza * mnoznik;
            mnoznik++;
            j = 0;
        }
            
    }
    cout << endl << endl;
    cout << wspolny_dz << endl;
}

Będę wdzięczny za naprowadzenie na błąd.

Answer 1

Nie jestem pewien, ale obstawiam, że wstawienie j = 0; w 37 linii może namieszać w programie. W C++ masz coś w rodzaju continue i break, może się przydadzą?

Poza tym robisz błąd robiąc tablicę "na zapas", to nie turbo pascal :)

 

Comments

Faktycznie. Zrobiłem zmienną niezależną od j i wydaje mi się, że teraz działa. Dzięki wielkie. :D Choć trochę ciekawi mnie, dlaczego coś się psuje kiedy "j" jest zerowane.

 

Już próbowałem wcześniej zastosować break bo myślałem, że może pętla "for" ustala na samym początku, że zostanie zakończona jeśli warunek się nie spełni, a nie na końcu, ale to też nie pomogło.

Anyways, teraz śmiga. xd

---

Zobacz czy śmiga rzeczywiście, bo kolega Aisekai poniżej dał wiele dobrych rat.

Answer 2

Na szybko:

1. Z tego co widzę, źle zrozumiałeś wejście.

-Najpierw na wejściu dostajesz liczbę zestawów,

-potem na wejściu zostaje wprowadzone ile liczb ma dany zestaw,

-wprowadzony zostaje zestaw (każda liczba oddzielona spacją)

-Krok 2 i 3 zostaje powtórzony tyle razy, ile wynosiła liczba co pojawiła się jako 1 na wejściu.

A ty masz tylko jedną iterację.

2.  Dalej, tworzenie na początku tablicy z 100000 komórkami to zły pomysł. Koncepcja na program powinna wyglądać tak:

- Pobierz pierwszą wartość z wejścia (n)

-Utwórz pętlę (for, while, do-while) która wykona się (n) razy.

-Utwórz dynamicznie tablicę (jeśli potrzebna) i zapisz w niej dane

-Wykonaj algorytm wyznaczania NWW dla wszystkich liczb

-Wypisz  wspólny dzielnik i znak nowej linii.

3. Wydaje mi się (na szybko), że ten algorytm wyznaczania NWW nie jest poprawny. Poczytaj o algorytmach do wyznaczania NWW 2 liczb. Dobrze napisany program, nie będzie wymagał dynamicznego alokowania danych wejściowych.

Edit: Do wyznaczenia NWW, można skorzystać z zależności, że NWW(a,b)*NWD(a,b)=a*b więc można łatwo zauważyć, że NWW(a,b) = (a*b)/NWD(a,b).

Może Ci się przydać wiedza, że NWD(a,b,c)=NWD(NWD(a,b),c)

Comments

Dzięki za porady. Wiem, że wejście nie jest poprawne, powinienem to podkreślić przy tworzeniu tematu. Chciałem najpierw zająć się samym środkiem zadanka a potem dostosować je pod spoja. O algorytmach wyznaczania NWW poczytam, po prostu na początek chciałem samemu spróbować to rozwiązać.

Mój pomysł na to był taki, że najpierw znajduje największą liczbę spośród podanych i wstępnie zakładam, że wspólny dzielnik to ta największa liczba.

Następnie wszystkie podane liczby są dzielone przez ten dzielnik. Jeśli z któregoś z dzieleń reszta będzie inna od 0 to do dzielnika dodaję największą z liczb. I tak leci w kółko aż reszta z dzielenia przez każdą liczbę zawsze będzie równa 0.

Wydaje mi się, że nie ma tu błędu, choć mogę się mylić. Jeszcze raz dzięki za porady. :D

---

Aaa, ok. Nie zrozumiałem idei tego wcześniej, ale teraz jak to przedstawileś, to wygląda że dobry algorytm, może mniej optymalny niż standardowe znalezienie NWD, obliczenie iloczynu ab i podzielenie go przez nwd, ale jest ok.