Zabawy algorytmiczne i programowanie

[Maklak2]

Przenoszę to z wątku o spotkaniach w Warszawie, żeby nie robić spamu. 

 

Na początek ciekawostka, która niszczy system (czyli powinno się spodobać Chemikowi): 

https://www.destroyallsoftware.com/talks/wat 

 

---

 

Na ostatnim spotkaniu ktoś coś mówił o rekurencji w trójkącie pascala. Spróbuj tak: 

/* row - row number, starting from 1, pos - position in a row, starting from 1 */
unsigned long long pascal(int row, int pos)
{
  if ((row < 1) || (pos <1) || (row < pos)) { return 0ul; }

  if ((pos == 1) || (pos == row)) { return 1ul; }

  return pascal(row-1, pos-1) + pascal(row-1, pos);
}

Problem w tym, że czas wykonania tej funkcji będzie posnął wykładniczo i dlatego to nie jest dobre rozwiązanie tego problemu. Hm, może powinienem na to założyć osobny wątek. 

 

Odpowiedź: Dziękuję, że piszesz. To ja pytałem o ten Trójkąt Pascala (w realu nazywam się Witek - jestem jedną z nielicznych osób, które były w sobotę u Arpegiusa i to ja męczyłem Ciebie wtedy na meecie w Lisopadzie). Problem polega na tym, że kod ma być w Pythonie lub Logo, a nie w C++. 

 

Moja odpowiedź: Po pierwsze napisałem, że to jest tak naprawdę źle, bo za długo będzie liczyć, wielokrotnie wykonując pascal() dla tych samych argumentów. Lepsze rozwiązanie wykorzystuje tablicę trójkątną do memoizacji. Przy czym nawet tego nie kompilowałem, więc pewnie gdzieś jest błąd. Aha i to nie jest odporne na wątki, do tego memory musiałoby być parametrem funkcji pascal_rec. 

unsigned long long *memory = NULL;  // For memoization. 
 
static unsigned long long pascal_rec(int row, int pos); // Recursive helper function 
 
/* row - row number, starting from 1, pos - position in a row, starting from 1 */

unsigned long long pascal(int row, int pos)
{
  if ((row < 1) || (pos <1) || (row < pos)) { return 0ul; } // Stupid values 

  if ((pos == 1) || (pos == row)) { return 1ul; } // Trivial problem 
 
  /* An even better solution would be to keep memory, resize it with realloc and fill as needed, but let's keep it simple and stupid. */ 
  memory = calloc(((row-1)*(row-2))/2, sizeof(unsigned long long)); 
  if (memory == NULL) { return 0; } 

  unsigned long long ret = pascal_rec(row-1, pos-1) + pascal_rec(row-1, pos);
  free(memory);
  memory = NULL; 
  return ret; 
}
 
static inline ind(int row, int pos)  // Compute index in memory 
{
  return (row*(row-1)/2) + (pos-1);
} 
 
static unsigned long long pascal_rec(int row, int pos)
{  
   if (memory[ind(row,pos)] != 0)   // Advantage of memoization - cutting off recursive calls on the same arguments as in the past. 
   {  return memory[ind(row,pos)]; 
   } 
   
   if ((pos == 1) || (pos == row))   // Trivial problem 
   { memory[ind(row,pos)] = 1ul;
   } else
   { memory[ind(row,pos)] = pascal_rec(row-1, pos-1) + pascal_rec(row-1, pos);   // Use recursion, but store intermediate results in memory 
   }
 
   return memory[ind(row,pos)]; 
} 

Ugh, ale ten edytor tekstu jest toporny. 

A na inne języki programowania to sam sobie przetłumacz. Tutaj jest tylko idea. 

 

---

 

 

To teraz problem ode mnie: 

 

Mamy tablicę n-1 elementową z unikatowymi wartościami od 0 do n-1 (albo jak kto woli od 1 do n). To znaczy że są w niej wszystkie liczby z podanego zakresu, za wyjątkiem jednej. Znajdź tę brakującą liczbę. 

 

[cAnon]

Ciekawe.

Swego czasu szukałem takiego wątku, jednak wtedy go nie było.

Teraz jest, ale nie pamiętam, po co go szukałem.

Ale dobrze, że jest.

 

Może kiedyś nam się zbierze na jakiś wspólny projekcik.

 

 

P.s.:

 

czas wykonania tej funkcji będzie posnął wykładniczo 

rósł*

[Ravin]

To teraz problem ode mnie: 

 

Mamy tablicę n-1 elementową z unikatowymi wartościami od 0 do n-1 (albo jak kto woli od 1 do n). To znaczy że są w niej wszystkie liczby z podanego zakresu, za wyjątkiem jednej. Znajdź tę brakującą liczbę. 

 

Tak na szybko wymyślone:

Liczysz sumę wszystkich liczb w tablicy, a następnie obliczasz różnicę pomiędzy tym co wyszło a sumą n wyrazów ciągu arytmetycznego a0=0, r=1 ((0+n-1)/2*n)

Złożoność O(n).

[Maklak2]

Szybkie i eleganckie rozwiązanie, zakładając że n jest na tyle małe, żeby w tym sumowaniu nie wystąpił błąd. Ja wymyśliłem tylko sortowanie (O(n*log(n))), zliczanie (O(n) pamięci) i pewną metodę zbliżoną do sortowania, ale o O(n) i nie zachowującą lokalności odwołań. To Twoje jest najlepsze o ile n <= sqrt((sizeof(typeof(n))). 

 

EDIT: Ups, tak chodziło o pow(2, sqrt(8*sizeof(typeof(n)))) Generalnie o to, że np dla 32 bitowych intów problemy z artihmethic overflow zaczną się jakoś powyżej 2^16. W każdym razie jestem pod wrażeniem. Także tego pomysłu z xorowaniem wszystkiego. 

Edytowano Grudzień 16, 2013 przez Maklak2

[Ravin]

Szybkie i eleganckie rozwiązanie, zakładając że n jest na tyle małe, żeby w tym sumowaniu nie wystąpił błąd. Ja wymyśliłem tylko sortowanie (O(n*log(n))), zliczanie (O(n) pamięci) i pewną metodę zbliżoną do sortowania, ale o O(n) i nie zachowującą lokalności odwołań. To Twoje jest najlepsze o ile n <= sqrt((sizeof(typeof(n))). 

Chciałeś chyba napisać coś w stylu maxvalue(typeof(n)) - sizeof zwraca długość typu w bitach, a nie maksymalną wartość, no ale pewnie się czepiam

Co do długości to łatwo napisać program dodający liczby o praktycznie dowolnej długości (w szczególności w asemblerze x86 można to zrobić bardzo wydajnie - kawałek liczby o długości jednego słowa procesora na jedną instrukcję dodawania ADC )

Inne rozwiązanie jest policzyć wcześniej xora wszystkich liczb (0 - n-1) i później zxorować z liczbami z tablicy. Będzie wolniej, ale bez problemu z rozmiarem typu.

Na sortowanie też wpadłem, ale uznałem, że na pewno jest coś prostszego.

[Arpegius]

Niebędę komentował Maklaka. TL;DR 
 

Chciałeś chyba napisać coś w stylu maxvalue(typeof(n)) - sizeof zwraca długość typu w bitach, a nie maksymalną wartość, no ale pewnie się czepiam

Czyli o std::numeric_limits<typeof(n)>::max()
 

Co do długości to łatwo napisać program dodający liczby o praktycznie dowolnej długości (w szczególności w asemblerze x86 można to zrobić bardzo wydajnie - kawałek liczby o długości jednego słowa procesora na jedną instrukcję dodawania ADC )

Wydajnie? ROTFL
Niestety procesory nie mają magicznej możliwości wektoryzowania takich instrukcji. Zresztą poco wymyślać koło na nowo jak są takie biblioteki jak np GMP, albo języki które już to obsługują (Python).
 
W zadaniu pewnie chodziło o zrozumienie rekurencji no ale mówiłem że kod wyświetlający trójkąt Pascala łatwiej zrobić pętlą, np. w Pythonie:
 

x

=[1]
for i in range(input("Podaj ilosc lini:")):
     print x
     x=map(sum,zip([0]+x,x+[0]))

Jeżeli chodzi o wyliczanie wartości to też robienie tego rekurencją jest kiepskim pomysłem, lepiej go przekształcić w wzór iteracyjny:

def symbol_newtona(n, k):
    r = 1
    for i in range(1, k+1):
        r = r * (n-i+1) / i
    return r

---

Roziwązanie problemu maklaka w pythonie jak by ktoś się tym zainteresował:

import random

n=input("n=")

tablica = random.sample(range(n),n-1)

def rozwiazanie_najkrotsze(t):
    return list(set(range(len(t)+1))-set(t))[0]

def rozwiazanie_szybsze(t):
    wyk=[False]*(len(t)+1)
    for x in t:
        wyk[x]=True
    return wyk.index(False)

print tablica
print rozwiazanie_najkrotsze(tablica)
print rozwiazanie_szybsze(tablica)

Edytowano Grudzień 17, 2013 przez Arpegius

[Maklak2]

> Czyli o std::numeric_limits<typeof(n)>::max() 

A tak właściwie to o sqrt(2.0* std::numeric_limits<typeof(n)>::max()), co wynika z tego że suma kolejnych liczb jest bliska połowie kwadratu największej liczby. 

 

Trochę się wygłupiłem z tym trójkątem pascala. Wszystko jest na wikipedii. http://pl.wikipedia.org/wiki/Tr%C3%B3jk%C4%85t_Pascala Włącznie z tym, żeby używać symbolu Newtona a nie rekurencji (przynajmniej jeśli się chce tylko jedną liczbę). Jedyna komplikacja z symbolem Newtona jest taka, że trzeba to albo robić na doublach albo jakoś sprytnie mnożyć i dzielić, żeby nie było arithmethic overflow. 

 

Coś mi się zdaje, że xorowanie wszystkich liczb od 0 do n da się zrobić jakoś sprytnie. Zauważyłem że po pierwsze cyfry dwójkowe w tym xorze powtarzają się okresowo a po drugie że dla 3, 7, 15 i zapewne też dalej, ten xor się zeruje. 

[Arpegius]

Coś mi się zdaje, że xorowanie wszystkich liczb od 0 do n da się zrobić jakoś sprytnie. Zauważyłem że po pierwsze cyfry dwójkowe w tym xorze powtarzają się okresowo a po drugie że dla 3, 7, 15 i zapewne też dalej, ten xor się zeruje.

No jasne że się da ;-F jak sobie wypiszesz odpowiednio dużo to się natychmiast zorientujesz, bez wyliczania tego na kartce ;-D

W sumie ten patent z xorem niezły jest:

def rozwiazanie_najszybsze(t):

    n=len(t)+1

    return reduce(int.__xor__,t,0)^[0,n^1,1,n][n&3]

Edytowano Grudzień 17, 2013 przez Arpegius

[Maklak2]

Arpegius, jak mówisz do mnie w Pythonie to Cię nie rozumiem. 

 

> Pora się go chyba w końcu nauczyć bo Python strasznie popularny ostatnio. 

Tylko ten brak { } w Pythonie mnie dobija. 

 

Tak z innej beczki, znalazłem niezłego bloga, ale jest w dużej mierze o programowaniu urządzeń wbudowanych: http://blog.feabhas.com/

Edytowano Grudzień 17, 2013 przez Maklak2

[Ravin]

Arpegius, jak mówisz do mnie w Pythonie to Cię nie rozumiem.

Ja tak samo   Pora się go chyba w końcu nauczyć bo Python strasznie popularny ostatnio...

 

Wydajnie? ROTFL

Niestety procesory nie mają magicznej możliwości wektoryzowania takich instrukcji.

 

Może równolegle dodawać przez jednostki wektorowe się nie da, ale zwyczajnie zsumować parę długich liczb można bardzo prosto. Gorzej z mnożeniem np

Edytowano Grudzień 17, 2013 przez Ravin

[wprzybylkowski]

Arpegius, jak mówisz do mnie w Pythonie to Cię nie rozumiem. 

 

> Pora się go chyba w końcu nauczyć bo Python strasznie popularny ostatnio. 

Tylko ten brak { } w Pythonie mnie dobija. 

 

Tak z innej beczki, znalazłem niezłego bloga, ale jest w dużej mierze o programowaniu urządzeń wbudowanych: http://blog.feabhas.com/

Nie martw się, jest od tego darmowy podręcznik (http://pl.wikibooks.org/wiki/Zanurkuj_w_Pythonie). Znajomość tego języka jest wymagana w konkursie LOGIA (http://logia.oeiizk.waw.pl/). Przeszedłem do drugiego etapu i w ramach przygotowań rozwiązuję zadania z poprzednich edycji tego konkursu, stąd wzięło się zadanie o Trójkącie Pascala. Jeśli chcesz znać dokładniej jego treść, wejdź tutaj: http://logia.oeiizk.waw.pl/nowa/page.php?sr=logia13/2etap

[Ravin]

Nie martw się, jest od tego darmowy podręcznik (http://pl.wikibooks.org/wiki/Zanurkuj_w_Pythonie). Znajomość tego języka jest wymagana w konkursie LOGIA (http://logia.oeiizk.waw.pl/).

Od kiedy Python jest wymagany w Logii, a nie Logo/Logomocja? Albo ja nie rozumiem Twojej wypowiedzi albo od czasu gdy byłem laureatem dużo się zmieniło :o

[Arpegius]

Ja tak samo   Pora się go chyba w końcu nauczyć bo Python strasznie popularny ostatnio...

Ahaha, ok tak naprawdę to specjalnie tworze takie jednolijkowce żeby was trochę potrolować, ale faktycznie w pythonie dużo i często się korzysta z takich ficzerów, tylko kod się rozbija na wiele linijek. Dla osób które nie miały styczności z zasadą działania  właściwie to matematycznie można by rzec funktorów reduce i map, oraz funkcji zip i range  to taki kod będzie wyjątkowo magiczny i nieczytelny, to samo się tyczy wyjątkowo pythonowego mnożenia listy lub ciągu znaków przez liczbę.

A tak apropo jak chcecie się uczyć pythona to najlepiej od razu Pythona3 (przykłady dawałem w Pythonie2), niewiele się różni, ale lepiej mieć dobre nawyki, no i mniej problemów, przykładowo z kodowaniem znaków.

Pythona świetnie się używa w konsoli, ale nie polecam korzystania z surowej albo graficznej IDLE, bo jest strasznie toporna. Polecam skorzystać z IPythona, jest wersja graficzna (qtconsole) oraz webowa przez przeglądarkę (notebook).

Edytowano Grudzień 18, 2013 przez Arpegius

[wprzybylkowski]

Od kiedy Python jest wymagany w Logii, a nie Logo/Logomocja? Albo ja nie rozumiem Twojej wypowiedzi albo od czasu gdy byłem laureatem dużo się zmieniło :o

Tak było kiedyś, a teraz wymagana jest znajomość obu języków.

[Khornel]

Tak było kiedyś, a teraz wymagana jest znajomość obu języków.

Według regulaminu (może go źle zrozumiałem) jest napisane, że mamy wybór pomiędzy Logo, a Pythonem.

[wprzybylkowski]

Według regulaminu (może go źle zrozumiałem) jest napisane, że mamy wybór pomiędzy Logo, a Pythonem.

Masz rację, ale w dziale "literatura" na stronie logia.oeiizk.waw.pl jest napisane, że musisz przeczytać "Zanurkuj w Pythonie".

[Arpegius]

Jeżeli chodzi o różne algorytmiczne zagadki to kiedyś pamiętam bawiłem się na http://pl.spoj.com/ (na angielskiej jest więcej) teraz tam jest ogromna baza zadań, jak znajdziecie jakieś ciekawe to możemy porozwiązywać.

Na uwagę zasługują zadnia optymalizacyjne (challenge), gdzie nie trzeba dać konkretnego wyniku, a dowolny poprawny który jest potem oceniany.

Edytowano Grudzień 18, 2013 przez Arpegius

[Mon]

o, nie wiedziałem, że tu jest taki temat. Z ciekawości, ktoś w OI startuje w tym roku?

[Camed]

Łojej. Python. To ni C#, ni VB, ale tak z ciekawości zacznę pisać rozwiązania w VB, chyba że ten temat typowo pythonowy. Ją tam znam w nim tylko funkcję "print" i nic więcej c:

Łojej. Python. To ni C#, ni VB, ale tak z ciekawości zacznę pisać rozwiązania w VB, chyba że ten temat typowo pythonowy. Ją tam znam w nim tylko funkcję "print" i nic więcej c:

[Arpegius]

Łojej. Python. To ni C#, ni VB, ale tak z ciekawości zacznę pisać rozwiązania w VB, chyba że ten temat typowo pythonowy. Ją tam znam w nim tylko funkcję "print" i nic więcej c:

VB? BASIC? A co to niby jest? Nawet LUA i Pascal wyglądają lepiej, a i JavaScript jest bardziej przyjazny (a jest w ogóle nieprzyjazny). Nie wiem skąd się biorę jeszcze tak młodzi ludzie piszący w tak niepopularnych i prehistorycznych składiowo językach   ( to już zalatuje flejmem )

Oczywiście że możesz. Tylko proszę o umieszczaniu kodu w Spoilerach bo nie każdy ma ochotę ich czytać.

(Z tego że maklak rozpoczął pisanie w C, nie oznacza że to wątek dedykowany do C. Ani z tego że zrobiłem offtop o nauce Pythona.)

[Camed]

Visual Basic jest bardzo przyjazny ;-; Moje pierwsze próby ogarniała Pythona zakończyły się klęską, a VB samo weszło. Przynajmniej zgadzamy się co do JS, który WCALE nie jest przyjazny :broohof:

Acha. I VB jest popularny, a nawet bardzo popularny, od kiedy Microsh*t wprowadził go do Visual Studio czyli 2008 rok. I język jest cały czas rozwijany

Edytowano Grudzień 19, 2013 przez Camed

[Arpegius]

Visual Basic jest bardzo przyjazny ;-; Moje pierwsze próby ogarniała Pythona zakończyły się klęską, a VB samo weszło. Przynajmniej zgadzamy się co do JS, który WCALE nie jest przyjazny :broohof:

Acha. I VB jest popularny, a nawet bardzo popularny, od kiedy Microsh*t wprowadził go do Visual Studio czyli 2008 rok. I język jest cały czas rozwijany

Co?   Przyjazny?  Ty chyba nigdy nie widziałeś bardziej zaawansowanego kodu. Po za tym to całe .NET daje złudne przenośności na inne platformy, a tak naprawdę Mono nie działa.

Poza tym jak można polec w nauce Pythona

 

[Maklak2]

Wątek jest generalnie na dyskusję o programowaniu, językach programowania, linki do artykułów o programowaniu, rozwiązywanie problemów algorytmicznych (jak ktoś chce) i inne tego typu rzeczy. Pisałem w C bo przychodzi mi to najbardziej naturalnie. Spoilery to jak kto lubi, ja tam wolę tagi code. 

 

VB pozwala dosyć łatwo pisać GUI. Jest też VBA wbudowane w Offica, w którym można robić dziwne rzeczy w Excellu. 

 

> Poza tym jak można polec w nauce Pythona. 

Zobaczyłem brak nawiasów klamrowych i uznałem to za tak kretyński pomysł, że poległem na zasadzie "jak to wino kosztowało więcej niż 10 zeta za butelkę, to nie piję". Później wróciłem do Perla i na niego narzekam  

 

A tak w ogóle to siła języka programowania nie leży w składni, ale w bibliotece standardowej i różnych powszechni dostępnych rozszerzeniach. Zresztą i tak liczy się efekt końcowy a nie droga do niego. Jak komuś szybciej i łatwiej pisać w Visual Basicu, Lua czy czymkolwiek innym co już zna, to niech sobie pisze. No a Pythonowcy drażnią mnie tym, że ich standardową odpowiedzią na dowolny problem jest "zrób to w Pythonie". 

 

Tak z innych rzeczy, polecam artykuł "The Keyhole Problem", który jest trochę o GUI, trochę o bazach danych, ale głównie o tym, żeby na ekranie starać się upakować jak najwięcej użytecznych informacji. http://aristeia.com/TKP/ 

[Arpegius]

VB pozwala dosyć łatwo pisać GUI. Jest też VBA wbudowane w Offica, w którym można robić dziwne rzeczy w Excellu.

Kto teraz używa legalnego płatnego Offica? Twój argument jest inwalidą.

 

A przy użyciu Pythona można pisać makra do LibreOffice (OpenOffice), Gimpa czy Blendera.

 

Do GUI pod Pythonem jest przykładowo PyGTK, które jak całe GTK się ładnie rozciąga i skaluje o czym ten koleś pieprzy przez pół tej książki.

Jest też np Kivy do pisania mobilnych aplikacji graficznych w Pythonie.

 

Ale ja wole pisać aplikacje przy użyciu QtQuick2 ( część frameworku Qt5 który jest naprawdę przenośny ), wykorzystuje on takie języki jak C++, Javascirpt, oraz cudo zwane QML.

 

Edytowano Grudzień 19, 2013 przez Arpegius

[Khornel]

Jaki język waszym zdaniem jest najprostszy i najłatwiej się go nauczyć?