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] +
" "
);
}
}