Jump to content
thoga31

[Médio] 5 números, 5 condições, quantas soluções?

Recommended Posts

thoga31

Considere-se 5 números, A, B, C, D e E, que pertencem ao intervalo [1, 9].

Objectivo: pretende-se conhecer a lista de conjuntos {A, B, C, D, E} que cumpram as seguintes condições:

  1. A != B != C != D != E
  2. A + B + C + D + E = 23
  3. (A + B + C) / D = E
  4. Não se quer os conjuntos em que os valores de A, B e C sejam iguais entre si. Ou seja, o conjunto {1, 2, 3, 4, 5} é o mesmo que {3, 1, 2, 4, 5}, pelo que só se quer um deles. Isto deve-se ao facto de A+B+C constituir o numerador da condição nº3 - a ordem destes três números é, então, indiferente, e consideram-se os conjuntos-solução iguais.
  5. O ponto 4 aplica-se igualmente aos valores de D e E. Considerando que A+B+C = P, temos que P/D = E <=> P/E = D. Desta forma, considera-se que {1, 2, 3, 4, 5} é o mesmo que {1, 2, 3, 5, 4}.

Input: não aplicável.

Output: são esperados 6 conjuntos.

Restrições: incluídas no objectivo.


Knowledge is free!

Share this post


Link to post
Share on other sites
pmg

5 ciclos encadeados ... Brute Force FTW! :)


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
pmg

http://ideone.com/osrU8J

#include <stdio.h>

int main(void) {
   for (int a = 1; a < 10; a++) {
       for (int b = a + 1; b < 10; b++) {
           for (int c = b + 1; c < 10; c++) {
               for (int d = 1; d < 10; d++) {
                   if ((d == a) || (d == b) || (d == c)) continue;
                   for (int e = d + 1; e < 10; e++) {
                       if ((e == a) || (e == b) || (e == c)) continue;
                       if (a + b + c + d + e != 23) continue;
                       if ((a + b + c) / d != e) continue;
                       if ((a + b + c) % d == 0) printf("(%d + %d + %d) / %d = %d\n", a, b, c, d, e);
                   }
               }
           }
       }
   }
   return 0;
}

Edit

DIGA NAO A MAGIC NUMBERS

// ...
#define TARGET_SUM 23
// ...
                       if (a + b + c + d + e != TARGET_SUM) continue;

// ...

Edited by pmg
DIGA NAO A MAGIC NUMBERS

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
thoga31

A solução que eu e o @pwseo desenvolvemos enquanto estávamos a analisar o desafio do ponto de vista da Programação Funcional :D

import Control.Monad (guard)
import Data.List (nub, nubBy, permutations)

solutions = do
 a <- [1..9]
 b <- [1..9]
 c <- [1..9]
 d <- [1..9]
 e <- [1..9]
 guard $ nub [a,b,c,d,e] == [a,b,c,d,e]
 guard $ a + b + c + d + e == 23
 guard $ (a + b + c) / d == e
 return [a,b,c,d,e]

main :: IO ()
main = mapM_ (print . map truncate) $ nubBy f solutions
 where
   f (a:b:c:_) (d:e:f:_) = [a,b,c] `elem` permutations [d,e,f]

Aquele do pode ser reduzido ao seguinte, mas pessoalmente gosto mais do do:

solutions = [[a,b,c,d,e] | a <- [1..9], b <- [1..9], c <- [1..9], d <- [1..9], e <- [1..9], nub [a,b,c,d,e] == [a,b,c,d,e], a + b + c + d + e == 23, (a + b + c) / d == e]

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
thoga31

Os imports são fantasmas e tu tens medo de fantasmas, certo? :P

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
pmg

Agora ja funciona

http://ideone.com/5XCGSX

Eu nao sei Haskell, nao sei absolutamente nada de Haskell.

Nao sei (nao sabia) o que sao os imports ... e nao tenho medo de fantasmas.

Acho os imports muito importantes: tao importantes como os #includes em C

Edited by pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
thoga31

Agora ja funciona

http://ideone.com/5XCGSX

Eu nao sei Haskell, nao sei absolutamente nada de Haskell.

Nao sei (nao sabia) o que sao os imports ... e nao tenho medo de fantasmas.

Acho os imports muito importantes: tao importantes como os #includes em C

Calma, homem, estava apenas a brincar...

Mas uma coisa: se sabes o que são os #include's em C, então sabes o que são os import's, ou outra qualquer designação, noutras LP's. Todos têm a mesma função. :)


Knowledge is free!

Share this post


Link to post
Share on other sites
HappyHippyHippo

não vamos comparar resultados em relação a linguagens

é claro que cada uma tem um objectivo, tornado a realização de um trabalho mais simples ou não dependendo desse objectivo.

se usasse uma das muitas bibliotecas matemáticas de C que existem por ai, o calculo das permutações também seria numa linha.

se querem minimizar, peguem numa linguagem lógica como ProLog ou Mercury


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
pwseo

se querem minimizar, peguem numa linguagem lógica como ProLog ou Mercury

A linguagem usada pelo thoga tem uma funcionalidade que se adapta bem a este tipo de computações com diversos resultados, onde podemos simplesmente especificar os dados e as condições que estes devem cumprir. Semelhante a prolog, portanto, mas com outra sintaxe.

Aqui fica uma nova versão em Haskell praticamente sem imports (a função guard faz partida stdlib de Haskell e já existe "nativamente" nas list comprehensions, mas aqui importamos explicitamente para a podermos chamar dentro do bloco "do".

Inspirei-me na solução do pmg e passei para Haskell. A solução inicial do thoga31 não é tão optimizada porque o problema original nada dizia acerca de soluções "repetidas" (pontos 4 e 5), e havia 72 soluções iniciais.

import Control.Monad (guard)
 
solutions = do
  a <- [1..9]
  b <- [a + 1..9]
  c <- [b + 1..9]
  d <- [1..9]
  guard $ d `notElem` [a, b, c]
  e <- [d + 1..9]
  guard $ e `notElem` [a, b, c]
  guard $ sum [a, b, c, d, e] == 23
  guard $ quotRem (a + b + c) d == (e, 0)
  return [a, b, c, d, e]
 
main = mapM_ print solutions

EDITS: Correcções sugeridas pelo pmg mais abaixo.

Edited by pwseo

Share this post


Link to post
Share on other sites
pmg

No problema a resolver (com soma = 23) nao acontece que a divisao inteira de (a + b + c) por d de um valor "errado" igual a e. Com soma = 21 ja acontece ... e, segundo me parece, as solucoes Haskell apresentadas estao erradas ...

Exemplo: (1 + 6 + 7) / 3 = 4 (soma 21)

Para soma = 21 o problema apresentado nao tem solucoes!!

Edited by pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
pwseo

No problema a resolver (com soma = 23) nao acontece que a divisao inteira de (a + b + c) por d de um valor "errado" igual a e. Com soma = 21 ja acontece ... e, segundo me parece, as solucoes Haskell apresentadas estao erradas ...

Sim, tens razão, mas já alterei o meu exemplo para funcionar correctamente. De facto esse foi um erro introduzido por mim ao utilizar a divisão inteira (já tinha discutido isso com o thoga31 mas voltei a esquecer-me).

No teu exemplo em C isso não acontece porque há conversão dos inteiros para doubles durante o cálculo (acho eu), e o resultado final é truncado para um int. Como em Haskell os dados são fortemente tipados, tal conversão implícita não ocorre.

Solução: deixo o Haskell fazer os cálculos com Doubles (como já acontecia no exemplo do thoga) e converto o resultado final para Integer.

Edited by pwseo

Share this post


Link to post
Share on other sites
pmg

No teu exemplo em C isso não acontece porque há conversão dos inteiros para doubles durante o cálculo ...

Not quite

O codigo apresentado por mim apenas faz calculos inteiros.

O que acontece é que eu verifico o resultado da divisao inteira e o resultado do modulo

// ...
if ((a + b + c) / d != e) continue; // divisao
if ((a + b + c) % d == 0) printf("(%d + %d + %d) / %d = %d\n", a, b, c, d, e); // modulo
// ...


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.