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.680 ]
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; }
Calculando PI usando série de Leibniz
Agenda feita em C usando árvore binária
Atenção a quem posta conteúdo de dicas, scripts e tal (2)
Manutenção de sistemas Linux Debian e derivados com apt-get, apt, aptitude e dpkg
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
Como Atualizar Fedora 39 para 40
Instalar Google Chrome no Debian e derivados
Consertando o erro do Sushi e Wayland no Opensuse Leap 15
Instalar a última versão do PostgreSQL no Lunix mantendo atualizado
Flathub na sua distribuição Linux e comandos básicos de gerenciamento
ASRock H310CM-HG4 vs Linux [RESOLVIDO] (18)
Microfone do meu headset não é recinhecido. Meu notebook é um Acer Asp... (12)