Aula 2.27 - Exercício sobre como encontrar os números que formam as partições únicas de um inteiro qualquer.
Exercício: Fazer a decomposição de um número inteiro positivo na soma de todos os possíveis fatores. Exemplo:
4
3+1
2+2
2+1+1
1+1+1+1
Entendeu? Tente fazer aí.
~
~~
~~~
~~~~
~~~~~
Resolução:
Bom, a ideia é imprimir os números em ordem decrescente. Os números que formam uma decomposição são obtidos a partir da decomposição que fizemos anteriormente a eles, por exemplo na decomposição do número 4: "2 + 2" é obtido a partir de "3 + 1". Cada decomposição é armazenada no vetor "vet[]" que é inicializado com o número que deseja decompor, assim imprimimos o vetor e em seguida atualizamos ele com a próxima decomposição. O loop do primeiro while (linha 5) termina quando a decomposição atual for somente de números 1 (linha 17).
Como obter uma decomposição a partir da decomposição atual? Bom, dado o vetor e seu tamanho, nós precisamos atualizar o vetor para armazenar a próxima decomposição. Valores no vetor precisam estar em ordem decrescente.
1- Encontre um valor diferente de 1 a mais direita do vetor, e armazene a contagem de números 1's na variável "vaium", que indicará a soma dos valores no lado direito a ser atualizado. Nossa variável "ultimo" será nosso index de valores diferentes de um.
2- Decremente o valor do vetor em 1 e aumente o valor de "vaium" em 1 (linhas 20 e 21). Assim:
- Se o vetor na posição da variável "ultimo" é maior ou igual a variável "vaium", coloque "vaium" na posição "ultimo" do vetor, assim o vetor na posição "ultimo+1" será nossa nova decomposição (linhas 28 e 29).
3- Copie o vetor na posição "ultimo" para posição "ultimo+1" e reduza "vaium" enquanto o vetor na posição "ultimo" for menor que "vaium".
Recomendo realizar um teste de mesa, caso tenha ficado complexo o entendimento.
Fonte: https://www.geeksforgeeks.org/generate-unique-partitions-of-an-integer/
COMENTÁRIOS