Na jutro wykład nr 13 (według eduxa) – Automaty Stosowe
LUB NA JUTRO WYKŁAD NUMER 12 (ten z posta niżej), nie wiem jak to będzie liczone. Najlepiej się obu nauczyć 🙂
Mam tylko średnio czytelną notatkę z wykładu:
(kliknij obrazek, aby powiększyć)
Na jutro wykład nr 13 (według eduxa) – Automaty Stosowe
LUB NA JUTRO WYKŁAD NUMER 12 (ten z posta niżej), nie wiem jak to będzie liczone. Najlepiej się obu nauczyć 🙂
Mam tylko średnio czytelną notatkę z wykładu:
(kliknij obrazek, aby powiększyć)
Notatka z wykładu. Po // są komentarze, ICH NIE PISZEMY NA TABLICY!
// lex z przykladow do wykladu nr 12 // a teraz bizon: // definicje %{ include costam.h %} %token NUM %% // teraz gramatyka input : /* nic */ | input expr "\n" {printf("\n");}; // daje printf ktore 'przywroci koniec linii' expr : expr '+' mult { printf("+");}; | expr '-' mult { printf("-");}; | mult; // zejscie nizszego rzedu (??) mult : mult '*' term { printf("*");}; | mult '/' term { printf("/");}; | term; term : NUM { printf("%d", $1);}; | '(' expr ')'; %% // main int main() { yyparse(); return 0; }
Jak usuwać asocjacje wiele do wiele lub wiele do jeden? Pojawia się tu jeden banalny programistyczny problem. Nie można usuwać z listy/mapy po której się właśnie iteruje:
ŹLE:
public void usun() throws Exception { for(Wyplata wyplata : wyplaty) { this.usunWyplate(wyplata); } wyplaty.clear(); wszystkieWyplaty.clear(); }
DOBRZE:
@SuppressWarnings("unchecked") public void usun() throws Exception { for(Wyplata wyplata : (Vector<Wyplata>) wyplaty.clone()) { this.usunWyplate(wyplata); } wyplaty.clear(); wszystkieWyplaty.clear(); }
Jak widać w pierwszym przypadku próbuje usuwać elementy z Vector’a po którym iteruje. Nie ważne czy będzie to iteracja for(Klasa element : lista) czy for(int i = 0; i < lista.size(); i++) i tak problem będzie występował i usunie się tylko jeden/kilka elementów z listy lub wywali Exception.
Rozwiązaniem (DOBRY kod) jest zrobienie 'płytkiej’ kopii listy funkcją clone() i iterowanie po niej.
Ewentualnie to też powinno się sprawdzić (nie testowałem):
while(lista.size() > 0) { // usuwa pierwszy element jak dluga sa jakies elementy lista.remove(0); // mozna tu tez dac 'lista.get(0)', cos z tym zrobic, a potem dopiero remove(0) }
Dostałem pierwszy kod programu od kolegi i z wielu wymienionych błędów najbardziej rzuca się jeden który powtarza się w każdym projekcie który sprawdzam. W 2 klasach są funkcje do dodawania asocjacji. Wywołanie 'jednej’ wywołuje 'drugą’, ale wywołanie 'drugiej’ nie wywołuje 'pierwszej’.
Przez co w projekcie o np. Schronisku [świetny pomysł do wykorzystania jak nie macie żadnego) obiekt 'Buda’ może wiedzieć jaki 'pies’ powinien w niej siedzieć, ale 'Pies’ nie wie, że ma 'budę’.
Krótki przykład z kodem kolegi przed i po przeróbkach.
UWAGA: to jest kod w pseudokodzie (prawie w C#), ale w niczym się nie odpali, można się tylko wzorować na nim i poprawić samodzielnie błąd w swoim problemie
BAARDZO WAŻNE: w kodzie przykładowym poprawiam kod który przechowuje odniesienia jako 'int’ z ID obiektu (które jest 'gdzieś tam nadawane’ unikalne) i używam 'restauracja.GetID()’, a nie referencji do obiektu (samo 'restauracja’), bo w tym projekcie jest założenie, że dane będą przechowywane w bazie danych i muszą mieć unikalne ID, a w JAVIE której większość używa trzymamy dane w pliku (ObjectPlus za to odpowiada) i powinniśmy trzymać referencje, a nie ID jakieś przechowywane w każdym obiekcie – o to może się baaaardzo czepiać przy sprawdzaniu projektów.
Czyli używamy:
private ArrayList<Student> znajomiStudenci = new ArrayList<Student>();
a nie:
private ArrayList<Integer> idZnajomiStudenci = new ArrayList<Integer>();
Teraz przejdziemy wreszcie do przykładowego kodu:
public void KLIENT.DodajUlubionaRestauracje(Restauracja restauracja) { // kompozycja!, zapamietujemy w Directory [HashMap w javie] jakis String unikalny i jakas wartosc/obiekt LubianeRestauracje.Add(restauracja.GetNazwa(), restauracja.GetID()); // to jest ok, wywoluje metode w drugiej klasie restauracja.DodajKlienta(this); // this, nie this.GetID() } // przekazac trzeba obiekt (Klient klient), a nie 'id' samo (int id), bo chcemy na nim cos wywolac public void RESTAURACJA.DodajKlienta(Klient klient) { // tutaj lipa, nic nie wywolujemy w drugim obiekcie Klienci.Add(klient.GetID()); /* Co z tego wynika? jesli jakis programista wywola: RESTAURACJA.DodajKlienta(klientStefan); to restauracja bedzie widziala, ze stefan ja lubi, ale stefan nie bedzie tego wiedzial */ } // KOD POPRAWIONY: public void KLIENT.DodajUlubionaRestauracje(Restauracja restauracja) { // dodajemy tylko jak nie mamy, dzieki temu unikniemy zapetlenia, ze funkcja X wywola Y, a Y wywola X i tak w kolko if(!LubianeRestauracje.Contains(restauracja.GetID())) { LubianeRestauracje.Add(restauracja.GetNazwa(),restauracja.GetID()); // WAZNE, najpierw dodaje do swojej tablicy/listy, a potem wywoluje metode drugiego obiektu [inaczej zapetlenie] restauracja.DodajKlienta(this); } } public void RESTAURACJA.DodajKlienta(Klient klient) { if(!Klienci.Contains(klient.GetID())) { Klienci.Add(klient.GetID()); KLIENT.DodajUlubionaRestauracje(this); } }
…
Odp. 1:
Odp. 2:
Odp. 3:
Treść zadania + odpowiedź:
Co gdzie się 'przenosi’:
Mój projekt pierwszy z baaardzo obszernym komentarzem.
Krótka instrukcja użycia:
Wymagania co do projektu są tu:
http://www.users.pjwstk.edu.pl/~mtrzaska/Files/MAS/MAS-informacje-stacjonarne.pdf
Jak zrobić 'ekstensje’ (są w projekcie, ale tu macie opis o co chodzi):
http://www.mtrzaska.com/plik/mas/mas-wyklad-nr-04
Projekt składa się z 4 plików:
Main.java
import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.util.Date; import java.util.Random; public class Main { public static void main(String[] arg) throws Exception { // jesli wczesniej cos zapisalem [odpalam program po raz kolejny] to wczytaj to co bylo // DEMONSTRACJA DZIALANIA 'TRWALYCH EKSTENSJI' (trwale czyli nie znikaja po zamnieciu programu) if(new File("mojeTajneDane").isFile()) { try { // plik jest w 'workspace' FileInputStream fileIn = new FileInputStream("mojeTajneDane"); ObjectInputStream inStream = new ObjectInputStream(fileIn); // odczytuje wszystko z dysku do pliku 'mojeTajneDane' jedna linijka // 'magia javy' zrobi reszte ObjectPlus.odczytajEkstensje(inStream); inStream.close(); fileIn.close(); } catch(IOException i) { i.printStackTrace(); return; } catch(ClassNotFoundException c) { System.out.println("Klasa nie znaleziona."); c.printStackTrace(); return; } } // utworz nowego Grzegorza o wzroscie miedzy 165, a 195 Random rand = new Random(); Student studencik = new Student("Grzegorz" + rand.nextInt(100), 165 + (rand.nextInt(31))); // na date urodzenia ustawiamy czas jaki jest 'teraz' studencik.ustawDateUrodzenia(new Date()); // wywoluje przeciazana metode z parametrem 'int' studencik.dodajOcene(2 + rand.nextInt(4)); // wywoluje przeciazana metode z parametrem 'Double' studencik.dodajOcene(new Double(2 + ((double)rand.nextInt(7) / 2))); // pokaz wszystkich Grzegorzy jacy istnieja ObjectPlus.pokazEkstensje(Student.class); // przed zamknieciem programu zapisz wszystkie ekstensje do pliku // DEMONSTRACJA DZIALANIA 'TRWALYCH EKSTENSJI' (trwale czyli nie znikaja po zamnieciu programu) try { // plik jest w 'workspace' FileOutputStream fileOut = new FileOutputStream("mojeTajneDane"); ObjectOutputStream outStream = new ObjectOutputStream(fileOut); // zapisuje wszystko na dysk do pliku 'mojeTajneDane' jedna linijka // 'magia javy' zrobi reszte ObjectPlus.zapiszEkstensje(outStream); outStream.close(); fileOut.close(); } catch(IOException i) { i.printStackTrace(); } } }
Osoba.java
import java.util.Date; public abstract class Osoba extends ObjectPlus { /* wymagane do serializacji, w przyszlosci jak cos zmienisz w tej klasie [dodasz/usuniesz atrybut] to zmienisz ta liczbe na inna, dzieki temu mechanizm 'serialize' nie pozwoli zaladowac pliku z dysku z starymi danymi do programu ktory uzywa innej klasy (przeciez moze byc zupelnie inna klasa o nazwie Student i dane takie jak 'oceny' moga w niej nie wystepowac) */ private static final long serialVersionUID = 1L; /* PRZYPOMNIENIE: Co to jest 'protected'? * To takie cos jak 'private' tylko, ze zmienna jest widziana w klasach 'dziedziczacych' (rozszerzajacych). * Dzieki temu bedzie mozna wyswietlac np. 'imie' w studencie ktory dziedziczy po osobie. */ // atrybut prosty, wymagany, pojedynczy, obiektu protected String imie; /* * WYMAGANY: * zawsze kiedy go ustawiamy to sprawdzamy czy ktos nam nie przekazal 'null' */ // atrybut prosty, opcjonalny, pojedynczy, obiektu protected String nazwisko; /* * OPCJONALNY: * zawsze kiedy go wyswietlany to sprawdzany cyz ktos nam nie przekazal 'null' * jesli 'null' to trzeba wyswietlic o tym informacje lub inaczej to 'obsluzyc', * bo proba wyswietlenie 'null' skonczy sie bledem programu */ // atrybut zlozony, opcjonalny, pojedynczy, obiektu protected Date dataUrodzenia; /* * ZLOZONY: * to taki ktory zawiera w sobie wiecej niz jedna informacje * ogolnie chodzi o odniesienie sie do innego obiektu (oprocz 'String') * */ // atrybut prosty, wymagany, pojedynczy, obiektu protected int wzrost = 0; /* * jest tu tylko po to, zeby wyliczac srednia (i miec cos 'pochodnego') */ // atrybut prosty, pojedynczy, wyliczalny (pochodny), klasowy private static double sredniWzrost = 0; /* * KLASOWY: * dotyczy klasy, czyli wszystkich 'Osob', a nie jednej konkretnej * technicznie: zmienna typu static * * POCHODNY: * mozna go wyliczyc, w tym wypadku wystarczylo by pobrac wszystkie Osoby z 'ekstensji' ObjectPlus * pobrac ich wzrost i wyliczyc srednia, ale prosciej to po prostu pamietac * i liczyc tylko raz przy dodawaniu osoby */ // atrybut prosty, pojedynczy, klasowy - potrzebny do liczenia sredniej private static int iloscOsob = 0; // konstruktor nie jest 'pusty', bo imieOsoby jest 'wymagane', wiec musi byc w kazdym konstruktorze Osoba(String imieOsoby, int wzrostOsoby) { /* * BARDZO WAZNE: kazdy konstruktor klasy dziedziczacej po klasie ObjectPlus musi wywolywac 'super()' * Co to jest 'super()'? * Jest to cos co odpali konstruktor w klasie 'wyzej' / 'u rodzica' czyli w ObjectPlus. * A co to robi? * To zapewnia, ze kazdy utworzony obiekt jest na liscie 'ekstensji' w ObjectPlus. * Konstruktor w ObjectPlus zajmuje sie dodawaniem/tworzeniem list ekstensji. */ super(); // tutaj dbamy, aby wymagany atrybut byl ustawiony, a nie wskazywal na 'null' if(imieOsoby == null) { throw new NullPointerException("Osoba musi miec imie"); } this.imie = imieOsoby; // 'int' nie moze byc 'nullem', wiec tego nie sprawdzamy // ale wymagamy podania tego w konstruktorze, wiec kazda osoba bedzie miala wpisany wzrost this.wzrost = wzrostOsoby; // to nam sie przyda do liczenia sredniej iloscOsob++; // a tu troche Drabikologi i mamy srednia sredniWzrost += (this.wzrost - sredniWzrost) / iloscOsob; } /* * PRZESLANIANIE METOD: * w nadklasie Osoba metoda ta zwraca tylko imie, * a w Student imie z dodanym na poczatku tekstem 'Student' * jaki tego sens? trudno mi wymyslic jakas sensowna przeslaniana funkcje * * technicznie: w klasie dziedziczacej jest metoda o takiej samej nazwie, takich samych argumentach, * ale zwraca cos innego */ public String getImie() { return this.imie; } /* * METODA KLASOWA: * metoda operujaca na zmiennych klasowych, a nie obiekcie * technicznie: typu static */ public static double getSredniWzrost() { return sredniWzrost; } /* * demonstracja roznicy w poslugiwaniu sie atrybutami 'wymaganymi' i 'opcjonalnymi' */ public void ustawImie(String imie) { if(imie == null) // uwaga wymagany! { throw new NullPointerException("Osoba musi miec imie"); } this.imie = imie; } public void ustawNazwisko(String nazwisko) { this.nazwisko = nazwisko; } public void ustawDateUrodzenia(Date dataUrodzenia) { this.dataUrodzenia = dataUrodzenia; } public String toString() { String ret = new String(); ret += "Imie: " + getImie(); ret += "\nNazwisko: "; if(nazwisko != null) // uwaga opcjonalny! ret += nazwisko; else ret += "bez nazwiska"; ret += "\nWzrost: " + wzrost; ret += "\nData urodzenia: "; if(dataUrodzenia != null) // uwaga opcjonalny! ret += dataUrodzenia; else ret += "nie znana"; return ret; } }
Student.java
import java.util.Vector; public class Student extends Osoba { /* wymagane do serializacji, w przyszlosci jak cos zmienisz w tej klasie [dodasz/usuniesz atrybut] to zmienisz ta liczbe na inna, dzieki temu mechanizm 'serialize' nie pozwoli zaladowac pliku z dysku z starymi danymi do programu ktory uzywa innej klasy (przeciez moze byc zupelnie inna klasa o nazwie Student i dane takie jak 'oceny' moga w niej nie wystepowac) */ private static final long serialVersionUID = 1L; // atrybut prosty, powtarzalny, obiektu private Vector<Double> oceny = new Vector<Double>(); /* * POWTARZALNY: * obiekt zawiera 0 lub wiecej takich 'elementow' * technicznie: lista/tablica */ Student(String imieOsoby, int wzrostOsoby) { /* * 'super', bo dziedziczy po klasie ktora dziedziczy po ObjectPlus * z parametrem 'imieOsoby' i 'wzrostOsoby', bo takie atrybuty sa wymagana w Osoba */ super(imieOsoby, wzrostOsoby); } /* * PRZESLANIANIE METOD: * w nadklasie Osoba metoda ta zwraca tylko imie, * a w Student imie z dodanym na poczatku tekstem 'Student' * jaki tego sens? trudno mi wymyslic jakas sensowna przeslaniana funkcje * * technicznie: w klasie dziedziczacej jest metoda o takiej samej nazwie, takich samych argumentach, * ale zwraca cos innego */ public String getImie() { return "Student " + this.imie; } /* * PRZECIAZANIE METOD: * metody maja taka sama nazwe, ale przyjmuja rozne parametry * w tym przypadku jedna 'Double', a druga 'int' */ public void dodajOcene(Double ocena) throws Exception { if(ocena == null || ocena < 2 || ocena > 5) { throw new Exception("Ocena musi byc pomiedzy 2, a 5"); } oceny.add(ocena); } public void dodajOcene(int ocena) throws Exception { if(ocena < 2 || ocena > 5) { throw new Exception("Ocena musi byc pomiedzy 2, a 5"); } oceny.add(new Double(ocena)); } public String toString() { // na poczatek opisu studenta wklejamy opis z Osoby (imie, nazwisko..) wywolujac metode z klasy // z ktorej dziedziczymy, robimy to uzywajac 'super' String ret = super.toString(); ret += "\nOceny: "; if(oceny.size() > 0) { for(Double ocena : oceny) { ret += ocena + ","; } } else { ret += "brak ocen"; } return ret; } }
ObjectPlus.java
import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.util.Hashtable; import java.util.Vector; /* * To jest klasa z wykladu nr 4 z drobnymi zmianami, zeby eclipse nie wywalal 'ostrzezen' * -------------------- * klasa zrobina przez wykladowce!, wiec raczej nie powinien sie czepiac * ale trzeba rozumiec KAZDY szczegol jej dzialania! * */ public class ObjectPlus implements Serializable { /* wymagane do serializacji, w przyszlosci jak cos zmienisz w tej klasie [dodasz/usuniesz atrybut] to zmienisz ta liczbe na inna, dzieki temu mechanizm 'serialize' nie pozwoli zaladowac pliku z dysku z starymi danymi do programu ktory uzywa innej klasy (przeciez moze byc zupelnie inna klasa o nazwie Student i dane takie jak 'oceny' moga w niej nie wystepowac) */ private static final long serialVersionUID = 1L; /* (w tym tlumaczeniu bede uzywal slowa 'tablica' zamiast 'lista', roznica? lista [z ktorej korzystamy pod nazwa Hashtable!] sama 'rosnie' jak do niej dodajemy obiekty, a tablice maja staly rozmiar np. 'new Integer[5]' - 5 elementow) Tlumaczenie typow: 1. Class<? extends ObjectPlus> - obiekt typu Class pobrany z obiektu ktory rozszerza ObjectPlus, czyli np. Osoba lub Student, String czy Integer nie rozszerzaja ObjectPlus, wiec nie zostana zaakceptowane 2. Vector<ObjectPlus> - lista/kontener obiektow typu ObjectPlus, do takiej listy mozna wsadzic dowolny obiekt ktory rozszerza ta klase, czyli np. Student czy Osoba Opis: To jest 'tablica tablic', a dokladniej tablica ktora jako klucz nie ma liczby, a.. KLASE (Class)! Class to o dziwo w Javie klasa ktora przechowuje informacje o klasie, mozna pobrac obiekt typu Class z kazdego obiektu w Javie uzywajac: Class klasaObiektu = mojObiekt.getClass(); No wiec mamy juz tablice ktora uzywa jako klucza Class, a jakie dane przechowuje? Przechowuje Vector<ObjectPlus>, czyli tablice obiektow typu ObjectPlus: 1. Osoba rozszerza ObjectPlus [extends], wiec tez moga ja wrzucic do tej tablicy 2. Student rozszerza Osoba ktora rozszerza ObjectPlus, wiec tez moge ja tam wrzucic A po co mi wogole tablica tablic zamiast zwyklej tablicy? Bo ObjectPlus w projekcie docelowym moze byc rozszerzany przez wiele obiektow roznych klas jak np. 'Wplata', 'Ocena', 'Przedmiot' itd., a nie chce mi sie pisac nowego ObjectPlus dla kazdej z nich Nie chce tez przechowywac wszystkich obiektow w jednej tablicy [typu Object, wtedy moge tam wrzucic wszystko], bo wtedy 'pobranie wszystkich 'Student' wymagalo by przegladania wszystkich elementow tablicy i sprawdzania ktorzy to Studenci. */ private static Hashtable<Class<? extends ObjectPlus>, Vector<ObjectPlus>> ekstensje = new Hashtable<Class<? extends ObjectPlus>, Vector<ObjectPlus>>(); /** * Konstruktor. */ public ObjectPlus() { Vector<ObjectPlus> ekstensja = null; Class<? extends ObjectPlus> klasa = this.getClass(); if(ekstensje.containsKey(klasa)) { // Ekstensja tej klasy istnieje w kolekcji ekstensji // jest juz jakis np. Student, wiec jest i lista studentow, nie chce tworzyc nowej listy, // tylko dodac nowego studenta do listy juz istniejacej ekstensja = ekstensje.get(klasa); } else { // Ekstensji tej klasy jeszcze nie ma -> dodaj ją // to wystepuje kiedy pierwszy raz dodajemy obiekt danego typu (np. Student) do ekstensji ekstensja = new Vector<ObjectPlus>(); ekstensje.put(klasa, ekstensja); } // a tu wreszcie dodaje studenta do listy nowej LUB istniejacej ekstensja.add(this); } /** * Zapisuje wszystkie ekstensje do podanego strumienia (wersja z serializacja). * Metoda klasowa. * @throws IOException */ public static void zapiszEkstensje(ObjectOutputStream stream) throws IOException { /* 'magia javy' zamienia obiekt (Hashmape) zawierajacy inne obiekty w tekst, wiec jak zawiera liste Studentow to Ci studenci maja np. atrybut 'Date dataUrodzenia' i to tez sie zapisze (Date jest 'serializable' jak wiekszosc klas uzywanych na codzien w javie) (wszystkie obiekty jakie zawiera ekstensja musza rozszerzac interfejs 'Serializable') java znajdzie wszystkie powiazane obiekty z tymi obiektami ktore mamy w hashmap 'ekstensje' i wszystkie powiazane z ich powiazaniami itd. i wszystko zapisze jako tekst! a potem jeszcze moze z tego tekstu odtworzyc ten obiekt [i obiekty powiazane], magia! UWAGA: to zapisze tylko zmienne 'obiektu', zmienne 'klasowe' (te z 'static') nie zostana zapisane i to jeden z problemow z takim prostym zapisem, ale mozna samemu dopisac zapis 'static' na szczescie to nie jest wymagane w MP_1, a jedynie w projekcie semestralnym */ stream.writeObject(ekstensje); } /** * Odczytuje wszystkie ekstensje z podanego strumienia (wersja z serializacja). * Metoda klasowa. * @throws IOException * @throws ClassNotFoundException */ @SuppressWarnings("unchecked") public static void odczytajEkstensje(ObjectInputStream stream) throws IOException, ClassNotFoundException { /* tutaj 'magia javy' odtwarza dane zapisane jako tekst do pliku (zapisane w funkcji wyzej) */ ekstensje = (Hashtable<Class<? extends ObjectPlus>, Vector<ObjectPlus>>) stream.readObject(); } /** * Wyswietla ekstensje. * Metoda klasowa. * @throws Exception */ public static void pokazEkstensje(Class<? extends ObjectPlus> klasa) throws Exception { /* wystarczy gdzies w programie wywolac ta funkcje tak: ObjectPlus.pokazEkstensje(Student.class); aby wyswietlic wszystkie obiekty typu 'Student' istniejace w programie */ Vector<ObjectPlus> ekstensja = null; if(ekstensje.containsKey(klasa)) { // Ekstensja tej klasy istnieje w kolekcji ekstensji ekstensja = ekstensje.get(klasa); } else { throw new Exception("Unknown class " + klasa); } System.out.println("Ekstensja klasy: " + klasa.getSimpleName()); for(Object obiekt : ekstensja) { System.out.println(obiekt + "\n"); } } }
Mam nadzieję, że będziecie przestrzegać instrukcji.
Wszystko w .zip:
1.15.
b*(a(bb)*)*
[nic, same 'b’, zaczyna sie na (’a’ lub 'b’) i po kazdym 'a’ parzysta liczba 'b’]
1.16.
(aa*(b(bb)*))*a* | ((b(bb)*)aa*)* | (b(bb)*)
[nic, same 'a’, zaczyna sie na 'a’ i konczy (na 'b’ lub na 'a’)] | [zaczyna sie na 'b’ i konczy na 'a’] | [zaczyna sie na 'b’ i konczy na 'b’]
1.17.
((a(aa)*) | (b(bb)*))* – nie jestem pewien czy to nie pusci parzystych
1.18.
(a*aabaaa*)*a*
[nic, same 'a’ lub do woli 'a’, ale conajmniej 2, potem 'b’ i do woli 'a’, ale conajmniej 2]
lub:
(aabaa | a)*
[nic, same 'a’ lub do woli 'a’, ale conajmniej 2 przed i po 'b’, a potem do woli 'a’]
1.19.
b* | b*a(bbba)*b*
[nic, same 'b’] | [zaczyna sie od 'b’ lub jednego 'a’, potem przed kazdym 'a’ jest 'bbb’, a potem do woli 'b’]
Treść zadania:
Mamy N procesów jednowątkowych uruchomionych w klastrze komputerów – na różnych węzłach. Procesy zorganizowane są w listę cykliczną. Między procesami „wędruje” token. Proces P, który ma token może się rozmnożyć jak chce, ale nie musi. Jak się rozmnoży to następny proces jest wstawiany do listy przed procesem P, a token wędruje sobie dalej. Jak lista ma 2*N procesów wówczas wszystkie procesy się kończą
Rozwiązanie może działać na paru węzłach (komputerach). Przykład (skrypt startowy) odpala program parę razy na jednym komputerze na różnych portach.
Kompilacja:
g++ zso3.cpp -o zso3
Skrypt startowy:
#!/bin/bash iloscProcesow=5 portPoczatkowy=12000 plik=zso3 iloscPortowMiedzyProcesami=$(($iloscProcesow*2+1)) ./$plik $portPoczatkowy 127.0.0.1 $(($iloscPortowMiedzyProcesami+$portPoczatkowy)) $iloscProcesow 0 & for i in `seq 1 $((iloscProcesow-2))` do ./$plik $(($i*$iloscPortowMiedzyProcesami+$portPoczatkowy)) 127.0.0.1 $((($i+1)*$iloscPortowMiedzyProcesami+$portPoczatkowy)) $iloscProcesow $i & done ./$plik $((($iloscProcesow-1)*$iloscPortowMiedzyProcesami+$portPoczatkowy)) 127.0.0.1 $portPoczatkowy $iloscProcesow $(($iloscProcesow-1)) &
Kod programu (usuń 'sleep’ żeby pkt. nie stracić 🙂 ):
/* Mamy N procesów jednowątkowych uruchomionych w klastrze komputerów – na różnych węzłach. Procesy zorganizowane są w listę cykliczną. Między procesami „wędruje” token. Proces P, który ma token może się rozmnożyć jak chce, ale nie musi. Jak się rozmnoży to następny proces jest wstawiany do listy przed procesem P, a token wędruje sobie dalej. Jak lista ma 2*N procesów wówczas wszystkie procesy się kończą */ #include <stdio.h> #include <unistd.h> #include <stdlib.h> #include <errno.h> #include <fcntl.h> #include <sys/signalfd.h> #include <signal.h> #include <semaphore.h> #include <sys/types.h> #include <sys/socket.h> #include <sys/un.h> #include <netinet/in.h> #include <arpa/inet.h> char wlasneIP[] = "127.0.0.1"; struct sockaddr_in adresDlaSocketuOczekujacegoNaPolaczenia, adresDlaSocketuDoWysylania, adresDlaSocketuKlienta; char errorBuffer[300]; int socketOczekujacyNaPolaczenia, socketDoWysylania, socketKlienta; int wielkoscPakietu; int iloscProcesowToken; int portDoNasluchiwania; char* targetIP; int portDoKtoregoMaWysylac; int iloscProcesowNaStarcie; int startowyNumerProcesu; void handle_error(const char* msg) { fprintf(stderr, "%s\n", msg); perror(NULL); close(socketOczekujacyNaPolaczenia); close(socketDoWysylania); close(socketKlienta); exit(EXIT_FAILURE); } void utworzSocketNasluchujacyNaPorcie(int port) { socketOczekujacyNaPolaczenia = socket(AF_INET, SOCK_STREAM, 0); if(socketOczekujacyNaPolaczenia == -1) { handle_error("Nie udalo sie utworzyc socketu nasluchujacego."); } int optval = 1; setsockopt(socketOczekujacyNaPolaczenia, SOL_SOCKET, SO_REUSEADDR, &optval, sizeof optval); bzero((char *) &adresDlaSocketuOczekujacegoNaPolaczenia, sizeof(adresDlaSocketuOczekujacegoNaPolaczenia)); adresDlaSocketuOczekujacegoNaPolaczenia.sin_family = AF_INET; adresDlaSocketuOczekujacegoNaPolaczenia.sin_addr.s_addr = INADDR_ANY; adresDlaSocketuOczekujacegoNaPolaczenia.sin_port = htons(port); if(bind(socketOczekujacyNaPolaczenia, (struct sockaddr *) &adresDlaSocketuOczekujacegoNaPolaczenia, sizeof(adresDlaSocketuOczekujacegoNaPolaczenia)) == -1) { sprintf(errorBuffer, "Nie udalo sie powiazac socketu nasluchujacego z INADDR_ANY na porcie %d.", port); handle_error(errorBuffer); } if(listen(socketOczekujacyNaPolaczenia, 2) == 1) { handle_error("Nie udalo sie rozpoczac nasluchiwania na sockecie."); } } void utworzPolaczenieDoWysylaniaTokenu(char* ip, int port) { socketDoWysylania = socket(AF_INET, SOCK_STREAM, 0); if(socketDoWysylania == -1) { handle_error("Nie udalo sie utworzyc socketu wysylajacego."); } bzero((char *) &adresDlaSocketuDoWysylania, sizeof(adresDlaSocketuDoWysylania)); adresDlaSocketuDoWysylania.sin_family = AF_INET; adresDlaSocketuDoWysylania.sin_addr.s_addr = inet_addr(ip); adresDlaSocketuDoWysylania.sin_port = htons(port); while(1) { if(connect(socketDoWysylania, (struct sockaddr *) &adresDlaSocketuDoWysylania, sizeof(adresDlaSocketuDoWysylania)) == -1) { if(errno != ECONNREFUSED) { sprintf(errorBuffer, "Nie udalo sie polaczyc z socketu wysylajacego do IP %s do portu %d.", ip, port); handle_error(errorBuffer); } else { fprintf(stderr, "Proba polaczenia z socketu wysylajacego do IP %s do portu %d nie powiodla sie, polaczenie odrzucone. Czekam chwile.\n", ip, port); } // 0.1 sec miedzy probami kolejnych polaczen usleep(100000); } else { break; } } fprintf(stderr, "Polaczono socket wysylajacy do IP %s na port %d z listenera %d.\n", ip, port, portDoNasluchiwania); } void czekajNaPolaczenie() { wielkoscPakietu = sizeof(struct sockaddr_in); socketKlienta = accept(socketOczekujacyNaPolaczenia,(struct sockaddr *) &adresDlaSocketuKlienta, (socklen_t*) &wielkoscPakietu); if(socketKlienta == -1) { handle_error("Akceptowanie polaczenia nie powiodlo sie."); } fprintf(stderr, "Klient z IP %s i portu %d\n", inet_ntoa(adresDlaSocketuKlienta.sin_addr), ntohs(adresDlaSocketuKlienta.sin_port)); } void wyslijToken() { int wyslaneBajty = 0; int intDoNeta = htonl(iloscProcesowToken); if((wyslaneBajty = send(socketDoWysylania, (const char*) &intDoNeta, 4, 0)) == -1 || wyslaneBajty != 4) { handle_error("Wysylanie inta sie nie powiodlo."); } fprintf(stderr, "Wyslano token %d\n", iloscProcesowToken); } void odbierzToken() { int odebraneBajty = 0; if((odebraneBajty = recv(socketKlienta, (void*) &iloscProcesowToken, 4, 0)) == -1 || odebraneBajty != 4) { handle_error("Odbieranie inta sie nie powiodlo."); } iloscProcesowToken = ntohl(iloscProcesowToken); fprintf(stderr, "Odebrano token %d\n", iloscProcesowToken); } int main(int argc, char *argv[]) { if(argc != 6) { handle_error("Program wymaga 5 parametrow."); } portDoNasluchiwania = atoi(argv[1]); targetIP = argv[2]; portDoKtoregoMaWysylac = atoi(argv[3]); iloscProcesowNaStarcie = atoi(argv[4]); startowyNumerProcesu = atoi(argv[5]); iloscProcesowToken = iloscProcesowNaStarcie; int startowyPortDoNasluchiwania = portDoNasluchiwania; // utworz socket oczekujacy na polaczenia utworzSocketNasluchujacyNaPorcie(portDoNasluchiwania); if(startowyNumerProcesu == 0) // pierwszy proces { // polacz sie z celem utworzPolaczenieDoWysylaniaTokenu(targetIP, portDoKtoregoMaWysylac); // czekaj na polaczenie czekajNaPolaczenie(); // wyslij do celu token (ilosc procesow) wyslijToken(); } else // inny niz pierwszy proces { // czekaj na polaczenie czekajNaPolaczenie(); // polacz sie z celem utworzPolaczenieDoWysylaniaTokenu(targetIP, portDoKtoregoMaWysylac); } while(1) { usleep(100000); // odbierz liczbe odbierzToken(); if(iloscProcesowToken >= iloscProcesowNaStarcie * 2) { // osiagnieto limit procesow, wyslij nastepnemu na liscie informacje o tym i zakoncz program usleep(100000); wyslijToken(); break; } if(rand() % 2 == 0) { // dodaj 1 proces do listy przed aktualnym procesem int wolnyPortDoKomunikacjiMiedzyDzieckiemRodzicem = startowyPortDoNasluchiwania + iloscProcesowToken; pid_t czyToDziecko = fork(); if(czyToDziecko == 0) // dziecko { portDoKtoregoMaWysylac = wolnyPortDoKomunikacjiMiedzyDzieckiemRodzicem; // polacz sie z rodzicem utworzPolaczenieDoWysylaniaTokenu(wlasneIP, portDoKtoregoMaWysylac); usleep(100000); } else // rodzic { portDoNasluchiwania = wolnyPortDoKomunikacjiMiedzyDzieckiemRodzicem; // utworz socket oczekujacy na polaczenie od dziecka utworzSocketNasluchujacyNaPorcie(portDoNasluchiwania); usleep(100000); // czekaj na polaczenie od dziecka czekajNaPolaczenie(); usleep(100000); // wprowadz nowa ilosc procesow na liscie iloscProcesowToken++; // wyslij token (liczbe procesow) wyslijToken(); usleep(100000); } } else { // wyslij token dalej wyslijToken(); usleep(100000); } } // zamykanie wszystkich socketow danego procesu close(socketKlienta); close(socketOczekujacyNaPolaczenia); close(socketDoWysylania); // komunikat na koniec fprintf(stderr, "Zamknieto sockety. ID startowe: %d, suma procesow: %d, nasluchiwal na porcie: %d, wysylal do: %d\n", startowyNumerProcesu, iloscProcesowToken, portDoNasluchiwania, portDoKtoregoMaWysylac); return 1; }
Niestety innych zadań trzecich nie mam. Sam 2 pierwsze zadania obroniłem na tyle punktów, że już trzeciego nie musiałem pisać.
Rok temu napisałem. Nie pamiętam polecenia, ale było za to dużo punktów.
Jest to klient DNS obsługiwany z linii poleceń (co ma robić przekazuje mu się jako argumenty). Klient skacze od DNS do DNS, aż znajdzie 'authority’ DNS lub wpadnie w pętle [wtedy się zatrzymuje]. Wykonuje on dużo operacji na bitach, aby przygotować/odczytać pakiet DNS, więc nie fajnie się to pisało.
Link do pobrania/przejrzenia kodu:
http://skalski.at/files/?dir=files/PJWSTK/SKJ_Klient_DNS
Opis użycia:
Do klienta mozna przekazac 3 parametry: -d=DOMENA-SZUKANA -t=TYP-ZAPYTANIA -ns=STARTOWY-DNS Obslugiwane typy: parametr (typ zapytania) 1 (A) 2 (NS) 5 (CNAME) 6 (SOA) 15 (MX) 16 (TXT) Przykladowe argumenty do programu (kolejnosc dowolna): java Main "-d=www.wp.pl" java Main "-d=www.wp.pl" "-t=1" java Main "-d=www.wp.pl" "-t=6" "-ns=62.233.233.233" Jerzy Skalski, WID324, s9473