Van egy 7 és egy 13 literes tejjel teli kanna, valamint egy 19 literes üres kanna. A kérdés: Legkevesebb hány lépésben lehet (csak a három kanna felhasználásával! ) az egyes kannákba történő áttöltögetéssel kimérni az összes tejmennyiség felét?

A legrovidebb megoldas nekem ez lett

A: 19 literes

B: 13 literes

C: 7 literes

A, B, C

0 13 7

7 13 0

19 1 0

12 1 7

12 8 0

5 8 7

5 13 2

18 0 2

18 2 0

11 2 7

11 9 0

4 9 7

4 13 3

17 0 3

17 3 0

10 3 7

10 10 0

Huh! Nem teljesen értem a kérdést. Ott nem világos, hogy hol kell lenni az összes tejmennyiség felének. Feltételezem, hogy a 19 literesbe kell kimérni a felét.

A 13 literesből átöntök 3 litert a 19 literesbe.

A 7 literesből átöntöm a 7 litert a 19 literesbe.

Így a 19 literesben, és a 13 literesben 10-10 liter tej lesz.

Minden ABC betukbol alkotott par meghataroz egy atontest. pl AB azt jelenti, hogy A-bol B-be ontunk amig B meg nem telik vagy A ki nem fogy.

Ilyen betu parbol vagy 6 db.

Ezekbol a parokbol alkotott sorozatok megadnak egy atontesi strategiat.

n hosszu sorozatbol 6^n kulonbozo van, de nem mindnek van ertelme. Pl nem lehetnek ismetlodesek a sorozatban, es az elso elem az csak 2 kulonbozo lehet, that valojaban felso hatarnak (2/5)*5^n sokkal jobb, de meg ez is egy boseges felul becsles. Mivel 2 kulonbozo muvelet mindig lehetseges, ezert 2^n egy also becslese az ertelmes ontogetesi sorozatoknak.

Egy adott sorozat vizsgalatanal meg kell allni ha egy ures edenybol probalunk atonteni valamit, ha teli edenybe probalunk onteni valamit. Ekkor a fa hibasnak minostiheto es a sorban kovetkezo fa vizsgalatara lehet atterni.

Szinten meg kell allni, ha valamelyik edenyben pontosan 10 liter folyadek van, ez ugyanis egy helyes megoldast ad.

Kene irni egy python scriptet a keresesre.

Szelessegi keresessel Kb 100 millio sorozatot fog kelleni vegigvizsgalni mire meglesz az eredmeny.

A: 19 literes

B: 13 literes

C: 7 literes

A, B, C sorrendbe felirva minden egyes atontesi lepesben elofordulo UJ konfiguraciot egy meg kezelheto listat kapunk:

(ne feledjuk, csak olyan uj eloszlast irjunk fel ami meg nem volt, amibe nem lehet kevesebb lepessel eljutni.)

0)

(0,13,7)

1)

(7,13,0), (13,0,7)

2)

(19,1,0), (7,6,7); (13,7,0), (19,0,1)

3)

(12,1,7); (14,6,0); (6,7,7); (6,13,1)

4)

(12,8,0); (14,0,6); - ; (6,8,6)

5)

(5,8,7);(1,13,6); (12,8,0)

6)

(5,13,2);(1,12,7);

7)

(18,0,2);(8,12,0);

8)

(18,2,0);(8,5,7)

9)

(11,2,7);(15,5,0)

10)

(11,9,0);(15,0,5)

11)

(4,9,7);(2,13,5)

12)

(4,13,3); -

13)

(17,0,3)

14)

(17,3,0)

15)

(10,3,7)

megvan a 10-es.

Sajnos ez ugyanaz mint az elozo megoldasom, csak most mar tudjuk, hogy 15 lepesen belul nem lehet megcsinalni (hacsak el nem kerulte egy atontesi lehetoseg a figyelmemet)

Hmm ez mozaikos, tudsz linket is adni hozza? A KoMaL-t szoktam figyelni, hogy ahhoz ne adjak meg valaszt. Kar, hogy utolag nem lehet torolni amit beirt az ember. Lehet jelenteni az adminoknak ha akarod, ok el tudjak tuntetni a kerdest.

Amugy meg egy masik megoldasi lehetoseg:

A fenti allapotvektotokat hasznalva kiszamithato, hogy van 8*13-1 = 103 kulonbozo allapotvektor. (a 7 literes edenyben lehet 0-7 liter, a 13 literesben 0-13 liter, es olyan nincs, hogy mindkettoben 0 legyen)

Ezeket egy graf pontjainak tekinthetuk es nyilat huzunk be egyik pontbol a masikba, ha 1 atontessel at lehet jutni egyik allapotbol a masikba.

Ez egy 103 pontos iranyitott graf, meg pont kezelheto.

Van 15 lehetseges vegallapot, amikor valamelyik edenyben: vagy a 13 literesben, vagy a 19 literesben pont 10 liter folyadek van.

Van egy kezdoallapot. Kerdes az, hogy melyik a legrovidebnb iranyitott ut a kezdo allapotbol valamelyik vegallapotba. Ha programozas megoldas jar valakinek a fejeben, ez szerintem egy gyors megoldasra fog vezetni.