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.858 ]
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; }
Ponteiro para Ponteiro para Ponteiro
Script para trocar o papel de parede do fluxbox em GTK
Jogo da Velha com IA invencivel
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Meu Fork do Plugin de Integração do CVS para o KDevelop
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Cups: Mapear/listar todas as impressoras de outro Servidor CUPS de forma rápida e fácil
Criando uma VPC na AWS via CLI
Tem como instalar o gerenciador AMD Adrenalin no Ubuntu 24.04? (16)
Arch Linux - Guia para Iniciantes (2)
Problemas ao instalar o PHP (11)
Tenho dois Link's ( IP VÁLIDOS ), estou tentando fazer o failover... (0)