Torgowi Programiści - Nauka programowania od podstaw

Cytuj:

---

Mistrzu dragon napisał

Skoro krowa goni tylko w prawo , a X oznacza miejsce na które nie może stanąć , to może stanąć tylko na 1 pole w każdej kolumnie a wtedy wychodzi 42 :

Kod:

---

1 8 4 2 6
9 8 8 1 2
6 7 8 9 8
1 9 8 6 5

---

Czy ja coś mylę?

---

Masz rację, sorki. Poprawione ;).

Podpisuję się też pod większością tego, co napisał Zeimer. Dodam tylko, że języki logiczne wcale nie są takie bezużyteczne - znajdują spore zastosowania w dziedzinie sztucznej inteligencji i parserów/lekserów DCG (chociaż teraz pisanie parserów/lekserów zostało zautomatyzowane i do tego służy Bison i Yacc). Dla początkujących - to drugie zagadnienie dotyczy tworzenia własnych języków programowania. To kolejna, zajebiście interesująca dziedzina informatyki - jeżeli mój mózg na to pozwoli, chciałbym pisać magisterkę z tego tematu...

Programowanie funkcyjne zaś pokazuje pięknie świat - jak nasze konstrukcje myślowe potrafią się przełożyć na coś formalnego. W dodatku pokazują, ile rzeczy na świecie jest fraktalnych ("złożonych z samych siebie") - np. listę możemy wyrazić za pomocą elementu startowego i mniejszej listy. W Common Lispie np. lista:

Kod:

---

[1,2,3,4,5]

---

To:

Kod:

---

(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 Nil)))))

---

W matematyce ma to nazwę tzw. indukcji strukturalnej i to naprawdę fajna rzecz. I wcale nie jest trudna, tylko groźnie brzmi ;).

Została powołana grupa użytkowników "Torgowi Programiści". Rozmawiamy tam o różnego rodzaju wskazówkach do zadań, oraz o własnych "programistycznych wojażach". Wszystkich zainteresowanych proszę o pisanie bodajże do użytkownika Abe PW, aby zaprosił ich do grupy.

Pozdrawiam
Killavus

Co do użyteczności języków logicznych - zależy ona od tego, ile można zarobić na rozwiązywaniu problemów z domeny logicznej. Strzelam, że pisanie kompilatorów i parserów oraz sztuczna inteligencja nie są dochodowe, więc języki logiczne pozostaną raczej ciekawostką i obiektem badań.

Co do pracy magisterskiej - sam chciałbym się zająć algorytmami lub językami programowania. Jako, że algorytmy mają się dobrze, a uniwersalny i idealny język programowania dalej nie istnieje skłaniam się ku temu drugiemu.

Dodam jeszcze listę języków programowania, których radzę unikać: Objective-C, Visual Basic, Perl, Pascal, Delphi, Lisp (jeżeli już bierzemy się do FP to tylko Haskell).

@down
Moim zdaniem to co jest czynnikiem decydującym o wyborze języka jest elegancja, prosta oraz łatwość rozumowania o poprawności.

Co do Lispów... może jeszcze nie dorosłem do lubienia ich.

Cytuj:

---

Zeimer napisał

Co do użyteczności języków logicznych - zależy ona od tego, ile można zarobić na rozwiązywaniu problemów z domeny logicznej. Strzelam, że pisanie kompilatorów i parserów oraz sztuczna inteligencja nie są dochodowe, więc języki logiczne pozostaną raczej ciekawostką i obiektem badań.

Co do pracy magisterskiej - sam chciałbym się zająć algorytmami lub językami programowania. Jako, że algorytmy mają się dobrze, a uniwersalny i idealny język programowania dalej nie istnieje skłaniam się ku temu drugiemu.

Dodam jeszcze listę języków programowania, których radzę unikać: Objective-C, Visual Basic, Perl, Pascal, Delphi, Lisp (jeżeli już bierzemy się do FP to tylko Haskell).

---

O ile z Lispem się nie zgodzę, to do języków funkcyjnych wartych polecenia polecam jeszcze SML (Standard ML - chyba jedyny język programowania na ziemi, który posiada formalną specyfikację semantyki ;)). Lisp wraca do łask z pomocą Clojure.

Co do dochodowości sztucznej inteligencji nie jest to wcale taka słaba dziedzina - systemy inteligentnych agentów do systemów klasy ERP to potężna kasa. LLVM to np. przykład pracy nad kompilatorami i lekserami, na który wyłożono naprawdę sporo hajsu i ludzie nad nim pracujący z pewnością mają godną płacę ;).

Tak z czysto formalnego punktu widzenia Haskell jest nawet złym językiem na początek programowania funkcyjnego - ciężko się wnioskuje o wydajności programów (trzeba zaprzęgnąć koindukcję, a to dosyć wysoka matematyka), ponad to ukrywa się wiele aspektów często spotykanych w czystym FP - np. obliczenia za pomocą kontynuacji nie istnieją w Haskellu (są zastąpione leniwością). Najlepszy kurs formalnego programowania, słynny kurs z MIT używa Scheme do nauki FP. To gorliwy i dynamiczny język funkcyjny.

Pozdrawiam
Killavus

Witam, programuje jako freelancer od prawie 6 lat, znam C++, C, Javę, PHP, Asma x86 , Asma PPC i SPU, Lua. Jeśli macie pytania dawać .

@Killavus
rozwiązanie zadań w c++ (jeśli można)
o krowie: http://ideone.com/gfOZRq //przy planszy 10x10 zdarzaja sie juz bledy - naprawa in progress
sito: http://ideone.com/L1ad0s
Oceńcie czy dobrze rozwiązane.
Zapewne te problemy dałoby się rozwiązać w prostszy sposób niż ja to zrobiłem, no ale cóż - jestem początkujący.
Mam nadzieję, że nie zepsuję nikomu zabawy swoimi rozwiązaniami :)

Cytuj:

---

Dark Eagle napisał

@Killavus
rozwiązanie zadań w c++ (jeśli można)
o krowie: http://ideone.com/gfOZRq //przy planszy 10x10 zdarzaja sie juz bledy - naprawa in progress
sito: http://ideone.com/L1ad0s
Oceńcie czy dobrze rozwiązane.
Zapewne te problemy dałoby się rozwiązać w prostszy sposób niż ja to zrobiłem, no ale cóż - jestem początkujący.
Mam nadzieję, że nie zepsuję nikomu zabawy swoimi rozwiązaniami :)

---

Zadanie o krowie jest źle. Sprawdź sobie taką planszę:

Kod:

---

2 9 9 9
1 0 0 0
9 1 1 1
0 0 0 0

---

Twój algorytm wybierze tą ścieżkę:

Kod:

---

2 9 9 9
1 0 0 0
9 1 1 1
0 0 0 0

---

A powinien wziąć tą:

Kod:

---

2 9 9 9
1 0 0 0
9 1 1 1
0 0 0 0

---

Co do sita, wygląda ok, tylko jeden krok mnie zastanawia: //wypelnienie tablicy liczbami z zakresu(1,zakres) - po co to robisz, skoro i tak zaraz zamieniasz to na 0 wszędzie?

PS Taka technika, którą obrałeś przy rozwiązywaniu krów to tzw. strategia zachłanna - w ten sposób np. można wydawać resztę w automatach z napojami. W tym problemie jednak jest wymagane rozwiązanie dynamiczne - musisz sprawdzić wszystkie możliwe trasy w kolumnie, bo być może kiepska początkowo droga przerodzi się w cośbardzo dobrego.


Pozdrawiam
Killavus

Taa, niezła gafa. Już pracuję nad naprawą. Teraz dopiero widzę ile błędów xdddddddd
#edit
no właśnie, po głębszym zastanowieniu się też do tego doszedłem...
no to pierw spróbuję tą strategią zachłanną poprawnie wykonać, a potem zastanowię się nad rozwiązaniem dynamicznym
Dzięki za wskazówki ;)
#edit 2
http://ideone.com/gfOZRq
juz jest wersja poprawiona (nadal greedy)

Zapraszam wszystkich do robienia zadań. Koledzy rzucili się widzę na trudne, ale warto też zrobić łatwe :).
Dodam link do głównego posta do zadań z list i tablic.

Pozdrawiam
Killavus

Dobra, ja zrobię implementacje krówek w PHP . Generacja możliwych ścieżek , liczenie całkowitych sum i sortowanie, klucze w tablicy są X i Y w jednym bajcie ( po 4 bity na każdy, więc nie obsluguje więcej niż 8x8, jak ktos bedzie chcial to niech se zmieni xD ja oszczędzam pamięć lol ;_: poza tym, dla ciekawskich jak można wykorzystać operacje logiczne w programowaniu chciałem zastosować XD ) , mam prawie gotowe, pewno jutro wrzucę ;d

Ostatnio naszła mnie ochota na naukę programowania. Myślę, że jest to przydatna umiejętność w życiu. Miałem już kiedyś styczność z C++, więc podstawy mam w miarę opanowane (podstawowe podstawy:)). Zacząłem uczyć się pythona z codecademy.com, później wszedłem do tego działu w poszukiwaniu jakiejś książki do niego i natknąłem się na ten temat :)

Postanowiłem zrobić te zadanka:
-3 funkcję zmieniające listę: http://ideone.com/FCrucp
-sito Erastotenesa: http://ideone.com/jQHlFE

Za krowę zabiorę się jak znajdę więcej czasu :)

Super temat :D Aż sie ciepło na sercu robi widząc taki zapał do nauki. Programuje od 2 gim (teraz 1 rok studiów) i do dziś nie straciłem ani troche zainteresowania chociaż niektorzy ludzie (np moi prof) usilnie starają się mi to obrzydzić.

I pamiętajcie:
"Komputery są głupsze od ludzi. Programiści są głupsi od komputerów" P.Coelho

Cytuj:

---

DarkSide napisał

Ostatnio naszła mnie ochota na naukę programowania. Myślę, że jest to przydatna umiejętność w życiu. Miałem już kiedyś styczność z C++, więc podstawy mam w miarę opanowane (podstawowe podstawy:)). Zacząłem uczyć się pythona z codecademy.com, później wszedłem do tego działu w poszukiwaniu jakiejś książki do niego i natknąłem się na ten temat :)

Postanowiłem zrobić te zadanka:
-3 funkcję zmieniające listę: http://ideone.com/FCrucp
-sito Erastotenesa: http://ideone.com/jQHlFE

Za krowę zabiorę się jak znajdę więcej czasu :)

---

Co do funkcji podzielny - niestety, Twoja funkcja łapie także 2 i 4. Sprawdź to.

Co do sita, działa ono poprawnie, niestety - jest trochę wolne. Chodzi głównie o pętlę z k. Musisz oznaczyć tylko 2*x, 3*x, ... k*x. Czemu więc przelatujesz przez całą tablicę za każdym razem gdy znajdziesz liczbę pierwszą, zwłaszcza, że możesz to zrobić łatwo w programie, żeby odwiedzał tylko te liczby, co trzeba?

Tzw. asymptotyczna złożoność jest ta sama, co prawda (O(n^2)), ale warto pomyśleć jak w praktyce łatwo to przyspieszyć.

Nikt jeszcze nie zrobił dobrze zadania z krowami - zapraszam do zmierzenia się z tym problemem. Co więcej, zapraszam też do grupy - PW do użytkownika Abe pozwoli Wam do niej dołączyć! :)

Dorzucę kolejną wskazówkę, która w sumie jest rozwiązaniem jak dobrze się ją zrozumie.

Zauważmy jedną rzecz - mianowicie możemy rozpatrywać mniejsze względem liczby kolumn plansze.

Dla jednokolumnowej planszy rozwiązanie jest bardzo proste - wybieramy maksimum ze wszystkich liczb w kolumnie. Możemy sobie przepisać do pomocniczej tablicy całą tą kolumnę, wtedy będziemy mogli szybko odpowiadać na pytanie "najlepsza ścieżka z wiersza x".

Dla dwukolumnowej planszy możemy zauważyć, że skoro mamy już policzone dobre rozwiązanie dla pierwszej kolumny, to wystarczy skorzystać z tego rozwiązania. Aby uzyskać 'dobre' rozwiązanie dla dwukolumnowej planszy wystarczy popatrzeć na poprzednią kolumnę, po czym dodać maksymalną wartość z pól które są w poprzedniej kolumnie i możemy z nich dojść do aktualnego pola.

Przykładowo:

Kod:

---

1 x # reszta planszy
8 y # reszta planszy
3 z # reszta planszy

---

Rozpatrując x bierzemy wartość liczbową z pola x i dodajemy maksimum z 1 i 8. Czyli 8. Przy y patrzymy na maksimum 1, 8, 3. Przy z patrzymy na 8, 3.

A co z k-kolumnową planszą, gdy rozpatrujemy k+1 kolumnę?

W czwartek ogarniam następną część, niestety wcześniej mam kolokwium ;)

Pozdrawiam
Killavus

Próbowałem zrobić krowę i nie rozumiem jednej rzeczy w moim kodzie http://ideone.com/us5q8d
Przepuszczałem go przez http://www.pythontutor.com i nie rozumiem kroku 63 -> 64 (linia 25). Dlaczego gdy zapisuję wartość do pomocniczej listy suma_pom, to nadpisuje mi też wartość w liście suma? Dalej nie sprawdzałem.

#edit
poprawione i mam nadzieję, że działa :) nie wiem czy bym to rozkminił bez podpowiedzi :p

Cytuj:

---

DarkSide napisał

Próbowałem zrobić krowę i nie rozumiem jednej rzeczy w moim kodzie http://ideone.com/us5q8d
Przepuszczałem go przez http://www.pythontutor.com i nie rozumiem kroku 63 -> 64 (linia 25). Dlaczego gdy zapisuję wartość do pomocniczej listy suma_pom, to nadpisuje mi też wartość w liście suma? Dalej nie sprawdzałem.

---

Lista to typ złożony. Z punktu widzenia zarządzania pamięcią wpada do wielu szuflad (i pamiętamy adres pierwszego elementu). W Pythonie (i w większości języków funkcyjnych) w przypadku operatora "=" przepisywane są adresy, a nie obiekty. Na przykładzie:

Kod:

---

l = [1,2,3]  # Zostaje zadeklarowana zmienna l i zdefiniowana jako nowa lista [1,2,3]. Załóżmy, że adres tej listy to 1.
r = [2,3,4] # Zostaje zadeklarowana zmienna r i zdefiniowana jako nowa lista [2,3,4]. Załóżmy, że adres tej listy to 2.

l = r # Do zmiennej r zostaje przepisany adres zmiennej l. W takim wypadku zmienna l wskazuje na adres nr 2, oraz r wskazuje na adres zmiennej 2.
l[0] = 2  # W obiekcie o adresie wskazywanym przez zmienną l (2) zostaje zmieniona wartość.
print r[0] # W obiekcie o adresie wskazywanym przez zmienną r (też 2!) zostaje pobrana wartość i to ona zostaje wypisana na ekran.

---

Jedyne typy, w których wartości przy przypisaniu zostają skopiowane to tzw. typy proste (liczby, pojedyńcze znaki).

Kod:

---

l = 2  # Zostaje zadeklarowana zmienna l i zdefiniowana jako liczba 2.
r = 3 # Zostaje zadeklarowana zmienna r i zdefiniowana jako liczba 3.
l = r  # Wartość zmiennej l zostaje nadpisana (kopiowana jest wartość r, czyli 3)

---

Dlaczego tak jest? Obiekty potrafią być wielkie, a kopiowanie z jednego miejsca pamięci do drugiego jest operacją czasochłonną. Z kolei skopiowanie adresu (która jest liczbą) do drugiej zmiennej jest bardzo proste i szybkie. Co ciekawe, w przypadku C wszystkie typy są jednakowo traktowane - zostają po prostu skopiowane. Dlatego też powstały tzw. wskaźniki, żeby zachować wydajność.

Ty zaczynasz wskazywać na ten sam kawałek pamięci w linii 29.

Rozwiązaniem tego problemu w przypadku list jest kopiowanie ich element po elemencie (za pomocą pętli for). W tym wypadku z racji tego, że w liście przechowujemy typy proste zostają one skopiowane. Istnieją również inne metody (trudniejsze), które jednak nie opłacająsię w przypadku tak prostego przypadku. Np. deep copy - http://docs.python.org/2/library/copy.html.

Aby udowodnić, że C robi to kopiowaniem, podrzucam kawałek kodu - http://pastie.org/7720395. Wykracza on troszeczkę ponad poziom naszego kursu, ale tylko nieznacznie - już niedługo nie dojdziemy do struktur.

Dzisiaj, późno w nocy (taki mam tryb życia) napiszę kolejną część ;).

Pozdrawiam
Killavus

Witam, uczę się cpp od paru dni ze strony cpp0x.pl, niestety doszedłem do chyba 5 czy 6 rozdziału i już kurwicy przy tym dostaję. Po pierwsze nie rozumiem w ogóle o co autorowi chodziło w tym zadaniu, po drugie ta 'praca domowa' na moje oko jest niewykonalna, a ja z jednym kodem pierdolę się już za przeproszeniem od godziny.
Może byłem zbyt ambitny, czy cpp to był dobry wybór do nauki na mój pierwszy strzał z programowaniem? Może powinienem spróbować czegoś innego?