tartaglia.pas

{ COMIENZO DE DESCRIPCION

C\'alculo del n\'umero combinatorio $ C (n,r) $, donde
$ 0 \le r \le n $, usando el tri\'angulo de Tartaglia
(o de Pascal) mediante:
i)  un procedimiento (muy caro) basado en la siguiente
    propiedad recursiva:
    $ C (n,r) = 1 $, si $r=0$ o $r=n$, sino
    $ C (n,r) = C (n-1,r-1) + C (n-1,r) $, en los
    dem\'as casos;
ii) un procedimiento por programaci\'on din\'amica, en
    donde directamente se construye el tri\'angulo de
    Tartaglia hasta el nivel requerido.
Por ejemplo, para el n\'umero combinatorio $ C (30,12) $
constatamos $k1=172.986.449$ llamadas de recursi\'on,
las cuales se reducen a $k2=930$ operaciones por
programaci\'on din\'amica.
keywords: algoritmos

FIN DE DESCRIPCION }
{
 numero        nro de llamadas           nro de llamadas
 combinatorio    por recursion        por prog. dinamica
 C (16, 8)              25.739                       129   
 C (30,12)         172.986.449                       930
}
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ Id: tartaglia.pas 2002/06/20 mstorti Exp jdelia rodrigop  }

program  tartaglia ;
const
  Nbig = 100;
	
type
  entero = longint ;
	  
var 
  count1 : entero ; { contador llamadas recursivas }
  count2 : entero ; { contador operac. en el trian. Pascal }
  a : array [1..Nbig, 1..Nbig] of entero;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ERROR (s : string) ;
begin
   write ('ERROR: ');
   writeln (s);
   halt ;
end ; { procedure }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure LEE_DATOS (var n, r: entero);
begin
   writeln ;
   writeln (' Calculo del numero combinatorio C (n r) ');
   writeln (' en donde 0 <= r <= n, por: ');
   writeln (' a) recursion (muy caro)    ');
   writeln (' b) programacion dinamica   ');
   writeln ;
   write   (' numero de elementos         ; n = ? ');
   readln  (n);
   write   (' a tomar en combinaciones de ; r = ? ');
   readln  (r);
   if ( n < 0    ) then ERROR (' debe ser n >= 0 ') ;
   if ( r < 0    ) then ERROR (' debe ser r >= 0 ') ;
   if ( r > n    ) then ERROR (' debe ser 0 <= r <= n ') ;
   if ( n > Nbig ) then ERROR (' n > Nbig ') ;
end ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ numero combinatorio por propiedad recursiva en el
  triangulo de Pascal (o de Tartaglia)                      }
function TARTA1 (n, r: entero): entero ;
begin
   count1 := count1 + 1 ;
   if  ( n = 1 ) or ( r = 0 ) or ( r = n ) then
     TARTA1 := 1
   else begin
     TARTA1 := TARTA1 (n - 1, r) + TARTA1 (n - 1, r - 1)
   end ; {if}
end ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ numero combinatorio por programacion dinamica, en donde
  directamente se construye el triangulo de Pascal          }
function PASCALBIN (n, m : entero): entero;
var
   i, j : entero;
begin  
   for i := 1 to (n) do begin
      for j := 1 to (n + 1) do begin
	 if (j = 1) or (j = i+1) then
	    a [i,j] := 1
	 else begin
	    a [i,j] := a [i-1, j-1] + a [i-1,j];
	 end ; {if}
	 count2 := count2 + 1;
      end ; {j}
   end ; {i}
   PASCALBIN := a [n, m+1];
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ programa ppal}
var	  
   n, r, z1, z2 : entero ;
begin	       
   count1 := 0 ;
   count2 := 0 ;
   LEE_DATOS (n, r);
   z1 := TARTA1    (n, r) ;
   z2 := PASCALBIN (n, r) ;
   writeln ;
   writeln (' por recursion             C (n,r) = ', z1);
   writeln (' por programacion dinamica C (n,r) = ', z2);
   writeln ;
   writeln (' nro de llamadas recursivas        = ', count1);
   writeln (' nro de operac. en progr. dinamica = ', count2);
   writeln (' ');
end .

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}