unbearable0 Temat założony przez niniejszego użytkownika |
Zadanie SPOJ - NWD Chochlik ? » 2017-02-16 18:15:02 Witam ! Rozwiązuje zadanie : http://pl.spoj.com/problems/PP0501A/ W skrócie polega na wyznaczeniu Największego Wspólnego Dzielnika dwóch liczb. Pomysł na algorytm, który wykorzystałem opierał się na rozbiciu tych dwóch liczb na czynniki pierwsze wpisanie tych czynników do tabeli od najmniejszego do największego i wyznaczeniu części wspólnej tych dwóch tabeli. Tabela ograniczona jest do 12 kolumn ponieważ liczby na których się pracuje w tym zadaniu maksymalnie mogą przyjąć wartość 1 mln czyli w postaci 12 liczb: [2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5]. Te działania zawarte są w funkcji nwd(int a,int b) która wykonuje się t razy wartośc t jest podana na początku przez użytkownika: SPOJ uważa jednak, że program zwraca nie poprawna odpowiedz tylko gdzie siedzi ten chochlik ? Czy ktoś z Was ma jakiś pomysł ? Maksymalny czas programu to 1 sekunda. Mój wykonuje się 0.4 Max Pamieć 1536MB moj program około 16MB. #include<iostream>
#include<cstdlib>
using namespace std;
int decay_a( int a, int b[] )
{
int k = 2;
int i = 0;
while( a > 1 )
{
while( a % k == 0 )
{
b[ i ] = k;
a /= k;
i++;
}
k++;
}
}
int nwd( int one, int two )
{
int NWD = 1;
int decay_one[ 12 ] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
int decay_two[ 12 ] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
decay_a( one, decay_one );
decay_a( two, decay_two );
for( int i = 0; i < 12; i++ )
{
for( int b = 0; b < 12; b++ )
{
if( decay_one[ i ] == 0 && decay_two[ b ] == 0 )
{
break;
}
if( decay_one[ i ] == decay_two[ b ] )
{
NWD *= decay_one[ i ];
decay_two[ b ] = 0;
break;
}
}
}
cout << NWD << endl;
}
int main()
{
int one, two, t = 0;
cin >> t;
for( int i = 0; i < t; i++ )
{
cin >> one >> two;
nwd( one, two );
}
return 0;
}
|
|
michal11 |
» 2017-02-16 18:21:34 A jest jakiś powód dla którego nie możesz użyć tego algorytmu int nwd( int a, int b )
{
int c;
while( b != 0 )
{
c = a % b;
a = b;
b = c;
}
return a;
}
z https://pl.wikipedia.org/wiki/Algorytm_Euklidesa ? I popraw link do zadania bo teraz prowadzi od razu w wysłania rozwiązania a nie do treści, chyba że jest jakiś sposób żeby wrócić do treści ale ja tego nigdzie tam nie widzę. |
|
unbearable0 Temat założony przez niniejszego użytkownika |
Odpowiedz » 2017-02-16 18:29:26 Oczywiście jest i to tylko jeden powód: To nie jest rozwiązanie, które wymyśliłem. Wiem, że jest pełno rozwiązań tego typu w internecie, i faktycznie zwracają ten sam wynik co metoda wykorzystana w tym kodzie - rozbicie na czynniki pierwsze. Ale są to jakieś gotowe rozwiązania, które 90% ludzi przepisuje tylko po to, żeby mieć ptaszka przy kolejnym zadaniu..
No i z jakiegoś powodu tamte rozwiązania są akceptowane przez SPOJ a moje nie :D
Dziękuje poprawiłem link :) |
|
michal11 |
» 2017-02-16 18:39:33 Być może w jakimś przypadku "wychodzisz" poza twój zakres tablicy i mnożysz przez 0? Spróbuj zainicjować tablicę jedynkami i sprawdź co z tego wyjdzie. |
|
unbearable0 Temat założony przez niniejszego użytkownika |
Odpowiedz » 2017-02-16 21:48:46 Niestety to nie to :( |
|
Avengens |
» 2017-02-16 21:59:34 0 <= a,b <= 1000000
Przy wpisaniu 1 1 0 twój kod zwraca 1. |
|
Nazgul |
» 2017-02-17 01:08:18 Nie do końca rozumiem w czym jest problem.
Z tego co sprawdzam, to twój program działa poprawnie, ten przykład ze stronki co podałeś, również rozwiązuje identycznie;)
//EDIT
Nie, jednak coś wyszło. przerobiłem ten kod w taki sposób, żeby obliczał sobie to nwd dla kombinacji liczb od 0 do 10000
i się okazało że dla wartości one=1, two=8192 program się wysypuje, nie rozumiem tylko czemu wysypuje się dopiero przy wyjściu z funkcji nwd.
Pewnie to destruktor tablicy, czy coś w tym stylu, w każdym razie problem niejasny, ale chodzi o przepełnienie tablicy decay_two.
8192|2
4094|2
2048|2
1024|2
512|2
256|2
128|2
64|2
32|2
16|2
8|2
4|2
2|2
1
to jest 13 dzielników, nie 12;D
"1 mln czyli w postaci 12 liczb: [2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5]" <- to jest błędem.
już bardziej prawidłowe jest podejście z drugiej strony
1|
2|2 1
4|2 2
8|2 3
16|2 4
32|2 5
64|2 6
128|2 7
256|2 8
512|2 9
1024|2 10
2048|2 11
4096|2 12
8192|2 13
16384|2 14
32768|2 15
65536|2 16
131072|2 17
262144|2 18
524288|2 19
1048576|2 <----20!
czyli żeby bezpiecznie móc operować na liczbach < 1000000 to powinniśmy te tablice rozszerzyć do liczby dzielników 1048576, bo dopiero to nam wyczerpuje maksymalną liczbę dzielników (dla liczb <= 1048576) czyli, zmodyfikuj swój kod tak, żeby te tablice "decay_one" i "decay_two", żeby miały rozmiar 19(dopiero 1048576 potrzebuje 20, a my tego nie potrzebujemy:) ) , a nie 12(jak ustawisz 12, to możesz operować bezpiecznie tylko na liczbach < 8192)
Żeby ci pokazać jeszcze wyraźniej błąd w myśleniu, to jakbyśmy założyli, że algorytm ma być dla liczb < 15485857(zamiast 1000000) i byśmy mieli określić na podstawie tej liczby rozmiar naszych tablic potrzebnych na rozkład na czynniki.. to by nam wyszło że rozmiar tych tablic = 1 (sic!)!!!!!!!
15485857 po rozkładzie na czynniki to po prostu [15485857]
(Liczba 15485857 jest liczbą pierwszą, ma tylko dwa dzielniki.. 1 i samą siebie)
|
|
unbearable0 Temat założony przez niniejszego użytkownika |
» 2017-02-17 10:14:47 Racja! Racja !
Wracam do domu i zobaczę czy SPOJ przymie po poprawkach czy będzie już żarł za dużo pamięci :)
Modyfikacja wielkości sprawiła, że spoj akceptuje kod |
|
| « 1 » 2 |