LeírásTároljuk egy t[] tömbben a lehetőségek számát, jelentse t[i] azt, hogy az i., (i+1)., ..., n. tárgy hányféle módon kerülhet a kemencébe.Ha az i. tárgyat d másikkal együtt égetjük ki, akkor a maradék tárgyak elhelyezéseinek száma t[i + d + 1], ahol d lehetséges értékei: 0, 1, ..., k - 1. (t[n + 1] = 1) Minden lehetséges d más csoportosítást ad, tehát d-re összegezve kapjuk meg t[i] értékét. A t[] tömb elemei t[n], t[n-1], ..., t[1] sorrendben határozhatók meg. t[n] = 1 és az utolsó k tömbelem 1, 2, 4, ..., 2k - 1, hiszen ezekre még nincs kapacitás korlát, ezért minden tárgy esetén dönthetünk, hogy új csoportot kezdünk-e. MegvalósításBe: n, k t[n]:=1 Ciklus i := (n - 1)-től (n - k + 1)-ig t[i] := 2 * t[i + 1] Ciklus végeCiklus i := (n - k)-tól 1-ig a := 0 Ciklus j := (i + 1)-től (i + k)-ig a:=a + t[j] Ciklus vége t[i] := a Ciklus vége Ki: t[1]Megoldások:Tihanyi Balázs (VB.NET): tb_szam.vb Torma Róbert (Pascal): tr_szam.pas Mészáros Balázs (C): mb_szam.c |
|
|
2004-2016 BDG algoritmus szakkör