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
Contar elementos de uma lista encadeada
Braco Robotico em OpenGL
Lista Simplesmente Encadeada
Script MakePach para correção de platarforma 32 bits para 64
Arvore Binária
Comentários
Indicar para um amigo
Escrever um script