Função "Partição de Inteiros" Recursiva COM Tabela Estática em C

Publicado por Perfil removido (última atualização em 22/06/2012)

[ Hits: 5.010 ]

Download part002.c




De quantos modos diferentes pode-se escrever 6 como soma de números maiores que zero?

6 = 5+1 = 4+2 = 3+3 = 4+1+1 = 3+2+1 = 2+2+2 = 3+1+1+1 = 2+2+1+1 = 2+1+1+1+1 = 1+1+1+1+1+1

11 modos diferentes. p(6) = 11.

O cálculo do número de partições de um inteiro usa uma recursão bem mais demorada que a dos números de Fibonacci ou a fatorial.

Este exemplo usa variáveis estáticas dentro da implementação da função.

Quando um valor é calculado, ele simplesmente é armazenado para consulta futura, já que este cálculo recursivo solicita valores já calculados em sua recursão.

Poderia ser citado por alguém o uso a função realloc(), mas preferi deste modo para observar o funcionamento do código.

A tabela dos valores anotados é expandida quando há a necessidade de serem armazenados mais valores que a sua capacidade naquele instante da execução.

O tempo de demora é absurdamente inferior ao que seria se não fosse usada essa tabela.

Há uma condição na função que se verificada destrói a tabela, usada para desalocar o espaço ao fim da execução.

Pode-se testar a destruição da tabela antes de uma chamada da função em main() para ser verificada a eficácia.

Parte dos resultados pode ser conferida neste link: http://oeis.org/A000041

  



Esconder código-fonte

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

unsigned int part (unsigned int n) {

   static unsigned int tam = 0;
   static unsigned int *tab;
   static unsigned int *tmp;

   if (n==-1 && tab!=NULL) { 
      free (tab);
      tab = NULL;
      tam = 0;
      return 0;
   }      

   if (n==0 || tam<n) {

      tmp = (unsigned int *) calloc ((n<4?4:n+1),sizeof(unsigned int));

      if (tmp==NULL) {
         puts("Erro de alocacao");
         exit (1);
      }

      if (tam<4) {
         *(tmp+0) = 1;
         *(tmp+1) = 1;
         *(tmp+2) = 2;
         *(tmp+3) = 3;
         tam = 3;
      } else {
         unsigned int m;
         for (m=0;m<=tam;m++)
            *(tmp+m) = *(tab+m);
         free (tab);
      }

      tab = tmp;
      tmp = NULL;
      tam = n;

   }

   if (n<0) return 0;
   if (n<=3) return *(tab+n);

   unsigned int i=0, j=0; 
   unsigned int p=0;
   unsigned int k, s;

   if (*(tab+n)) 
      return *(tab+n);
   else {
      for (k=1,s=1;i<n||j<n;k++,s=-s) {

         i = (3*k*k-k)/2;
         j = (3*k*k+k)/2;

         if (i<=n) p += s * ((*(tab+(n-i))==0)?part(n-i):*(tab+(n-i)));
         if (j<=n) p += s * ((*(tab+(n-j))==0)?part(n-j):*(tab+(n-j)));

      }

      *(tab+n) = p;
   }

   return p;

} 

int main (void) {

   printf ("particao de %3u = %15u\n", 30, part(30));
   printf ("particao de %3u = %15u\n", 60, part(60));
   printf ("particao de %3u = %15u\n", 45, part(45));
   printf ("particao de %3u = %15u\n", 90, part(90));
   printf ("particao de %3u = %15u\n", 120, part(120));
   printf ("particao de %3u = %15u\n", 105, part(105));

   part(-1);

   return 0;

}

Scripts recomendados

torre de hanoi em C

Pilha

Árvore AVL ordenação

Informação do sistema

Programa recursivo para obter raiz quadrada


  

Comentários


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts