Informatika gyűjtemény

Egy szinttel feljebb Megoldás

2004050607080910

NézetNyomtat

A megoldás algoritmusa

Tá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.

Az algoritmus:

     Be: n, k 
     t[n]:=1
     Ciklus i := (- 1)-től (- k + 1)-ig 
          t[i] := 2 * t[+ 1]
     Ciklus vége
     Ciklus i := (- k)-tól 1-ig 
          a := 0
          Ciklus j := (+ 1)-től (+ k)-ig 
              a:=+ t[j]
          Ciklus vége
          t[i] := a
     Ciklus vége
     Ki: t[1]

Megoldások