Descrição
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;
}
Scripts recomendados
Arvores Red Black
Aplicção em C++
Stack (LIFO)
Biblioteca dos.h
Biblioteca de tipos abstratos
Comentários
Indicar para um amigo
Escrever um script