Laboratorium programowania zad 11

Zadanie z laboratorium programowania na Informatyce UW.

Zadanie 11 (termin wysylania rozwiazan: 17 kwietnia 2008, godz. 23:59)

(Gra w Zycie)

Gra w Zycie jest symulacja dzialania automatu komorkowego.
Symulacje przeprowadzimy na prostokatnej planszy, ktorej
krawedzie sa ze soba "sklejone", tzn. idac w prawo z pola
znajdujacego sie na prawej krawedzi trafimy na pole krawedzi
lewej (i na odwrot) a idac w gore z pola na gornej krawedzi
trafimy na pole krawedzi dolnej (i na odwrot).

Kazda komorka planszy moze byc w jednym z dwoch stanow:
"zywa" lub "martwa". Na podstawie stanow komorek na planszy
liczymy ich stan w "nastepnej generacji" zgodnie z regulami:

* Jesli zywa komorka ma dwoch lub trzech zywych sasiadow,
  to pozostaje zywa, wpp. umiera.

* Jesli martwa komorka ma trzech zywych sasiadow, to staje sie
  zywa, wpp. pozostaje martwa.

Sasiadami komorki jest 8 komorek stykajacych sie z nia krawedzia
lub wierzcholkiem. Ze wzgledu na "sklejenie" krawedzi planszy,
kazda komorka ma dokladnie 8 sasiadow.

Napisz program, ktory wczyta z wejscia stan planszy i wypisze
na wyjscie stan planszy w nastepnej generacji.

Postac danych:

Na wejsciu programu znajdzie sie pewna liczba wierszy. W wierszach
beda znaki ' ' (spacja) i '#' oznaczajace odpowiednio komorke
martwa i zywa. Dlugosci wszystkich wierszy beda rowne.

Postac wyniku:

Program wypisze na wyjscie stan planszy w generacji nastepnej po
tej, ktora wczytal. Format wyniku ma byc identyczny z formatem
danych. Pozwoli to na przekazanie na wejscie programu jego wlasnego
wyniku i obliczanie w ten sposob kolejnych generacji.

Uwaga:

Nie wolno nakladac ograniczen na liczbe wierszy na wejsciu i dlugosc
kazdego wiersza. Wolno zalozyc, ze caly stan planszy zmiesci sie na
raz w pamieci.

Wskazowka:

Dane trzeba wczytywac znak po znaku, np. za pomoca funkcji getchar().

A oto rozwiązanie:

#include 
#include 
#include 

//Bedziemy przechowywac liczby w liscie dwuwymiarowej
typedef struct plansza_el{     
      int zywa;           
      struct plansza_el * lewy;
	  struct plansza_el * prawy;
	  struct plansza_el * gora;
	  struct plansza_el * dol;
	  
};



char wypisz (struct plansza_el* komorka)
{
	//Generuje znak bedacy oznaczeniem stanu komorki.
	int zywych; //liczba zywych sasiadow
	char stan;
	//gora,dol
	zywych=komorka->gora->zywa;
	zywych+=komorka->dol->zywa;
	//prawa,lewa
	zywych+=komorka->prawy->zywa;
	zywych+=komorka->lewy->zywa;
	//gora skos
	zywych+=komorka->gora->prawy->zywa;
	zywych+=komorka->gora->lewy->zywa;
	//dol skos
	zywych+=komorka->dol->prawy->zywa;
	zywych+=komorka->dol->lewy->zywa;

	
	if(komorka->zywa==1)
	{
		//Jesli zywa komorka ma dwoch lub trzech zywych sasiadow,to pozostaje zywa, wpp. umiera.
		if((zywych==2)||(zywych==3))
		{
			stan='#';
		}
		else
		{
			stan=' ';
		}
		
	}
	else
	{
		//Jesli martwa komorka ma trzech zywych sasiadow, to staje sie zywa, wpp. pozostaje martwa.
		stan=' ';
		
		if(zywych==3)
		{
			stan='#';
		}
	}

	return stan;

}



int main (int argc, char *argv[])
{
	int wynik,przejscie;
	struct plansza_el *start=NULL;
	struct plansza_el *wiersz=NULL;
	struct plansza_el *kolumna=NULL;
	struct plansza_el *teraz=NULL;
	char znak;

	//pierwsza komorka
	start=malloc(sizeof(struct plansza_el));
	start->prawy=NULL;
	start->lewy=NULL;
	start->gora=NULL;
	start->dol=NULL;

	teraz=start;
	wiersz=start;
	kolumna=NULL;
	przejscie=0;
	
	wynik=scanf("%c",&znak);

	if(znak=='#')
	{
		teraz->zywa=1;
	}
	else
	{
		teraz->zywa=0;
	}
	
	wynik=scanf("%c",&znak);
	
	while(wynik!=EOF)
	{
	//no i czytamy
	
		if((znak=='#')||(znak==' '))
		{
	
			if (przejscie==1)
			{
				//pierwszy znak po przejsciu do nowego wiersza.
				//wpierw 'zapinamy' poprzedni wiersz
				teraz->prawy=wiersz;
				wiersz->lewy=teraz;
				//tworzymy nowy wiersz
				wiersz->dol=malloc(sizeof(struct plansza_el));
				wiersz->dol->gora=wiersz;
				//zeby sledzic 'gory'
				kolumna=wiersz;
				wiersz=wiersz->dol;
				teraz=wiersz;
				teraz->lewy=NULL;
				teraz->prawy=NULL;
				teraz->dol=NULL;
				przejscie=0;
				
			}
			else
			{
				if (kolumna!=NULL)
				{
					//przesuwamy w poprzednim wierszu gore
					kolumna=kolumna->prawy;
				}

				teraz->prawy=malloc(sizeof(struct plansza_el));
				//pozycja prawy-lewy:
				teraz->prawy->lewy=teraz;
				teraz=teraz->prawy;
				teraz->prawy=NULL;
				//pozycja gora-dol
				teraz->dol=NULL;
				teraz->gora=kolumna;
				if(kolumna!=NULL)
				{
					//chyba ze pierwsza kolumna
					teraz->gora->dol=teraz;
				}
			}
			
			//wartosc:
			if(znak=='#')
			{
				teraz->zywa=1;
			}
			else
			{
				teraz->zywa=0;
			}
			
		}
		else if(znak=='n')
		{
			przejscie=1;
		}
		//no i mamy zabezpieczenie przed nieprawidlowymi znakami na wejsciu.
		wynik=scanf("%c",&znak);
	}
	
	//Teraz powinno byc wszystko ladnie wczytane. Trzeba jeszcze 'zapiac' ostatni wiersz i 'pozapinac' gory z dolami planszy.
	//ostatni wiersz:
	teraz->prawy=wiersz;
	wiersz->lewy=teraz;
	//gory z dolami:
	
	
	//dla pierwszej kolumny:
	teraz=start;
	teraz->gora=wiersz;
	wiersz->dol=teraz;
	teraz=teraz->prawy;
	wiersz=wiersz->prawy;
	
	while (teraz!=start)
	{
		teraz->gora=wiersz;
		wiersz->dol=teraz;
		teraz=teraz->prawy;
		wiersz=wiersz->prawy;
	}
	
	//Teraz plansza jest zapetlona. czas na wypisywanie.
	
	wiersz=start;
	
	while(wiersz!=NULL)
	{
		teraz=wiersz;
		while(teraz!=NULL)
		{
			printf("%c",wypisz(teraz));
			teraz=teraz->prawy;
			if(teraz==wiersz)
			{
				//warunek stopu
				teraz=NULL;
			}
		}
		
		wiersz=wiersz->dol;
		printf("n");
		if(wiersz==start)
		{
			//warunek stopu
			wiersz=NULL;
		}
	}

	
//A teraz sprzatamy po sobie:
	wiersz=start;
	
	while(wiersz!=NULL)
	{
		teraz=wiersz;
		while(teraz!=NULL)
		{
			kolumna=teraz;
			teraz=teraz->prawy;
			free(kolumna);
			if(teraz==wiersz)
			{
				//warunek stopu
				teraz=NULL;
			}
		}
		kolumna=wiersz;
		wiersz=wiersz->dol;
		free(kolumna);
		if(wiersz==start)
		{
			//warunek stopu
			wiersz=NULL;
		}
	}
	

return 1;
}

Programowanie obiektowe zad 1

Zadanie numer 1 z laboratorium programowania obiektowego

Laboratorium programowania obiektowego
Zadanie zaliczeniowe 1
termin oddawania rozwiazan: 16 kwietnia 2008

Lamiglowki z dopasowaniem krawedzi (ang. edge-matching puzzle)
polegaja na ukladaniu danego zbioru elementow tak, by elementy
sasiadujace pasowaly do siebie.

Istnieje wiele wariantow lamiglowek tego typu, rozniacych sie,
miedzy innymi, liczba wymiarow przestrzeni, w ktorej rozwiazujemy
lamiglowke. W przestrzeni trojwymiarowej zadaniem rozwiazujacego
jest skladanie trojwymiarowych "klockow". W przestrzeni
jednowymiarowej kazdy element ma maksymalnie dwoch sasiadow, jak
w grze w domino.

Najczesciej lamiglowki rozwiazywane sa w przestrzeni dwuwymiarowej,
czyli wymagaja ukladania elementow na plaszczyznie. Przykladem
takich lamiglowek sa popularne "puzzle", a takze Tetravex i
Eternity II.

W lamiglowce Tetravex kwadratowe elementy, ktorych jest n*n,
nalezy ulozyc na kwadratowej planszy o boku dlugosci n.
Spotyka sie warianty z plansza 2 na 2, 3 na 3, 4 na 4 itd.
Krawedzie kazdego elementu oznaczone sa cyframi dziesietnymi.
Dwa elementy moga ze soba sasiadowac, jesli na krawedziach,
ktorymi sie stykaja, sa te same cyfry. Np. na prawo od elementu,
ktory na prawej krawedzi ma cyfre "5" mozna polozyc tylko
element, ktory na lewej krawedzi ma "5".

Kazdy element Tetravex ma okreslona orientacje na planszy, tzn.
wiadomo, ktora krawedz ma byc u gory, ktora po prawej itd.
Inaczej mowiac, elementow Tetravex nie mozna obracac.

Lamiglowka Rotavex ma takie same zasady, jak Tetravex, ale pozwala
na obracanie elementow - kazdy mozna umiescic na planszy na cztery
rozne sposoby.

Moglibysmy tez rozwazac lamiglowke, ktorej elementy sa oznaczone
cyframi po obu stronach. Jej rozwiazanie wymagaloby ustalenia
nie tylko, gdzie ma byc dany element i jak go obrocic, lecz takze,
na ktora strone go odwrocic.

Zarowno Tetravex, jak i Rotavex, mozna tez rozwiazywac, poslugujac
sie elementami, ktorych krawedzie oznaczono nie cyframi, lecz
symbolami lub kolorami. Zasady rozwiazywania bylyby w tym wypadku
takie same.

Osoby rozwiazujace lamiglowki z dopasowaniem krawedzi staraja sie
ustalic pozycje poszczegolnych elementow na drodze dedukcji.
Podczas rozwiazywania Tetravex mozna np. zauwazyc, ze jesli jest
element, ktory na lewej krawedzi ma cyfre, ktora nie wystepuje na
prawej krawedzi zadnego innego elementu, to element ten musi sie
znalezc na lewej krawedzi planszy.

Innym sposobem rozwiazywania jest uzycie "metody prob i bledow",
tzn. umieszczanie na poszczegolnych polach planszy, na wszystkie
mozliwe sposoby, kolejnych elementow i sprawdzanie na biezaco,
czy aktualny element nie koliduje z tymi, ktore juz sa na planszy.

Ten sposob jest bardzo pracochlonny, ale jesli rozwiazywaniem
lamiglowki mialby sie zajmowac komputer, nie stanowi to problemu.
Zaleta tego sposobu rozwiazywania jest latwosc znalezienia
wszystkich rozwiazan lamiglowki, ktora ma wiecej niz jedno
rozwiazanie.

Na efektywnosc dzialania "metody prob i bledow" wplyw moze miec
kolejnosc wypelniania pol elementami. Robienie tego "losowo" raczej
nie jest dobrym pomyslem. Lepiej jest ukladac elementy wiersz po
wierszu, albo np. wypelniac nimi kolejne kwadraty o lewym gornym
wierzcholku w lewym gornym rogu planszy. W pierwszym przypadku, na
planszy 3 na 3, ukladalibysmy elementy na polach (1,1), (1,2), (1,3),
(2,1), (2,2) itd. W drugim przypadku kolejnosc pol bylaby nastepujaca:
(1,1), (1,2), (2,2), (2,1), (1,3), (2,3), (3,3), (3,2), (3,1).
Tu najpierw wypelnilismy kwadrat o boku 1 (czyli pole (1,1)),
nastepnie rozszerzylismy go do kwadratu o boku 2 (dodajac pola (1,2),
(2,2), (2,1)) a nastepnie 3.

Zbuduj w Smalltalku hierarchie klas pozwalajacych na reprezentacje
lamiglowek z dopasowaniem krawedzi i ich rozwiazywanie. Klasy nalezy
zdefiniowac tak, by bylo mozliwe wykonanie nastepujacego fragmentu
kodu z wynikiem zgodnym z komentarzami:

""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
s:=Set new.
s add: (
  ElementKwadratowyJednostronny
    gora:  (KrawedzZWartoscia new: 8)
    prawo: (KrawedzZWartoscia new: 1)
    dol:   (KrawedzZWartoscia new: 2)
    lewo:  (KrawedzZWartoscia new: 9)).
s add: (
  ElementKwadratowyJednostronny
    gora:  (KrawedzZWartoscia new: 0)
    prawo: (KrawedzZWartoscia new: 2)
    dol:   (KrawedzZWartoscia new: 4)
    lewo:  (KrawedzZWartoscia new: 3)).
s add: (
  ElementKwadratowyJednostronny
    gora:  (KrawedzZWartoscia new: 6)
    prawo: (KrawedzZWartoscia new: 9)
    dol:   (KrawedzZWartoscia new: 4)
    lewo:  (KrawedzZWartoscia new: 2)).
s add: (
  ElementKwadratowyJednostronny
    gora:  (KrawedzZWartoscia new: 2)
    prawo: (KrawedzZWartoscia new: 9)
    dol:   (KrawedzZWartoscia new: 4)
    lewo:  (KrawedzZWartoscia new: 8)).
s add: (
  ElementKwadratowyJednostronny
    gora   (KrawedzZWartoscia new: 0)
    prawo: (KrawedzZWartoscia new: 2)
    dol:   (KrawedzZWartoscia new: 2)
    lewo:  (KrawedzZWartoscia new: 5)).
s add: (
  ElementKwadratowyJednostronny
    gora:  (KrawedzZWartoscia new: 7)
    prawo: (KrawedzZWartoscia new: 9)
    dol:   (KrawedzZWartoscia new: 0)
    lewo:  (KrawedzZWartoscia new: 9)).
s add: (
  ElementKwadratowyJednostronny
    gora:  (KrawedzZWartoscia new: 4)
    prawo: (KrawedzZWartoscia new: 8)
    dol:   (KrawedzZWartoscia new: 0)
    lewo:  (KrawedzZWartoscia new: 7)).
s add: (
  ElementKwadratowyJednostronny
    gora:  (KrawedzZWartoscia new: 2)
    prawo: (KrawedzZWartoscia new: 1)
    dol:   (KrawedzZWartoscia new: 7)
    lewo:  (KrawedzZWartoscia new: 1)).
s add: (
  ElementKwadratowyJednostronny
    gora:  (KrawedzZWartoscia new: 4)
    prawo: (KrawedzZWartoscia new: 3)
    dol:   (KrawedzZWartoscia new: 8)
    lewo:  (KrawedzZWartoscia new: 2)).

"Na zmiennej 's' umiescilismy zbior dziewieciu elementow
dla Tetravex lub Rotavex"

l1:=Tetravex elementy: s.

"Na zmiennej 'l1' jest obiekt reprezentujacy lamiglowke
Tetravex o zadanym zbiorze elementow. Plansza jest rozmiaru
3 na 3, bo elementow bylo 9."

l2:=Rotavex elementy: s.

"Na zmiennej 'l2' jest obiekt reprezentujacy lamiglowke
Rotavex o tym samym zbiorze elementow."

l3:=Tetravex losowaOBoku: 4.

"Na zmiennej 'l3' znalazla sie lamiglowka Tetravex o planszy
4 na 4, wygenerowana losowo. Generujac lamiglowke nalezy
zadbac, by miala przynajmniej jedno rozwiazanie."

r1:=UkladanieWierszami new rozwiazanie: l1.

"Na zmiennej 'r1' znalazla sie reprezentacja rozwiazania
lamiglowki 'l1' znaleziona metoda prob i bledow, ukladajaca
poszczegolne elementy wierszami. Gdyby rozwiazanie nie
istnialo (tu istnieje), na 'r1' powinien byc nil. Reprezentacja
rozwiazania moze byc np. kolekcja elementow uporzadkowana
wg kolejnosci ich wystapienia na planszy."

r2:=UkladanieKwadratow new wszystkieRozwiazania: l1.

"Na zmiennej 'r2' jest kolekcja wszystkich rozwiazan lamiglowki
'l1', znalezionych metoda prob i bledow, ukladajaca poszczegolne
elementy w kolejnosci wypelniania kwadratow."

r3:=UkladanieWierszami new wszystkieRozwiazania: l2.

"Na zmiennej 'r3' jest kolekcja rozwiazan lamiglowki 'l2'
znalezionych metoda prob i bledow, ukladajaca elementy wierszami."

r4:=UkladanieKwadratow new rozwiazanie: l3.

"Na zmiennej 'r4' jest rozwiazanie lamiglowki 'l3' znalezione
metoda prob i bledow, ukladajaca elementy kwadratami."
""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""

Uwaga 1: zadanie trzeba rozwiazac obiektowo. Nalezy unikac powtarzania
kodu lub pisania wielokrotnie podobnych fragmentow.

Uwaga 2: hierarchia klas powinna umozliwiac latwe rozbudowywanie
systemu o inne lamiglowki i inne metody rozwiazywania.

Wskazowka: jesli chcemy miec gwarancje, ze wylosowana lamiglowka
bedzie miala rozwiazanie, nalezy ja wylosowac w stanie ulozonym.

Pytania do tresci zadania prosze kierowac na adres:

zaroda@mimuw.edu.pl

A oto rozwiązanie (Paczka do Dolphina Smalltalka):

zadanie_zaliczeniowe

Laboratorium programowania zad 10

Zadanie z laboratorium programowania na Informatyce UW.

Zadanie 10 (termin wysylania rozwiazan: 9 kwietnia 2008, godz. 23:59)

Seria bedziemy nazywali niepusty ciag liczb calkowitych wiekszych od zera.

Ciag serii bedziemy reprezentowali za pomoca ciagu liczb calkowitych, w
ktorym znajda sie kolejne elementy poszczegolnych serii ze znakiem
zaleznym od parzystosci numeru serii. Elementy pierwszej serii zapiszemy
jako liczby dodatnie, elementy drugiej serii jako ujemne, trzeciej
dodatnie itd. Po ostatnim elemencie ostatniej serii ma byc zero.

Np. ciag szesciu serii: 3 1 5, 4, 1 6, 1 6, 8 2, 4 bedzie reprezentowany
przez ciag liczb:

3
1
5
-4
1
6
-1
-6
8
2
-4
0

Napisz program, ktory wczyta z wejscia liczby calkowite reprezentujace
ciag serii i wypisze na wyjscie reprezentacje ciagu serii powstalego z
ciagu danego przez pominiecie tych serii, ktore sa identyczne z seriami
bezposrednio je poprzedzajacymi. Kazda liczbe reprezentacji ciagu serii
nalezy wypisac w oddzielnym wierszu.

Np. dla danych zapisanych powyzej program powinien wypisac na wyjscie:

3
1
5
-4
1
6
-8
-2
4
0

Uwaga: w rozwiazaniu wolno zalozyc, ze w pamieci zmieszcza sie na raz
dwie sasiadujace w ciagu serie. Nie wolno jednak nakladac zadnego
ograniczenia na dlugosc ciagu serii ani na dlugosc pojedynczej serii.

Wskazowka: serie mozna przechowywac w tworzonej dynamicznie (za pomoca
funkcji malloc) tablicy liczb calkowitych. Gdyby okazalo sie, ze utworzona
tablica jest zbyt mala, by zmiescic cala wczytywana serie, tworzymy
tablice dwa razy wieksza.

A oto rozwiązanie:

#include 
#include 
#include 

//Bedziemy przechowywac liczby w liscie dwuwymiarowej
typedef struct liczba_el{     
      int var;           
      struct liczba_el * nastepny; 
};


struct seria_el {
      struct liczba_el * liczba;    
      struct seria_el* nastepny; 
};

int porownaj (struct seria_el* pier,struct seria_el* dr)
{
//porownuje serie czy sa takie same

int rowne;
struct liczba_el* pierwszy;
struct liczba_el* drugi;
	rowne=0;
	
	if ((pier!=NULL)&&(dr!=NULL))
	{
		pierwszy=pier->liczba;
		drugi=dr->liczba;
		rowne=1;

		
		while((pierwszy!=NULL)&&(drugi!=NULL)&&(rowne==1))
		{
			if (pierwszy->var==drugi->var)
			{
				pierwszy=pierwszy->nastepny;
				drugi=drugi->nastepny;
			}
			else
			{
				rowne=0;
			}
			
		}

		if ((rowne==1)&&(pierwszy!=drugi))
		{
			//Sprawdzenie czy koncza sie oba w tym samym miejscu
			rowne=0;
		}
	}
	return rowne;
}

int bezwzgl(int liczba)
{
//Liczy wartosc bezwzgledna
	if (liczbaliczba=malloc(sizeof(teraz_liczba));
	start->nastepny=NULL;
	start->liczba->nastepny=NULL;
	teraz_seria=start;
	teraz_liczba=start->liczba;
	
	wynik=scanf("%d",&liczba);

	teraz_liczba->var=bezwzgl(liczba);			//
	poprzednia=liczba;
	wynik=scanf("%d",&liczba);
	
	

	while(wynik!=EOF)
	{
	
	
		if((liczba*poprzednia) liczba=NULL;
			}
			else
			{
				//nowa seria
				teraz_seria->nastepny=malloc(sizeof(start));
				poprzednia_seria=teraz_seria;
				teraz_seria=teraz_seria->nastepny;
			}
			teraz_seria->liczba=malloc(sizeof(tmp_liczba));
			teraz_liczba=teraz_seria->liczba;
			teraz_liczba->nastepny=NULL;
			teraz_seria->nastepny=NULL;
			teraz_liczba->var=bezwzgl(liczba);		//
		}
		else
		{
			//Nowa liczba w serii.
			teraz_liczba->nastepny=malloc(sizeof(teraz_liczba));
			teraz_liczba=teraz_liczba->nastepny;
			teraz_liczba->var=bezwzgl(liczba);		//
		}
		poprzednia=liczba;
		wynik=scanf("%d",&liczba);
		
		

	}

//I teraz trzeba wypisac!!
	
	mnoznik=1;

	teraz_seria=start;
	while(teraz_seria!=NULL)
	{
		teraz_liczba=teraz_seria->liczba;
		while(teraz_liczba!=NULL)
		{
			//Zwyczajnie wypisujemy
			printf("%dn",((teraz_liczba->var)*mnoznik));
			tmp_liczba=teraz_liczba;
			teraz_liczba=teraz_liczba->nastepny;
			free(tmp_liczba);
		}
		
		//czyscimy
		start=teraz_seria;
		teraz_seria=teraz_seria->nastepny;
		free(start);
		//Naprzemiennie ustawiamy mnoznik
		mnoznik=mnoznik*-1;
	}

return 1;
}

Systemy Rozproszone Zad 1

Takie zadanie dostaliśmy na laboratorium systemów rozproszonych:

Napisać serwer obsługujący grę w kółko i krzyżyk. Użytkownik jako programu klienta używa programu telnet.
Komunikacja między klientem a serwerem odbywa się za pomocą protokołu TCP przez wymianę tekstów.
Serwer wysyła do klienta w trybie tekstowym aktualną sytuację na planszy. Klient wysyła swoje ruchy też w postaci tekstowej.

Serwer po odebraniu połączenia od klienta oczekuje pewien ustalony czas i jeśli w tym czasie zgłosi się drugi klient, to serwer łączy tych klientów w parę, rozgrywającą partię między sobą.
Serwer jest wtedy pośrednikiem w tej grze. Jeśli w zadanym czasie nie zgłosi się drugi klient, to serwer przejmuje jego rolę i staje się partnerem w grze. Jeśli w czasie gry któryś z pary graczy rozłączy się, to serwer i w tym przypadku przejmuje jego rolę i kontynuuje grę za niego. Komunikacja między klientem a serwerem powinna być identyczna niezależnie od tego, czy klient gra z serwerem, czy z innym klientem.

Serwer musi móc równocześnie obsługiwać wielu pojedynczych klientów i wiele par klientów. Serwer powinien być odporny na różne złośliwe zachowania klienta: dane niezgodne z oczekiwanymi, nagłe zerwanie połączenia itp. Serwer utrzymuje wszystkie niezbędne informacje o wszystkich rozgrywanych w danym momencie grach. Serwer musi dbać o zwalnianie zasobów po odłączeniu się klienta. Program powinien być napisany w C lub C++ z użyciem interfejsu gniazd.

Gra jest tylko pretekstem dla implementacji komunikacji sieciowej i serwer nie musi implementować żadnej rozsądnej strategii. Serwer może grać w sposób zupełnie przypadkowy, byle zgodnie z zasadami gry. Serwer powinien jakoś reagować na niepoprawne zagrania klienta.

A oto rozwiązanie:

#include 
#include  
#include 
#include 
#include 
#include 


int plansza[3][3];	//Dla planszy
int polaczony;		//Czy klient 2 jest podlaczony
int newsockfd2;		//Socket klienta 2

void gra(int,int);

void error(char *msg)
{
    perror(msg);
    exit(1);
}


void* thr(void *sockfd)
{
	//Tworzy watek podlaczajacy klienta.
	int *sock;
	int clilen2,sock2;
	struct sockaddr_in cli2_addr;
	printf("Startuje watekn");
	sock=(int *)sockfd;
	sock2=*sock;
    newsockfd2 = accept(sock2, 
        (struct sockaddr *) &cli2_addr, &clilen2);
    if (newsockfd2 < 0) 
        error("BLAD podczas accept klienta 2 n");
	printf("Klient podlaczonyn");
	polaczony=1;
}

int main(int argc, char *argv[])
{
     int sockfd,sockfd2, newsockfd, portno, clilen, pid,watek,i;
     struct sockaddr_in serv_addr, cli_addr, cli2_addr;
	 pthread_t tr;

	printf("Startujemy serwer n");
	 polaczony=0;
	 //Budujemy serwer:
     if (argc < 2) {
         fprintf(stderr,"BLAD, brak portu.n");
         exit(1);
     }
     sockfd = socket(AF_INET, SOCK_STREAM, 0);
     if (sockfd < 0) 
        error("BLAD otwierajac socket n");
     bzero((char *) &serv_addr, sizeof(serv_addr));
     portno = atoi(argv[1]);
     serv_addr.sin_family = AF_INET;
     serv_addr.sin_addr.s_addr = INADDR_ANY;
     serv_addr.sin_port = htons(portno);
	 //Bind i sluchamy:
     if (bind(sockfd, (struct sockaddr *) &serv_addr,
              sizeof(serv_addr)) < 0) 
              error("ERROR on binding");
     listen(sockfd,5);
     clilen = sizeof(cli_addr);
	 
	 //Petla.  Czekamy na przychodzace polozenia.
     while (1) {
		//Podlaczenie klienta 1.
		
		if(polaczony==0)
		{
			watek = pthread_create( &tr, NULL,thr, (void*) &sockfd);
			while(polaczony==0)
			{
				sleep(1);
			}
		}
		newsockfd=newsockfd2;
		polaczony=0;
		
		//Podlaczenie klienta 2.
		watek = pthread_create( &tr, NULL,thr, (void*) &sockfd);
		/////////////////////
		
		for (i=0;i<10;i++)
		{
			if(polaczony==0)
			{
				sleep(1);
			}
			else
			{
				break;
			}
		}
		

		//No i oddzielamy od glownego procesu.
         pid = fork();
         if (pid < 0)
             error("BLAD podczas fork. n");
         if (pid == 0)  {
			//Stary proces.
			//Zamykamy niepotrzebne gniazdo.
             close(sockfd);
			//Zaczynamy gre,
             gra(newsockfd,newsockfd2);
             exit(0);
         }
         else close(newsockfd);
     }
     return 0;
}

/*****************GRA*********************
Tu sie zaczyna sama gra,
 *****************************************/
 
int wypisz(char wynik[15])
{
	//Funkcja sprawdza wynik, wypisuje co trzeba.
	int i,j,zwr,wolnych;
	zwr=0;
	wolnych=0;
	
	
	//sprawdczamy czy sa wolne miejsca na planszy
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(plansza[i][j]==0)
			{
				wolnych++;
			}
		}
	}
	
	if(wolnych==0)
	{
		zwr=-1;
	}
	
	//sprawdzamy w wierszach
	for(i=0;i0))
			zwr=plansza[i][2];
			
	}
	
	//W kolumnach
	for(i=0;i0))
			zwr=plansza[2][i];
	}
	
	//W skosach
	if((plansza[0][0]==plansza[1][1])&&(plansza[1][1]==plansza[2][2])&&(plansza[2][2]>0))
		zwr=plansza[2][2];
		
	if((plansza[0][2]==plansza[1][1])&&(plansza[1][1]==plansza[2][0])&&(plansza[2][0]>0))
		zwr=plansza[2][0];

		
	//Koniec sprawdzania wyniku.
	
	/*if(zwr==-1)
	{
		wynik=" NIEROZEGRANErn";
	}
	else if(zwr==1)
	{
		wynik="Gre wygral Xrn";
	}
	else if(zwr==2)
	{
		wynik="Gre wygral Orn";
	}
	else
	{*/
	
		//Wypisujemy wynik
		for(i=0;i<3;i++)
		{
			for(j=0;j<3;j++)
			{
				if(plansza[i][j]==0)
				{
					wynik[(i)*5+j]=' ';
				}
				else if(plansza[i][j]==1)
				{
					wynik[(i)*5+j]='X';
				}
				else if(plansza[i][j]==2)
				{
					wynik[(i)*5+j]='O';
				}
			}
			wynik[(i)*5+3]='r';
			wynik[(i)*5+4]='n';		
		}
	//}
	return zwr;
}


// 'Sztuczna inteligencja' na poziomie wspolczesnego gimnazjalisty. Wstawia w pierwsze wolne miejsce.
int AIruch(int gracz)
{
	int i,j;
	i=0;
	j=0;
	
	while((plansza[i][j]!=0)&&(i2)
		{
			j=0;
			i++;
		}
	}
	
	if(i<3)
	{
		plansza[i][j]=gracz;
	}
	
	return 0;
}


 
void gra (int sock,int sock2)
{
	//Sama gra.
   int i,j,n;
   char buffer[256];
   char wynik[15];
	int ruch;
	int rozgrywka;
	int dwoch;
	
	//Init
   	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			plansza[i][j]=0;
		}
	}
	
	rozgrywka=0;
	dwoch=1;
	
   
   //Dopoki gra sie nie skonczyla
	while(rozgrywka==0)
	{
	// Kolejne ruchy.
		write(sock,"Nowa tura graczu X rn",21);
		write(sock2,"Nowa tura graczu O rn",21);
		
		//Dopoki nie wykonany prawidlowefggo ruchu
		ruch=0;
		while(ruch==0)
		{

			j=5;
			i=5;
			
			//Dopoki nie wpisano prawidlowego znaku
			while((i2))
			{
				bzero(buffer,256);
				write(sock,"Wpisz wiersz graczu X rn",24);
				read(sock,buffer,256);
				i=0;
				while((i<256)&&((buffer[i]'3')))
				{
						i++;
				}
				
				i=buffer[i]-49;
			}
			
			//Wopoki nie dobry znak
			while((j2))
			{
				bzero(buffer,256);
				write(sock,"Wpisz kolumne graczu X rn",25);
				read(sock,buffer,256);
				j=0;
				while((j<256)&&((buffer[j]'3')))
				{
						j++;
				}
				j=buffer[j]-49;
			}
		
			//Wykonujemy ruch.
			if(plansza[i][j]==0)
			{
				plansza[i][j]=1;
				ruch=1;
			}
		}
		
		rozgrywka=wypisz(wynik);
		ruch=0;
		
		//Jesli klient 2 jest podlaczony
		if(polaczony==1)
		{
			
			//I tak samo.
			while((ruch==0)&&(rozgrywka==0))
			{
				write(sock2,wynik,15);
				i=5;
				while((i2))
				{
					bzero(buffer,256);
					write(sock2,"Wpisz wiersz graczu O rn",24);
					read(sock2,buffer,256);
					i=0;
					while((i<256)&&((buffer[i]'3')))
					{
							i++;
					}
					
					i=buffer[i]-49;
				}
				


				j=5;
				while((j2))
				{
					bzero(buffer,256);
					write(sock2,"Wpisz kolumne graczu O rn",25);
					read(sock2,buffer,256);
					j=0;
					while((j<256)&&((buffer[j]'3')))
					{
							j++;
					}
					j=buffer[j]-49;
				}
			
				//Wykonujemy ruch.
				if(plansza[i][j]==0)
				{
					plansza[i][j]=2;
					ruch=1;
				}
				
				
			}//Ruchy wykonane.
		}
		else
		{
		//Jesli klient 2 nie podlaczony - intelygencyja
			AIruch(2);
		}
		
		rozgrywka=wypisz(wynik);
		write(sock,wynik,15);
	}
	
	write(sock,wynik,15);
	if(polaczony==1)
	{
	write(sock,wynik,15);
	}
	printf("Gra skonczona - wynik: [%i]n%sn",rozgrywka,wynik);
}





Laboratorium programowania zad 9

Zadanie z laboratorium programowania na Informatyce UW.

Zadanie 9 (termin wysylania rozwiazan: 14 III 2008, godz. 23:59)

(Poziomy drzewa)

Napisz program, ktory wczyta z wejscia ciag napisow, z ktorych
kazdy bedzie zajmowal jeden wiersz, utworzy z nich drzewo BST,
a nastepnie wypisze to drzewo poziomami.

Kolejne napisy wczytywane z wejscia program bedzie wstawial
do drzewa BST, przechodzac do lewego poddrzewa, jesli wstawiany
napis jest "<=" (w porzadku leksykograficznym) od napisu
w aktualnym wezle, wpp. przechodzac do prawego poddrzewa.

Po utworzeniu drzewa, program powinien je wypisac na wyjscie
poziomami - w pierwszym wierszu nalezy wypisac napis z korzenia,
w drugim napisy jego synow itd. Lacznie program wypisze tyle
wierszy, ile jest niepustych poziomow w drzewie.

Na i-tym poziomie jest 2^i pozycji, na ktorych moze sie znalezc
wezel. Program powinien wypisac zawartosc kazdej pozycji.
Jesli jest na niej wezel, wypisujemy napis, ktory sie w nim
znajduje, oraz jedna spacje. Jesli na danej pozycji poziomu
nie ma wezla, program wypisuje pare nawiasow okraglych i jedna
spacje.

Np. dla danych:

kota
ala
miec
by
chciala

program powinien wypisac:

kota 
ala miec 
() by () () 
() () () chciala () () () () 

A oto rozwiązanie:

program zad8;
type

	drzewo_t=^drzewo_r_t;
	drzewo_r_t=record
		prawy:drzewo_t;
		lewy:drzewo_t;
		napis:string;
	end;
	
	//Tutaj beda przechowywane napisy
	napis_t=^napis_r_t;
	napis_r_t=record
		nastepny:napis_t;
		wezel:drzewo_t;
	end;
	
	//A tu cale wiersze
	wiersz_t=^wiersz_r_t;
    wiersz_r_t=record 
		lisci:integer; //niepustych lisci
		nastepny:wiersz_t;
		napis:napis_t; //Pierwszy plik
	end;


	procedure spacer(wezel:drzewo_t;poziom:wiersz_t);
	var teraz:napis_t;
	begin
		if (wezelnil) then
		begin
			if (poziom^.napis=nil) then
			begin
				new(poziom^.napis);
				teraz:=poziom^.napis;
				teraz^.nastepny:=nil;
			end
			else
			begin
				teraz:=poziom^.napis;
				while teraz^.nastepnynil do
					teraz:=teraz^.nastepny;
				new(teraz^.nastepny);
				teraz:=teraz^.nastepny;
				teraz^.nastepny:=nil;
			end;
			
			teraz^.wezel:=wezel;
			
			if wezel^.napis'()' then
				poziom^.lisci+=1;
			
			if poziom^.nastepny=nil then
			begin
				new(poziom^.nastepny);
				poziom^.nastepny^.nastepny:=nil;
				poziom^.nastepny^.napis:=nil;
				poziom^.nastepny^.lisci:=0;
			end;
			
			//No i rekurencja:
			
			spacer(wezel^.lewy,poziom^.nastepny);
			spacer(wezel^.prawy,poziom^.nastepny);
			
		end;
	end;
	
var wiersz:string;
teraz,drzewo:drzewo_t;
lista,teraz_lista:wiersz_t;
napis:napis_t;

begin

	if not EOF then
	begin

		readln(wiersz);
		
		new(drzewo);
		new(drzewo^.lewy);
		new(drzewo^.prawy);
		drzewo^.lewy^.lewy:=nil;
		drzewo^.lewy^.prawy:=nil;
		drzewo^.lewy^.napis:='()';
		drzewo^.prawy^.lewy:=nil;
		drzewo^.prawy^.prawy:=nil;
		drzewo^.prawy^.napis:='()';
		drzewo^.napis:=wiersz;
		
		while not EOF do
		begin
			readln(wiersz);
			teraz:=drzewo;
			
			while teraz^.napis'()' do
			begin
				if wiersz > teraz^.napis then
					teraz:=teraz^.prawy
				else
					teraz:=teraz^.lewy;
			end;
			
			teraz^.napis:=wiersz;
			new(teraz^.lewy);
			new(teraz^.prawy);
			teraz^.lewy^.lewy:=nil;
			teraz^.lewy^.prawy:=nil;
			teraz^.lewy^.napis:='()';
			teraz^.prawy^.lewy:=nil;
			teraz^.prawy^.prawy:=nil;
			teraz^.prawy^.napis:='()';
			
		end;
		//Teraz powinismy miec wszystko w drzewie.

		new(lista);
		lista^.nastepny:=nil;
		lista^.napis:=nil;
		lista^.lisci:=0;
				
		spacer(drzewo,lista);
		//Teraz wszystko przygotowane do wypisania.
//to wymaga przejrzenia:

	
		teraz_lista:=lista;
		while teraz_lista^.nastepnynil do
		begin
		
			if	(teraz_lista^.lisci>0) then
			begin
				napis:=teraz_lista^.napis;
				while napis^.nastepnynil do
				begin
					write(napis^.wezel^.napis);
					
					if (napis^.wezel^.napis'') then
						write(' ');
					
					//sprzatamy:
					//tmp_napis:=napis;
					napis:=napis^.nastepny;
					//dispose(tmp_napis);
				end
			end;
			//usuwamy straznika:
			
			writeln();
			
			//Sprzatamy:
			//tmp_teraz_lista:=teraz_lista;
			teraz_lista:=teraz_lista^.nastepny;
			//dispose(tmp_teraz_lista);
		end;
		dispose(teraz_lista);
		//usuwamy straznika
	end
end.

Laboratorium programowania zad 8

Zadanie z laboratorium programowania na Informatyce UW.

Zadanie 8 (termin wysylania rozwiazan: 7 III 2008, godz. 23:59)

(Grupowanie plikow)

Napisz program, ktory wczyta z wejscia informacje o plikach i podzieli
te pliki na grupy tak, by laczny rozmiar plikow w jednej grupie nie
przekroczyl 700 (megabajtow).

Postac danych:

Na wejsciu programu jest ciag wierszy, z ktorych kazdy opisuje jeden
plik. W wierszu jest kolejno:

- liczba calkowita wyrazajaca rozmiar pliku (w megabajtach)
- jedna spacja
- nazwa pliku (wolno zalozyc, ze moze byc wartoscia typu string)

Postac wyniku:

Program powinien wypisac tyle wierszy, ile grup plikow utworzy.
W kazdym maja sie znalezc nazwy plikow, ktore trafily do danej
grupy, z zachowaniem kolejnosci, w jakiej pliki pojawily sie
na wejsciu. Po kazdej nazwie pliku wypisujemy jedna spacje.

Algorytm:

Program wczytuje z wejscia informacje o kolejnych plikach i dla
kazdego szuka pierwszej grupy, do ktorej plik ten sie zmiesci. Robi
to, przechodzac po utworzonych do tej pory grupach w kolejnosci, w
jakiej te grupy powstawaly. Jesli plik nie miesci sie w zadnej z
dotychczas powstalych grup, tworzymy nowa.

Pliki o rozmiarze przekraczajacym 700 program powinien zignorowac.

Np. dla danych:

400 jeden
10 dwa
300 trzy
500 cztery
111 piec
2222 szesc
222 siedem
1 osiem
10 dziewiec
200 dziesiec

program powinien wypisac:

jeden dwa piec osiem dziewiec 
trzy siedem 
cztery dziesiec 

Wskazowka:

W rozwiazaniu nalezy zbudowac liste grup, a z kazda grupa zwiazac
liste plikow, ktore przydzielilismy do tej grupy.

A oto rozwiązanie:

program zad8;
type

	//Struktura danych to lista dwuwymiarowa. 

	//Tutaj beda przechowywane pliki
	plik_t=^plik_r_t;
	plik_r_t=record
		nastepny:plik_t;
		nazwa:string;
		rozmiar:integer;
	end;
	
	//A tu cale wiersze
	grupa_t=^grupa_r_t;
    grupa_r_t=record 
		wolne:integer; //Wolne miejsce w grupie
		nastepny:grupa_t;
		plik:plik_t; //Pierwszy plik
		ostatni:plik_t;
	end;


var rozmiar:integer;
nazwa:string;
plik,tmp_plik: plik_t;
grupa,pierwszy,tmp_grupa:grupa_t;
znaleziono:boolean;
spacja:char;
begin



	//Tworzymy pierwsza grupe

	new(pierwszy);
	pierwszy^.nastepny:=nil;
	grupa:=pierwszy;
	grupa^.wolne:=700;

	new(grupa^.plik);
	plik:=grupa^.plik;
	plik^.nastepny:=nil;
	plik^.nazwa:='';
	grupa^.ostatni:=plik;
	
	
	//Wczytujemy pliki
	while not EOF do
	begin
		read(rozmiar);
		read(spacja);
		read(nazwa);
		znaleziono:=false;
		grupa:=pierwszy;
		
		//write('Umieszczamy plik "');
		//write(nazwa);
		//write('" o rozmiarze ');
		//write(rozmiar);
		
		if rozmiar<701 then
		begin
			while ((grupa^.nastepny  nil) AND (znaleziono=false))  do
			begin
				//Dla kazdej grupy przechowujemy ilosc wolnego miejsca. dzieki temu nie musimy biegac po tej liscie.
				if ((grupa^.wolne >= rozmiar) AND (znaleziono=false)) then
				begin
					//writeln('    OK. jest grupa z ');
					//write(grupa^.wolne);
					//write(' miejsca');
					//Znalezlismy grupe w ktorej jest wystarczajaco miejsca
						grupa^.ostatni^.nazwa:=nazwa;
						grupa^.ostatni^.rozmiar:=rozmiar;
						new(grupa^.ostatni^.nastepny);
						grupa^.ostatni:=grupa^.ostatni^.nastepny;
						grupa^.ostatni^.nastepny:=nil;
						grupa^.wolne:=grupa^.wolne-rozmiar;
					//Zeby nie wstawiac pliku kilka razy:
					znaleziono:=true;
				end
				else
				begin
					//writeln('    w tej grupie jest za malo. tylko ');
					//write(grupa^.wolne);
					//write(' miejsca');
					grupa:=grupa^.nastepny;
				end
			end;
			
			if (znaleziono=false) then
			begin
				grupa^.wolne:=700-rozmiar;

				//wstawiamy plik:
				
				new(grupa^.plik);
				grupa^.plik^.nazwa:=nazwa;
				grupa^.plik^.rozmiar:=rozmiar;
				
				//Wstawiamy strażnika
				
				new(grupa^.plik^.nastepny);
				grupa^.plik^.nastepny^.nastepny:=nil;
				grupa^.plik^.nastepny^.rozmiar:=0;
				grupa^.plik^.nastepny^.nazwa:='';
				grupa^.ostatni:=grupa^.plik^.nastepny;

				//I straznika dla grupy
				new(grupa^.nastepny);
				grupa:=grupa^.nastepny;
				grupa^.nastepny:=nil;

			end
		end
	end;
	//I pliki wczytane. Wystarczy wypisac.

	
	grupa:=pierwszy;
	while grupa^.nastepnynil do
	begin
		plik:=grupa^.plik;
		while plik^.nastepnynil do
		begin
			write(plik^.nazwa);
			
			if (plik^.nazwa'') then
				write(' ');
			
			//sprzatamy:
			tmp_plik:=plik;
			plik:=plik^.nastepny;
			dispose(tmp_plik);
		end;
		//usuwamy straznika:
		dispose(plik);
		
		writeln();
		
		//Sprzatamy:
		tmp_grupa:=grupa;
		grupa:=grupa^.nastepny;
		dispose(tmp_grupa);
	end;
	dispose(grupa);
	//usuwamy straznika
end.

Laboratorium programowania zad 7

Zadanie 2 z laboratorium programowania na Informatyce UW.

Zadanie 7 (termin wysylania rozwiazan: 29 II 2008, godz. 23:59)

(Kolumny)

Napisz program, ktory wczyta z wejscia tekst i wypisze ten tekst na
wyjscie w dwoch kolumnach rozdzielonych spacja, znakiem kreski pionowej |
i jeszcze jedna spacja.

Jesli liczba wierszy tekstu (N) jest parzysta, w pierszej kolumnie znajdzie
sie kolejno N/2 pierwszych wierszy, a w drugiej N/2 nastepnych. Jesli liczba
wierszy jest nieparzysta, srodkowy wiersz nalezy umiescic na koncu kolumny
pierwszej.

Spacje, kreske i spacje rozdzielajace kolumny nalezy wypisac w tym samym
miejscu kazdego wiersza. Znaki te powinny sie znalezc bezposrednio za koncem
najdluzszego wiersza pierwszej kolumny. Krotsze wiersze pierwszej kolumny
nalezy uzupelnic na koncu odpowiednia liczba spacji.

Np. dla danych:

ala ma kota
to jest kot ali
ela ma psa
azor to pies eli
ola nie ma psa

program powinien wypisac:

ala ma kota     | azor to pies eli
to jest kot ali | ola nie ma psa
ela ma psa      | 

Uwaga:

Wolno zalozyc, ze wiersze tekstu wejsciowego nie sa bardzo dlugie i moga byc
wartoscia typu string. Nie wolno nakladac ograniczenia na liczbe wierszy na
wejsciu.

Wskazowka:

Przed rozpoczeciem wypisywania, tekst z wejscia nalezy wczytac do listy,
ktorej kazdy wezel bedzie przechowywal w polu typu string zawartosc jednego
wiersza.

A oto rozwiązanie:

program zad7;
type

	//Struktura danych to lista dwuwymiarowa. 

	//Tutaj beda przechowywane litery
	litera=^literka;
	literka=record
		nastepny:litera;
		txt:char;
	end;
	
	//A tu cale wiersze
	wiersz=^wier;
    wier=record 
		txt:litera;
		nastepny:wiersz;
		dlugosc:integer;
    end;


var znak:char;
pierwszy,teraz,tmp,prawy:wiersz;
teraz_znak,tmp_znak:litera;
wierszy,dlugosc,najdluzszy,obrotow,i,j,liter:integer;

begin

	if not EOF then
	begin

		//Wczytujemy pierwszy wiersz na liste.
		new(pierwszy);
		pierwszy^.nastepny:=nil;
		teraz:=pierwszy;
		
		read(znak);
		new(teraz^.txt);
		teraz_znak:=teraz^.txt;
		teraz_znak^.nastepny:=nil;
		teraz_znak^.txt:=znak;

		dlugosc:=1;
		//Wczytujemy litery w wierszach az nie trafimy na koniec
		while ((znakchar(10)) AND (not EOF)) do
		begin
			read(znak);
			new(teraz_znak^.nastepny);
			teraz_znak:=teraz_znak^.nastepny;
			teraz_znak^.nastepny:=nil;
			teraz_znak^.txt:=znak;
			dlugosc:=dlugosc+1;

		end;
		wierszy:=1;
		teraz^.dlugosc:=dlugosc;

		
		while not EOF do
		begin
			new(teraz^.nastepny);
			teraz:=teraz^.nastepny;
			teraz^.nastepny:=nil;

			//wczytujemy kolejne wiersze na liste
			
			read(znak);
			new(teraz^.txt);
			teraz_znak:=teraz^.txt;
			teraz_znak^.nastepny:=nil;
			teraz_znak^.txt:=znak;
			//Musimy wiedziec  ile bedzie wierszy
			wierszy:=wierszy+1;
			dlugosc:=1;
			
			//Wczytujemy litery w wierszach az nie trafimy na koniec
			while znakchar(10) do
			begin
				read(znak);
				new(teraz_znak^.nastepny);
				teraz_znak:=teraz_znak^.nastepny;
				teraz_znak^.nastepny:=nil;
				teraz_znak^.txt:=znak;
				dlugosc:=dlugosc+1;
			end;

			//Szukamu najdluzszego wiersza.
			
			teraz^.dlugosc:=dlugosc;

		end;


		najdluzszy:=0;
		//Teraz powinnismy miec wszystko w liscie dwuwymiarowej i dane w zmiennych najdluzszy i wierszy.
		//Zeby wypisywac wszycstko w ten ladny sliczny sposob, znajdziemy wskaznik do pierwszego wiersza prawej kolumny.
		obrotow:=(wierszy div 2) + (wierszy mod 2);
		teraz:=pierwszy;
		//Wskaznik do pierwszego wiersza prawej kolumny
		

			for i:=1 to obrotow do
			begin
				if teraz^.dlugosc>najdluzszy then
					najdluzszy:=teraz^.dlugosc;
				teraz:=teraz^.nastepny;
			end;


		prawy:=teraz;
		teraz:=pierwszy;


		//Wypisujemy.

		for i:=1 to obrotow do
		begin
			tmp:=teraz;
			teraz_znak:=teraz^.txt;
			liter:=0;
				//Wypisujemy litery i caly czas sprzatamy po sobie.
				while teraz_znak  nil do
				begin
					//Mie chcemy przeciez wypisac koncow wierszy /r i /n
					if ((ord(teraz_znak^.txt)10) AND (ord(teraz_znak^.txt)13)) then
						write(teraz_znak^.txt);
					tmp_znak:=teraz_znak;
					teraz_znak:=teraz_znak^.nastepny;
					dispose(tmp_znak);
					liter:=liter+1;
				end;
			
			// spacje
			for j:=liter to najdluzszy-1 do
				write(' ');
			//Kreseczka
			write(' | ');


			teraz:=teraz^.nastepny;
			dispose(tmp);


			//Jesli jest prawy - wypisujemy
			if (prawynil) then
			begin
			
				tmp:=prawy;
				teraz_znak:=prawy^.txt;
				liter:=0;
				//Wypisujemy litery i caly czas sprzatamy po sobie.
				while teraz_znak  nil do
				begin
					write(teraz_znak^.txt);
					tmp_znak:=teraz_znak;
					teraz_znak:=teraz_znak^.nastepny;
					dispose(tmp_znak);
				end;	
		
				prawy:=prawy^.nastepny;
				dispose(tmp);
			end
			else
				writeln();
			//Jesli go nie bylo - musimy znak nowego wiersza.	
			

		end
	end
end.

Laboratorium programowania zad 6

Zadanie 6 z laboratorium programowania na Informatyce UW.

Zadanie 6 (termin wysylania rozwiazan: 22 II 2008, godz. 23:59)

(Odwracanie tekstu)

Napisz program, ktory wczyta z wejscia tekst, a nastepnie wypisze go na
wyjscie, odwracajac kolejnosc wierszy.

Np. dla danych:

program czesc;
begin
  writeln('Czesc')
end.

program powinien wypisac:

end.
  writeln('Czesc')
begin
program czesc;

Wolno zalozyc, ze dlugosci wierszy tekstu na wejsciu nie przekraczaja 65535,
ale nie wolno nakladac ograniczenia na liczbe wierszy.

Wskazowka:

Wczytaj tekst z wejscia i utworz pomocniczy plik binarny, w ktorym po
zawartosci kazdego wiersza znajda sie dwa bajty dlugosci tego wiersza.
Nastepnie przejdz po wierszach zapisanych w tym pliku, w kolejnosci od
ostatniego do pierwszego, i wypisz je na wyjscie.

Pliku pomocniczego nie trzeba usuwac po zakonczeniu pracy programu.

A oto rozwiązanie:

program zad6;
type

	//Struktura danych to lista dwuwymiarowa. Wiersze rosna w tyl, dzieki czemu naturalnie sie odwracaja.

	//Tutaj beda przechowywane litery
	litera=^literka;
	literka=record
		nastepny:litera;
		txt:char;
	end;
	
	//A tu cale wiersze
	wiersz=^wier;
    wier=record 
		txt:litera;
		nastepny:wiersz;
    end;


var znak:char;
pierwszy,teraz,tmp:wiersz;
teraz_znak,tmp_znak:litera;

begin

	teraz:=nil;

	//Wczytujemy kolejne wiersze nowe przystawiajac z przodu. Dzieki temu odwracaja sie naturalnie.
	while not EOF do
	begin
		new(pierwszy);
		pierwszy^.nastepny:=teraz;
		teraz:=pierwszy;
		
		read(znak);
		new(teraz^.txt);
		teraz_znak:=teraz^.txt;
		teraz_znak^.nastepny:=nil;
		teraz_znak^.txt:=znak;
		
		//Wczytujemy litery w wierszach az nie trafimy na koniec
		while znakchar(10) do
		begin
			read(znak);
			new(teraz_znak^.nastepny);
			teraz_znak:=teraz_znak^.nastepny;
			teraz_znak^.nastepny:=nil;
			teraz_znak^.txt:=znak;
		end
	end;

	//Wiersze
	while teraz  nil do
	begin
		tmp:=teraz;
		teraz_znak:=teraz^.txt;
			//Wypisujemy litery i caly czas sprzatamy po sobie.
			while teraz_znak  nil do
			begin
				write(teraz_znak^.txt);
				tmp_znak:=teraz_znak;
				teraz_znak:=teraz_znak^.nastepny;
				dispose(tmp_znak);
			end;
		teraz:=teraz^.nastepny;
		dispose(tmp);
	end
end.

Laboratorium programowania zad 5

Zadanie 5 z laboratorium programowania na Informatyce UW.

Zadanie 5 (termin wysylania rozwiazan: 15 II 2008, godz. 23:59)

(Komentarze)

Komentarze zaczynaja sie od pary znakow / i koncza na koncu wiersza.

Napisz program, ktory skopiuje plik tekstowy, wyrownujac wszystkie
komentarze tak, by zaczynaly sie w tej samej kolumnie. Komentarz,
ktorego poczatek jest najbardziej wysuniety w prawo, ma pozostac w
tym samym miejscu wiersza, a poczatki wszystkich, ktore zaczynaja
sie wczesniej, maja zostac przesuniete poprzez poprzedzenie ich
odpowiednia liczba spacji.

Program bedzie wywolywany z jednym parametrem - nazwa pliku tekstowego,
a wynikowy tekst wypisze na standardowe wyjscie.

Np. dla danych umieszczonych w pliku dane.txt:

wiersz pierwszy // to jest komentarz
drugi// to tez komentarz
tu nie ma komentarza
4 wiersz // ten komentarz zaczal sie od // a konczy tu

program wywolany poleceniem:

./zadanie5 dane.txt

powinien wypisac na wyjscie:

wiersz pierwszy // to jest komentarz
drugi           // to tez komentarz
tu nie ma komentarza
4 wiersz        // ten komentarz zaczal sie od // a konczy tu

Wskazowka:

Program powinien przejsc po pliku tekstowym dwa razy - raz, by poznac
pozycje najbardziej wysunietego komentarza i drugi raz, by stworzyc
kopie.

A oto rozwiązanie:

program zad5;
USES crt;
//Program napisany na zajęcia z Laboratorium Języka Pascal i C. Zadania nr 5.


var
argumentow,dlugosc,i,j,najdluz:integer;
parametr,wiersz:string;
znaleziono:boolean;
plik:text;



begin

	//Przechwutujemy liczbe argumentow
	argumentow:=ParamCount();

	if (argumentow=1) then
	begin
		//Czytamy parametr
		parametr:=ParamStr(1);

		//Otwieramy plik
		assign(plik, parametr);
		reset(plik);
		najdluz:=0;
		while not EOF(plik) do
		begin
			//Wczytujemy po wierszu
			readln(plik,wiersz);
			dlugosc:=length(wiersz);
			i:=1;
			while ((inajdluz) then
						najdluz:=i;
					znaleziono:=true;
				end;
				i:=i+1;
			end;

		end;
		//wczytane. Teraz najdluz to pierwszy najdalej wysuniety / 

		//Przeskakujemy do poczatku.
		reset(plik);
				
		while not EOF(plik) do
		begin
			//Po wierszu
			readln(plik,wiersz);
			dlugosc:=length(wiersz);
			for i:=1 to dlugosc-1 do
			begin
				//Znalezlismy znak komentarza
				if ((wiersz[i]='/') AND (wiersz[i+1]='/')) then
				begin
					//Dodajemy spacje
					for j:=i to najdluz-1 do
					begin
						write(' ');
					end;
				end;
				//Piszemy znak
				write(wiersz[i]);
			end;
			//Piszemy ostatni znak z wiersza
			write(wiersz[i+1]);
			//I znak nowego wiersza.
			writeln();
		end;
		
	end
end.

Laboratorium programowania zad 4

Zadanie 4 z laboratorium programowania na Informatyce UW.

Zadanie 4 (termin wysylania rozwiazan: 8 II 2008, godz. 23:59)

(Samotnik)

Gra logiczna o nazwie Samotnik jest rozgrywana przez jedna osobe
na planszy, ktorej czesc pol zajmuja pionki.

Pojedynczy ruch polega na przeskoczeniu pionkiem pionka znajdujacego
sie na jednym z czterech sasiednich pol, zdjeciu przeskoczonego pionka
z planszy i umieszczeniu pionka, ktory przeskoczyl, bezposrednio
za polem przeskoczonym (wczesniej musi byc ono puste).

Np. ze stanu (kropka oznacza puste pole, gwiazdka to pionek):

**.

przejdziemy do:

..*

ze stanu:

.**

przejdziemy do:

*..

ze stanu:

.
*
*

przejdziemy do:

*
.
.


ze stanu:

*
*
.

przejdziemy do:

.
.
*

Napisz program, ktory dla zadanego stanu planszy S i wartosci n
wypisze wszystkie stany, z ktorych po n ruchach dojdziemy do
stanu S.

Postac danych:

Program jest wywolywany z jednym argumentem bedacym nieujemna
liczba calkowita, a ze standardowego wejscia wczytuje stan
planszy. Reprezentacja stanu sklada sie z siedmiu wierszy, kazdy
po siedem znakow. Znak kropki '.' reprezentuje puste pole
planszy, znak gwiazdki '*' reprezentuje pionka a znak spacji
reprezentuje miejsce poza plansza - tam pionek nigdy znalezc sie
nie moze.

Np. ciag znakow:

  ***  
  ***  
*******
***.***
*******
  ***  
  ***  

jest zapisem stanu poczatkowego Samotnika w jego klasycznej wersji.

Postac wyniku:

Program wypisuje na wyjscie wszystkie stany planszy, z ktorych
po n ruchach mozna osiagnac stan zadany na wejsciu. Kazdy stan
wypisujemy w takim formacie, w jakim byly dane na wejsciu (siedem
wierszy po siedem znakow). Dodatkowo, po kazdym stanie planszy
wypisujemy jeden pusty wiersz.

Np. dla danych postaci:

  ...  
  ...  
.......
...*...
.......
  ...  
  ...  

program wywolany poleceniem:

./rozwiazanie 1 < dane

powinien wypisac:

  ...  
  ...  
.......
.......
...*...
  .*.  
  ...  
    
  ...  
  .*.  
...*...
.......
.......
  ...  
  ...  
                
  ...  
  ...  
.......
....**.
.......
  ...  
  ...  
                        
  ...  
  ...  
.......
.**....
.......
  ...  
  ...  


Dla tych samych danych, program wywolany z argumentem 3 powinien
wypisac, miedzy innymi, stan:

  ...  
  ...  
...*...
.**....
.......
  .*.  
  ...  

Pelny wynik programu wywolanego z argumentem 3 jest zalacznikiem do
tresci zadania.

(Uwaga: Kolejnosc stanow wypisywanych na wyjscie nie musi byc taka,
jak w tym przykladzie, ale gdyby udalo sie Panstwu ja zachowac,
ulatwiloby mi to sprawdzanie rozwiazan.)

Mozna zalozyc, ze dane na wejsciu programu, oraz argument wywolania,
beda poprawne.

Wskazowka 1:

Zacznij od rozwiazania problemu cofniecia stanu planszy o jeden,
czyli do stanu bezposrednio poprzedzajacego zadany. Nastepnie
zastanow sie, jak zastosowac rekurencje do rozwiazania problemu
w wersji pelnej.

Wskazowka 2:

Liczbe argumentow, z ktorymi wywolano program, mozemy poznac wywolujac
funkcje ParamCount. Funcja ParamStr(i) zwroci nam i-ty argument
wywolania programu w postaci wartosci typu string.

Wartosc liczbowa reprezentowana przez wartosc typu string mozemy
obliczyc samodzielnie, lub skorzystac z procedury Val. Wywolanie
Val(s,x,w) umiesci na zmiennej x typu integer wartosc liczby, ktorej
ciag cyfr znajduje sie na zmiennej s typu string. Gdyby postac s
byla bledna, na zmiennej w typu word znajdzie sie kod bledu.

A oto rozwiązanie:

program zad3;
//Program napisany na zajęcia z Laboratorium Języka Pascal i C. Zadania nr 4.

type
//plansza
plan=array [1..7,1..7] of char;

var start:plan;
argumentow,iteracji,i,j,blad:integer;
parametr,wiersz:string;


procedure wypisz(plansza:plan);
//Jak nietrudno sie domyslic, procedura wypisuje plansze
var i,j:integer;
begin
		for i:=1 to 7 do
		begin
			for j:=1 to 7 do
			begin
				write(plansza[i,j]);
			end;
			writeln();
		end;
		writeln();
end;



procedure ruch(plansza:plan;iteracja:integer);
//Rekurencyjna procedura. Wykonuje ruchy az iteracja spadnie do 0
var i,j:integer;
plansza2:plan;
begin

	//Doszlismy do odpowiedniej liczby ruchow
	if (iteracja=0) then
	begin
		wypisz(plansza);
	end
	else
	begin
		iteracja:=iteracja-1;
		//Idziemy po planszy. Dla kazdego pionka zaklada ze znalazl sie tam w wyniku ruchu
		for i:=1 to 7 do
		begin
			for j:=1 to 7 do
			begin
				//Mamy pionek
				if (plansza[i,j]='*') then
				begin
				
					//No i teraz zakladamy ze pionek znalazl sie tam w wyniku:
				
					//skok z dolu
					if ((i2) AND (plansza[i-1,j]='.') AND (plansza[i-2,j]='.')) then
					begin
						plansza2:=plansza;
						plansza2[i,j]:='.';
						plansza2[i-1,j]:='*';
						plansza2[i-2,j]:='*';
						ruch(plansza2,iteracja);
					end;
					
					//skok z prawej
					if ((j2) AND (plansza[i,j-1]='.') AND (plansza[i,j-2]='.')) then
					begin
						plansza2:=plansza;
						plansza2[i,j]:='.';
						plansza2[i,j-1]:='*';
						plansza2[i,j-2]:='*';
						ruch(plansza2,iteracja);
					end;					

				end
			end
		end
	end
	
end;







begin

	//Przechwutujemy liczbe argumentow
	argumentow:=ParamCount();

	if (argumentow=1) then
	begin
		//Czytamy parametr
		parametr:=ParamStr(1);
		Val(parametr,iteracji,blad);

		//Wczytujemy wejscie
		for i:=1 to 7 do
		begin
			readln(wiersz);
			for j:=1 to 7 do
			begin
				start[i,j]:=wiersz[j];
			end
		end;
		
		//wczytane.
		//Wywyolujemy
		ruch(start,iteracji);
	end
end.