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 a recursão pura e simples sem armazenar os valores já calculados, necessitando de um novo cálculo a cada chamada.

Isto porque pelo método de recursão, ela pode ter a necessidade de calcular valores anteriormente calculados.

Quanto maior o valor requerido, maior o tempo.

Quem não tiver saco de esperar a eternidade de cálculo para os valores deste código, sugiro modificar para um tempo que não seja tão cansativa a demora.

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

• Download part001.c
• Enviar nova versão

Esconder código-fonte

#include <stdio.h>

unsigned int part (unsigned int n) {

   if (n<0) return 0;
   if (n==0) return 1;
   if (n<=3) return n;

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

   for (k=1,s=1;i<n||j<n;k++,s=-s) {

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

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

   }

   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));

   return 0;

}

Driver ATI que funciona

Manipulação de um vetor de registros

Lista Simplesmente Encadeada

Arquivos utilizados no artigo: "Desenvolvendo um plugin para o XMMS"

Fibbonacci com Memoization - O(n)