NWW z n liczb

[Dracon]

Napisałem taki kod w C++

Kod: [Zaznacz]

#include<iostream>
using namespace std;
long int nww(long a, long b){
long bb=b; long aa=a;
while (aa!=bb)
if (aa<bb){bb=bb-aa;}else{aa=aa-bb;}
return((a*b)/aa);
}
long int nww(long a, long b);
int main(){
int n, t;
cin>>t; long nww2[t];
for(int i=0; i<=t-1; i++){ //liczba testow
 nww2[i]=0;
 cin>>n;
 long int a[n];
 for(int j=0; j<=n-1; j++){cin>>a[j];}//podawanie n liczb
 cout<<endl;
 //obliczanie nww z 2 liczb, cyklicznie
 nww2[i]=a[0];
 for(int k=1; k<=n-1; k++){ nww2[i]=nww(nww2[i],a[k]);}
}
for(int i=0; i<=t-1; i++){cout<<nww2[i]<<endl;}
}
Kod działa tak, jak powinien. Rzecz w tym, że na stronie wyświetla się komunikat "przekroczono limit czasu". Nie wiem już co zrobić, by program liczył szybciej. Próbowałem zmienić typy danych i połączyłem funkcję NWD i NWW w jedną.
Zadanie na SPOJ'u: http://pl.spoj.pl/problems/NWW/
Proszę o pomoc.

[Demonical Monk]

Po co ci ta tablica?

Kod: [Zaznacz]

cin>>t; long nww2[t];Mimo że wydaje się, że jest inaczej to stdin i stdout są dwoma niezależnymi strumieniami. Nie musisz sobie zapisywać wyników - wczytujesz jedną parę liczb, liczysz, wypisujesz wynik na stdout.

Druga sprawa - nie ogarniam twojego algorytmu (namieszałeś), zapewne liczysz znacznie więcej niż potrzeba. Na początek radziłbym użyć metody słupkowej (znanej wszystkim dobrze z podstawówki), jest w miarę efektywna.

Trzecia sprawa - "wynik mieści się w zakresie [1..2^64-1]". Long to tylko 2^32, musisz użyć typu "unsigned long long".

[Dracon]

Po co ci ta tablica?

Ta tablica zapisuje wszystkie wyniki, by wyświetlić je na samym końcu (inaczej się nie da, bo liczone są w zmiennych lokalnych), jak SPOJ przykazał.

Kod: [Zaznacz]

long int nww(long a, long b){
        long bb=b; long aa=a; //tworzy kopie liczb a i b, by obliczyć NWD
        while (aa!=bb) //algorytm Euklidesa (NWD)
         if (aa<bb){bb=bb-aa;}else{aa=aa-bb;} //algorytm Euklidesa (NWD)
        return((a*b)/aa); //zwraca NWW, równe a*b/NWD(a,b)
}
/*potem wywołuję funkcję na pierwszych dwóch liczbach, następnie na NWW poprzednich i trzeciej ... NWW poprzednich i n */
 nww2[i]=a[0]; //pierwsza liczba
 for(int k=1; k<=n-1; k++){ nww2[i]=nww(nww2[i],a[k]);} //pętla


Trzecia sprawa - "wynik mieści się w zakresie [1..2^64-1]". Long to tylko 2^32, musisz użyć typu "unsigned long long".

Hmm... zobaczę. ;)

[Demonical Monk]

Ale po cholerę? Nie musisz wcale wypisywać wyników na koniec, możesz stopniowo po każdym bloku wypisywać wynik.

Kod: [Zaznacz]

cout<<endl;Kolejna głupota - dostaniesz "niepoprawny wynik". Na potrzeby testowania programów polecam zrobić sobie pomocniczy skrypt .bat:

Kod: [Zaznacz]

@echo off
program.exe < input.txt > output.txt
pause
Wtedy program zostanie przetestowany jak na SPOJu, wczyta wejście z pliku input.txt, a zapisze do output.txt.

[Dracon]

Kod: [Zaznacz]

#include<iostream>
using namespace std;
long int nww(unsigned long long int a, unsigned long long int b){
unsigned long long int bb=b; unsigned long long int aa=a;
while (aa!=bb)
if (aa<bb){bb=bb-aa;}else{aa=aa-bb;}
return((a*b)/aa);
}
long int nww(unsigned long long int a, unsigned long long int b);
int main(){
int n, t;
cin>>t; unsigned long long int nww2[t];
for(int i=0; i<=t-1; i++){ //liczba testow
 nww2[i]=0;
 cin>>n;
 unsigned long long int a[n];
 for(int j=0; j<=n-1; j++){cin>>a[j];}//podawanie n liczb
 cout<<endl;
 //obliczanie nww z 2 liczb, cyklicznie
 nww2[i]=a[0];
 for(int k=1; k<=n-1; k++){ nww2[i]=nww(nww2[i],a[k]);}
}
for(int i=0; i<=t-1; i++){cout<<nww2[i]<<endl;}
}
Nie poszło. "Przekroczono limit czasu".

To z tym bat'em zaraz sprawdzę.
//EDIT: Działa jak należy.

[Demonical Monk]

Nic nie poprawiłeś, zmieniłeś tylko typ danych... Użyj innego algorytmu.

[Dracon]

Uważam, że ten http://upload.wikimedia.org/wikipedia/pl/math/2/6/4/2649d8d42e45d97b05f386826e97a6ff.png algorytm jest krótszy i szybszy, niż ten z rozkładem na czynniki pierwsze. Właśnie na ten pierwszy można znaleźć w internecie gotowe, napisane algorytmy (jednak dla dwóch liczb).
Nie mam pojęcia jak to jeszcze uprościć.

[Dracon]

Kod: [Zaznacz]

#include<iostream>
using namespace std;
long int nww(unsigned long long int a, unsigned long long int b){
        unsigned long long int bb=b; unsigned long long int aa=a;
        unsigned long long int c=0;
        while (bb!=0){
          c=aa%bb; aa=bb; bb=c;}
        return((a*b)/aa);
}
long int nww(unsigned long long int a, unsigned long long int b);
int main(){
int n, t;
cin>>t;
for(int i=0; i<=t-1; i++){ //liczba testow
 unsigned long long int nww2=0;
 cin>>n;
 unsigned long long int a[n];
 for(int j=0; j<=n-1; j++){cin>>a[j];}//podawanie n liczb
 //obliczanie nww z 2 liczb, cyklicznie
 nww2=a[0];
 for(int k=1; k<=n-1; k++){ nww2=nww(nww2,a[k]);}
 cout<<nww2<<endl;
}
}
Zrobiłem tak. Na kompie działa, na stronie wywala błędną odpowiedź.
Trochę przerobiłem algorytm (z tego na zasadzie odejmowania, na ten z mod). Chyba szybszy, tak mi się wydaje.

[Demonical Monk]

To przygotuj kilka zestawów testowych i sam przetestuj czy twój program zwraca oczekiwane wyniki, dobrze też jest użyć wyżej wymienionego skryptu albo podobnego, wtedy masz pewność że twój program prawidłowo wypisuje odpowiedzi (bo w konsoli nie zawsze widać, miesza się stdin z stdout).

[Dracon]

Właśnie przetestowałem to tym skryptem. Działa dobrze, tyle, że na komputerze. Na SPOJ'u coś nie śmiga.

[Demonical Monk]

Wystarczająco dużymi liczbami testowałeś?

[Dracon]

input:

3
3
2 3 5
3
6 9 15
4
15 236 3217 1234

(odpowiednio: liczba testów, ilość liczb w teście 1, liczby testu 1, ilość liczb testu 2, liczby testu 2, ilosc liczb testu 3, liczby do testu 3)
output:

30
90
18446744072146124084

(odpowiednio: wynik testu 1, 2 i 3)

//edit:Większe liczby:

4
3
2 3 5
3
6 9 15
4
15 236 3217 1234
5
15421 234126 3213427 1234223 231341

out:

30
90
18446744072146124084
2034996966

Raczej działa...

[Demonical Monk]

2^64-1 = 18446744073709551615

Maksymalna liczba, której może użyć sędzia. Chodziło mi o tego typu wejście, SPOJ ma zwykle dość "porządne" testy.

[Dracon]

Wtedy wychodzi niepoprawna liczba, ale to przecież logiczne - NWW jest zawsze większe (lub równe największej) niż liczb z których jest wyliczane, nie mieści się w zmiennej. Powinno być dobrze.

[Demonical Monk]

Wtedy wychodzi niepoprawna liczba, ale to przecież logiczne - NWW jest zawsze większe (lub równe największej) niż liczb z których jest wyliczane, nie mieści się w zmiennej. Powinno być dobrze.

No to nie ma innej opcji - twój algorytm działa nieprawidłowo. Skomentuj porządnie szczególnie funkcję "nww" bo ten kod za bardzo nic nie mówi.

[Adanos]

Niestety, algorytm masz zły.
lcm(15, 236, 3217, 1234) = 7026507060
lcm(15421, 234126, 3213427, 1234223, 231341) = 473237144062940936529431658

Kod: [Zaznacz]

long int nww(unsigned long long int a, unsigned long long int b){
        unsigned long long int bb=b; unsigned long long int aa=a;
        unsigned long long int c=0;
        while (bb!=0){
          c=aa%bb; aa=bb; bb=c;}
        return((a*b)/aa);
}
Skąd wiesz, że a jest większa od b? Przykład:
15 % 9 =6
9 % 15 = 9

Kod: [Zaznacz]

using namespace std;Nie powinno się tego używać globalnie, tylko jak już co, to lokalnie w funkcji.

Operacja modulo jest chyba kosztowniejsza od odejmowania.

Na razie tyle.

EDYCJA
Tu masz szybszą metodę obliczania NWD: http://en.wikipedia.org/wiki/Binary_GCD_algorithm

Funkcję nww masz typu long int, a argumenty unsigned long long int. Uważasz, że wynik będzie mniejszy od argumentów?

W funkcji main brakuje return 0;.

@niżej, możliwe, nie byłem pewien.

[Demonical Monk]

Operacja modulo jest chyba kosztowniejsza od odejmowania.

Zrobiłem benchmark, widocznej różnicy nie ma. Nawet jeśli, to kosztowność na poziomie nanosekund można sobie odpuścić.

[Dracon]

Kod: [Zaznacz]

#include<iostream>
int nwd(unsigned long long int a, unsigned long long int b){
    if(a == b || a == 0 || b == 0)
        return a|b;
    if(a%2 == 0){
        if(b%2 == 0)
            return (2*nwd(a/2, b/2));
        else
            return  nwd(a/2, b);
    }
    else if(b%2 == 0)
        return nwd(a, b/2);
    else{
        if(a > b)
            return nwd((a-b)/2, b);
        else
            return nwd((b-a)/2, a);
    }
}
long int nww(unsigned long long int a, unsigned long long int b){
        return((a*b)/nwd(a,b));
}
long int nww(unsigned long long int a, unsigned long long int b);
int main(){
using namespace std;
int n, t;
cin>>t;
for(int i=0; i<=t-1; i++){ //liczba testow
 unsigned long long int nww2=0;
 cin>>n;
 unsigned long long int a[n];
 for(int j=0; j<=n-1; j++){cin>>a[j];}//podawanie n liczb
 //obliczanie nww z 2 liczb, cyklicznie
 nww2=a[0];
 for(int k=1; k<=n-1; k++){ nww2=nww(nww2,a[k]);}
 cout<<nww2<<endl;
}
}
Zastosowałem ten algorytm, nie działa.

//edit:

Funkcję nww masz typu long int, a argumenty unsigned long long int.

Powieście mnie, przeoczyłem...

[Adanos]

Co znaczy nie działa? Zwraca takie same wyniki?

[Dracon]

Kod: [Zaznacz]

#include<iostream>
unsigned long long int nwd(unsigned long long int a, unsigned long long int b){
    if(a == b || a == 0 || b == 0)
        return a|b;
    if(a%2 == 0){
        if(b%2 == 0)
            return (2*nwd(a/2, b/2));
        else
            return  nwd(a/2, b);
    }
    else if(b%2 == 0)
        return nwd(a, b/2);
    else{
        if(a > b)
            return nwd((a-b)/2, b);
        else
            return nwd((b-a)/2, a);
    }
}
unsigned long long int nww(unsigned long long int a, unsigned long long int b){
        return((a*b)/nwd(a,b));
}
unsigned long long int nww(unsigned long long int a, unsigned long long int b);
int main(){
using namespace std;
int n, t;
cin>>t;
for(int i=0; i<=t-1; i++){ //liczba testow
 unsigned long long int nww2=0;
 cin>>n;
 unsigned long long int a[n];
 for(int j=0; j<=n-1; j++){cin>>a[j];}//podawanie n liczb
 //obliczanie nww z 2 liczb, cyklicznie
 nww2=a[0];
 for(int k=1; k<=n-1; k++){ nww2=nww(nww2,a[k]);}
 cout<<nww2<<endl;
}
return 0;
}Teraz poprawiłem. Też nie działa (czyli SPOJ nie przyjmuje). Wyniki w testach na komputerze co prawda inne:

(input)
4
3
2 3 5
3
6 9 15
4
15 236 3217 1234
5
15421 234126 3213427 1234223 18446744073709551615

(output)
30
90
7026507060
1962680376499006638