Zadanie dla programisty

[piwosz]

Pary zawsze kolo siebie?

 

 

 

Nie, lista może być dowolnie wymieszana

[Rafek00]

Czytam to już trzeci raz i chyba nadal nie bardzo rozumiem jaka jest myśl przewodnia tego tematu

Nie martw się, ja też stwierdziłem, że nic nie ogarniam z tego tematu

[Faszysta Rasista Homofob]

Nie wiem czy chcesz zadania rodem z przedszkola programistycznego czy coś z algorytmiki,

W tablicy w bazie danych za pomocą SQL bez używania wyrażeń regularnych itp. ....

Nie jest to zbyt trudne, ale ze znajomych mi osób tylko dwie wiedziały jak to zrobić szybko i prosto, a reszta kombinowała jak koń pod górę.

Edytowane 22 Lutego 2014 przez jake

[FurioSan]

Z SQL takim dość nie trywialnym i popularnym jest usuwanie dublikatow z tabel bez pk

[jaras]

Mając listę N liczb wiemy o nich, że wszystkie liczby na liście występują dwukrotnie oprócz jednej. (...) Dla danej listy znajdź jedną liczbę niepasującą. Nic nie zakładaj o przedziale liczbowym. Rozwiąż to zadanie w czasie liniowym i pamięci stałej(!). Wszystkie chwyty dozwolone.

W tablicy w bazie danych za pomocą SQL bez używania wyrażeń regularnych itp. ....

Nie jest to zbyt trudne, ale ze znajomych mi osób tylko dwie wiedziały jak to zrobić szybko i prosto, a reszta kombinowała jak koń pod górę.

Aż jestem szczerze zaciekawiony tym stałopamięciowym rozwiązaniem.

[FurioSan]

No ja tez jeszcze poniżej n/2 +1 przy liniowym czasie nie mam. Przy nie liniowym np nlogn + n to kłopot znika

 

 

 

A co do regexp w bazie danych to różnie z ich wsparciem

[Faszysta Rasista Homofob]

ale np. takie, jak znaleźć w tablicy rekordy, które zawierają tylko litery.

Nie wiem czy chcesz zadania rodem z przedszkola programistycznego czy coś z algorytmiki, ale tutaj masz jedno:

Mając listę N liczb wiemy o nich, że wszystkie liczby na liście występują dwukrotnie oprócz jednej. Czyli lista wygląda na przykład tak:

12 12 10 10 13 15 15

Liczba która jest tutaj sama to 13.

Dla danej listy znajdź jedną liczbę niepasującą. Nic nie zakładaj o przedziale liczbowym.

Rozwiąż to zadanie w czasie liniowym i pamięci stałej(!). Wszystkie chwyty dozwolone.

Strzelam: XOR?

[piwosz]

Strzelam: XOR?

 

 

 

Tak,

prosta własność

X xor X = 0

0 xor X = X

 

Więc po z'Xorowaniu wszystkich liczb zostaje ta bez pary

[FurioSan]

ok, zle przeczytałem. zadziała

Edytowane 22 Lutego 2014 przez FurioSan

[jaras]

Więc po z'Xorowaniu wszystkich liczb zostaje ta bez pary

Pozostaje XORowanie pesymistycznego przypadku przy zachowaniu zadelkarowanych złożoności. Mi wychodzi obliczeniowa jakoś ((n-2 + 1) / 2) * (n/2).

Edytowane 22 Lutego 2014 przez jaras

[FurioSan]

Jaras nie

 

>>> def find(l):

... a = None

... for itm in l:

... if a is None:

... a = itm

... else:

... a^=itm

... return a

 

nie alokujesz na każdy element - masz 'jedna' zmienna tymczasową.

a przejechac po całej tablicy i tak musisz ( raz )

[jaras]

Ja wiem, że chodzi o znalezienie tego jednego a nie wyeliminowanie pozostałych. Co więcej - wiem że Twój algorytm działa, niemniej jednak siedzę i walę łbem o ścianę próbując zrozumieć jak dla przykładowego ciągu:

 

1, 2, ...n-1, n-1, ..., 2, 1, n

 

i jednej zmiennej tymczasowej jesteś w stanie stwierdzić, po minięciu n-tego wyrazu ciągu, czy aktualnie odwiedzany element wystąpił już wcześniej. Tak czysto teoretycznie...

Edytowane 22 Lutego 2014 przez jaras

[FurioSan]

Nie jesteś!

musisz przeczytać cały ciąg.

i to tu jest trick.

 

dwa przykłady

 

ciągi

1,2,1

 

zapis binarny

01,10,01

xory

01xor10 = 11

11xor01 = 10

 

w innej

10,01,01

10xor01 = 11

11xor01 = 10

 

 

teraz dziedzina niech bedzie zbior 3 elementowy

a nasz ciag to

01,10,11,01,11

01xor10 = 11

11xor11 = 00

00xor01 = 01

01xor11 = 10

 

 

Ale dlaczego to rozwiazanie jest złe - to czekam na odpowiedz (bo ja juz wiem)

 

 

PS

Nic nie zakładaj o przedziale liczbowym.

Edytowane 22 Lutego 2014 przez elroy

[jaras]

ok - poprintowalim i zrozumielim

[piwosz]

Sposób prosty, warto zrozumieć co się dzieje na pojedyńczych bitach po operacji XOR

[FurioSan]

Piwosz.

A co powie ci XOR dla ciągu.

1,1.1,1

 

 

Skoro niczego nie zakładamy apropos przedziału z liczbami(poza tym ze są liczbami)

[piwosz]

Wybaczcie za nieporozumienie.

Chodziło mi o to, że liczby nie są podane na przykład z przedziału [0;100] czy [0;1000000]. O liczbach rzeczywistych w kontekście zadanek programistycznych zazwyczaj nie myślę, bo są one nie pełnie reprezentowane w komputerze, czyli 1.23456789 może być tak samo odebrane przez komputer jak 1.23456788 itp... ;-) Podsumowując, chodziło o liczby całkowite.