Laboratorium Funkcyjnego zadanie

Zadanie zaliczeniowe z programowania funkcyjnego:

(*Prosty kalkulator wyrazen. Na razie BARDZO prosty. Ograniczenia:*)
(*1. Dobrze jest nawiasowac wyrazenia, gdyz nie jest dobrze rozwiazany konflikt dodawanie / odejmowanie i mnozenie / dzielenie*)
(*2. Liczby ujemne lepiej zapisywac jako np(0-5) .*)



(* Najpierw funkcje zabezpieczajace wszystko.*)
let numer a = (a >= '0') && (a  Printf.printf "n%sn" mess;;

(*POBIERAMY LINIE Z WEJSCIA I KALKULUJEMY:******)
kalkulator ((input_line stdin)^"=");;

Laboratorium programowania zad 15

Zadanie z laboratorium programowania na Informatyce UW.

Zadanie 15 (termin wysylania rozwiazan: 21 maja 2008, godz. 23:59)

(Permutowanie napisu)

Napisz program, ktory wczyta z wejscia ciag znakow zakonczony koncem
wiersza oraz niepusty ciag liczb calkowitych zakonczony liczba zero,
ktorej nie uznajemy za czesc ciagu.

Nie znamy maksymalnej dlugosci zadnego z ciagow, wiec bedziemy je
przechowywac w strukturach listowych. Po listach bedziemy sie
poruszali cyklicznie - po liscie liczb w jednym kierunku a po
liscie znakow w dwoch kierunkach. Oznacza to, ze program bedzie sie
poslugiwal dwukierunkowa lista cykliczna znakow oraz jednokierunkowa
lista cykliczna liczb.

Po utworzeniu obu list, program powinien wypisac zawartosc ciagu
znakow, w kolejnosci wyznaczonej przez ciag liczb, rozpoczynajac
od pierwszego znaku i pierwszej liczby, zgodnie z nastepujacym
przepisem:

* wypisujemy aktualny znak
* usuwamy go z listy
* niech k bedzie aktualna liczba na liscie liczb
  - jesli k jest wieksze od zera, to przesuwamy sie o k znakow do
    przodu (wzgledem usunietego znaku) na liscie cyklicznej znakow
  - jesli k jest mniejsze od zera, to przesuwamy sie o k znakow do
    tylu (wzgledem usunietego znaku)
* zmieniamy k na nastepna liczbe (uwzgledniajac cyklicznosc listy)

Np. dla danych:

alamakota
3 -2 0

program powinien wypisac:

amlkataoa

A oto rozwiązanie:

#include 
#include 
#include 

//Struktura dla znakow zasugerowana w zadaniu
typedef struct znak_el{     
      char znak;           
      struct znak_el * nastepny; 
	  struct znak_el * poprzedni; 
};


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



int main (int argc, char *argv[])
{

	//Inicjujemy
	int liczba,kierunek,wynik,skok;
	char znak;
	struct znak_el *teraz_znak=NULL;
	struct znak_el *start_znak=NULL;
	struct znak_el *tmp_znak=NULL;
	struct liczba_el *teraz_liczba=NULL;
	struct liczba_el *start_liczba=NULL;
	struct liczba_el *tmp_liczba=NULL;

	
	wynik=scanf("%c",&znak);

	if((znak!='r')&&(znak!='n')&&(wynik!=EOF))//jesli nie bylo znakow w pierwszym wierszu.
	{
		//pierwszy element ciagu znakow
		start_znak=malloc(sizeof(struct znak_el));
		start_znak->nastepny=start_znak;
		start_znak->poprzedni=start_znak;
		start_znak->znak=znak;		
		wynik=scanf("%c",&znak);
		teraz_znak=start_znak;
		

		while((znak!='r')&&(znak!='n')&&(wynik!=EOF))	//wesole atrakcjie dla koncow znakow w roznych systemach.
		{
			teraz_znak->nastepny=malloc(sizeof(struct liczba_el));
			teraz_znak->nastepny->poprzedni=teraz_znak;
			teraz_znak->nastepny->nastepny=start_znak;
			teraz_znak=teraz_znak->nastepny;
			teraz_znak->znak=znak;
			wynik=scanf("%c",&znak);
		}
		start_znak->poprzedni=teraz_znak; //Zapetlamy koncowke
		
		//znaki powinny byc wczytane.
		
		//wczytujemy liczby
		wynik=scanf("%d",&liczba);
		
		if((wynik!=EOF)&&(liczba!=0))	//Jesli sa liczby
		{
			
			start_liczba=malloc(sizeof(struct liczba_el));
			start_liczba->nastepny=start_liczba;

			start_liczba->liczba=liczba;		
			wynik=scanf("%d",&liczba);
			teraz_liczba=start_liczba;
			
			while((liczba!=0)&&(wynik!=EOF))	//dopoki....
			{
				
				teraz_liczba->nastepny=malloc(sizeof(struct liczba_el));
				teraz_liczba->nastepny->nastepny=start_liczba;
				teraz_liczba=teraz_liczba->nastepny;
				teraz_liczba->liczba=liczba;
				wynik=scanf("%d",&liczba);

			}
			
			teraz_znak=start_znak;
			teraz_liczba=start_liczba;
			//OK. Powinno byc wczytane, Trzeba wypisac.
			
		
			
			//I teraz trzeba wypisac!!
			
			while(teraz_znak->nastepny!=teraz_znak)	//Jesli jest wiecej niz jeden znak w liscie
			{
				//dopoku nie zostal jeden znak na liscie.
				//wypisujemy,
				printf("%c",teraz_znak->znak);
				//usuwamy
				tmp_znak=teraz_znak;
				teraz_znak->poprzedni->nastepny=teraz_znak->nastepny;
				teraz_znak->nastepny->poprzedni=teraz_znak->poprzedni;

				
				//ustalamy wlasnosci skoku
				if(teraz_liczba->liczba>0)
				{
					kierunek=1;
					skok=teraz_liczba->liczba;
				}
				else
				{
					kierunek=-1;
					skok=teraz_liczba->liczba*-1;
				}
				teraz_liczba=teraz_liczba->nastepny;
				
				//teraz wlasciwy skok.
				
				while(skok>0)
				{
					if(kierunek==1)
					{
						//skok do przodu
						teraz_znak=teraz_znak->nastepny;
					}
					else
					{
						//skok do tylu
						teraz_znak=teraz_znak->poprzedni;
					}
					skok+=-1;
				}
				//przesunieto nastepny znak do wypisania.

				//faktyczne usuwanie znaku.
				free(tmp_znak);
			}
			
			//dobrze. W tej chwili powinien zostac jeden znak w liscie.
			printf("%cn",teraz_znak->znak);

			free(teraz_znak);

		
			//no dobrze, ale tez byloby milo po sobie posprzatac. zostaly nam liczby..
			
			while(teraz_liczba->nastepny!=start_liczba)
			{
				tmp_liczba=teraz_liczba;
				teraz_liczba=teraz_liczba->nastepny;
				free(tmp_liczba);
			}
		}
		else
		{
			//Szwindel. Nie bylo liczb.
			return 2;
		}

	}
	else
	{
		//Szwindel. Nie bylo znakow.
		return 1;
	}

return 0;
}

Laboratorium programowania zad 14

Zadanie z laboratorium programowania na Informatyce UW.

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

(Liczby w kolumnach)

Napisz program, ktory wczyta z wejscia ciagi liczb calkowitych zakonczone
zerami i wypisze je na wyjscie w kolumnach.

Postac danych:

Na wejsciu programu znajdzie sie N ciagow liczb calkowitych. W kazdym ciagu
bedzie K wartosci niezerowych zakonczonych zerem. Liczby ciagow (N) i
dlugosci kazdego ciagu (K) nie znamy - beda zalezaly od danych.

Program powinien sprawdzac, czy wszystkie ciagi sa tej samej dlugosci (K).
Gdyby tak nie bylo, program powinien wypisac na wyjscie slowo "blad".

Postac wyniku:

Program wypisze na wyjscie K wierszy, w kazdym po N liczb. W pierwszym
wierszu znajdzie sie pierwsza liczba kazdego ciagu, w drugim druga liczba itd.

Liczby wypisujemy w kolumnach o szerokosci 10 znakow, z wyrownaniem do prawej
krawedzi kolumny.

Np. dla danych:

1 2 3 0 10 20 30 0 100 200 300 0 1000 2000 3000 0

program powinien wypisac:

         1        10       100      1000
         2        20       200      2000
         3        30       300      3000

Wskazowka 1:

Wymagana szerokosc kolumny i wyrownanie liczby da nam wywolanie funkcji
printf z pierwszym parametrem "%10d".

Wskazowka 2:

Liczby wczytane z wejscia mozna przechowywac na liscie list (lista ciagow,
dla kazdego ciagu lista liczb).

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 main (int argc, char *argv[])
{
	int liczba,seria,w_serii,ilosc_serii,wynik,i,j,k;
	struct liczba_el *teraz_liczba=NULL;
	struct liczba_el *tmp_liczba=NULL;
	struct seria_el *teraz_seria=NULL;
	struct seria_el *tmp_seria=NULL;
	struct seria_el *start=NULL;


	//pierwszy element pierwszej serii
	start=malloc(sizeof(start));
	start->liczba=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=liczba;			//
	wynik=scanf("%d",&liczba);
	
	seria=0;
	w_serii=1;
	ilosc_serii=1;
	

	while(wynik!=EOF)
	{
		if(liczba==0)
		{
			//koniec serii
			wynik=scanf("%d",&liczba);

				if(seria==0)
				{
					//jesli koniec pierwszej serii
					seria=w_serii;
				}
				else if(w_serii!=seria)
				{
					//w tej serii inna ilosc danych
					printf("blad");
					exit(1);
				}
				
			if(wynik!=EOF)
			{
				//jesli nie jest to ostatnia seria
				w_serii=1;
				ilosc_serii++;
				//nowa seria
				teraz_seria->nastepny=malloc(sizeof(start));
				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=liczba;
			}
		}
		else
		{
			w_serii++;
			//Nowa liczba w serii.
			teraz_liczba->nastepny=malloc(sizeof(teraz_liczba));
			teraz_liczba=teraz_liczba->nastepny;
			teraz_liczba->var=liczba;		//
		}

		wynik=scanf("%d",&liczba);

	}
//Wczytane.
	
//I teraz trzeba wypisac!!
	

	for(i=0;i<seria;i++)
	{
		//ilosc wierszy - rozmiar serii.
		teraz_seria=start;
		
		for(j=0;jliczba;
			
			for(k=0;knastepny;
			}
			//Zwyczajnie wypisujemy
			printf("%10d",teraz_liczba->var);
			//i przechodzimy do nastepnej serii.
			teraz_seria=teraz_seria->nastepny;
		}
		printf("n");
	}
	
	//no dobrze, ale tez byloby milo po sobie posprzatac.
	
	teraz_seria=start;
	while(teraz_seria!=NULL)
	{
		teraz_liczba=teraz_seria->liczba;
		
		while(teraz_liczba!=NULL)
		{
			tmp_liczba=teraz_liczba;
			teraz_liczba=teraz_liczba->nastepny;
			free(tmp_liczba);
		}
	
		tmp_seria=teraz_seria;
		teraz_seria=teraz_seria->nastepny;
		free(tmp_seria);
	}

return 0;
}

Laboratorium programowania zad 13

Zadanie z laboratorium programowania na Informatyce UW.

Zadanie 13 (termin wysylania rozwiazan: 7 maja 2008, godz. 23:59)

(Kodowanie)

Spacje i tabulacje znajdujace sie na koncu wiersza pliku tekstowego
nie sa widoczne dla osoby czytajacej tekst. Mozna to wykorzystac do
ukrywania w tekscie informacji. Np. jeden bajt mozemy zakodowac w
tekscie, umieszczajac na koncu wiersza osiem znakow: spacje (oznaczajace
bit 0) i tabulacje (oznaczajace bit 1). Przyjmiemy, ze bity beda
uporzadkowane w kolejnosci od najbardziej znaczacego.

Napisz program ktory, w zaleznosci od sposobu wywolania, ukryje
w kolejnych wierszach tekstu po jednym bajcie pliku binarnego, lub
odczyta je z tekstu.

Program bedzie wywolywany z dwoma argumentami - litera 'c' lub 'd'
oznaczajaca tryb pracy, oraz nazwa pliku binarnego.

Program wywolany poleceniem:

./zsi07z13 c binaria wynik

ma zakodowac zawartosc pliku binarnego o nazwie "binaria" w tekscie
wczytanym z wejscia (tu jest nim zawartosc pliku o nazwie "tekst") i
wypisac na wyjscie wynik kodowania (w tym wypadku wynik trafi do pliku
o nazwie "wynik").

Niech liczba wierszy tekstu wejsciowego bedzie rowna K, a liczba bajtow
pliku binarnego N.

Jesli K jest wieksze lub rowne N, N poczatkowych wierszy tekstu wynikowego
ma zawierac reprezentacje kolejnych bajtow, a pozostalych K-N wierszy
nalezy skopiowac z wejscia na wyjscie bez zmian.

Jesli K jest mniejsze niz N postepujemy tak, jakby na koncu tekstu
wejsciowego bylo dodatkowo N-K wierszy pustych.

Program wywolany poleceniem:

./zsi07z13 d binaria <tekst

ma odkodowac dane ukryte w tekscie wczytanym z wejscia (tu jest nim
zawartosc pliku "tekst") i zapisac je w pliku binarnym o nazwie "binaria".

Zakladamy, ze tekst wejsciowy dla tego wywolania programu zawiera poprawnie
zakodowana informacje. Oznacza to, ze N poczatkowych wierszy tego tekstu
konczy sie osmioma znakami spacji i tabulacji. Jesli tekst wejsciowy ma
wiecej niz N wierszy, na koncu wiersza o numerze N+1 nie ma osmiu znakow
spacji i tabulacji. Program powinien utworzyc plik "binaria" i zapisac do
niego N odczytanych bajtow.

W zalacznikach do tresci sa pliki przykladowe:

zsi07z13.binaria
zsi07z13.tekst1
zsi07z13.tekst2
zsi07z13.wynik1
zsi07z13.wynik2

pasujace do ciagu wywolan programu:

./zsi07z13 c zsi07z13.binaria zsi07z13.wynik1
./zsi07z13 d zsi07z13.binaria <zsi07z13.wynik1
./zsi07z13 c zsi07z13.binaria zsi07z13.wynik2
./zsi07z13 d zsi07z13.binaria <zsi07z13.wynik2

A oto rozwiązanie:

#include 
#include 
#include 

//bufor - jeden bajt zapisany tym specyficznym sposobem.
char bufor[8];

int rozkoduj ()
{
	//koduje ciag spacji i tabulacji na liczbe w kodzie U2 od najbardziej znaczacego bitu.
	int i,wynik,mnoznik;
	
	//dla ujemnego bitu:
	if (bufor[0]=='t')
	{
		wynik=-128;
	}
	else
	{
		wynik=0;
	}
	
	mnoznik=64; 
		
	//7 razy:
	for (i=1;i<8;i++)
	{
		if(bufor[i]=='t')
		{
			wynik=wynik+mnoznik;
		}
		
		mnoznik=mnoznik/2;
	}

	return wynik;

}

int zakoduj (int liczba)
{
	//koduje liczbe znak na ciag spacji i tabulacji.
	//Oczywiscie W ZADANIU NIE NAPISANO ZE KOD JEST UZUPELNIENIOWY DO 2!! MUSIELISMY SIE SAMI DOMYSLIC!!
	int i,wynik,mnoznik;
	
	//na poczatku dla ujemnego bitu:
	
		if (liczba<0)
		{
			liczba=liczba+128;
			bufor[0]='t';
		}
		else
		{
			bufor[0]=' ';
		}
		
	
	mnoznik=64; 
	wynik=0;
		
	
	//7 razy:
	
	for (i=1;i=mnoznik)
		{
			//ta liczba jest w rozkladzie.
			bufor[i]='t';
			liczba=liczba-mnoznik;
		}
		else
		{
			bufor[i]=' ';
		}
		
		mnoznik=mnoznik/2;
	}
	
	return 0;

}



int main (int argc,char *argv[])
{
	FILE * f;
	char znak,binarny;
	int wynik, wynikb, bufor_index, i;

	//Argumanry wywolania
	if(argv[1][0]=='c')
	{// czyli musimy zakodowac tekst
		//printf("%s",argv[2]);
		f=fopen(argv[2],"rb");
		
		wynik=scanf("%c",&znak);
		wynikb=fscanf(f,"%c",&binarny);
		
		while(wynik!=EOF)
		{
			if(znak=='r')
			{
				//nic nie robimy. to zle znaki sa.
			}
			else if (znak=='n')
			{
				//kodujemy
				//jesli jest co kodowac.
				
				if(wynikb!=EOF)
				{
					//printf("[%d]",binarny);
					zakoduj(binarny);
					printf("%s",bufor);
					wynikb=fscanf(f,"%c",&binarny);
				}
				//i koniec linii:
				printf("n");
			}
			else
			{
				//przepisujemy znak.
				printf("%c",znak);
			}
			wynik=scanf("%c",&znak);
		} // ok. caly tekst zrodlowy przepisalismy
		
		//Jesli jeszcze cos do zakodowania:
		
		while(wynikb!=EOF)
		{
			zakoduj((int) binarny);
			printf("%s",bufor);
			//printf("[%d]",binarny);
			wynikb=fscanf(f,"%c",&binarny);
			//i koniec linii:
			printf("n");

		}
		//zamykamy binaria
		fclose(f);
	}
	else if(argv[1][0]=='d')
	{//bedziemy dekodowac
	
		f=fopen(argv[2],"wb");
		wynik=scanf("%c",&znak);
		
		while(wynik!=EOF)
		{
			if(znak=='r')
			{
				//nic nie robimy. to zle znaki sa.
			}
			else if((znak=='t')||(znak==' '))
			{
				//mamy jeden z tajemnych znakow. przepisujemy do bufora.
				if (bufor_index<8)
				{
					bufor[bufor_index]=znak;
					bufor_index++;
				}
				else if (bufor_index==8)
				{
					//dziwna sytuacja. Znaczy ze na koncu tekstu byly biale znaki i do tego zostalo cos dokodowane. musimy przesunac bufor,
					for (i=0;i<7;i++)
					{
						bufor[i]=bufor[i+1];
					}
					bufor[7]=znak;
					//bufor przesuniety,
										
				}
			}
			else if (znak=='n')
			{
				//rozkodowujemy.
				
				if(bufor_index==8) //rowniotko 8 bitow.
				{
					binarny=rozkoduj();
					fprintf(f,"%c",binarny);
				}
				//printf("n");
			}
			else
			{
				//przepisujemy znak i zerujemy bufor.
				bufor_index=0;
				//printf("%c",znak);
			}
			
			wynik=scanf("%c",&znak);
		}

		fclose(f);
	}

return 0;
}

Laboratorium programowania zad 12

Zadanie z laboratorium programowania na Informatyce UW.

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

(Kolumny jeszcze raz)

Napisz program, ktory wczyta z wejscia tekst w dwoch kolumnach
rozdzielonych spacja, znakiem '|' i jeszcze jedna spacja i wypisze
go na wyjscie w jednej kolumnie.

Dane programu beda mialy format podobny do wyniku programu numer 7
(z Pascala). Jedyna roznica bedzie dotyczyla ostatniego wiersza. Jesli
jest w nim tylko tekst pierwszej kolumny (jak w przykladzie ponizej),
wiersz bedzie zakonczony znakiem '|' bez nastepujacej po nim spacji.

Program powinien wypisac na wyjscie najpierw zawartosc calej pierwszej
kolumny danych, a nastepnie drugiej. Ma wiec odwrocic wynik dzialania
programu numer 7.

Mozna zalozyc, ze w kazdym wierszu danych znak '|' wystapi tylko raz i
bedzie sluzyl wylacznie do oddzielania kolumn.

Program nie powinien wypisywac na wyjscie spacji konczacych wiersze
pierwszej kolumny, czyli tych, ktore program numer 7 dopisywal, by
wyrownac znaki '|'.

Np. dla danych:

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

program powinien wypisac:

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

Uwaga:

Nie wolno nakladac ograniczen na maksymalna dlugosc wiersza danych, ani
na liczbe wierszy.

Wskazowka:

Wczytujac dane, zawartosc pierwszej kolumny kopiuj bezposrednio na wyjscie,
a zawartosc drugiej wpisuj do pomocniczego pliku tekstowego. Na zakonczenie
przepisz zawartosc tego pliku na wyjscie.

A oto rozwiązanie:

#include 

int main(void)
{
  FILE *f;
  char znak;
  int i,wynik,spacji;

  //Zrobimy tak jak we wskazowce. Wiersze po | zapiszemy w pliku tymczasowym.
  spacji=0;
  f=fopen("tymczasowy","w");
  wynik = scanf("%c", &znak);

	while(wynik!=EOF)
	{
	
		while ((znak!='|')&&(wynik!=EOF))
		{
			//znaki przed |
			if (znak==' ')
			{
				//Spacja. Jesli nie jest spacja wyrownujaca, zostawnie wypisana przed nastepnym znakiem
				spacji=spacji+1;
			}
			else
			{
				i=0;
				while(i<spacji)
				{
					//wypiszemy zapamietane spacje.
					printf(" ");
					i++;
				}
				spacji=0;
				//no i znak.
				printf("%c",znak);
			}
			wynik = scanf("%c", &znak);
		}
		
		if (znak=='|')
		{
			spacji=0;
			wynik = scanf("%c", &znak);
			
			if (znak==' ')
			{
				//Cos tu bedzie dalej napisane.
				printf("n");
				wynik = scanf("%c", &znak);
				//koncowka linii.
				while (znak!='n')
				{
					//do konca linii.
					fprintf(f,"%c",znak);
					wynik = scanf("%c", &znak);
				}
				fprintf(f,"n");
			}
		}
		wynik = scanf("%c", &znak);
	}//ok, teraz polowa na wyjciu, polowa w pliku. wypisujemy plik.
	
	fclose(f);
	//Zapisalismy do pliku pomocniczego. teraz go przeczytamy.
	f=fopen("tymczasowy","r");
	
	wynik = fscanf(f,"%c", &znak);
	
	while(wynik!=EOF)
	{
		printf("%c",znak);
		wynik=fscanf(f,"%c",&znak);
	}
	fclose(f);
	return 0;
}

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.