ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      01 Mar 2002  16:12:28
 To : Valera Selev
 Subject : Задачка
 -------------------------------------------------------------------------------- 
 

 
 Replying to a message of Valera Selev to All:
 
  VS>     Есть N прямоугольных блоков, 3<=N<=100, из которых составляют
  VS> "ступеньки". Ширина основы должна быть не меньше 2, и каждый шаг
  VS> вправо должен вести вверх (т.е. для двух соседних столбцов правый
  VS> строго выше левого). Для заданого N определить, сколько различных
  VS> вариантов можно "построить" из N блоков. Hапример, для N=5 влзможно
  VS> только два варианта, для N=11 - 11.
 
 Пусть S(n,k) число лесенок из n блоков и k ступенек. Тогда
 
 S(n,k) = S(n-1*k,k-1) + S(n-2*k,k-1) + ... + S(n-[n/k]*k,k-1).
 
 Это формула получается так: если первая ступенька имеет высоту 1, то выше ее
 находится лесенка из N-k блоков и k-1 ступенек; если первая ступенька имеет
 высоту 2, то выше ее находится лесенка из N-2*k блоков и k-1 ступенек и т.д.
 Максимальная высота первой ступеньки равна [n/k].
 
 Очевидно, что S(0,1) = 0 и S(n,1) = 1 для всех n>0. 
 
 Решение задачи выглядит так: 
 
 ===cut===
 var S:array[0..100,1..100] of longint;
     n,k,i,j:integer;
     m:longint;
 begin
   readln(n);
   S[0,1]:=0; for i:=1 to n do S[i,1]:=1;
   for k:=2 to n do for i:=1 to n do
   begin
     S[i,k]:=0;
     for j:=1 to (i div k) do inc(S[i,k],S[i-k*j,k-1]);
   end;
   m:=0;
   for k:=2 to n do inc(m,S[n,k]);
   writeln(m);
 end.
 ===cut===
 
 Regards,      ш.ш
         Max    ~
 
 --- FleetStreet 1.27.3.7
  * Origin:  (2:5015/60)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Задачка   Valera Selev   01 Mar 2002 00:04:16   Задачка   Max Alekseyev   01 Mar 2002 16:12:28