Dana jest grupa osób (o liczności n). Należy podzielić ta grupę na dwie podgrupy jednakowo liczne, ale takie by różnica wieku (chodzi o sumę wieku wszystkich osób z danej grupy) pomiędzy grupami była możliwie największa. Algorytm wyznaczenia rozwiązania:
budujemy wszystkie możliwe podziały, obliczmy różnicę wieku pomiędzy podgrupami i wybieramy parę o największej różnicy.
Wypisz dane dla wyznaczonego n.
Jaki jest koszt (liczymy dodawania i porównania) algorytmu dla przykładowych danych n osób?
W tym zadaniu przyjmijmy następujące dane:
n=11
Wiek osoby o numerze i oznaczony W(i) (i = 1,2,…,n) wyznaczony jest według wzoru
W(i) = (3*n) mod (i+10) + 5
Zaproponuj algorytm, który działałby szybciej i oszacuj jego koszt.
algorytm sortowania
-
- Użytkownik
- Posty: 12
- Rejestracja: 13 mar 2009, o 19:22
- Płeć: Kobieta
- Pomógł: 3 razy
-
- Użytkownik
- Posty: 374
- Rejestracja: 21 cze 2007, o 11:28
- Płeć: Mężczyzna
- Lokalizacja: Łostowice
- Pomógł: 146 razy
algorytm sortowania
Algorytm, który działałby szybciej to posortowanie uczniów ze względu na wiek i podział w połowie na uczniów młodszych i starszych.wiolcia4444 pisze:Zaproponuj algorytm, który działałby szybciej i oszacuj jego koszt.
Koszt algorytmu sprowadza się do kosztu danej metody sortowania.
- kwak2k
- Użytkownik
- Posty: 24
- Rejestracja: 13 paź 2008, o 09:56
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 6 razy
algorytm sortowania
hm jak mamy grupe 11 osob, to jak mozemy podzielic tą grupę na dwie jednakowo liczne (nie wliczając w to działania piły łańcuchowej)
a tak na zdrowy rozsądek to sortujemy grupe ludzi, potrzebujemy najwiekszej różnicy, zatem grupa a musi dawać max, grupa b musi dawać min. , czyli dzielimy jak to kolega napisal powyzej na pół posortowaną grupę od najwiekszej do najmniejszej i tyle. Oczywiscie zakladajac ze jest to grupa parzysta
a tak na zdrowy rozsądek to sortujemy grupe ludzi, potrzebujemy najwiekszej różnicy, zatem grupa a musi dawać max, grupa b musi dawać min. , czyli dzielimy jak to kolega napisal powyzej na pół posortowaną grupę od najwiekszej do najmniejszej i tyle. Oczywiscie zakladajac ze jest to grupa parzysta