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

• Download part002.c
• Enviar nova versão

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;

}

S. MarioBros - Editor de fase 0.1

Ordenação quicksort

Tabuada com QT4

Fila em C

CD Player 0.1