Matematyka.pl

Koncepcyjnie najprostsze wydaje mi się zrobienie tego na trzech taśmach: na pierwszej masz pierwszą z mnożonych liczb, na drugą taśmę przepisujesz drugą, na trzeciej będzie wynik. Dobrze jest myśleć o liczbach jak o zapisanych w odwrotnej kolejności: od najmniej znaczących do najbardziej znaczących ...

To niedobrze. Twierdzenie Rado-Edmondsa stosuje się tylko do niektórych algorytmów zachłannych (np. Kruskala), algorytm Dijkstry pod to twierdzenie nie podpada (a przynajmniej ja nie znam i nie widzę związku). W ogóle ciężko mówić o jakiejś ogólnej definicji algorytmów zachłannych - to raczej termin...

Ja nie o to pytam. Pytam, który algorytm jest tematem pracy. Dijkstry (najkrótsze ścieżki w grafie z jednym źródłem), czy Kruskala (minimalne drzewo rozpinające)? Kod, który napisałeś, oraz zastosowanie matroidów wskazują na Kruskala.
Z drugiej strony, uparcie piszesz o Dijkstrze.

Na pewno mowa o algorytmie Dijkstry? Ten, który przedstawiłeś, to algorytm Kruskala...

Hm, a te dwie instrukcje to co miały robić?

Na pewno tylko tyle?

Raczej chodzi mi o to, że zadania geometryczne mogą być praktycznie jedynym czynnikiem różnicującym kolejność miejsc. Nie żebym miał coś przeciwko geometrii, ale wypadałoby, żeby coś oprócz niej też miało znaczenie Tak sie zlozylo, ze to wlasnie zadania niegeometryczne glownie beda rozstrzygac o ko...

Raczej chodzi mi o to, że zadania geometryczne mogą być praktycznie jedynym czynnikiem różnicującym kolejność miejsc.
Nie żebym miał coś przeciwko geometrii, ale wypadałoby, żeby coś oprócz niej też miało znaczenie

No, to czyni zadanie 1 również łatwiutkim. Cała suma musi się dzielić przez n , a to oznacza, że n jest nieparzyste. Pomińmy oczywisty przypadek n=1 , niech zatem n = 2k+1 . Cała suma bez ostatniego wyrazu to (k+1)(2k+1) - a_n , i to musi dawać resztę 0 modulo 2k . Stąd a_n = k+1 . Obliczając tak sa...

Chyba nie rozumiem treści zadania 1. Brakuje mi przynajmniej jednego kwantyfikatora.

Moim zdaniem jest to M. Nie wiem, jak by musiała wyglądać definicja, żeby było inaczej, i raczej byłaby mało sensowna.

Algorytm liniowy, za to z dużą dodatkową pamięcią: 1. Oba drzewa zamieniasz na posortowane tablice (czyli wypisujesz w porządku inorder) 2. Tablice scalasz w jedną posortowaną tablicę. 3. Z wynikowej tablicy tworzysz nowe drzewo. Algorytm bez dodatkowej pamięci, za to z gorszą złożonością: Z drzewa ...

Zależy, co rozumiesz przez "poprzednik". Zwykle "poprzednik N" oznacza "największy klucz mniejszy niż N". To, co jest pamiętane w drzewie, a także czy da się takiego poprzednika łatwo znaleźć, nie ma dla definicji znaczenia. A szukać go trzeba trochę sprytniej: zaczynas...

Dla uporządkowanego ciągu można zrobić to w czasie liniowym. Ustawić jeden wskaźnik na początek, drugi na koniec, i dopóki się nie spotkają, przesuwać jeden z nich - dolny jeśli iloczyn jest za mały, górny jeśli za duży.

Nie bardzo wiem, jak sformułowane jest twierdzenie, o które chodzi, ale podejrzewam taką interpretację: jeśli można dobrać taki wykładnik \(\displaystyle{ \epsilon > 0}\), dla którego \(\displaystyle{ d(n) = O( \frac{a^n}{n^ \epsilon })}\) to złożoność wynosi \(\displaystyle{ \theta(a^n)}\).