Strony: [1]
  Drukuj  
Autor Wątek: Struktury danych  (Przeczytany 2170 razy)
maciosz
Administrator
Hero Member
*****
Wiadomości: 725


5564019
Zobacz profil Email
« : Grudnia 19, 2014, 06:07:28 »

Struktury danych

Na razie hasło, bo bardzo konkretnego zadania nie wymyśliliśmy. Będzie to też jakieś zadanie wieloetapowe, powoli zapoznające użytkownika ze strukturami danych od najprostszych list przez kolejki po grafy. Padły też sieci neuronowe, ale nie chcę wprowadzać w błąd co do zamysłów autora, więc tej myśli nie skomentuję.
« Ostatnia zmiana: Marca 10, 2015, 04:08:45 wysłane przez maciosz » Zapisane

Chaos zawsze pokonuje porządek, gdyż jest lepiej zorganizowany.
Terry Pratchett
Behoston
Administrator
Sr. Member
*****
Wiadomości: 374


277797 mati-20
Zobacz profil WWW Email
« Odpowiedz #1 : Lutego 10, 2015, 11:49:55 »

też mógłbym zrobić.
tj umieść te dane na drzewie takim a takim
Zapisane

Ilu bioinformatyków potrzeba do wkręcenia żarówki? Żadnego, bo i tak nie ma prądu.
Behoston
Administrator
Sr. Member
*****
Wiadomości: 374


277797 mati-20
Zobacz profil WWW Email
« Odpowiedz #2 : Lutego 11, 2015, 06:14:56 »


zastanawiam się czy zadanie nie jest zbyt obszerne.



w zadaniu chcę pokazać, że nawet proste rzeczy generują struktury danych

Struktury danych są bardzo istotnym elementem całego informatycznego świata. Każda rzecz jest jakąś daną zapisaną w jakiejś mniej lub bardziej skomplikowanej strukturze. Najprostszym przykładem może być jakaś liczba zapisana na zmiennej x=8. Jednak w praktyce zapisywanie wszystkiego na zmienne jest zupełnie niewygodne. Wyobraźmy sobie, że mamy do zapisania 50 kolejnych wyników jakiegoś doświadczenia. Dla przykładu możemy myśleć o bardzo życiowej sytuacji: mamy hodowle drożdży i badamy jak wysokie stężenie alkoholu są w stanie znieść. Możemy oczywiście napisać:
Kod:
d0=10
d1=8
d2=10
d3=12
d4=6
d5=8
d6=7
d7=12
d8=10
d9=16
d10=16
d11=9
d12=14
d13=9
d14=11
d15=17
d16=18
d17=9
d18=5
d19=17
d20=11
d21=17
d22=7
d23=7
d24=12
d25=9
d26=5
d27=18
d28=6
d29=7
d30=9
d31=9
d32=6
d33=8
d34=8
d35=11
d36=13
d37=16
d38=8
d39=8
d40=12
d41=5
d42=18
d43=15
d44=17
d45=18
d46=7
d47=8
d48=13
d49=5
d50=12
d51=11
d52=11
d53=12
d54=5
d55=17
d56=7
d57=15
d58=10
d59=14
d60=18
d61=5
d62=8
d63=9
d64=10
d65=14
d66=15
d67=13
d68=16
d69=14
d70=17
d71=16
d72=10
d73=7
d74=14
d75=15
d76=17
d77=11
d78=10
d79=18
d80=18
d81=9
d82=12
d83=18
d84=12
d85=13
d86=7
d87=10
d88=16
d89=12
d90=16
d91=8
d92=11
d93=15
d94=8
d95=7
d96=7
d97=10
d98=13
d99=13

Ten zapis przysparza bardzo nieprzyjemnych problemów: trzeba wymyślić bardzo dużo nazw zmiennych oraz trzeba te nazwy zapamiętać, żeby mieć jak sprawdzić jaką tolerancją cechuje się szczep hodowany w cylindrze51518155. W tym wypadku pamiętamy, że wszystkie zmienne wyglądają podobnie ale co jeśli chcieli byśmy dowiedzieć się jaka jest maksymalna tolerancja? Wpisanie
Kod:
max(d0,d1,d2,d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49,d50,d51,d52,d53,d54,d55,d56,d57,d58,d59,d60,d61,d62,d63,d64,d65,d66,d67,d68,d69,d70,d71,d72,d73,d74,d75,d76,d77,d78,d79,d80,d81,d82,d83,d84,d85,d86,d87,d88,d89,d90,d91,d92,d93,d94,d95,d96,d97,d98,d99)
stanowczo jest złym pomysłem.

Zauważmy, że nazwy zmiennych ustaliliśmy według dość logicznego wzoru d# gdzie d jest skrótem od drożdże a # to numer hodowli. To sugeruje nam, że skoro coś się powtarza wiele razy to można to w jakiś sposób pominąć i pamiętać tylko raz. Taka chęć uproszczenia zapisu wyników prowadzi nas do dużo wygodniejszej struktury danych - listy.

Dzięki niej nie musimy kolejno wpisywać wartości. Wystarczy, że na liście zapiszemy nasze dane
Kod:
d=[10, 8, 10, 12, 6, 8, 7, 12, 10, 16, 16, 9, 14, 9, 11, 17, 18, 9, 5, 17, 11, 17, 7, 7, 12, 9, 5, 18, 6, 7, 9, 9, 6, 8, 8, 11, 13, 16, 8, 8, 12, 5, 18, 15, 17, 18, 7, 8, 13, 5, 12, 11, 11, 12, 5, 17, 7, 15, 10, 14, 18, 5, 8, 9, 10, 14, 15, 13, 16, 14, 17, 16, 10, 7, 14, 15, 17, 11, 10, 18, 18, 9, 12, 18, 12, 13, 7, 10, 16, 12, 16, 8, 11, 15, 8, 7, 7, 10, 13, 13]
a następnie użyjemy tej samej funkcji co poprzednio jako argument wprowadzając listę. Struktura ta posiada odpowiednią implementację aby takie użycie dało pożądany efekt.
Cytuj
max(d)

Jak widać nawet tak podstawowa struktura ułatwia nam znacząco niektóre zdania.

Załóżmy teraz, że chcemy przebadać nasze uczynne drożdże np. pod kątem odporności na jakieś związki chemiczne które zabijają bakterie, które psują produkcję alkoholu.
Załóżmy, że do dyspozycji mamy tylko jedno stanowisko badawcze bo problem nie jest szczególnie poważny i nie przeszkadza w produkcji alkoholu.
Do tego celu należało by utrzymać jakąś kolejność. Lista nadaje się do tego celu lecz sami musimy pamiętać w którym miejscu skończyliśmy. To nie jest najlepsze rozwiązanie, ponieważ w którymś momencie najpewniej zapomnimy zapisać gdzie jesteśmy lub pomylimy się przy zapisie. W ten sposób możemy  pominąć np. jakiś szczególnie ciekawy szczep, który sam potrafi poradzić sobie z bakteriami.
Aby uniknąć tego typu problemów możemy zastosować strukturę stosu danych.
W praktyce ta struktura funkcjonuje bardzo często w świecie realnym w laboratoriach:
http://st.depositphotos.com/1010710/3384/i/950/depositphotos_33844999-Petri-dishes.jpg
Szalki układane są na stosie i kolejno badane.
Zastanówmy się co jest potrzebne do implementacji takiej struktury danych w programie. Właściwie potrzebny nam jest jakiś spis szalek, który jednoznacznie określa pozycję każdej z nich i pozycję szalki w spisie, która jest kolejna do wzięcia na badanie. Dodatkowo możemy założyć, że taki stos szalek nie może przekroczyć jakiejś wysokości, ponieważ gdy będzie wyższy niż 15 szalek będzie go bardzo łatwo przewrócić.
Jako spisu użyjemy listy lub tablicy jednowymiarowej o długości 15 miejsc. Dodatkowo przy ustawianiu szalki na stosie zwiększamy licznik mówiący nam gdzie leży ostatni element (analogicznie przy zdejmowaniu szalki licznik zmniejsza się). Jak widać do struktury listy/tablicy dodaliśmy tylko jedną zmienną a uzyskaliśmy bardzo życiowy model danych.

Przebadaliśmy już szczepy drożdży i okazało się, że kilka z nich ma mechanizmy obronne przeciw bakteriom. Odkrycie wydaje się być bardzo przełomowe i inwestujemy w (przynajmniej) dwa stanowiska które będą szczegółowo przeprowadzać kolejne testy na naszych drożdżach.
Na tym etapie stos jest już nieprzydatny. Jeśli reprezentowali byśmy stanowiska badawcze jako stosy, to w sytuacji gdy badanie pierwsze trwa krócej na 2 stosie lądowały by coraz to nowe szczepy i szczep nr. 2 przebadany mógłby być jako ostatni co jest złym pomysłem. (Na pierwszym stosie mamy wszystkie szczepy kolejno: 1,2,3,... badamy pierwszy z góry stosu i po przebadaniu kładziemy na stos drugiego stanowiska. Zaraz potem robimy tak samo ze szczepem nr. 2. Jednak zanim szczep pierwszy zostanie przebadany przykrywamy szczep 2 szczepem 3,4,...)
Wyniki badań mogły by wyjść błędne ze względu na bardzo różny odstęp czasu w kolejnych etapach badania i pomieszaną kolejność. Do poprawienia sytuacji zamiast stosu można użyć kolejnej bardzo życiowej struktury jaką jest kolejka. Dokładamy szalkę na górę stosu a zabieramy szalkę z dołu (bo np mamy taki stojak który na dole umożliwia wysunięcie jednej szalki).
Mimo, że kolejka jest naturalnie spotykana jej implementacja jest nieco trudniejsza. Można również przedstawić ją jako listę/tablicę o znanej długości (bo w rzeczywistości taki stojak ma jakąś określoną pojemność). Tu musimy pamiętać gdzie jest początek naszej kolejki i gdzie koniec ale to poziomem trudności nie przekracza poprzedniej struktury. Trudnością jest tu sposób w jaki zapisujemy kolejne elementy. Musimy naszą listę zapętlić - zrobić tak, aby kolejnym miejscem po ostatnim było miejsce pierwsze i na odwrót. Innymi słowy musimy pamiętać aby licznik końca po dodaniu na ostatnie miejsce tablicy przeskoczył na pierwsze (o ile nie jest zapełnione przez początkowy element). Tak samo licznik początku przy pobieraniu musi przeskoczyć przy ostatnim miejscu tablicy na miejsce pierwsze i nie może "zderzyć się" z licznikiem końca.


ZADANIE:
Zaimplementuj strukturę listy tak aby poniższy kod:
dodał do niej elementy:
Kod:
lista.append(5)
lista.append(8)
...

pobierał dane wartości:
Kod:
lista.get(2)
...
* przechodził po wszystkich elementach
Kod:
for i in lista: print i
* zwracał wartość maksymalną
Kod:
lista.max()

Zaimplementuj za pomocą gotowych list/tablic strukturę stosu:
Kod:
stos=stos(15)
I umieść na niej wartości:
Kod:
stos.put(8)
stos.put(5)
...
Następnie pobierz kilka wartości (polecenie pop zmniejsza licznik i zwraca element z góry stosu):
Kod:
stos.pop()

Zaimplementuj za pomocą gotowych list/tablic strukturę kolejki:
Kod:
kolejka=kolejka(15)
A następnie dodaj wartości:
Kod:
stos.put(12)
stos.put(7)
...
następnie pobierz część wartości:
Kod:
stos.get()
stos.get()
i znów dodaj:
...
<sprawdzanie czy kolejka ładnie się zapętla czy wywala/nadpisuje>
« Ostatnia zmiana: Marca 10, 2015, 03:18:32 wysłane przez Behoston » Zapisane

Ilu bioinformatyków potrzeba do wkręcenia żarówki? Żadnego, bo i tak nie ma prądu.
maciosz
Administrator
Hero Member
*****
Wiadomości: 725


5564019
Zobacz profil Email
« Odpowiedz #3 : Lutego 14, 2015, 12:56:40 »

ZADANIE W TRAKCIE PISANIA!
zastanawiam się czy zadanie nie jest zbyt obszerne.

W sensie że teraz ma za dużo treści? Czy że za dużo się może kryć pod opisem "struktury danych"? To, co na razie jest napisane, brzmi mi bardzo spoko.
Zapisane

Chaos zawsze pokonuje porządek, gdyż jest lepiej zorganizowany.
Terry Pratchett
Behoston
Administrator
Sr. Member
*****
Wiadomości: 374


277797 mati-20
Zobacz profil WWW Email
« Odpowiedz #4 : Lutego 16, 2015, 01:38:51 »

w znaczeniu że przeciągam usera od rzeczy tak beznadziejnie prostych aż do samego końca w 1 zadaniu. I treści będzie właściwie na tutorial cały xD
Zapisane

Ilu bioinformatyków potrzeba do wkręcenia żarówki? Żadnego, bo i tak nie ma prądu.
Behoston
Administrator
Sr. Member
*****
Wiadomości: 374


277797 mati-20
Zobacz profil WWW Email
« Odpowiedz #5 : Marca 07, 2015, 02:33:01 »

powiedzmy że gotowe. Mogę dodać słowniki jeszcze do tego nie wiem czy drzewa też ale na to imo kolejna cześć zadania
Zapisane

Ilu bioinformatyków potrzeba do wkręcenia żarówki? Żadnego, bo i tak nie ma prądu.
maciosz
Administrator
Hero Member
*****
Wiadomości: 725


5564019
Zobacz profil Email
« Odpowiedz #6 : Marca 09, 2015, 12:50:37 »

Ok, podoba mi się życiowe opisanie stosu i kolejki, ale nie bardzo rozumiem, jak właściwie brzmi polecenie i jaka jest odpowiedź.
Chyba, że to będzie zadanie do jakiegoś tutorialu z programowania, w którym nie będzie konkretnego pola na odpowiedź, bo polecenia będą brzmiały po prostu: "Napisz funkcję która cośtam. Spróbuj zmodyfikować ją, żeby umiała cośtam. Zaimplementuj cośtam. Sprawdź, jak parametry zmieniają cośtam." Czyli generalnie "napisz i pobaw się tym, co napisałeś".

Nie jest właściwie wprost napisane, co oznaczają liczby w podanym na początku kawałku kodu; rozumiem, że to jakieś liczbowe przedstawienie tolerancji drożdży na alkohol?

mamy hodowle drożdży
(...)
chcemy przebadać nasze uczynne bakterie
Drożdże to nie bakterie Mrugnięcie Chyba że to już o czymś innym, ale warto by to zaznaczyć, bo brzmi jak byśmy cały czas o tym samym stworzonku pisali. Więc żeby nie wprowadzać w błąd jakoś to zaznaczyć.
Zapisane

Chaos zawsze pokonuje porządek, gdyż jest lepiej zorganizowany.
Terry Pratchett
Behoston
Administrator
Sr. Member
*****
Wiadomości: 374


277797 mati-20
Zobacz profil WWW Email
« Odpowiedz #7 : Marca 09, 2015, 06:21:02 »

OMG ale fail :OOOOOOOOOOOOO
żegnajcie, idę się zastrzelić

Jedyne sensowne sprawdzenie można zrobić dopiero na liście (wpisz dane i wypisz)
dane dodam potem
jak na razie zadanie jest moim zdaniem skończone
« Ostatnia zmiana: Marca 10, 2015, 03:17:51 wysłane przez Behoston » Zapisane

Ilu bioinformatyków potrzeba do wkręcenia żarówki? Żadnego, bo i tak nie ma prądu.
maciosz
Administrator
Hero Member
*****
Wiadomości: 725


5564019
Zobacz profil Email
« Odpowiedz #8 : Marca 10, 2015, 04:08:36 »

No ok. Dalej niespecjalnie rozumiem jakie jest konkretnie polecenie, ale z tym się niech już tester męczy.
Zapisane

Chaos zawsze pokonuje porządek, gdyż jest lepiej zorganizowany.
Terry Pratchett
Behoston
Administrator
Sr. Member
*****
Wiadomości: 374


277797 mati-20
Zobacz profil WWW Email
« Odpowiedz #9 : Marca 10, 2015, 04:11:14 »

Trzeba będzie to Dopracować jak będziemy wiedzieli co z serwerem
Zapisane

Ilu bioinformatyków potrzeba do wkręcenia żarówki? Żadnego, bo i tak nie ma prądu.
Strony: [1]
  Drukuj  
 
Skocz do:  


SimplePortal 2.3.1 © 2008-2009, SimplePortal