Função "Partição de Inteiros" Recursiva SEM Tabela Estática em C
Publicado por Perfil removido (última atualização em 14/06/2012)
[ Hits: 5.981 ]
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
#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; }
Busca, inserção e remoção de elementos numa lista
Programa recursivo para obter raiz quadrada
Mudando Cor da Letra e Fundo de Tela
Aprenda a Gerenciar Permissões de Arquivos no Linux
Como transformar um áudio em vídeo com efeito de forma de onda (wave form)
Como aprovar Pull Requests em seu repositório Github via linha de comando
Visualizar arquivos em formato markdown (ex.: README.md) pelo terminal
Dando - teoricamente - um gás no Gnome-Shell do Arch Linux
Como instalar o Google Cloud CLI no Ubuntu/Debian
Mantenha seu Sistema Leve e Rápido com a Limpeza do APT!
Procurando vídeos de YouTube pelo terminal e assistindo via mpv (2025)
Alguém já usou o framework Avalonia para desenvolver interfaces de usu... (4)
Ajuda Pra Melhoria do NFTABLES. (8)
Sinto uma leve lentidão ao arrastar, miniminizar e restauras as janela... (2)
Pastas da raiz foram para a área de trabalho [RESOLVIDO] (7)