Odpowiedzi na egzamin praktyczny z

ASD (wersja końcowa)

Cześć A: Zadania sprawdzające umiejętność stosowania metod
konstrukcji algorytmów

Podczas tego etapu egzaminu student będzie losował jedno z poniższych zadań
programistycznych. Po jego rozwiązaniu student odpowie na trzy pytania dotyczące
przedstawionego rozwiązania. Odpowiedzi na te pytania będą podstawą do wystawianie
oceny od dst do bdb.

1. P

ROBLEM PLECAKOWY DECYZYJNY ALGORYTMEM BRUTALNEJ SIŁY PRZEGLĄDAJĄCYM

WSZYSTKIE PODZBIORY PRZEDMIOTÓW Z PLECAKA

.

class

PlecakDecBS

{
final

static

int

N = 6;

final

static

int

MAX_V = 10;

final

static

int

[] V = {6,2,3,2,3,1};

final

static

int

[] W = {6,4,5,7,10,2};

public

static

void

main(

String

[] args)

{

int

p = 0;

int

v,w;

int

b1,b2,b3,b4,b5,b6;

int

[] tab =

new

int

[N];

for

(b1 = 0; b1 <= 1; b1++)

for

(b2 = 0; b2 <= 1; b2++)

for

(b3 = 0; b3 <= 1; b3++)

for

(b4 = 0; b4 <= 1; b4++)

for

(b5 = 0; b5 <= 1; b5++)

for

(b6 = 0; b6 <= 1; b6++)

{
v = b1*V[0] + b2*V[1] + b3*V[2] + b4*V[3] + b5*V[4] + b6*V[5];

if

(v <= MAX_V)

{
w = b1*W[0] + b2*W[1] + b3*W[2] + b4*W[3] + b5*W[4] + b6*W[5];

if

(p < w)

{
p = w;
tab[0] = b1; tab[1] = b2; tab[2] = b3;
tab[3] = b4; tab[4] = b5; tab[5] = b6;
}
}
}
System.

out

.println(

"Wartosc plecaka: "

+ p);

System.

out

.print(

"Przedmioty w plecaku: "

);

for

(

int

i = 0; i < N; i++)

if

(tab[i] == 1) System.

out

.print(i +

" "

);

System.

out

.println();

}

}

2. P

ROBLEM PRODUKCJI LODÓW WSZYSTKICH SMAKÓW METODĄ PRZESZUKIWANIA Z NAWROTAMI

.

public

class

Lody {

//permutacja N elementowa

final

static

int

N = 6;

/*

* tablica reprezentujaca liste elementow

*/

private

static

int

[] lista =

new

int

[N];

private

static

int

[][] czasy =

{

{ 0, 7, 20, 21, 12, 23 },

{ 27, 0, 13, 16, 46, 5 },

{ 53, 15, 0, 25, 27, 6 },

{ 16, 2, 35, 0, 47, 10 },

{ 31, 29, 5, 18, 0, 4 },

{ 28, 24, 1, 17, 5, 0 }

};

private

static

int

minczas = Integer.MAX_VALUE;

static

void

permutacje(

int

i) {

/*

* Wypisanie permutacji w przypadku gdy lista wypelniona jest elementami -

* znaleziono jeden ze stanow koncowych

*/

int

czas = 0;

if

(i == N) {

for

(

int

a = 0; a < N - 1; a++) {

czas += czasy[lista[a]][lista[a + 1]];

}

czas += czasy[lista.length - 1][lista[0]];

if

(czas<minczas){

minczas = czas;

}

System.out.println();

}

else

{

//Dla kazdego elementu ze zbioru {1,...,N}

for

(

int

j = 0; j < N; j++) {

int

k;

//Dla aktualnej listy elementow o dlugosci "i"

for

(k = 0; k < i; k++) {

/*

* Sprawdzenie, czy element "j" znajduje sie na liscie

* jeśli tak, to przejscie do kolejnego stanu (czyli dodanie

* elementu na koniec listy) nie bedzie mozliwe - petla zostanie

* przerwana, wartosc "k" nie zrowna sie z wartoscia "i"

*/

if

(lista[k] == j) {

break

;

}

}

/*

* Jesli warunek jest spelniony to znaczy, ze jest mozliwe przejscie

* do kolejnego stanu (element j dodawany jest na koniec listy)

*/

if

(k == i) {

lista[k] = j;

permutacje(i + 1);

}

}

}

}

public

static

void

main(String[] args) {

/*

* Zaczynamy od stanu poczatkowego - lista jest pusta (zawiera

* zero elementow)

*/

permutacje(0);

System.out.println(minczas);

}

}

3.

P

ROBLEM PLECAKOWY DECYZYJNY METODĄ PRZESZUKIWANIA Z NAWROTAMI

.

public

class

PlecakNawroty

{

final

static

int

N = 6;

// liczba przedmiotów

final

static

int

MAX_V = 10;

// objetość plecaka

final

static

int

[] V = { 2, 6, 3, 3, 1, 2 };

// objetości przedmiotów

final

static

int

[] W = { 4, 6, 5, 10, 2, 7 };

// wartości przedmiotów

private

static

int

[] tab =

new

int

[N];

//pomocnicza tablica na aktualny podzbior

private

static

int

[] rozw =

new

int

[N];

//tablica na optymalny podzbior

private

static

int

maxW = 0;

//Pole na maksymalna obietosc

static

void

pakowanie(

int

i,

int

sumV,

int

sumW)

{

for

(

int

j = 0; j < N; j++)

{

int

k;

for

(k = 0; k < i; k++)

{

if

(tab[k] == j)

break

;

}

if

(k == i)

{

int

newSumV = sumV + V[j];

if

(newSumV <= MAX_V)

{

tab[k] = j;

int

newSumW = sumW + W[j];

pakowanie(i + 1, newSumV, newSumW);

}

else

{

if

(sumW>maxW)

{

maxW = sumW;

for

(

int

l = 0; l < N; l++) rozw[l] = 0;

for

(

int

l = 0; l <= i; l++) rozw[tab[l]] = 1;

}

}

}

}

}

public

static

void

main(String[] args)

{

pakowanie(0, 0, 0);

System.out.println(

"Wartosc optymalnie zapakowanego plecaka: "

+ maxW);

System.out.print(

"Przedmioty w plecaku: "

);

for

(

int

i = 0; i < N; i++)

if

(rozw[i] == 1) System.out.print(i +

" "

);

System.out.println();

}

}

4.

P

ROBLEM ODGADYWANIA LICZBY METODĄ DZIEL I ZWYCIĘŻAJ

.

class

OdgadywanieLiczbyDZ

{

private

static

int

liczba =

new

Random

().nextInt(1000 + 1);

private

static

int

krok;

public

static

void

main(

String

[] args)

{
znajdz(0, 1001);
}

static

void

znajdz(

int

a,

int

b)

{

krok++;

int

polowa = a + (b-a)/2;

if

(polowa == liczba)

System.

out

.println(

"Liczba "

+ liczba +

" znaleziona po "

+ krok +

" krokach.\n"

);

else

{

if

(liczba < polowa) znajdz(a, polowa);

if

(polowa < liczba) znajdz(polowa, b);

}

}

}

5.

P

ROBLEM OBLICZANIA WARTOŚCI DWUMIANU

N

EWTONA METODĄ PROGRAMOWANIA

DYNAMICZNEGO

.

public

class

newtondynamicznie

{

public

static

int

n = 5;

public

static

void

newton(

int

[][] t_newton,

int

k)

{

int

i, j, l = 0;

for

(i = 0; i < n; i++)

{
t_newton[i][0] = 1; t_newton[i][i] = 1;
}

for

(j = 2 + l; j < n; j++)

{

for

(i = 1; i < n; i++)

{
t_newton[j][i] = t_newton[j - 1][i - 1] + t_newton[j - 1][i];
}

if

(i == k)

{

break

;

}
l++;
}
}

public

static

void

main(String[] args) {

int

[] [] tab =

new

int

[n][n];

newton(tab,n);

for

(

int

i=0; i<tab.length-1;i++) {

for

(

int

j=0; j<tab.length-1;j++){ System.

out

.print(tab[i][j] +

" "

);

}
System.

out

.println(

""

); }}

}

6.

P

ROBLEM PLECAKOWY DECYZYJNY ALGORYTMEM ZACHŁANNYM

(

DOWOLNA HEURYSTYKA

).

class

PlecakDec

{
final

static

int

N = 6;

final

static

int

MAX_V = 10;

final

static

int

[] V = {6,2,3,2,3,1};

final

static

int

[] W = {6,4,5,7,10,2};

static

int

P(

int

i,

int

v)

{

int

w1;

int

w2;

if

(i == 0 && v < V[0])

return

0;

if

(i == 0 && v >= V[0])

return

W[0];

w1 = P(i-1,v);

if

(i > 0 && v < V[i])

return

w1;

w2 = W[i] + P(i-1,v-V[i]);

if

(w2 > w1)

return

w2;

else

return

w1;

}

public

static

void

main(String[] args)

{
System.

out

.println(

"Wartosc przedmiotow: "

+ P(N-1,MAX_V));

}
}

7.

P

ROBLEM KOSMONAUTÓW ALGORYTMEM ZACHŁANNYM

(

DOWOLNA HEURYSTYKA

).

public

class

KosmoZachlanny

{

final

static

int

N = 5;

// liczba kosmonautow

static

int

[][] D = { { 1, 0, 0, 1, 0 },

{ 0, 1, 1, 1, 0 },

{ 0, 0, 1, 0, 1 },

{ 1, 2, 0, 0, 1 } };

public

static

void

planuj()

{

boolean[] rozw =

new

boolean[N];

int

lKosmo = 0;

boolean[] rozwD =

new

boolean[N];

while

(

true

)

{

int

maxlD = 0;

int

maxPoz = -1;

for

(

int

i = 0; i<N; i++)

//Szukamy najlepszego w sensie liczby

dziedzin, ktory jeszcze nie zostal zabrany

{

if

(!rozw[i])

//jesli jeszcze nie zabrany

{

int

lD = D[0][i] + D[1][i] + D[2][i] + D[3][i];

if

(lD>maxlD)

{

maxlD = maxlD; maxPoz = i;

};

}

}

if

(maxPoz>-1)

{

for

(

int

i = 0; i<N; i++)

{

if

(D[0][maxPoz] == 1) rozwD[i] =

true

;

}

rozw[maxPoz] =

true

;

lKosmo++;

boolean AND =

true

;

for

(

int

i = 0; i<N; i++)

{

if

(!rozwD[i]) { AND =

false

;

break

; }

}

if

(AND)

break

;

}

else

break

;

}

System.out.println(

"Liczba kosmonautow: "

+ lKosmo);

System.out.print(

"Konsmonauci: "

);

for

(

int

i = 0; i < N; i++)

if

(rozw[i]) System.out.print(i + 1 +

" "

);

System.out.println();

}

public

static

void

main(String[] args)

{

planuj();

}

}

8.

P

ROBLEM PLECAKOWY DECYZYJNY METODĄ

M

ONTE

C

ARLO

.

class

PlecakowyMonteCarlo

{

static

final

int

N = 6;

// liczba przedmiotow

static

final

int

MAX_V = 10;

// objetosc plecaka

final

static

int

[] V = { 2, 6, 3, 3, 1, 2 };

// objetości przedmiotów

final

static

int

[] W = { 4, 6, 5, 10, 2, 7 };

// wartości przedmiotów

public

static

void

main(String[] args)

{

String optKonfig =

new

String();

int

optV = -1;

int

optW = 0;

Random los =

new

Random();

for

(

int

i = 0; i < 10; i++)

//Bedzie 10 prob losowania

{

int

[] ustaw =

new

int

[N];

//Inicjujemy wstepne ustawienie przedmiotow

for

(

int

j = 0; j < N; j++) ustaw[j] = j;

for

(

int

j = 0; j < N; j++)

//tasowanie przedmiotow

{

int

rndIndex = los.nextInt(N);

if

(rndIndex != j)

{

int

pom = ustaw[j];

//Zamiana elementow

ustaw[j] = ustaw[rndIndex];

ustaw[rndIndex] = pom;

}

}

String locKonfig =

new

String();

int

sumV = 0;

int

sumW = 0;

int

j = 0;

//Bierzemy przedmioty do plecaka od poczatku tablicy dopoki sie mieszcza

while

((j < N) && (sumV + V[ustaw[j]] <= MAX_V))

{

sumV = sumV + V[ustaw[j]];

sumW = sumW + W[ustaw[j]];

locKonfig = locKonfig +

" "

+ ustaw[j];

j++;

}

if

(sumW > optW)

{

optW = sumW;

optV = sumV;

optKonfig = locKonfig;

}

}

System.out.println(

"Calkowita objetość: "

+ optV);

System.out.println(

"Calkowita wartosc: "

+ optW);

System.out.println(

"Konfiguracja: "

+ optKonfig);

System.out.println(

"Niewykorzystana objętość: "

+ (MAX_V - optV));

}

}

9.

B

INARNE WYSZUKIWANIE ELEMENTU W TABLICY POSORTOWANEJ LICZB CAŁKOWITYCH

(

WERSJA

ITERACYJNA

).

public

class

BinarneIT {

static

public

boolean szukaj(

int

[] tab,

int

elem,

int

lewy,

int

prawy) {

while

(lewy <= prawy) {

int

srodek = (lewy + prawy) / 2;

if

(tab[srodek] == elem) {

return

true

;

}

if

(elem < tab[srodek]) {

prawy = srodek - 1;

}

if

(elem > tab[srodek]) {

lewy = srodek + 1;

}

}

return

false

;

}

static

public

void

main(String[] args) {

int

[] tab = { 1, 3, 4, 6, 8, 10 };

int

elem = 3;

boolean wynik = szukaj(tab, elem, 0, tab.length - 1);

System.out.println(

"Wynik="

+ wynik);

}

}

10.

B

INARNE WYSZUKIWANIE ELEMENTU W TABLICY POSORTOWANEJ LICZB CAŁKOWITYCH

(

WERSJA

REKURENCYJNA

).

public

class

BinarneRek

{

static

public

boolean szukaj(

int

[] tab,

int

elem,

int

lewy,

int

prawy)

{

if

(lewy <= prawy)

{

int

srodek = (lewy + prawy) / 2;

if

(tab[srodek] == elem)

return

true

;

else

{

if

(elem<tab[srodek])

return

szukaj(tab, elem, lewy, srodek - 1);

else

return

szukaj(tab, elem, srodek + 1, prawy);

}

}

return

false

;

}

static

public

void

main(String[] args)

{

int

[] tab = { 1, 3, 4, 6, 8, 10 };

int

elem = 3;

boolean wynik = szukaj(tab, elem, 0, tab.length - 1);

System.out.println(

"Wynik="

+ wynik);

}

}

11.

S

ORTOWANIE TABLICY METODĄ BĄBELKOWĄ

.

package scalanie;

public

class

Scalanie

{

// metoda sortuje elementy tablicy przekazanej jako parametr

public

static

void

sortowanieBabelkowe(

int

[] wejscie) {

// porównujemy pary elementów w tablicy

for

(

int

i = wejscie.length-1; i > 1; i--) {

for

(

int

j = 0; j < i; j++) {

// jeśli nie są one odpowiednio uporządkowane

// zamieniamy je miejscami

if

(wejscie[j] > wejscie[j+1]) {

// zamiana elementów

int

x = wejscie[j];

wejscie[j] = wejscie[j+1];
wejscie[j+1] = x;
}
}
}
}

// metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie

public

static

void

pokazTablice(

int

[] wejscie) {

// każdy element znajdujący się w tablicy wyświetlamy na ekranie

for

(

int

x : wejscie) System.

out

.print (x +

" "

);

System.

out

.println ();

}

public

static

void

main(String[] args) {

// tworzymy tablicę wypełniając ją od razu danymi

int

[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};

// wyświetlamy tablicę na ekranie

pokazTablice(tablica);

// sortujemy tablicę

sortowanieBabelkowe(tablica);

// wyświetlamy posortowaną tablicę na ekranie

pokazTablice(tablica);
}

}

12.

S

ORTOWANIE TABLICY METODĄ PRZEZ WSTAWIANIE

.

package scalanie;

public

class

Scalanie

{

// metoda sortuje elementy tablicy przekazanej jako parametr

public

static

void

sortowaniePrzezWstawianie(

int

[] wejscie) {

// pobieramy elementy z części nieposortowanej tablicy

for

(

int

i = 1; i < wejscie.length; i++) {

// zapisujemy element w zmiennej

int

liczba = wejscie[i];

// oraz jego indeks w tablicy

int

j = i;

// w pętli "robimy" dla niego miejsce w

// posortowanej części tablicy

while

(( j > 0) && (wejscie[j-1] > liczba)) {

wejscie[j] = wejscie[j-1];
j--;
}

// wstawiamy go na odpowiednie miejsce

wejscie[j] = liczba;
}
}

// metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie

public

static

void

pokazTablice(

int

[] wejscie) {

// każdy element znajdujący się w tablicy wyświetlamy na ekranie

for

(

int

x : wejscie) System.

out

.print (x +

" "

);

System.

out

.println ();

}

public

static

void

main(String[] args) {

// tworzymy tablicę wypełniając ją od razu danymi

int

[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};

// wyświetlamy tablicę na ekranie

pokazTablice(tablica);

// sortujemy tablicę

sortowaniePrzezWstawianie(tablica);

// wyświetlamy posortowaną tablicę na ekranie

pokazTablice(tablica);
}

}

13.

S

ORTOWANIE TABLICY METODĄ PRZEZ WYBÓR

.

package scalanie;

public

class

Scalanie

{

// metoda sortuje elementy tablicy przekazanej jako parametr

public

static

void

sortowaniePrzezWybieranie(

int

[] wejscie) {

// zmienna przechowująca rozmiar tablicy

int

rozmiarTablicy = wejscie.length;

// pętla przejścia przez wszystkie elementy tablicy

for

(

int

i = 0; i < rozmiarTablicy; i++){

// zakladamy, ze element na pozycji i jest najmniejszy

int

min = wejscie[i];

// zapisujemy indeks tego elementu

int

indeks = i;

// szukamy w pozostałej części tablicy elementu mniejszego niz min

for

(

int

j = i; j < rozmiarTablicy; j++){

// jesli jest taki, on staje się teraz elementam najmniejszym

if

(wejscie[j] < min) {

min = wejscie[j];

// zapisujemy jego indeks

indeks=j;
}
}

// zamieniamy miejscami elementy w tablicy

// najmniejszy z aktualnym wskazywanym przez zmienną i

wejscie[indeks] = wejscie[i];
wejscie[i] = min;
}
}

// metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie

public

static

void

pokazTablice(

int

[] wejscie) {

// każdy element znajdujący się w tablicy wyświetlamy na ekranie

for

(

int

x : wejscie) System.

out

.print (x +

" "

);

System.

out

.println ();

}

public

static

void

main(String[] args) {

// tworzymy tablicę wypełniając ją od razu danymi

int

[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};

// wyświetlamy tablicę na ekranie

pokazTablice(tablica);

// sortujemy tablicę

sortowaniePrzezWybieranie(tablica);

// wyświetlamy posortowaną tablicę na ekranie

pokazTablice(tablica);
}

}

14.

S

ORTOWANIE TABLICY METODĄ QUICKSORT

.

package scalanie;

public

class

Scalanie

{

// metoda zamienia miejscami elementy o indeksach i oraz j

// w tablicy przekazanej jako parametr

private

static

void

zamien(

int

[] wejscie,

int

i,

int

j) {

int

temp = wejscie[i];

wejscie[i] = wejscie[j];
wejscie[j] = temp;
}

// metoda dzieli tablicę (od indeksu p do indeksu k) na dwie części

// - elementy mniejsze od wybranego elementu

// - elementy większe od wybranego elementu

private

static

int

podzial(

int

[] wejscie,

int

p,

int

k) {

// wybieramy element wg którego będziemy dzielić

// np. element ostatni

int

element = wejscie[k];

// ustalamy zakres na którym będziemy operować

int

i = p;

int

j = k - 1;

// pętla wyszukuje kolejne elementy większe i mniejsze od

// elementu dzielącego (zmienna element)

while

(i <= j) {

while

(wejscie[i] <= element && i < k) i++;

while

(wejscie[j] > element && j > p) j--;

// jeśli elementy są na niewłaściwych pozycjach zamieniamy je

if

(i < j) zamien(wejscie, i, j);

// jeśli indeksy się zrównają kończymy pętlę

if

(i == j)

break

;

}

// na końcu wstawiamy element dzielący na właściwą pozycję

zamien(wejscie, i, k);

// i zwracamy tę pozycję

return

i;

}

// metoda sortuje elementy tablicy przekazanej jako parametr

// dodatkowo w jej wywołaniu podajemy indeks pierwszego i ostatniego elementu

public

static

void

sortowanieSzybkie(

int

[] wejscie,

int

i,

int

j) {

// jeśli indeksy są równe lub niepoprawne zakończ działanie

if

( j <= i )

return

;

// dzielimy tablicę na części, indeks miejsca podziału zapisujemy w zmiennej os (oś)

int

os = podzial(wejscie, i, j);

// rekurencyjnie dokonujemy posortowania lewej i prawej części naszej tablicy

sortowanieSzybkie(wejscie, i, os-1);
sortowanieSzybkie(wejscie, os+1, j);
}

// metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie

public

static

void

pokazTablice(

int

[] wejscie) {

// każdy element znajdujący się w tablicy wyświetlamy na ekranie

for

(

int

x : wejscie) System.

out

.print (x +

" "

);

System.

out

.println ();

}

public

static

void

main(String[] args) {

// tworzymy tablicę wypełniając ją od razu danymi

int

[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};

// wyświetlamy tablicę na ekranie

pokazTablice(tablica);

// sortujemy tablicę

sortowanieSzybkie(tablica, 0, tablica.length-1);

// wyświetlamy posortowaną tablicę na ekranie

pokazTablice(tablica);
}

}

15.

S

ORTOWANIE TABLICY METODĄ SCALANIA

.

public

class

Scalanie

{

private

static

final

int

N = 8;

private

static

final

int

tab[] = {4,3,2,2,3,9,4,1};

private

static

final

int

t[] =

new

int

[N];

// tablica pomocnicza

// scalanie dwóch posortowanych ciągów

private

static

void

scal(

int

pocz,

int

sr,

int

kon)

{

int

i,j,q;

for

(i=pocz; i<=kon; i++) t[i]=tab[i];

// przeniesienie do tab pomocniczej

i=pocz; j=sr+1; q=pocz;

// ustawienie wskaźników tablic

while

(i<=sr && j<=kon) {

// Przenoszenie danych z sortowaniem ze zbiorów

pomocniczych do tablicy głównej

if

(t[i]<t[j])

tab[q++]=t[i++];

else

tab[q++]=t[j++];
}

while

(i<=sr) tab[q++]=t[i++];

// Przeniesienie nie skopiowanych danych ze zbioru

pierwszego w przypadku, gdy drugi zbiór się skończył

}

// sortowanie od pocz do kon

public

static

void

sortowaniewstawianie(

int

pocz,

int

kon)

{

int

sr;

if

(pocz<kon) {

sr=(pocz+kon)/2;
sortowaniewstawianie(pocz, sr);

// dzielenie lewej części

sortowaniewstawianie(sr+1, kon);

// dzielenie prawej części

scal(pocz, sr, kon);

// złączenie części lewej i prawej

}
}

public

static

void

main(String[] args) {

int

i;

System.

out

.println(

"Przed sortowaniem:"

);

for

(i=0; i<N; i++)

System.

out

.print(tab[i] +

" "

);

sortowaniewstawianie(0,N-1);

System.

out

.println(

"\n Po sortowaniu:"

);

for

(i=0; i<N; i++)

System.

out

.print(tab[i] +

" "

);

}

}