Algorytmy i struktury danych

[brava]

Witam

Potrzebuje pomocy gdyż na mojej uczelni koleś wogóle nie tłumaczy a reszta załogi tez nie wie jak sie do tego zabrać. Zrobiłem jedno zadanko z 2 ale i tak się doczepił koleś i kazał mi zrobic jeszcze kilka rzeczy w tym zadaniu. Ponizej wkleje 2 zadania i opis co trzeba zrobić. Jak ktoś potrafi to zrobić to będę wdzięczny jestem też w stanie coś tam odpalić komuś jeśli mi to dokładnie opisze co skad sie bierze jakby to zrobił moje gg to 2121345 jakby ktoś chciał o coś mnie zapytac. Byłoby fajnie gdyby ktoś to co robi umiał opisać tak jak ja to zrobiłem w 1 zadaniu bo po 1 bede wiedział co skąd się wzięło by to zrozumieć a po 2 koleś w takiej formie wymaga. Z góry dzięki. Gdyby do środy wieczór udało się to zrobić byłbym podwójnie wdzieczny


Zad1. Minimalizacja maksymalnej sumy.
Mamy na wejściu ciąg 2n liczb rzeczywistych dodatnich. Na wyjściu powinien pojawić się ciąg n par utworzonych z tych liczb o tej własności, że maksymalna suma spośród sum każdej pary liczb jest możliwie najmniejsza. Na przykład, dla ciągu (1,3,5,9) możliwymi parowaniami są: ((1,3), (5,9)), ((1,5),(3,9)) oraz ((1,9),(3,5)). Odpowiednimi sumami są: (4,14), (6,12) oraz (10,Cool, a zatem trzecie parowanie – dla którego maksymalna suma wynosi 10 – spełnia warunki zadania

Dla opisanego problemu zaprojektuj algorytm działający w czasie )(nlogn)

Rozwiązanie moje
1. Dla problemu opisanego w treści zadania należy zaprojektować algorytm działający w czasie O(nlogn). Celem działania algorytmu jest wypisanie par liczb ze zbioru o własności, takiej że maksymalna suma spośród sum każdej pary liczb jest możliwie najmniejsza.
Najprostszym rozwiązaniem tego problemu w zadanym czasie jest, najpierw posortowanie zadanego ciągu w sposób rosnący, a następnie sumowanie kolejno liczb: pierwsza i ostatnia, druga i przedostatnia i itd. Algorytm rozwiązujący zadanie w przedstawiony sposób znajduje się w punkcie 2.

2 Algorytm:

public void suma(int[] tabLiczb) {
int n = tabLiczb.length - 1;
quicksort (tabLiczb, 0, n);

for (int i = 0; i < tabLiczb.length/2; i++) {
System.out.println("Sumy: " +
"( " + tabLiczb + ", " + tabLiczb[n-i] +
") = " + (tabLiczb + tabLiczb[n-i]));
}
}

Opis działania algorytmu:

Do procedury przekazywana jest nieposortowana tablica zwierająca liczby rzeczywiste dodatnie. Następnie jest ona sortowana przy pomocy algorytmu quicksort o złożoności obliczeniowej O(nlogn). Następnie elementy posortowanej tablicy są sumowane w następujący sposób: pierwszy element z ostatnim, drugi z przedostatnim, itd. Dla tablicy o wielkości n, pętla for wykonuje się n/2 razy.
Całkowita złożoności algorytmu wynosi: nlogn + n/2, czyli O(nlogn), ponieważ O-notacja uwzględnia tylko element o największej złożoności obliczeniowej.


!!!Do tego co już zrobiłem kazał mi obliczyć złożoność obliczeniową, podać rozmiar danych wejściowych, rozmiar elementów w tablicy i odpowiedzieć czy ilość operacji w tablicy będzie stała czy zmienna

Zad 2. Mnożenie rekurencyjne
Poniższy algorytm wyznacza yz, gdzie y,z należy do N.

Algorytm
Mnóż(y,z)
1. If z=0
2. Then return 0
3. Else if add(z)
4. Then return Mnóż(2*y, [z/2])+y
5. Else return Mnóż(2*y, [z/2])

Jaka jest złożoność obliczeniowa?

tutaj wogóle nie wiem jak sie zabrac za to

[sathan]

Polecam:

Kenneth Ross, Charles Wright, Matematyka Dyskretna, Pwn 2006

Dla bardziej zaawansowanych informatyków:

R. Graham, D. Knuth, O. Patashnik, Matematyka Konkretna, Pwn 2006.

Profesjonalny wykład, przykłady, ćwiczenia z rozwiązaniami, niebanalne problemy.