Skocz do zawartości

Zabawy algorytmiczne i programowanie


Maklak2

Recommended Posts

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ę. 

 

Link do komentarza
Udostępnij na innych stronach

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ł*

Link do komentarza
Udostępnij na innych stronach

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

  • +1 2
Link do komentarza
Udostępnij na innych stronach

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 przez Maklak2
Link do komentarza
Udostępnij na innych stronach

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 :aj3:

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 :P)

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.

Link do komentarza
Udostępnij na innych stronach

Niebędę komentował Maklaka. TL;DR  :dunno:
 

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 :aj3:

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

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 :P)

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 przez Arpegius
Link do komentarza
Udostępnij na innych stronach

> 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. 

Link do komentarza
Udostępnij na innych stronach

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 przez Arpegius
Link do komentarza
Udostępnij na innych stronach

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 przez Maklak2
Link do komentarza
Udostępnij na innych stronach

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

Ja tak samo :dunno:  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 :P

Edytowano przez Ravin
Link do komentarza
Udostępnij na innych stronach

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

Link do komentarza
Udostępnij na innych stronach

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

Link do komentarza
Udostępnij na innych stronach

Ja tak samo :dunno:  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 przez Arpegius
Link do komentarza
Udostępnij na innych stronach

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 przez Arpegius
Link do komentarza
Udostępnij na innych stronach

Ł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:

Link do komentarza
Udostępnij na innych stronach

Ł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 :rarity5:  ( 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.)

Link do komentarza
Udostępnij na innych stronach

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 :x

Edytowano przez Camed
Link do komentarza
Udostępnij na innych stronach

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 :x

Co? :lol:  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 :facehoof:

 

Link do komentarza
Udostępnij na innych stronach

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/ 

Link do komentarza
Udostępnij na innych stronach

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 przez Arpegius
Link do komentarza
Udostępnij na innych stronach

Chcesz dodać odpowiedź ? Zaloguj się lub zarejestruj nowe konto.

Tylko zarejestrowani użytkownicy mogą komentować zawartość tej strony

Utwórz konto

Zarejestruj nowe konto, to bardzo łatwy proces!

Zarejestruj nowe konto

Zaloguj się

Posiadasz własne konto? Użyj go!

Zaloguj się
×
×
  • Utwórz nowe...