Programozás‎ > ‎Feladatok‎ > ‎Számolós‎ > ‎

Megoldás

Leírás

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.

Megvalósítás

Be: n, k
t[n]:=1
Ciklus i := (n - 1)-től (n - k + 1)-ig
  t[i] := 2 * t[i + 1]
Ciklus vége
Ciklus 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





Comments