Ubuntu.pl 🇺🇦️ - Forum Ubuntu

#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?

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

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 :/

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

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.

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.

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ć.

@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.

@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.

beluosus pisze:@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.

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

norvoles pisze:
beluosus pisze: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>.

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ęć.

Ubuntu.pl 🇺🇦️ - Forum Ubuntu

C++ Dzielniki liczby zoptymalizowanie algorytmu.

C++ Dzielniki liczby zoptymalizowanie algorytmu.

Re: C++ Dzielniki liczby zoptymalizowanie algorytmu.

Re: C++ Dzielniki liczby zoptymalizowanie algorytmu.

Re: C++ Dzielniki liczby zoptymalizowanie algorytmu.

Re: C++ Dzielniki liczby zoptymalizowanie algorytmu.

Re: C++ Dzielniki liczby zoptymalizowanie algorytmu.

Re: C++ Dzielniki liczby zoptymalizowanie algorytmu.

Re: C++ Dzielniki liczby zoptymalizowanie algorytmu.

Re: C++ Dzielniki liczby zoptymalizowanie algorytmu.

Re: C++ Dzielniki liczby zoptymalizowanie algorytmu.

Re: C++ Dzielniki liczby zoptymalizowanie algorytmu.

Re: C++ Dzielniki liczby zoptymalizowanie algorytmu.

Re: C++ Dzielniki liczby zoptymalizowanie algorytmu.