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.700 ]
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; }
[GAME-2] Acerte os rortões nas janelas (jogo com gráficos)
Agenda feita em C usando árvore binária
Como escolher o melhor escalonador de CPU para melhorar o desempenho da máquina
Curiosidade sobre DOOM Guy e Isabelle de Animal Crossing
Inicializando servidor Ubuntu na AWS e rodando apache em Container
Instalando TeamViewer no Debian 12
Conheça o Octopi, outro frontend para o Pacman com acesso ao AUR (Arch Linux e derivados)
Terminal transparente no Debian 12 com interface i3wm usando Xfce4-Terminal e Compton
Eu estou com problemas para usar o QBASIC no Dosbox X (4)