Skocz do zawartości


Close Open
Close Open

Ufosinio

Dołączył: 25 Jul 2006
Offline Ostatnio aktywny: Jan 17 2010 23:31 PM
*----

Moje posty

W temacie:[Pascal] Droga w Dijkstry

17 January 2010 - 23:19 PM

http://www.algorytm....c...1&Itemid=28

W temacie:Jednocyfrowa suma cyfr [cpp]

12 December 2009 - 18:04 PM

Chyba tak to powinno wygladac o ile sie nie walnolem nigdzie.
int sum(int a) {
 int licz=0;
 int d=1;
 while(a/d != 0) {
  licz+=(a/d)%10;  
  d*=10;		 
 } 
 if(licz/10==0) return licz;
 return sum(licz);  
}

W temacie:ciekawy algorytm

26 October 2009 - 23:13 PM

W przypadku gdy mam dane d to sytuacja jest łatwa (w którymś z OI było takie zadanie ale nie znany był bok d).
Niech S(i,j,u,w) to będzie suma elementów z prostokąta [i,j]x[u,w]. Widać, że wynik dla kwadratu o boku d zaczynającego się
w punkcje (i,j) to S(i,j,i+d,j+d).
Zauważ ,że S(i+1,j,i+1+d,j+d)=S(i,j,i+d,j+d) - S(i,j,i+1,j) + S(i+d,j,i+d+1,j);
Jeśli nie pomyliłem literek, ogólnie chodzi o to ,żę gdy mam policzony kwadrat [a,b]x[a+d,b+d] to wynik dla tego obok niego z prawej strony to będzie wynik dla tego minus ten pasek który zostawiamy ale plus pasek który dołączamy..
Narysuj sobie jakiś kwadrat np. [1,2]x[1+d,2+d] a potem [2,2]x[2+d,2+d] i zobacz tę zależność.
Wynik algorytmu to max(S(i,j,i+d,j+d)).
Kwestia jak szybko liczyć te paski które dodajemy/usuwamy przesuwając się, można użyć drzewa przedziałowego dla każdej kolumny
albo szybciej dla każdej kolumny wyznaczyć pref(i) i suf(i), niech pref(i)=suma pierwszych i elementów tej kolumny a suf(i) sumę i ostatnich elementów to S(i,j,i+1,j) = Cała suma kolumny - pref(j-1) - suf(j+1+d);
Oczywiście musisz wyznaczyć pref(i) i suf(i) dla każdej kolumny.
Jeśli dobrze wszystko zaimplementujesz to może działać w czasie O(nm) i takiej też pamięci.
Ja pokazałem oczywiście tylko przesuwanie w poziomie ale to same musisz zrobić dla pionu.

W temacie:Porownywanie tablic

20 October 2009 - 22:19 PM

raczej nie.

W temacie:Potrzebuje pomocy - generowanie permutacji w C

02 July 2009 - 00:01 AM

To go napisz...w czym problem?