­­­­­WYŻSZA SZKOŁA MENADŻERSKA

WYDZIAŁ INFORMATYKI STOSOWANEJ

I TECHNIK BEZPIECZEŃSTWA

Studia niestacjonarne

ALGORYTMY I ZŁOŻONOŚCI.

ZADANIE ZALICZENIOWE

WARSZAWA 2011 r.

Semestr letni, rok akademicki 2010/2011

Zadanie 6

Zgodnie z regułami gry w szachy, hetman (królowa) może atakować figury ustawione na polach w kolumnie, wierszu oraz dwóch przekątnych przechodzących przez pole, w którym jest ustawiony. O tych polach mówimy, że są atakowane przez hetmana.

Na rysunku

hetman stoi w polu (2,6) i atakuje (7+7+6+3) = 23 pola.

Zostały one zamalowane kolorem szarym.

a) Poniżej znajduje sie tabela o wymiarach 5x5. Korzystając z powyższej obserwacji, uzupełnij pola tabeli wpisując do każdego z nich liczbę pól, które atakowałby hetman znajdujący sie w tym polu.

Hetman stojący w polu (1,1) atakuje 12 pól planszy.

1 2 3 4 5

1 1 1 1 1 1

2 1 1 0 0 0

3 1 0 1 0 0

4 1 0 0 1 0

5 1 0 0 0 1

b) Określ liczbę atakowanych pól na szachownicy 32x32, gdy dane są współrzędne

ustawienia hetmana.

Dla (2,2) wynik = 95

Dla (5,4) wynik = 99

Dla (20,18) wynik = 117

Dla (25,30) wynik = 97

Podaj specyfikacje i utwórz algorytm, który dla dowolnej dodatniej liczby całkowitej n _ 50 i położenia

hetmana (x, y) na szachownicy o wymiarach n×n , gdzie 1_x,y_n, pozwoli obliczyć liczbę pól atakowanych

przez tego hetmana.

PROGRAM:

#include <cstdlib>

#include <iostream>

#include <fstream>

using namespace std;

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

{

int liczba,i=0,n,x,y;

ifstream plik;

plik.open("rozmiar.txt");

if(!plik)

cout<<"brak pliku"<<endl;

else

{

plik>>liczba;

plik>>x;

plik>>y;

n=liczba;

}

cout<<"szachownica ma rozmiar "<<n<<"x"<<n<<endl;

cout<<endl;

cout<<endl;

int a,b,ilosc;

int tab[n][n];

for(int i=0; i<=n-1 ; i++)

for(int j=0 ; j<=n-1 ; j++)

{

ilosc=2*(n-1);

a=i;

b=j;

while((a-1>=0)and(b+1<=n-1))

{

ilosc++;

a--;

b++;

}

a=i;

b=j;

while((a-1>=0)and(b-1>=0))

{

ilosc++;

a--;

b--;

}

a=i;

b=j;

while((a+1<=n-1)and(b+1<=n-1))

{

ilosc++;

a++;

b++;

}

a=i;

b=j;

while((a+1<=n-1)and(b-1>=0))

{

ilosc++;

a++;

b--;

}

tab[i][j]=ilosc;

}

for(int i=0 ; i<=n-1 ; i++)

{

for(int j=0 ; j<=n-1 ; j++)

{

cout<<tab[i][j]<<" ";

}

cout<<endl;

cout<<endl;

}

int tab2[n][n];

a=x;

b=y;

for(int i=0 ; i<=n-1 ; i++)

{

for(int j=0 ; j<=n-1 ; j++)

{

if((i==a)or(j==b))

tab2[i][j]=1;

else

tab2[i][j]=0;

}

}

while((a-1>=0)and(b+1<=n-1))

{

tab2[a-1][b+1]=1;

a--;

b++;

}

a=x;

b=y;

while((a-1>=0)and(b-1>=0))

{

tab2[a-1][b-1]=1;

a--;

b--;

}

a=x;

b=y;

while((a+1<=n-1)and(b+1<=n-1))

{

tab2[a+1][b+1]=1;

a++;

b++;

}

a=x;

b=y;

while((a+1<=n-1)and(b-1>=0))

{

tab2[a+1][b-1]=1;

a++;

b--;

}

cout<<endl;

cout<<endl;

cout<<endl;

for(int i=0 ; i<=n-1 ; i++)

{

for(int j=0 ; j<=n-1 ; j++)

{

cout<<tab2[i][j]<<" ";

}

cout<<endl;

cout<<endl;

}

ofstream plik2;

plik2.open("wynik.txt");

if(!plik2)

cout<<"brak pliku"<<endl;

else

{

plik2<<"zasieg z dowolnego pola"<<endl;

for(int i=0 ; i<=n-1 ; i++)

{

for(int j=0 ; j<=n-1 ; j++)

{

plik2<<(tab[i][j])<<" ";

}

plik2<<endl;

}

plik2<<endl;

plik2<<endl;

plik2<<endl;

plik2<<"zasieg z wybranego pola:"<<x<<"x"<<y<<"="<<tab[x][y]<<endl;

for(int i=0 ; i<=n-1 ; i++)

{

for(int j=0 ; j<=n-1 ; j++)

{

plik2<<(tab2[i][j])<<" ";

}

plik2<<endl;

}

}

system("PAUSE");

return EXIT_SUCCESS;

}

SCHEMAT ALGORYTMU

OPRACOWANIE ZŁOŻONOŚCI ALGORYTMU.