Znaleziono 148 wyników

autor: paladin
13 maja 2011, o 11:21
Forum: Informatyka
Temat: maszyna turinga-mnozenie liczb binarnych
Odpowiedzi: 1
Odsłony: 2283

maszyna turinga-mnozenie liczb binarnych

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 ...
autor: paladin
12 maja 2011, o 18:58
Forum: Informatyka
Temat: Algorytm Dijkstry jako algorytm zachlanny
Odpowiedzi: 5
Odsłony: 1065

Algorytm Dijkstry jako algorytm zachlanny

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...
autor: paladin
12 maja 2011, o 18:21
Forum: Informatyka
Temat: Algorytm Dijkstry jako algorytm zachlanny
Odpowiedzi: 5
Odsłony: 1065

Algorytm Dijkstry jako algorytm zachlanny

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.
autor: paladin
12 maja 2011, o 17:41
Forum: Informatyka
Temat: Algorytm Dijkstry jako algorytm zachlanny
Odpowiedzi: 5
Odsłony: 1065

Algorytm Dijkstry jako algorytm zachlanny

Na pewno mowa o algorytmie Dijkstry? Ten, który przedstawiłeś, to algorytm Kruskala...
autor: paladin
29 kwie 2011, o 00:24
Forum: Informatyka
Temat: sortowanie szybkie java
Odpowiedzi: 3
Odsłony: 1012

sortowanie szybkie java

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

Kod: Zaznacz cały

if (left < j) ;
if (i < right);
autor: paladin
29 kwie 2011, o 00:20
Forum: Zadania "z treścią"
Temat: ile osłów żyje w wiosce?
Odpowiedzi: 5
Odsłony: 375

ile osłów żyje w wiosce?

Na pewno tylko tyle?
autor: paladin
15 kwie 2011, o 12:28
Forum: Polska Olimpiada Matematyczna
Temat: LXII OM - finał
Odpowiedzi: 91
Odsłony: 19092

LXII OM - finał

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...
autor: paladin
14 kwie 2011, o 23:59
Forum: Polska Olimpiada Matematyczna
Temat: LXII OM - finał
Odpowiedzi: 91
Odsłony: 19092

LXII OM - finał

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
autor: paladin
14 kwie 2011, o 22:36
Forum: Polska Olimpiada Matematyczna
Temat: LXII OM - finał
Odpowiedzi: 91
Odsłony: 19092

LXII OM - finał

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...
autor: paladin
14 kwie 2011, o 16:03
Forum: Polska Olimpiada Matematyczna
Temat: LXII OM - finał
Odpowiedzi: 91
Odsłony: 19092

LXII OM - finał

Chyba nie rozumiem treści zadania 1. Brakuje mi przynajmniej jednego kwantyfikatora.
autor: paladin
2 sty 2011, o 11:50
Forum: Informatyka
Temat: B drzewa
Odpowiedzi: 3
Odsłony: 1156

B drzewa

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.
autor: paladin
1 sty 2011, o 22:40
Forum: Informatyka
Temat: suma dwóch zbiorów w postaci drzewa BST
Odpowiedzi: 1
Odsłony: 515

suma dwóch zbiorów w postaci drzewa BST

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 ...
autor: paladin
1 sty 2011, o 22:36
Forum: Informatyka
Temat: B drzewa
Odpowiedzi: 3
Odsłony: 1156

B 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: zaczynasz od korzenia (M) i wiesz, że ...
autor: paladin
24 paź 2010, o 00:17
Forum: Informatyka
Temat: Algorytm dla ciągu
Odpowiedzi: 4
Odsłony: 498

Algorytm dla ciągu

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.
autor: paladin
16 wrz 2010, o 17:13
Forum: Informatyka
Temat: Złożoność algorytmu rozwiązującego problem wież w Hanoi
Odpowiedzi: 4
Odsłony: 1665

Złożoność algorytmu rozwiązującego problem wież w Hanoi

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)}\).