C++ Dzielniki liczby zoptymalizowanie algorytmu.

[MAnonim93]

Kod: Zaznacz cały

#include<cstdio>

int main()
{
	int n;
	scanf("%d", &n);
	
	printf("%d\n",1);
	int koniec=n/2;
	for(int a=2; a<=koniec; a++)
	{	
		if(n%a==0)
		printf("%d\n",a);
	}
	if(n!=1)
	printf("%d\n",n);
	return 0;
}

Powyższy algorytm nie daje optymalnego rozwiązania a tylko 95% Tak jakby były liczby dla których nie wypisuje on wszystkich dzielników zgodnie z tym zadaniem: http://main.edu.pl/pl/user.phtml?op=sho ... ie&con=PAS Wie ktoś może dlaczego?

[dejmien666]

Nie wiem jak sprawdzić zajętość megabajtową pamięci takiego klocka ale coś takiego mam:

Kod: Zaznacz cały

#include <cstdlib>
#include <iostream>

int main()
{
	int liczba = 0;
	std::cout << "Podaj liczbe ";
	std::cin >> liczba;
	std::cout << std::endl << "Dzielniki liczby " << liczba << " to:" << std::endl << std::endl;

	for(int i = 1; i <= liczba; i++)
	{
		if(liczba%i == 0)
		{
			std::cout << i << std::endl;
		}
	}

	std::cin.ignore();
	std::cin.get();

	return 0;
}

Wierząc systemowi to dla dość dużych cyfr 120 KB pamięci zajmuje licząc. Raczej liczy ok...

Wg stronki:

D13560 = {1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 113, 120, 226, 339, 452, 565, 678, 904, 1130, 1356, 1695, 2260, 2712, 3390, 4520, 6780, 13560}

Wg programu:

Dzielniki liczby 13560 to:

1
2
3
4
5
6
8
10
12
15
20
24
30
40
60
113
120
226
339
452
565
678
904
1130
1356
1695
2260
2712
3390
4520
6780
13560

[MAnonim93]

Niestety twój program niczym się nie różni od mojego z wyjątkiem tego że wykonuje drugi tyle porównań. Dla liczby maksymalnej czyli 10^9 to twój wykona 50000000 więcej porównań. A nie ma przecież potrzeby sprawdzania tego. Bo chyba żadna liczba nie ma dzielników powyżej swojej połowy. np 24 - {1,2,3,4,6,8,12} i wszystkie mieszczą się w przedziale <2;24/2>? I nie mam pojęcia co tutaj jest nieprawidłowego :/

[bogaczew]

wg treści zadania w zbiorze odpowiedzi powinna być też liczba krótej dzielników szukasz. 24 jest podzielne przez 24.

[dejmien666]

Wg mnie Twój kod jest ok...

Jedyne czego można się przyczepić to nie zerowanie wartości zmiennych na początku - to dobry nawyk, chociaż tu nie jest potrzebny.
Drugie to że jak podasz nieparzystą liczbę to c++ zaokrągla w dół... to może wpłynąć na jakieś tam zakłamanie wyniku...

@up
Dodaje tą liczbę w ostatniej instrukcji warunkowej.

[MAnonim93]

Nie teraz bardziej to przeanalizowałem i wynika z tego że program ma kłopot z testem gdzie jest liczba 999999937, bo zajmuje mu to aż 6sec na 10 maksymalnie, i myślę że to tutaj tracę ptk. Ale nie wiem jak można to zrobić niezbyt skomplikowanie a żeby to udoskonalić. Jedyne co przychodzi mi do głowy to jakies sprawdzanie czy liczba nie jest pierwsza najpierw przez petlę for z pierwiastkiem. Czyli for(int a=2; a*a<liczba; a++) ponieważ to chyba sporo wydajniejsze jest. Bo inne testy daj rezultaty w blisko 0-1 sec a tylko przy tej liczbie jest 6sec, a ta liczba właśnie pierwsza jest.

Nadawanie zmiennym wartości 0 przy deklaracji to chyba dobry nawyk ale np. w PHP gdzie typy zmiennych są traktowane elastycznie, a w C++ to chyba nie ma różnicy (jeżeli oczywiście algorytm tego nie wymaga ) no chyba że się mylę? Pozdro.

[norvoles]

Osobiście stwierdzam, że Wasze algorytmy do rzyci są Oba są cholernie wolne.
Dlaczego? Bo bez sensu liczycie w pętli dzielniki od 1 do liczba, jak wystarczy liczyć tylko do pierwiastka z podanej liczby. Przy liczbach rzędu kilku milionów program liczy dzielniki tysiące razy szybciej

Mój kod jest taki:

Kod: Zaznacz cały

#include <iostream>
#include <cmath>
#include <list>

int main (int argc, char const* argv[])
{
	unsigned int liczba = 0;
	std::list<unsigned int> dzielniki(0);
	
	std::cout << "Podaj liczbę: ";
	std::cin >> liczba;
	
	//dzielniki 1 i liczba są oczywiste
	dzielniki.push_back(1);
	dzielniki.push_back(liczba);
	
	//liczymy od dwóch do pierwiastka włącznie
	for(int i = 2; i <= sqrt(liczba); ++i){
		if(liczba%i==0){
			//dodajemy do listy dzielnik
			dzielniki.push_back(i);
			//oraz drugi dzielnik - mamy dwa dzielniki w jednej pętli
			dzielniki.push_back(liczba/i);
		}
	}
	
	//sortujemy - dla estetyki
	dzielniki.sort();
	
	//wyświetlamy
	std::list<unsigned int>::iterator it = dzielniki.begin();
	for(it; it != dzielniki.end(); ++it)
		std::cout << *it << "\n";
		
	return 0;
}

Listy oczywiście nie trzeba używać, można wyświetlać dzielniki w parach od razu w pętli. To nie jest oczywiście najszybsza możliwość, bo da się to jeszcze przyspieszyć.

[beluosus]

@norvoles: jedna uwaga, sprawdź liczby 10^2n, czyli 100, 10000... i na liście zwróć uwagę na pierwiastek tej liczby, czyli dla 100 popatrz na 10. W ostatniej pętli pierwszy argument powinien być pusty.

[MAnonim93]

@norvoles twój algorytm dla liczby np 100 wyznaczy wartości : 1, {2, 4, 5, 10}, 100. A czy czasem nie zapomniałeś o 20, 25, 50 bo moim zdanie tak. Pętle for(int a=2; a*a<=liczba; a++) można wykorzystać do szukania liczb pierwszych. Niestety przy dzielnikach liczb całkowitych się nie sprawdzi. Bo liczba całkowita może mieć dzielniki większe od jej pierwiastka.

[norvoles]

@norvoles: jedna uwaga, sprawdź liczby 10^2n, czyli 100, 10000... i na liście zwróć uwagę na pierwiastek tej liczby, czyli dla 100 popatrz na 10. W ostatniej pętli pierwszy argument powinien być pusty.

Racja, nie zauważyłem tego, ale da się to łatwo rozwiązać dodając po posortowaniu listy linijkę:

Kod: Zaznacz cały

dzielniki.unique();

która usuwa z listy powtarzające się elementy.

[MAnonim93]

A sorki nie zauważyłem dzielenia czyli dodania drugiego dzielnika a więc wszystko jasne dzięki. Pozdro.

[beluosus]

Racja, nie zauważyłem tego, ale da się to łatwo rozwiązać dodając po posortowaniu listy linijkę:

Kod: Zaznacz cały

dzielniki.unique();

Tak - łatwo, ale lepiej zastosować się do "standardowego" algorytmu:

Kod: Zaznacz cały

         int lim = liczba/i;
         if (lim != i)
            dzielniki.push_back(lim);

I zamiast tego sorta można np. wyświetlać "i", a "liczba/i" dodawać do listy i wyświetlić na końcu w odwrotnej kolejności (od end() do begin()) - chyba będzie ciut szybciej.

Kod: Zaznacz cały

			 std::cout << i << "\n";
			 int lim = liczba/i;
			 if (lim != i)
				dzielniki.push_back(lim);

No i poza tym oczywiście użycie <cstdio> jest szybszym rozwiązaniem niż <iostream>.

[Razi]

Rozwiązanie z przechowywaniem dzielników jest bardzo kosztowne dla liczb będących silniami.
Można to też rozwiązać optymalnie dla pamięci i skorzystać z tego prawa że żadna liczba nie ma dzielnika większego niż jej połowa.
Ale można to rozwinąć jeszcze bardziej: jeśli l%2==0, to też l%(l/2)==0. Można od razu dodać se te 2 dzielniki do listy, wektora i potem posortować, ale jak wspomniałem to dużo pamięci kosztuje. przy dużych liczbach będących silniami.

Jeżeli l%2!=0, to też l%(l/2)!=0, ani dla liczb > l/2. Podstawmy za 2 jakąś zmienną, np a i znajdźmy pierwszy dzielnik. Leżeli liczba nie jest podzielna przez 2, 3 i 5 (w tej części można iść po liczbach pierwszych, jeżeli liczba nie jest podzielna przez 2, to też nie jest podzielna przez 4, 6 itd.), to też nie będzie miała dzielników większych niż l%(l/5).

Mając najmniejsze a, gdzie l%a==0, szukamy dzielników od a do l/a (włącznie).

W tym zadaniu taki algorytm również otrzymuje 100 pkt.

Tyle że nie opłaca się tworzyć tablicy liczb pierwszych w zadaniu, gdzie wypisywane są liczby pierwsze tylko jednej liczby. Trzeba by albo statycznie taką tablicę zrobić, żeby się opłacało, ale to zaś pamięć.