Todas as soluções possíveis para equação, onde os operadores são arbitrários?

5

Dado algo assim:

1 5 3 4 = 18

Eu preciso determinar (usando um algoritmo) se há uma combinação de operadores e colchetes que me levam a 18. Apenas "+" e "*" e "(" e ")" são permitidos.

Exemplo:

1 + 5 + (3 * 4) = 18

Além da força bruta, existe algum algoritmo em particular que seja capaz de calcular toda a combinação possível em tempo razoável? O RPN pode ajudar a codificar as possíveis soluções, mas as mesmas são muito (4 ^ n?).

    
por incognita 16.05.2011 / 09:26
fonte

3 respostas

5

A força bruta é realmente muito rápida se você evitar cálculos inúteis.

No pior dos casos você tem 2 ^ (N-1) operadores e N! (N-1)! formas de escolher os pares de números para as operações N-1. Então, por exemplo, para N = 4, isso dá 1.152 possibilidades.

Mas você pode reduzir isto substancialmente: se você vai olhar para 6 + 2 e 6 * 2, então não há necessidade de olhar para 2 + 6 e 2 * 6: apenas faça o número maior primeiro. Isso tira um fator de 2 ^ (N-1), trazendo o número de possibilidades para N! (N-1) !, então 144 para N = 4.

Há outras economias possíveis já que (20 + 6) +2 é o mesmo que 20+ (6 + 2), mas eu suspeito que isso não valha a pena otimizar até que N se torne grande. Outra é que a multiplicação por 1 não ajuda muito: esse tipo de coisa pode não ser uma economia com N = 4, mas poderia ser se você também estivesse olhando para a divisão (especialmente se o número menor não for um fator ou divisor de o maior número), como você pode remover um monte de possibilidades. A sugestão de rzzzwilson de parar quando o alvo é excedido funciona de maneira semelhante, embora só funcione se todas as operações não forem decrescentes (isto é, adição e multiplicação, mas não subtração ou divisão)

Como ilustração de algo semelhante, tente meu antigo applet Java aqui, com seis números e quatro operadores. Você pode colocar seus próprios números e alvo na caixa. Não é lindamente programado, mas ainda é bastante rápido.

    
por 16.05.2011 / 11:27
fonte
2

Problema interessante.

Eu não escrevi nenhum código, mas aqui estão meus pensamentos. Eu não fui capaz de pense em uma abordagem além da força bruta, com um pouco de "poda".

Usar uma representação RPN é o caminho a seguir, pois simplifica o manuseio de colchetes (como tal, eles vão embora). Usando o seu exemplo, o RPN é     1 5. 3 4 onde cada '. é um lugar onde um operador pode ser, exceto para o mais à direita '.' onde sabemos que tem que haver um ou mais operadores, porque é o RPN. Todos os outros '. tem zero ou mais operadores. Para valores N, você deve tem operadores N-1, é claro.

Agora, o problema se divide nessas partes: 1. Gere todas as combinações de operadores N-1 (2 ^ N) 2. Para cada combinação de operadores, gerar todos os 'recheios' do operador    pontos '.', isto é, agrupe a lista de operadores por 1s, 2s, ..., N-1s, mantendo    a ordem do operador (minha combinatorics-fu é fraca, não consigo descobrir isso) 3. Para cada combinação de combinações, avalie a expressão

A poda ocorre no último passo. Conforme você avalia, se a expressão valor vai além do resultado desejado, pare com uma falha, pois não há operadores que podem reduzir o valor da expressão.

    
por 16.05.2011 / 10:53
fonte
0

Este problema é NP completo e, portanto, não se pode esperar que seja solucionável em nada menor que O (n!). No entanto, como em todos os problemas NP completos, você pode, é claro, aproximar um algoritmo que o aproximaria de 18, ou alternativamente, geraria uma lista de números semelhantes com operadores que resultariam em 18.

    
por 16.05.2011 / 10:46
fonte