간단하고 재미있는(?) 수학문제
글쓴이: litiblue / 작성시간: 수, 2009/09/30 - 9:14오후
1 5 6 7
+ - ×÷
위의 4개의 숫자와 사칙연산을 이용해서 식을 만드는데 결과가 21이 나오게 하는 겁니다.
숫자는 순서에 상관없이 한 번씩만 사용해야 되고,
연산자는 같은 연산자를 여러번 쓸 수는 있는데, 숫자가 4개니까 연산은 3번만 해야 됩니다.
ex) (1-5)×(6-7) = 4 (21이 아니므로 답x)
(7÷6)×(5÷1) = 35/6 (21이 아니므로 답x)
도저히 못 풀겠네요. 아무리 생각해도 답이 없는 것 같은데 ㅠ.ㅜ;
원래 '알고리즘'과목 숙제 문젠데 이게 진짜 문제는 아니고 이걸 풀어서 트리를 그려야 하거든요.
프로그램 짜서 돌리면 되긴 하지만 너무 귀찮아요. kldp 고수님들 도와주세요.
프로그래밍 질문 아니니까 여기에 올리겠습니다.
Forums:
몇줄 안될것
몇줄 안될것 같은데...
걍 모든 경우의 계산을 다 해버리면 되는거 아닌가요?
emerge money
http://wiki.kldp.org/wiki.php/GentooInstallSimple - 명령어도 몇 개 안돼요~
http://xenosi.de/
https://xenosi.de/
귀차니즘 때문에 ㅋ
넹 몇줄 안되는데 이 것도 c만 가지고 하려니 귀찮네요.
다른 언어로는 금방 할 수 있을법도 한데. ^^;
근데 nhn입사 문제에 이런 문제를 머리로 풀라는 문제가 나왔다는 소문을 들어서,
머리로 도전해봤지만 GG. ㅠ.ㅜ
^^
짜볼까 하다가 nhn
짜볼까 하다가 nhn 얘기에 자극받아서 머리로만 생각해 봤는데,
1은 1이고, 5와 7은 소수이고, 6은 2x3 입니다. 모든 경우에 공약수가 1 외에 없으니 일단 나눗셈은 무효입니다. (1은 일단 제외)
그 후에 곱셈, 1을 일단 제외하면 나머지 중 제일 작은 5와 6을 곱해도 30, 1과 7로는 답이 안나옵니다.
결국 덧셈과 뺄셈만 가지고 1,5,6,7 혹은 5,6,7로 (1은 곱셈으로 제거 가능) 21을 만들어야 한다... 고 생각했는데
그럼 답이 안나온다...는게 제 결론입니다.
틀렸으려나요? 크크.
중간 결과가 항상
중간 결과가 항상 정수여야 하는 제한이 없다면
두 수가 서로소라고 해도 나눗셈을 할 수 있다고 봐야하겠지요.
(정답도 이 점을 이용한 것이구요. ㅎㅎ)
저도 int 와 int의 연산 결과는 int라는 생각의 습관 때문에 답이 잘 안떠오르더라구요.
음...
방법이 있을듯 한데요. 간단히 해결될 것 같진 않군요.
1 5 6 7
+ - × ÷
일단, 위의 8가지를 조합하는 경우의 수는 8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 40320.
연산자가 숫자 사이에 들어가도록 해야 하므로 4만여 가지보다는 적게 나올것 같습니다.
그런데, 연산자 우선 순위 및 괄호도 따져서 계산해야 하나요?
처음 질문하신 연산수식을 보니까 괄호도 있는데요.
그럼 또 경우의 수가 늘어납니다.
프로그램 알고리즘은 트리구조로 자료구조화 하여,
재귀호출하면서, 연산자 우선순위를 따져가면서 트리탐색해야 될듯하네요~
From:
*알지비 (메신저: rgbi3307(at)nate.com)
*학창시절 마이크로마우스를 만들었고, 10년동안 IT관련 개발자로 일하고 있음.
*틈틈히 커널연구회(http://www.kernel.kr/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
(피연산자)(연산자)(피
(피연산자)(연산자)(피연산자)(연산자)(피연산자)(연산자)(피연산자) 의 꼴이 되어야 하는데, 연산자는 중복해서 쓸 수 있지만, 피연산자는 그렇지 않으므로 가능한 경우의 수는 4 * 4 * 3 * 4 * 2 * 4 * 1 = 1536 개가 되겠네요.
--------------------------------------------------------------------------------
http://blog.sumin.us
그렇다면 원본 문제를 ..
제가 문제를 잘 못 해석했을 가능성이 다분 하네요.
그래서 문제를 한 번 올려볼까 합니다.
Draw an expression tree that has four external nodes, storing the numbers 1,5,6, and 7 (with each number stored one per external node but not necessarily in this order), and has three internal nodes, each storing an operation from the set {+,-,x,/} of binary arithmetic operators, so that the value of the root is 21. The operators are assumed to return rational numbers (not integers), and an operator may be used more than once(but we only store operator per internal node).
ALGORITHM DESIGN 이라는 책의 연습 문제 랍니다. 보시면 알겠지만 원래는 수식 트리를 그리는 문제 입니다. 그런데 수식트리가 문제가 아니죠ㅠ 조건이 문제지. 왠지 주객전도가 된 듯한 문제라는..
결국 프로그램을 짜야 하나요? 일단 자고 일어나서 열심히 코딩 해봐야겠습니다. 혹시 제가 잘 못 이해했다면 지적해주세요. ^^;
^^
문제 원문을 보니,
연산자 우선순위에 대한 언급은 없군요.
단지, {+,-,*,/} 연산자를 이진트리의 내부노드(internal node)로 구성하고,
{1,5,6,7} 숫자는 이진트리의 외부노드(external node)로 구성하는 것입니다.
문제에 충실한 답은,
트리의 높이(height)가 3인 완전 이진트리가 그려지고,
가지노드(내부노드)에 연산자들이 배치되는 경우의 수는 24.
리프노드(외부노드)에 숫자가 배치되는 경우의 수는 4! == 24.
전체 이진트리 경우의 수는 24x24 == 576.
이진트리 576개마다 InOrder로 탐색하면 되는데, 완전 노가다겠죠?
결국, 무식하게 반복연산을 빠르게 하는 컴퓨터의 힘을 빌려야 겠네요~
From:
*알지비 (메신저: rgbi3307(at)nate.com)
*학창시절 마이크로마우스를 만들었고, 10년동안 IT관련 개발자로 일하고 있음.
*틈틈히 커널연구회(http://www.kernel.kr/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
저도 아는 문제 하나
저도 아는 문제 하나 있는데...
한 노인이 친구인 수학자와 길을 걸어가며 나누는 대화
노인: 내 세 아들의 나이를 모두 곱하면 36 인데, 걔네들 나이가 각각 얼마인지 맞춰 보겠나?
수학자: (곰곰히 생각해 보더니) 정보가 더 필요하네.
노인: (지나치던 빌딩을 바라보며) 걔들 나이를 모두 더하면 저 빌딩의 창문 수와 같다네.
수학자: (신중히 생각하더니) 정보가 더 필요하네.
노인: 첫째 녀석 (the oldest son) 눈이 파란색 이라네.
수학자: 알았네. 각각 xxx 군!
세 아들 나이의 곱,
세 아들 나이의 곱, x*y*z = 36, x, y, z 는 모두 자연수.
{1, 1, 36}
{1, 2, 18}
{1, 3, 12}
{1, 4, 9}
{1, 6, 6}
{2, 2, 9}
{3, 3, 4}
세 아들의 나이를 모두 더하면 어떤 빌딩의 창문의 수, n, 와 같음.
1 + 1 + 36 = 38
1 + 2 + 18 = 20
1 + 3 + 12 = 16
1 + 4 + 9 = 14
1 + 6 + 6 = 13
2 + 2 + 9 = 13
3 + 3 + 4 = 10
중복되는 경우는
{1, 6, 6}
{2, 2, 9}
"the oldest sons" 가 아닌 "the oldest son" 이라고 말했으므로, 가장 나이가 많은 아들의 나이는 집합에서 유일한 요소임.
따라서 가능한 조합은 {x, y, z} = {2, 2, 9}
--------------------------------------------------------------------------------
http://blog.sumin.us
"세 아들의 나이를
"세 아들의 나이를 모두 더하면 어떤 빌딩의 창문의 수, n, 와 같음."
에서 왜 중복되는 경우가 빠져나오는건가요? ㅡㅜ
노인이 "걔들 나이를
노인이 "걔들 나이를 모두 더하면 저 빌딩의 창문 수와 같다네" 라고 말했을 때 수학자가 답을 한번에 알아내지 못하고 질문을 한번 더 했기 때문입니다.
--------------------------------------------------------------------------------
http://blog.sumin.us
질문을 한번
질문을 한번 더한거랑 중복이랑 무슨 상관인거죠 ㅡㅜ?
상황상 질문 한번 더했을때 노인이 "중복이 되는것중 하나가 답이다" 라는 말을 해야지만이 논리가 맞을거같은데요?
제가 이해를 못하고있다면 좀더 설명을 ㅡㅜ
아
아 죄송합니다.
창문을 수학자도 셀수가 있는 상황이군요 -_-;;
이제 이해를 ㅡㅜ
수학자는 창문의
수학자는 창문의 갯수를 알고 있다는게 포인트죠.
1 + 1 + 36 = 38
1 + 2 + 18 = 20
1 + 3 + 12 = 16
1 + 4 + 9 = 14
1 + 6 + 6 = 13
2 + 2 + 9 = 13
3 + 3 + 4 = 10
에서, 만약 창문의 갯수가 10개 였으면 3,3,4살이라는걸 바로 알 수 있었을텐데,
창문이 13개 있었기 때문에 가능한 경우가 두가지가 되고, 정보가 더 필요해졌습니다.
...이미 눈치채셨군요.
참고로 {2, 3, 6} 이
참고로
{2, 3, 6}
이 빠져있군요..ㅎㅎ
다른 사이트에서도 올렸는데 답이 있었네요
똑똑한 수험생들(오래된 사이트라 대학생인 사람들도 많지만) 많다는 오르비에서 답이 나왔네요.
내가 너무 대충 풀었나. ㅠ.ㅜ;
http://www.orbi7.com/Board/BoardView.aspx?ID=xi_agit_counsel&BoardID=219233&SearchValue=&SearchOption=&CurrentPage=2&PageState=0&Category=0&orderstr=&orderType=
링크 겁니다.
^^
brute force로 찾아
brute force로 찾아 보니...
>>> a = set([1,5,6,7]) >>> b = set([('+',lambda x,y:x+y), ('-',lambda x,y:x-y), ('*',lambda x,y:x*y), ... ('/',lambda x,y:1.*x/y if y else 9e99)]) >>> c = set([('((%d%s%d)%s%d)%s%d',lambda a,b,c,d,e,f,g: f(d(b(a,c),e),g)), ... ('(%d%s(%d%s%d))%s%d',lambda a,b,c,d,e,f,g: f(b(a,d(c,e)),g)), ... ('(%d%s%d)%s(%d%s%d)',lambda a,b,c,d,e,f,g: d(b(a,c),f(e,g))), ... ('%d%s((%d%s%d)%s%d)',lambda a,b,c,d,e,f,g: b(a,f(d(c,e),g))), ... ('%d%s(%d%s(%d%s%d))',lambda a,b,c,d,e,f,g: b(a,d(c,f(e,g))))]) >>> for i in a: ... for jj,j in b: ... for k in a-set([i]): ... for ll,l in b: ... for m in a-set([i,k]): ... for nn,n in b: ... for o in a-set([i,k,m]): ... for pp,p in c: ... v = p(i,j,k,l,m,n,o) ... if 20 < v < 22: print pp%(i,jj,k,ll,m,nn,o),v ... 6/(1-(5/7)) 21.0라는 군요. 좀 전에 올렸던 코드는 케이스가 하나 빠져 있었습니다...
오오..이거슨진리
오 역시ㅠ.ㅜ 감동의 kldp ㅋㅋ 수고하셨습니다.
막상 저는 답을 알고나니 코딩 열의가 사라지는 ..
근데 brute force가 뭔가요? 프로그래밍 언어 인가요?
저번에 다른 게시물에서도 본 듯한데.
^^
bruce force는 가능한
bruce force는 가능한 모든 방법을 시도해본다는 뜻으로 알고 있습니다.
Cryptography에서 쓰는 bruce force attack은(사전 전사공격) 가능한 모든 암호키를 대입하여
올바른 키를 찾는 것을 의미합니다.
아 그렇군요
그런데 저분이 쓰신 언어는 무슨 언어죠?
^^
python이군요
.....
저는 언제쯤 저렇게 생각한대로
구현을 할 수 있을지 부럽;;;;네요 ㅡㅜ
=================================
이제는 앞만 보며 전진해야만 할뿐.......
BLOG : http://khmirage.tistory.com/
==================================================================
정체된 일상.... 계기를 만들어야 하는데........
BLOG : http://khmirage.tistory.com/
' 0 ')
이런걸 순수하게 짜네는 사람들이 부럽습니다..
============================================================
선한 인간이냐 악한 인간이냐는 그사람의 의지에 달렸다. -에픽테토스-
의지 노력 기다림은 성공의 주춧돌이다. -파스퇴르-
============================================================
============================================================
선한 인간이냐 악한 인간이냐는 그사람의 의지에 달렸다. -에픽테토스-
의지 노력 기다림은 성공의 주춧돌이다. -파스퇴르-
============================================================
어떤게 먼저 인가요?
http://wiki.answers.com/Q/How_do_you_combine_1_5_6_7_to_21_using_addition_subtraction_and_multiplication
검색의 힘?!
오옷..
헐 도대체 어떻게 찾으신건지 ㅠ.ㅜ; 검색스킬이 마냥 존경스러울 뿐.
^^
....
http://www.google.com/search?q=1+5+6+7+21
;;
뭐라 드릴말씀이 .. ;;
문제를 푸는덴 참 다양한 방법이 존재하는군요.
^^
답이 나와버렸으니-_-
답이 나와버렸으니-_- 저도 제가 푼 방법을 공개합니다.
우선 경우의 수를 세 가지로 나누었습니다. 1, 5, 6, 7
1. 숫자 연산자 (나머지 세 숫자의 연산 결과)
2. (두 숫자의 연산 결과) 연산자 (두 숫자의 연산 결과)
3. (세 숫자의 연산 결과) 연산자 숫자
1번의 경우 가능한 경우.
+: 1 + 20, 5 + 16, 6 + 15, 7 + 14
5,6,7로 20을 만들거나, 1,6,7로 16, 1,5,7로 15, 1,5,6으로 14를 만들 수 있으면 됩니다. 전부 실패
-: 20보다 큰 수가 없으므로 +의 경우와 동일합니다.
*: 1 * 21, 5 * 21/5, 6 * 21/6, 7 * 3
5,6,7로 21은 불가. 1,6,7로 21/5를 만드는 건 밑이 5인 건 6-1 뿐이므로 불가.
1,5,7로 21/6, 곧 7/2를 만드는 것. 밑이 6인 경우는 5+1, 7-1인데 둘다 불가. 밑이 2인 것도 7-2이므로 불가. 1,5,6으로 3을 만드는 것도 불가.
/: 1 / 1/21. 5 / 5/21, 6 / 6/21, 7 / 7/21
5,6,7로 1/21 만드는 것 불가. 1,6,7로 5/21 만드는 것도 불가.
1,5,7로 2/7 만들기 왠지 가능해보임. 밑이 7이니 1/7, 5/7을 가지고 시도. 1/7은 5를 어떻게 해도 안 나옴. 5/7은 1에서 빼면 2/7이 나옴. 이거다!
그 결과, 6 / (1 - 5/7) 정답.
참고로, 1번과 3번은 +,-,*에서 거의 같기 때문에 3번은 /의 경우만 검토하면 됨. 2번이 가장 경우의 수가 많아서 어려운데 다행이 1, 3번을 찾다가 답이 나왔네요-_-
저는 Perl로
#!/usr/bin/env perl #a,b,c,d and A,B,C stand for numbers and operators, respectively my @tree_type = ("((aAb)B(cCd))", "(aA((bBc)Cd))", "(aA(bB(cCd)))", "(((aAb)Bc)Cd)", "((aA(bBc))Cd)"); my $nums = "1567"; my $Ops = "+-*/"; my @permuted_nums = (); permute([split("", $nums)], []); my @Ops = split("", $Ops); foreach my $op1 (@Ops) { foreach my $op2 (@Ops) { foreach my $op3 (@Ops) { foreach my $n (@permuted_nums) { foreach my $tree (@tree_type) { $_=$tree; s/A/$op1/g;s/B/$op2/g;s/C/$op3/g; s/a/$$n[0]/g;s/b/$$n[1]/g;s/c/$$n[2]/g;s/d/$$n[3]/g; my $expression = $_; $val=eval "$expression"; if ($val == 21) { print "$expression = $val\n"; } } } } } } sub permute { my @items = @{$_[0]}; my @perms = @{$_[1]}; unless (@items) { push @permuted_nums, \@perms; } else { my (@newitems, @newperms, $i); foreach $i (0 .. $#items) { @newitems = @items; @newperms = @perms; unshift (@newperms, splice(@newitems, $i, 1)); permute([@newitems], [@newperms]); } } } Dirk-Gently:~/Opus/Perl ioseph$ ./permute.pl (6/(1-(5/7))) = 21갑자기 궁금해 지네요
이런 프로그램은 어떤 언어로 짜면 가장 짧고 간결하게 짤 수 있을까요?
생산성 좋다는 파이썬으로 짜면 어떤가요? lisp은요? ^^; 궁금하네요.
^^
위에 제가 짠 코드가
위에 제가 짠 코드가 파이썬입니다. 가장 짧은 파이썬 코드는 아닙니다 -- itertools에 permutation 생성해 주는 게 있는 걸로 기억하는데 함수 이름을 기억해낼 수 없어서 당장 생각할 수 있는 최선의 코드를 짰습니다.
Common Lisp을 사용해서 날림으로 만들어 보면...
(defparameter *number-table* '(1 5 6 7)) (defparameter *func-table* '(+ - * /)) (defconstant answer 21) (defun perm (l) (if (null l) '(()) (mapcan #'(lambda (x) (mapcar #'(lambda (y) (cons x y)) (perm (remove x l :count 1)))) l))) (mapcar #'(lambda (seq) (multiple-value-bind (a b c d) (apply #'values seq) (dolist (f1 *func-table*) (dolist (f2 *func-table*) (dolist (f3 *func-table*) (handler-case (if (= (eval `(,f1 ,a (,f2 ,b (,f3 ,c ,d)))) answer) (format t "~a~a(~a~a(~a~a~a)) = ~a~%" a f1 b f2 c f3 d answer)) (division-by-zero () 'pass))))))) (perm *number-table*)) ... 6/(1-(5/7)) = 21뭔가 맘에 안 들지만 일단은 돌아갑니다... :)
-----
익명으로 쓴 글은 볼 수 없습니다.
http://monpetit.tistory.com/
-----
http://monpetit.posterous.com/
http://monpetit.tistory.com/
Lisp으로 C programming
Lisp으로 C programming 하셨군요. 저 위에 creativeidler님 설명과 유사하게 되어야 Lisp의 장점을 최대한 살려서 다른 프로그래밍 언어와는 확연한 차이를 보여줘야 정답(?)에 가깝지 않나 생각합니다. 즉, 사람의 사고를 기계에 번역한 듯한 느낌이 드는 것 보다 사람의 사고를 그대로 프로그래밍 언어로 표현한 듯한 느낌이 들어야 잘된 Lisp 프로그램 이라고 생각합니다.
예를 들면,
(defconstant +expression-templates+
'((exp1 + exp2 = answer)
(exp1 - exp2 = answer)
(exp2 - exp1 = answer)
(exp1 * exp2 = answer)
(exp1 / exp2 = answer)
(exp2 / exp1 = answer)))
에서 시작해서 컴퓨터가 주어진 answer에 대해 exp1과 exp2를 찾아나가서 최종적으로
exp1 = 6
exp2 = (exp21 - exp22)
exp21 = 1
exp22 = (exp221 / exp222)
exp221 = 5
exp222 = 7
이 나와야 된다고 생각합니다. Symbolic computation, Lisp의 장점중 하나죠.
시간 되면 한번 해보면 재미있겠는데, 워낙 벌려논 일들이 많아서 (핑계를 대며)... 언젠가 한번 준비되면 작성해 보렵니다.
그러게 말입니다.
그러게 말입니다. 이런 한심한 프로그램을 대체 누가 짰는지... 하하...
한 언어의 문법을 아는 것과 그 언어의 특성 또는 장점을 살리는 건 전혀 다른 문제라는 걸 다시 한 번 느낍니다.
게다가 아무 생각 없이 뚝딱 짠 프로그램은 역시나 버그투성이구요.
-----
익명으로 쓴 글은 볼 수 없습니다.
http://monpetit.tistory.com/
-----
http://monpetit.posterous.com/
http://monpetit.tistory.com/