Západočeská univerzita v Plzni

Fakulta aplikovaných věd

katedra informatiky a výpočetní techniky

ZÁPOČTOVÁ PRÁCE z UIR

Dva džbány, zadání č.: 106

4. 5. 2007	Martin Lipinský

A05450 KS

1. Formulace úlohy (zadání)

Zpracujte jednoduchý výcvikový program který plně demonstruje nalezení správného řešení (včetně všech ostatních) následující úlohy.

Máte k dispozici dva kameninové neprůhledné džbány – jeden o objemu a litrů a druhý o objemu b litrů přičemž b < a. Vaším úkolem je naplnit větší (tj. a litrový) džbán naléváním, přeléváním a vyléváním přesně c litry vody (c<a && c!=b); například máme čtyř- a třílitrový džbán a postupným naléváním, přeléváním a vyléváním máte větší (čtyřlitrový) naplnit dvěma litry vody.

Program zpracujte zcela obecně tak, aby bylo možno zadávat libovolné a,b i c při zachování zadaných podmínek (testujte). V případě řešitelnosti vypište všechna řešení v pořadí od nejlepšího k nejhoršímu.

2. Analýza úlohy

Úloha je vlastně stavový prostor reprezentovaný dvojicí (A,B).

Počáteční stav je (0,0)

Koncový stav je (C,0<=B<=Bmax)

A šest možných operátorů

Naplň A		(A,B) ->	(Amax,B)
Naplň B		(A,B) ->	(A,Bmax)
Vylij A		(A,B) ->	(0,B)
Vylij B		(A,B) ->	(A,0)
Přelij z A do B	Jeli A+B < Bmax	(A,B) ->	(0,A+B)
	Jeli A+B > Bmax	(A,B) ->	(A-(Bmax-B),Bmax)
Přelij z B do A	Jeli A+B < Amax	(A,B) ->	(A+B,0)
	Jeli A+B > Amax	(A,B) ->	(Amax,B-(Amax-A)

přičemž některé operace nemají zjevně smysl a jde je vyřadit hned při pokusu o jejich zavolání, například vylívání prázdného džbánu.

3. Popis algoritmu řešení

Program jednoduše „prohledáváním do hloubky“ projde všechny možné stavy které mohou nastat přičemž hlídá že se stavová dvojice (A,B) nedostala do stavu ve kterém již byla (slepá cesta). Po každém úspěšném kroku zároveň testuje jestli se nedostal do stavu který je požadovaný. Pokud to nastane, cestu si zapamatuje jako „výherní“ a pokračuje v prohledávání dokud neprojde celý stavový prostor a nezapamatuje si všechny výherní cesty.

Na závěr potom už jen vypíše všechny výherní cesty a nebo zahlásí že pro zadané hodnoty neexistuje žádné řešení (seznam výherních cest je prázdný).

Popis programu (programová dokumentace)

Jako programovací jazyk byla zvolena Java. Hlavním důvodem bylo že s ním mám největší zkušenosti. Neméně podstatnou výhodou je vestavěná podpora pro spoustu programových struktur které výrazně zrychlují a zjednodušují výsledný kód. Program není výrazně strojově náročný takže nebylo třeba, například z důvodu rychlosti či optimalizací volit nižší programovací jazyk. Zároveň je Java OO jazyk což implementaci celého procházecího algoritmu rekurzí včetně pamatování si prošlé cesty a provedených operací výrazně usnadnilo.

5. Popis obsluhy programu (uživatelská dokumentace)

Program je velmi jednoduchý. Vyžaduje pouze zadaní tří celých čísel reprezentujících velikost džbánu A, velikost džbánu B a množství vody kterou chceme odměřit do džbánu A, přičemž je kontrolováno že čísla odpovídají podmínkám uvedeným v zadání zpracovávané úlohy.

V případě chybného zadaní výchozích hodnot program zahlásí chybu. Pokud je zadání v pořádku, program zanalyzuje zadaná data a vytiskne výherní postupy pro zadané parametry případně ohlásí že daná úloha nemá řešení.

6. Rozbor výsledků, zhodnocení, závěr

Program se podařilo odladit. Neprováděl jsem z časových důvodů žádné rychlostní ani programové optimalizace. Nezdá se pro zkoušená zadaní že by to bylo třeba. Je zde ale jistě prostor k vylepšení.

Západočeská univerzita v Plzni

Vaclav Matousek

2007-06-04T22:27:00