[C++] Program - liczy NWD danych liczb


(enedil) #1

Witam :slight_smile:

Mam taki program:

#include 


using namespace std;


int nwd(int a,int b);

int najwieksza = 0;


int main()

{

int liczbaLiczb;

cin >> liczbaLiczb;

int *liczby = new int [liczbaLiczb];

for (int i = 0; i < liczbaLiczb; i++)

{

    cin >> liczby[i];

}

for (int i = 0; i < liczbaLiczb; i++)

{

    for (int j = 0; j < liczbaLiczb; i++)

    {

        if (i == j)

        {

            continue;

        }

        if (nwd(i, j) > najwieksza)

        {

            najwieksza = nwd(i, j);

        }

    }

}

cout << najwieksza;




}


int nwd(int a,int b) {


    int c; //tworzymy zmienn─ů c o typie int

    while(b!=0) //tworzymy p─Ötl─Ö dzia┼éaj─ůc─ů gdy b Ôëá 0

    {


        c=a%b; //zmienna c przyjmuje warto┼Ť─ç a modulo b

        a=b; //przypisujemy b do a

        b=c; //przypisujemy c do b


    }

    return a; //zwracamy a, czyli ┼╝─ůdane NWD(a,b)


}

Z za┼éo┼╝enia ma on wylicza─ç wszystkie mo┼╝liwe NWD dla danych liczb, a potem wy┼Ťwietli─ç najwi─Öksze NWD. Niestety po uruchomieniu i wpisaniu danych program co┼Ť mieli i nic nie wypisuje. Kto┼Ť wie na czym polega b┼é─ůd?


([alex]) #2

for (int j = 0 ; j < liczbaLiczb; i++ )


(kostek135) #3

Generalnie mo┼╝esz to troch─Ö z optymalizowa─ç, bo wykonujesz nie potrzebne operacje. Wykorzystaj NWD(a,b) = NWD(b,a).


(enedil) #4

@[alex] Dzięki, poprawione. Teraz już nie sprawdza gdy i > j. Musiałbym go jeszcze zoptymalizować.


([alex]) #5

Nie licz nwd(i,j) dwa razy:

if (nwd(i, j) > najwieksza)

            najwieksza = nwd(i, j);

(enedil) #6

To ju┼╝ zrobi┼éem. Teraz program wygl─ůda tak:

#include 


using namespace std;


int nwd(int a, int b);

int najwieksza = 0;


int main()

{

	int liczbaLiczb;

	cin >> liczbaLiczb;

	int *liczby = new int[liczbaLiczb];

	for (int i = 0; i < liczbaLiczb; i++)

	{

		cin >> liczby[i];

	}

	for (int i = 0; i < liczbaLiczb; i++)

	{

		for (int j = 0; j < liczbaLiczb; j++)

		{

			if (i >= j)

			{

				continue;

			}

			else if (nwd(liczby[i], liczby[j]) > najwieksza)

			{

				najwieksza = nwd(liczby[i], liczby[j]);

			}

		}

	}

	cout << najwieksza;

}


int nwd(int a, int b) {


	int c; //tworzymy zmienn─ů c o typie int

	while (b != 0) //tworzymy p─Ötl─Ö dzia┼éaj─ůc─ů gdy b Ôëá 0

	{


		c = a%b; //zmienna c przyjmuje warto┼Ť─ç a modulo b

		a = b; //przypisujemy b do a

		b = c; //przypisujemy c do b


	}

	return a; //zwracamy a, czyli ┼╝─ůdane NWD(a,b)

}

([alex]) #7

Nadal marnujesz czas na continue oraz nadal obliczasz nwd w dw├│ch miejscach.


(kostek135) #8

Generalnie problem jest do┼Ť─ç ciekawy. +1 za danie mi nad czym my┼Ťle─ç. P├│ki co ucinamy sta┼ée. Zacz─ů┼éem si─Ö zastanawia─ç, czy dla tego problemu mo┼╝na zej┼Ť─ç ni┼╝ej je┼Ťli chodzi o z┼éo┼╝ono┼Ť─ç asymptotyczn─ů do np. O(nlogn) albo O(n), przy wykorzystaniu np. dodatkowej pami─Öci. Wyniki moich rozwa┼╝a┼ä nie s─ů do ko┼äca jednoznaczne, ale podziel─Ö si─Ö nimi. O(n^2) to dobrze znany bruteforce, wi─Öc chcieliby┼Ťmy co nieco to ulepszy─ç. U┼╝ytkownik enedil nie poda┼é zakres├│w dla jakich algorytm ma by─ç poprawny, dlatego rozwa┼╝y┼éem sam kilka klas abstrakcji w kt├│re b─Ödzie on m├│g┼é wpada─ç. Przyjmijmy na ten moment, ┼╝e n jest liczb─ů liczb, dla kt├│rych mamy odnale┼║─ç NWD, a v oznacz maksymaln─ů warto┼Ť─ç jak─ů mo┼╝e posiada─ç pojedyncza liczba.

Nale┼╝y zauwa┼╝y─ç, ┼╝e algorytm brutalny w takim uj─Öciu b─Ödzie mia┼é z┼éo┼╝ono┼Ť─ç O(n^2 * log(v)), poniewa┼╝ policzenie NWD jest tak┼╝e pewnym, niesta┼éym kosztem. Ten koszt mo┼╝emy te┼╝ g├│rnie oszacowa─ç. Mo┼╝na dowie┼Ť─ç, ┼╝e algorytm Euklidesa wykona najwi─Öcej krok├│w dla 2 kolejnych liczb Fibonacciego, a co wi─Öcej wygenerowana liczba b─Ödzie liczb─ů poprzedni─ů w tym ci─ůgu. Przyk┼éadowo rozwa┼╝my

a = 34, b = 21

1. a=21 b=13

2. a=13 b=8

3. a=8 b=5

4. a=5 b=3

5. b=3 a=2

6. a=2 b=1

7. a=1 b=0

Koniec

Innymi s┼éowy koszt ten b─Ödzie r├│s┼é odwrotnie proporcjonalnie do wzrostu wyk┼éadniczego. Funkcj─ů odwrotn─ů do funkcji wyk┼éadniczej jest logarytm. Przyjmijmy te┼╝, ┼╝e log oznacz logarytm o podstawie 2. Teraz nasze dane podzielmy na 3 klasy abstrakcji 1. n = 10^9, v=10^6 czyli du┼╝e n i ma┼ée v Tu nasz algorytm naiwny zamrozi komputer na do┼Ť─ç d┼éugo szacunkowo b─Ödzie to (10^9)^2 * log(10^6) = 10^19 operacji 2. n=10^6, v=10^9 odwrotnie Tu b─Ödzie to oko┼éo 3 * 10^13, co te┼╝ nie mo┼╝na powiedzie─ç, by by┼éo ma┼éo 3. n=10^6, v=10^6 i ÔÇťma┼éeÔÇŁ dane Poniewa┼╝ v przez logarytm ma taki ma┼éy wp┼éyw i tu otrzymamy ca┼ékiem sporo, 10^13 Pierwszy pomys┼é w oparciu o dodatkow─ů pami─Ö─ç (du┼╝o pami─Öci) b─Ödzie dzia┼éa┼é tylko w przypadku ma┼éego v (v=10^6) i b─Ödzie polega┼é na faktoryzacji liczb pierwszych. Pierwsze co wykonamy, to algorytm sita, na liczbach 1-v. Jest ich tylko 10^6, wi─Öc nie powinno zaj─ůc to du┼╝o czasu bior─ůc pod uwag─Ö, ┼╝e uci─ů─ç szukanie mo┼╝emy na pewnym k = sqrt(v). Wykonanie sita zajmie nam vlog(v). Dla zainteresowanych jak dowie┼Ť─ç poprawno┼Ťci przesiewania z uci─Öciem na sqrt(v) i z┼éo┼╝ono┼Ťci link. Jedyn─ů r├│┼╝nic─ů jak─ů uzyskamy w stosunku do standardowego sita, jest to, ┼╝e tablica ta nie b─Ödzie zawiera─ç binarnej odpowiedzi na pytanie czy indeks jest/nie jest liczb─ů pierwsz─ů, ale najmniejsz─ů liczb─Ö pierwsz─ů przez kt├│r─ů ten indeks jest podzielny, dla 1 mo┼╝emy wybra─ç cokolwiek, bo nie jest interesuj─ůca z punktu widzenia rozk┼éadu. Przyk┼éadowy fragment tablicy

index = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

value = 0 2 3 2 5 2 7 2 3 2 11 2 13 2 3

Zauważmy, że teraz faktoryzacja liczby [1-v] jest bajecznie prosta, wystarczy, że wykonamy dzielenie index/a[index] w pętli tk długo jak spełniony jest warunek index != 1. A po drodze spamiętamy wszystkie a[index]. Przykładowo dla 12:

i = 12, a[i] = 2, i/a[i] = 6 (zapami─Ötaj 2)

i = 6, a[i] = 2, i/a[i] = 3 (zapami─Öaj 2)

i = 3, a[i]= 3, i/a[i] = 1 (zapami─Ötaj 3)

i = 1 (koniec)

Nasz rozk┼éad to 2*2*3. Z┼éo┼╝ono┼Ť─ç takiego wyszukania liczby zale┼╝y od ilo┼Ťci czynnik├│w, a poniewa┼╝ tych czynnik├│w mo┼╝e by─ç co najwy┼╝ej logarytmicznie wiele, to czas rozk┼éadu jednej liczby (maj─ůc wcze┼Ťniej wyliczon─ů tablic─Ö) wynosi O(log(v)) Okej, tylko co to nam daje? W sumie nic. Musimy zauwa┼╝y─ç jeszcze jeden fakt, co najlepiej zrobi─ç na podstaw├│wkowym wyja┼Ťnieniu NWD (z przecinaj─ůcymi si─Ö zbiorami). Stw├│rzmy jeszcze jedn─ů tablice o rozmiarze v. Od tej pory zastosujemy co┼Ť podobnego do counting-sort. Dla ka┼╝dego i wyliczonego powy┼╝ej b─Ödziemy zwi─Öksza─ç licznik pod indeksem i o 1. przyk┼éadowo, dla 12, nasza tablica wygl─ůda┼éaby nast─Öpuj─ůco:

index=1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

count=1 0 1 0 0 1 0 0 0 0 0 1 0 0 0

Teraz dodajmy do tego zbioru jeszcze troch─Ö liczb np. 4, 7, 13, 8, 9, 15, 10. Po przeprowadzeniu ich rozk┼éadu, i uaktualnieniu tablicy, wynik powinien by─ç nast─Öpuj─ůcy

index=1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

count=8 2 2 2 2 1 1 1 1 1 0 1 1 0 1

I teraz nasz max NWD, to pierwsza od prawej pozycja, kt├│ra jest wi─Öksza od 1. Tylko dlaczego to dzia┼éa? Na dobr─ů spraw─Ö po prostu zapami─Ötujemy wszystkie liczby generowane przez podzbiory zbioru przeci─Ö─ç, st─ůd nawi─ůzanie do zbior├│w z podstaw├│wki. Warto te┼╝ zauwa┼╝y─ç, ┼╝e w tym momencie stracili┼Ťmy informacj─Ö, kt├│re dwie liczby generuj─ů ten maks NWD, oczywi┼Ťcie liniowym przebiegiem, mo┼╝emy j─ů odzyska─ç, ale to nie jest celem zadania. Maks zosta┼é wyznaczony.

Jaka jest z┼éo┼╝ono┼Ť─ç naszego rozwi─ůzania?

  1. Generowanie tablicy czynnik├│w sitem: O(v*log(v))

  2. Wykonanie rozk┼éadu O(log(v)) i zwi─Ökszanie licznika O(1), przy czym robimy to n razy O(n*log(v)) (bo tyle jest liczb na wej┼Ťciu)

Czyli ca┼éo┼Ť─ç uzyska┼éo z┼éo┼╝ono┼Ť─ç O((n+v)*log(v))

Co przy założeniu, że v=10^6, w obu przypadkach daje lepsze wyniki.

Dla pierwszego b─Ödzie to co┼Ť oko┼éo: 10^10

Dla trzeciego: 2 * 10^7

Warto te┼╝ wzi─ů─ç poprawk─Ö, na to, ┼╝e tablic─Ö liczb do rozk┼éadu, mo┼╝emy precomputowa─ç. Co nie zmienia za bardzo asymptotycznie rozwi─ůzania, ale mo┼╝e zmniejszy─ç widocznie czas dzia┼éania.

Niestety tego algorytmu nie zastosujemy przy danych rz─Ödu drugiego v=10^9, poniewa┼╝ alokacja O(v) pami─Öci b─Ödzie niemo┼╝liwa. Pomys┼é na ulepszenie tego algorytmu przedstawi─Ö potem (edytuj─Ö post), bo teraz nie mam czasuÔÇŽ

Disclaimer: Rozwa┼╝anie mog─ů zawiera─ç jaki┼Ť b┼é─ůd (ka┼╝dy jest omylny), wi─Öc zapraszam do dyskusji =).


(enedil) #9

Ok, chyba zrozumia┼éem (we┼║ poprawk─Ö na m├│j wiek - 16 lat :slight_smile: ). Mam ograniczenie: wed┼éug Twoich oznacze┼ä n <= 1 * 10 ^ 5, v <= 1 * 10 ^ 6. Spr├│buj─Ö to jako┼Ť zaimplementowa─ç. BTW nie spodziewa┼éem si─Ö po tym zadaniu takiego poziomu abstrakcji :wink: