| 이전 주제 보기 :: 다음 주제 보기 |
| 글쓴이 |
메시지 |
김진영_
가입: 2009년 12월 9일
올린 글: 337
|
 올려짐: 2010년10월18일 23:14 주제: *숙제 4, 문제 1* 테스트 케이스를 제공해 드립니다. (몇 가지 경우 추가) |
 |
|
이번 숙제의 목적 중 하나는 올바른 프로그램인지 확신하기가 쉽지 않은 문제를 겪어 보는 것입니다.
간단한 테스트 케이스를 일부 제공해 드립니다. 물론 아래의 경우에 모두 맞는 답을 낸다고 해서 여러분의 프로그램이 올바르다는 보장은 없습니다. 하지만 어느 정도나마 숙제에 도움이 되셨으면 합니다. 수강생 여러분들의 추가적인 테스트 케이스 공유도 환영합니다.
| 코드: | (smatch (list 1 2 3)
(dot (dot (atom 1) (atom 2)) (atom 3)))
;#t
(smatch (list 1 2 3)
(dot (atom 1) (dot (atom 2) (atom 3))))
;#t
(smatch (list 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(star (star (optional (atom 1)))))
;#t
(smatch (list 1 2 3 4 5 6 7 8 9 0)
(dot
(dot
(dot (atom 1) (atom 2))
(dot (atom 3) (dot (atom 4) (atom 5))))
(dot
(dot (atom 6) (atom 7))
(dot (atom 8) (dot (atom 9) (atom 0))))))
;#t
(smatch (list 1)
(optional (optional (optional (atom 1)))))
;#t
(smatch ()
(optional (optional (optional (atom 1)))))
;#t
(smatch (list 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 8 9 9)
(dot
(dot (star (atom 9)) (star (atom 8)))
(bar (optional (atom 9)) (star (atom 9)))))
;#t
(smatch (list 1 0 0 1 1 2 2 2 2 0 1 0 1 2 2 0 0 1 1 1 1 1 1 2 0 0 0 1 0 1 0 0 1 2 2 2 2)
(dot (dot (atom 1) (star (bar (bar (star (atom 0)) (star (atom 1))) (star (atom 2))))) (atom 2)))
;#t
(smatch (list 1 0 0 1 1 2 2 2 2 0 1 0 1 2 2 0 0 1 1 1 1 1 1 2 0 0 0 1 0 1 0 0 1 2 2 2 1)
(dot (dot (atom 1) (star (bar (bar (star (atom 0)) (star (atom 1))) (star (atom 2))))) (atom 2)))
;#f
(define c1 (dot (dot (dot (atom 0)
(optional (atom 1)))
(optional (dot (atom 1)
(atom 0))))
(dot (optional (bar (dot (atom 3)
(atom 7))
(dot (atom 1)
(atom 0))))
(star (dot (star (atom 9))
(optional (atom 0)))))))
(smatch (list 0) c1)
;#t
(smatch (list 0 1) c1)
;#t
(smatch (list 0 3 7) c1)
;#t
(smatch (list 0 1 1 0 3 7 0 0 0 0 0 0 9 0 9 0 9 9 0) c1)
;#t
(smatch (list 0 1 1 0 3 7 1 0 0 0 0 0 0 0) c1)
;#f
(define c2 (dot (atom 0)
(star (bar (atom 1)
(dot (optional (atom 2))
(atom 3))))))
(smatch (list 0 1 1 1 1 1 1 3 1 1 3 3 1 3 1 3 3) c2)
;#t
(smatch (list 0 1 2 3 1 2 3 1 2 3 1 2) c2)
;#f
(smatch (list 0 1 1 1 1 1 1 1 2) c2)
;#f
|
김진영_ 가 2010년10월19일 20:28에 수정함, 총 2 번 수정됨 |
|
| 위로 |
|
 |
이종혁
가입: 2010년 9월 6일
올린 글: 11
|
| 올려짐: 2010년10월18일 23:18 주제: |
|
|
감사합니다  |
|
| 위로 |
|
|
심규민
가입: 2010년 10월 2일
올린 글: 21
|
| 올려짐: 2010년10월19일 11:36 주제: |
|
|
by 김찬민, 장준영, 심규민
| 코드: |
(smatch '(3 4) (atom 4))
(smatch '(0 1) (dot (atom 0) (atom 1)))
(smatch '(0) (bar (atom 0) (atom 1)))
(smatch '(2) (optional (atom 2)))
(smatch '(3 3 3 2) (star (atom 3)))
(smatch '(3 3 3 2) (dot (star (atom 3)) (optional (atom 2))))
(smatch '(2 3 3 2) (dot (optional (atom 2)) (dot (star (atom 3)) (atom 2))))
(smatch '(1 0 1 0 0 1 0 1 1 0) (star (bar (dot (atom 1) (atom 0)) (dot (atom 0) (atom 1)))))
(smatch '(1 0 1 0 0) (star (dot (atom 1) (atom 0))))
(smatch '(0 1 2 3) (bar (dot (optional (atom 0)) (optional (atom 1))) (dot (atom 2) (atom 3))))
(smatch '(1 0 1) (dot (optional (atom 1)) (bar (dot (optional (atom 0)) (optional (atom 1))) (dot (atom 2) (atom 3)))))
(smatch '(9 9 9 9) (dot (optional (atom 9)) (dot (dot (optional (atom 9)) (optional (atom 9))) (optional (atom 9)))))
(smatch '(9 9 9) (dot (optional (atom 9)) (dot (dot (optional (atom 9)) (optional (atom 9))) (optional (atom 9)))))
(smatch '(0 1 0) (dot (dot (optional (atom 0)) (optional (atom 1))) (dot (optional (atom 1)) (optional (atom 0)))))
(smatch '(0 1 0) (dot (atom 0) (bar (dot (optional (atom 0)) (optional (atom 1))) (dot (optional (atom 1)) (optional (atom 0))))))
(smatch '(0 0 0 0 9) (star (optional (atom 0))))
(smatch '(2 3 2 1 0 4) (star (dot (dot (dot (dot (optional (atom 0)) (optional (atom 1))) (optional (atom 2))) (optional (atom 3))) (optional (atom 4)))))
(smatch '(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2) (dot (star (bar (dot (atom 1) (atom 1)) (atom 1))) (atom 2)))
(smatch '(1 1 1 1 1 1 1 1 1 1 1 1 2) (dot (star (bar (dot (dot (atom 1) (atom 1)) (atom 1)) (bar (dot (atom 1) (atom 1)) (atom 1)))) (atom 2)))
(smatch '(0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 1 2) (dot (star (bar (bar (dot (atom 0) (atom 1)) (atom 0)) (dot (atom 1) (atom 0)))) (atom 2)))
(smatch '(0) (atom 0))
(smatch '(8 4) (dot (atom 8) (atom 4)))
(smatch '(9 6) (dot (dot (optional (atom 9)) (optional (atom 3))) (dot (optional (atom 6)) (optional (atom 7)))))
(smatch '(1 7) (dot (optional (dot (atom 1) (atom 0))) (dot (atom 1) (atom 7))))
(smatch '(1 1 1 1 1 1 1 1 1) (star (atom 1)))
(map (lambda (x) (smatch x (dot (star (dot (atom 1) (atom 0))) (atom 1)))) '((1 1) (1 0 1) (1 0 1 0 1) (1 0 1 0 2)))
(map (lambda (x) (smatch x (bar (dot (atom 1) (atom 2)) (dot (bar (atom 3) (atom 4)) (atom 5))))) '((1 2) (1 0) (1 3) (1 5) (2 4) (2 5) (3 4) (3 5) (4 5) (6 8 9)))
(map (lambda (x) (smatch x (dot (star (dot (optional (atom 7)) (optional (atom 5)))) (star (atom 4))))) '((7 5 4) (7 7 5 7 5 5 5 5 4 4) (7 4 5 4) (5 7 5 4) (5 7 4) (4 4 4) (3 1 9 2) (7 7 4)))
(map (lambda (x) (smatch x (dot (star (dot (atom 7) (optional (atom 5)))) (star (atom 4))))) '((7 5 4) (7 7 5 7 5 5 5 5 4 4) (7 4 5 4) (5 7 5 4) (5 7 4) (4 4 4) (3 1 9 2) (7 7 4)))
(map (lambda (x) (smatch x (dot (dot (bar (atom 1) (optional (atom 3))) (bar (atom 5) (atom 7))) (dot (bar (atom 2) (atom 4)) (bar (atom 6) (atom 8)))))) '((1 2 3 4) (1 3 2 4) (1 5 2 6) (3 5 4 6) (3 7 6 4) (1 7 2 8)))
(map (lambda (x) (smatch x (dot (dot (dot (atom 1) (atom 2)) (dot (atom 1) (atom 2))) (dot (dot (atom 1) (atom 2)) (dot (atom 1) (atom 2)))))) '((1 2) (1 2 1 2) (1 2 1 2 1 2) (1 2 1 2 1 2 1 2) (1 2 1 2 1 2 1 2 1 2) (1 1 1 1 2 2 2 2)))
(smatch '(1 4) (dot (if (smatch '(1 9) (dot (atom 1) (atom 9))) (atom 1) (atom 2)) (if (smatch '(1) (dot (optional (atom 1)) (atom 3))) (atom 7) (bar (star (atom 4)) (dot (atom 4) (atom 1))))))
(smatch '(1 1 1 1 1 4 4) (dot (dot (star (de-optional (optional (de-dot-0 (dot (atom 1) (atom 2)))))) (optional (dot (atom 4) (optional (de-bar-1 (bar (atom 9) (atom 3))))))) (de-dot-0 (dot (bar (atom 1) (star (atom 4))) (dot (atom 7) (de-star (star (atom 2))))))))
(map (lambda (x) (smatch x (dot (star (atom (+ (de-atom (list-ref (list (atom 0) (atom 5) (atom 8)) 1)) (de-atom (de-dot-0 (de-bar-1 (bar (dot (atom 2) (atom 3)) (dot (atom 1) (atom 4))))))))) (atom (* (de-atom (cadr (list (atom 1) (atom 2) (atom 3)))) (de-atom (de-bar-0 (de-dot-1 (de-dot-1 (dot (de-star (star (dot (atom 2) (atom 3)))) (de-optional (optional (dot (atom 1) (bar (atom 4) (atom 3))))))))))))))) '((1 3 3) (8 8 6) (5) (2 9) (3 9) (6 6 8) (1 7) (3 6) (8)))
(map (lambda (x) (smatch x (dot (dot (dot (dot (atom 1) (optional (atom 2))) (dot (optional (atom 3)) (optional (atom 4)))) (dot (dot (optional (atom 5)) (optional (atom 6))) (dot (optional (atom 7)) (optional (atom 8))))) (dot (star (atom 9)) (atom 0))))) '((1 9) (1) (0) (1 0) (1 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0) (1 2 9 0 1 3 4 9 9 0 1 5 6 7 9 9 9 0 1 8 9 2 3 9 9 9 9 0 1 4 5 6 7 8 9 9 9 9 9 0 1 0) (1 4 9 4 0) (1 5 0 1 9 9 0) (1 2 2 0) (1 4 1 4 0 0)))
#f
#t
#t
#t
#f
#t
#t
#t
#f
#f
#t
#t
#t
#t
#t
#f
#t
#t
#t
#t
#t
#t
#t
#t
#t
(#f #t #t #f)
(#t #f #f #f #f #f #f #t #t #f)
(#t #t #f #t #t #t #f #t)
(#t #f #f #f #f #t #f #t)
(#f #f #t #t #f #t)
(#f #f #f #t #f #f)
#t
#t
(#f #f #f #f #f #t #f #f #t)
(#f #f #f #t #t #f #f #f #f #f)
|
|
|
| 위로 |
|
|
김태훈
가입: 2010년 9월 6일
올린 글: 91
|
| 올려짐: 2010년10월19일 11:47 주제: |
|
|
| 감사합니다 ^^ |
|
| 위로 |
|
|
김진영_
가입: 2009년 12월 9일
올린 글: 337
|
| 올려짐: 2010년10월19일 12:47 주제: |
|
|
| 멋집니다. |
|
| 위로 |
|
|
김진영_
가입: 2009년 12월 9일
올린 글: 337
|
| 올려짐: 2010년10월19일 20:07 주제: |
|
|
학생들의 요청이 있어 몇 가지 extreme한 테스트 케이스를 추가로 제공해 드립니다. 이 중 일부는 2008학년도에 수강생 이충민씨(07)가 게시판에 올리셨던 테스트 케이스 중 어려워 보이는 것을 몇 가지 고른 것입니다.
채점 데이터의 거의 대부분은 처음에 올려 드렸던 것이나 심규민 학생이 올려 주신 정도의 크기로 구성됩니다. extreme한 테스트 케이스에서의 속도보다는, 숙제의 목표인 "항상 올바른 답을 내는 프로그램"을 작성하는 데 집중하시길
| 코드: | (define lst1 (list 1 2 2 2 9 9 9 9 9 9 9 0 2 2 2 2 2 9 9 0 3 8 9 0 0 2 3 9 0 0 2 2 2 2 2 2 3 7 0 3 6 3 0 3 2 3 0 2 3 9 0 6 5 4 2 0 2 2 2 2 2 3 9 9 9 0 3 8 7 5 2 0 3 2 2 2 2 2))
(define code1 (star (bar (bar (star (atom 1))
(bar (star (atom 2))
(bar (optional (atom 3))
(bar (star (atom 4))
(bar (star (atom 5))
(bar (star (atom 6))
(bar (star (atom 7))
(bar (star (atom 8))
(dot (atom 9)
(dot (star (atom 9))
(atom 0)))))))))))
(dot (atom 0)
(dot (star (atom 2)) (atom 3))))))
(smatch (append (append lst1 lst1) (append lst1 lst1)) code1)
;#t
(smatch (list 1 2 1 1 2 2 2 9 9 9 9 9 9 9 9 9 9 0 2 2 2 2 2 9 9 0 3 8 7 6 3 2 3 0 2 3 9 0 6 5 4 2 0 2 2 2 2 2 2 2 9 9 9 0 3 8 7 4 2 7 5 2 0 3 2 2 2 2 2) code1)
;#f |
| 코드: | (define (plus c)
(dot c (star c)))
(define code2 (star (bar (dot (star (bar (atom 5)
(atom 6)))
(dot (optional (atom 8))
(optional (atom 9))))
(dot (dot (star (atom 2))
(optional (atom 3)))
(dot (dot (plus (atom 4))
(optional (atom 5)))
(star (atom 6)))))))
(smatch '(5 6 8 9 2 3 5 6) code2)
(smatch '(5 6 8 9 2 3 4 5 6 2 3 2 4 6 6 6 6) code2)
(smatch '(3 4 5 4 5 6 6 4 5 6 6 4 5 4 2 3 2 2 4) code2)
;#f
;#f
;#f |
김진영_ 가 2010년10월19일 20:24에 수정함, 총 2 번 수정됨 |
|
| 위로 |
|
|
김태훈
가입: 2010년 9월 6일
올린 글: 91
|
| 올려짐: 2010년10월19일 20:16 주제: |
|
|
아래쪽 코드는 전부 #f 맞나요? ㅎㅎ 답을 안 올려 주셨네요 ㅎㅎ
위쪽 코드는.....스트링이 너무 길어요 ㅜㅜ 위쪽코드에 첫번째문제는 푸는데 두번째에서는 프로그램이 버티질 못하네요 ㅜㅜ 스트링을 좀 줄이고 하면 되는 걸로 봐선 무한루프는 아닌 것 같은데..ㅜㅜ
----------------------
위쪽 코드에서 첫번째 문제 빼고 두번째 문제만 넣었더니 프로그램이 버티긴 하는데 시간이 cpu time: 116689 real time: 125798 gc time: 13366 이렇게 나오네요.. 아마 2분 약간 넘게 걸린 것 같네요 ㅋㅋ 이 정도는 괜찮나요? ㅋ |
|
| 위로 |
|
|
김진영_
가입: 2009년 12월 9일
올린 글: 337
|
| 올려짐: 2010년10월19일 20:22 주제: |
|
|
답이 빠졌네요. 아래쪽 예제는 모두 #f가 맞습니다.
위쪽 예제의 두 번째 경우는 조교의 솔루션으로는 40초 정도 걸립니다. 다른 분들은 어느 정도 걸리시나요? |
|
| 위로 |
|
|
김태훈
가입: 2010년 9월 6일
올린 글: 91
|
| 올려짐: 2010년10월19일 22:19 주제: |
|
|
저의 경우 위에서 말씀드렸다시피 그건 2분 정도 걸립니다.
아까 추가예제 중 위에것을 한꺼번에 넣어놓고 딴짓할 때는 프로그램이 튕겼는데 넣어놓고 컴퓨터를 만지지 않고 있으면 두개 합쳐서 3분 정도에 답을 내는 것 같습니다.
내일이 되기 전에 더 좋은 알고리즘이 떠오른다면 수정해 보겠지마는, 아마 시험의 압박이 있어서 이대로 내지 않을까 싶네요...OTL
그래도 기존 예제들은 거의 순식간에 나오기 때문에 채점이 불가능하지는 않을것으로 보고 일단 내겠습니다.. |
|
| 위로 |
|
|
|
FAQ
검색
멤버리스트
사용자 그룹
사용자 등록하기
개인 정보
비공개 메시지를 확인하려면 로그인하십시오
로그인
