Matematické Fórum

Podobné se řešily zde tak třeba pomůže.

Já jsem to tedy řešil tou metodou pokus-omyl s tím, že jsem neověřoval, jestli je to nejjednodušší řešení. Tady je (pokud nezáleží na tom v jaké nádobě má být jaký objem):
10   7    7    4  -  objemy nádob
10   0    7    0  -  počáteční rozdělení
0     6    7    4  -  přelití objemu první nádoby nejprve do čtvrté, zbytek do druhé
7     6    0    4  -  přelití třetí nádoby do první
7     6    4    0  -  přelití čtvrté nádoby do třetí
7     2    4    4  -  naplnění čtvrté nádoby obsahem druhé
10   2    5    0  -  přelití objemu čtvrté nádoby nejprve do první, zbytek do třetí
6     2    5    4  -  naplnění čtvrté nádoby obsahem první
6     2    7    2  -  doplnění třetí nádoby obsahem čtvrté
10   2    3    2  -  doplnění první nádoby obsahem třetí

Proto jsem psal, že je to řešení v případě, že nezáleží na tom, v jaké nádobě má být jaký objem. Navíc v zadání není přesně specifikované pořadí nádob. Je tedy nutné, aby dva litry byly v sedmilitrových nádobách a tři litry ve čtyřlitrové?

↑ warchief:Systematické řešení je (třeba) pomocí tzv. stavového grafu.
Sestavíme všechny přípustné stavy a orientovanou (případně neorientovanou) hranou spojíme ty, mezi kterými existuje přelití podle pravidel.
Ve výsledném grafu hledáme nejkratší orientovanou cestu z výchozího do požadovaného stavu. Pěkně se to programuje.

Poznámka: Existuje i konstrukce řešení pomocí tzv. barycentrických souřadnic, ale to už je nad rámec, neboť pro 5 nádob bychom pracovali v pětirozměrném prostoru a pěkně kreslit se to stejně nedá.

Diky moc ;)

Měl bych tady něco z podobného soudku:)
Máme nádoby o objemu 10, 6, 9, 3 a 10 litru. Ty dvě desetilitrové jsou plné. A musíme docílit aby v nádobách bylo 5, 5, 5, 3 a 2litrů(přesně v tomto pořadí. Minimální počet má být 13 přelití, ale myslím že to není důležité.
Mám podobný problém jako Warchief:(

To "strojové řešení" znamená, že jsem to naprogramoval - konkrétně v Delphi. Takto vypadal zdroják, asi to není úplně nejelegantnější, ale psal jsem to tehdy zřejmě docela narychlo.

program sudy;

{$APPTYPE CONSOLE}

uses
  SysUtils,
  Classes,
  Contnrs;

type TPole = array[1..4] of Byte;
     TStav = class
       H: TPole;
       Cesta: String;
     end;

const Kap: TPole = (10, 7, 7, 4);

var F: TObjectQueue;
    Pom, Pom2: TStav;
    Pole: TPole;
    i, j: Integer;
    Bylo: array[0..10, 0..7, 0..7, 0..4] of Boolean;

begin
  F := TObjectQueue.Create;
  Pom := TStav.Create;
  Bylo[10, 0, 7, 0] := true;
  Pom.H[1] := 10;
  Pom.H[3] := 7;
  F.Push(Pom);
  while F.AtLeast(1) do begin
    Pom := F.Pop as TStav;
    if (Pom.H[1] = 10) and (Pom.H[2] = 2) and (Pom.H[3] = 2) and (Pom.H[4] = 3) then begin
      WriteLn(Pom.Cesta);
      Break;
    end else for i := 1 to 4 do for j := 1 to 4 do
     if (i <> j) and (Pom.H[i] > 0) and (Pom.H[j] < Kap[j]) then begin
      Pole := Pom.H;
      if Pole[i] > (Kap[j] - Pole[j]) then begin
        Pole[j] := Kap[j];
        Pole[i] := Pom.H[i] + Pom.H[j] - Kap[j];
      end else begin
        Pole[j] := Pom.H[i] + Pom.H[j];
        Pole[i] := 0;
      end;
      if not Bylo[Pole[1], Pole[2], Pole[3], Pole[4]] then begin
        Bylo[Pole[1], Pole[2], Pole[3], Pole[4]] := true;
        Pom2 := TStav.Create;
        Pom2.Cesta := Pom.Cesta + ' ' + IntToStr(i) + IntToStr(j);
        Pom2.H := Pole;
        F.Push(Pom2);
      end;
    end;
    Pom.Free;
  end;
  ReadLn;
end.

↑ fofo:
Z    10    0    0    0    10
================
1)    4    6     0    0    10
2)    4    6     9    0     1
3)    1    6     9    3     1
4)    0    6     9    3     2
5)    6    0     9    3     2
6)    6    6     3    3     2
7)   10   2     3    3     2
8)   10   0     5    3     2
9)   10   3     5    0     2
10)  7    3     5    3     2
11)  7    5     5    3     0
12)  5    5     5    3     2

Hotovo
PS  Je to tedy na 12 přelévání - ty píšeš, že minimální počet je 13.
Když to kontroliji, pak v mém postupu chybu nikde nevidím.

↑ fofo:
Jo rozumíme si. Máš pravdu.
Já v té euforii zapomněl, že není 2-litrová, ale desetilitrová.

↑ fofo:
A co takto:
       1     2    3    4     5      z  do
Z    10    0    0    0    10
=====================
1)    4    6     0    0    10     1   2
2)    4    6     9    0     1      5   3
3)    4    6     9    1     0      5   4
4)    4    0     9    1     6      2   5
5)    0    4     9    1     6      1   2
6)    0    4     5    1    10     3   5
7)    0    6     5    1     8      5   2
8)    6    0     5    1     2      2   1
9)    6    6     5    0     2      5   2
10) 10   2     5    1     2       2   1
11)  8    2     5    3     2       1   4
12)  8    5     5    0     2       4   2
13)  5    5     5    3     2       1   4

Když vám to tak hezky jde tak něco složitějšího:)
máme nádoby o objemu 10,6,9,9 a 10l ve kterých je 10,0,0,0 a 10l a máme dostal objemy 8,2,0,2 a 8l (v tomto pořadí)
minimum je 16 přelití(ale netrvám na tom)
tak s chutí do toho;)

↑ Honzc:
Opět správně:) Jsi fakt dobrej;)