ALGORITMOS E IMPLEMENTAÇÕESEncontrar as parcelas que compõem uma soma

Implementação de equações dentro da computação, programação e algoritmos.

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
CJAL
iniciante
Mensagens: 2
Registrado em: Sáb 18 Jul, 2020 22:32
Última visita: 24-09-21
Jul 2020 18 22:59

Encontrar as parcelas que compõem uma soma

Mensagem não lida por CJAL »

Prezados, boa noite. Esta é a minha primeira postagem aqui no Fórum. Perdoem-me se eu não utilizar uma linguagem matemática adequada, pois não sou desta área, embora trabalhe um pouco com ela. Tenho um problema computacional que gostaria de avaliar com vocês alguma solução eficiente.

Sejam p1, p2, p3, ..., pn o subconjunto de números primos contido no conjunto dos primeiros 64 números primos acima de 1000.

Problema: sabendo-se que todos, nenhum ou aleatoriamente alguns destes números primos compõem uma soma, a partir da soma informada, identificar quais são os números que a compõem. Obviamente, quando a soma é zero, nenhum número primo é utilizado e quando a soma corresponde a soma dos 64 números primos acima de 1000, todos eles compõem a soma. Todavia, a depender da situação somente alguns destes primos fazem parte da soma. Daí a necessidade de localizá-los rapidamente.

No problema são conhecidas as seguintes informações:

• O universo correspondente aos primeiros 64 números primos acima de 1000;
• O valor da soma dos 64 números primos deste universo;
• O valor da soma informada;
• O número n de parcelas que compõem a soma.

Se o problema tiver solução mais simples substituindo-se os 64 números primos por outra sequência, como uma PA, PG ou resultado de função (trigonométrica, logaritmo, etc.), peço a gentileza de discorrer. O conjunto dos primeiros 64 números primos acima de 1000 foi escolhido porque nenhum de seus componentes pode ser composto pela soma de outros componentes do mesmo conjunto.

Limitações: em razão de ser um problema computacional, fica inviável fazer a combinação aleatória ou sequenciada dos números e testa-las contra a soma. Assim, o método, se existir, deve ser mais eficiente. Ainda, multiplicar os número ou usar potências de 2 para depois fatorar também se mostra inviável em função da limitação para o cálculo e armazenamento do resultado da multiplicação.

Exemplo: sabendo que a soma de primos é 15493, quais números dentre os primeiros 64 primos acima de 1000 a compõe? O algoritmo, se existir, deve encontrar uma maneira eficiente de encontrar os primos 1039, 1051, 1061, 1091, 1103, 1117, 1123, 1249, 1259, 1283, 1297, 1367 e 1453.

Para facilidade, informa-se os primeiros 64 números primos acima de 1000:
1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459.

Aceito qualquer sugestão!

Grato por seu tempo.




Avatar do usuário
cpusam
sênior
Mensagens: 28
Registrado em: Qua 12 Fev, 2020 22:12
Última visita: 02-06-21
Ago 2020 08 22:05

Re: Encontrar as parcelas que compõem uma soma

Mensagem não lida por cpusam »

Caramba, esse problema pra mim não é nada simples. Acho que ele se trata mais de um problema derivado do Caixeiro Viajante.
Por exemplo:
-Os 64 números são 64 nós de um grafo
-temos então de um número para todos os uma relação, isso dá tipo um grafo completo.
-o que você quer é achar o caminho de tamanho 13 arestas que passa por K primos e some o número dado.
Nesse caso, usando força bruta acredito que dê pra usar uma permutação simples de 64!/(13!*(64-13)!), isso dá uma porrada de tentativas para 13 termos.

Eu estive estudando sozinho o problema do caixeiro viajante pra ver o que eu conseguia. Eu descobri uma fórmula que me dizia quantas combinações minimas seria preciso pra encontrar a primeira rota mínima.
Acho que o esse problema é tão difícil quanto o do caixeiro viajante.

Você viu onde tal problema? Fiquei curioso com isso.
Talvez se fizesse um algoritmo de estimativa estilo estimativa Fermi, pudesse dar uma resposta aproximada, mas acho que ai vai mais de criatividade do que de matemática pura.
Uma coisa que indico é o seguinte:
0-organize os 64 numeros do menor para o maior
1-comece com 2 termos e vá até 64, chame de X parcelas
2-vá comparando de X em X parcelas e contando quantos números são usados, comece do menor para o maior
3-se a soma alvo das parcelas de maior valor estiver entre essas parcelas, então é ali onde você deve procurar combinar
4-se não se a soma não estiver nas X parcelas e já tiver usados todos os 64 numeros, faça X_parcelas += 1 e volte ao passo 2

Supondo que chegue ao 3, dai teremos X parcelas e N números usados. daí é só pegar os N números e X parcelas e fazer a permutação simples.
No pior caso, você terá de fazer 64!/(32!*32!) combinações de 32 numeros para saber quantos somam o tanto lá.

É um algoritmo feio esse que eu fiz, mas se você entender ele pode te dar um norte melhor.




Avatar do usuário
Autor do Tópico
CJAL
iniciante
Mensagens: 2
Registrado em: Sáb 18 Jul, 2020 22:32
Última visita: 24-09-21
Ago 2020 11 16:46

Re: Encontrar as parcelas que compõem uma soma

Mensagem não lida por CJAL »

Prezado, obrigado pela resposta. Sim, eu estudei o problema do Caixeiro Viajante / Problema da Mochila, mas estes tem solução exponencial. Talvez seja a única solução possível.



Deleted User 25040
6 - Doutor
Última visita: 31-12-69
Set 2021 24 11:04

Re: Encontrar as parcelas que compõem uma soma

Mensagem não lida por Deleted User 25040 »

será que vc ainda está ai? acho que você poderia usar potencias de 2 já que não precisa que eles sejam primos




Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “ALGORITMOS E IMPLEMENTAÇÕES”