게시판 인덱스

 
 FAQFAQ   검색검색   멤버리스트멤버리스트   사용자 그룹사용자 그룹   사용자 등록하기사용자 등록하기 
 개인 정보개인 정보   비공개 메시지를 확인하려면 로그인하십시오비공개 메시지를 확인하려면 로그인하십시오   로그인로그인 

[HW4] HW4-1에서 트리를 이용한 프로그램이 끝나는지 확인할 때

 
글 쓰기   답변 달기     게시판 인덱스 -> 4190.210 Principles of Programming (Fall 2013)
이전 주제 보기 :: 다음 주제 보기  
글쓴이 메시지
강지훈



가입: 2008년 9월 2일
올린 글: 291
위치: 302동 312-2호

올리기올려짐: 2013년10월11일 14:37    주제: [HW4] HW4-1에서 트리를 이용한 프로그램이 끝나는지 확인할 때 인용과 함께 답변

다음과 같은 함수에 대해서는, 끝나는지 확인하지 않아도 좋습니다.

코드:
(define (tree-size tree)
  (if (isleaf? tree) 1
      (+ 1 (tree-size (leftsub tree)) (tree-size (rightsub tree)))))


즉 위 함수에 한정해서는

코드:
(define (tree-size tree)
  (printf "decreasing: ~s~n" ???)
  (if (isleaf? tree) 1
      (+ 1 (tree-size (leftsub tree)) (tree-size (rightsub tree)))))


??? 부분을 알아낼 필요가 없습니다.

감사합니다.
_________________
강지훈
프로그래밍의 원리 조교

Jeehoon Kang
TA, Principles of Programming


강지훈 가 2013년11월13일 1:09에 수정함, 총 1 번 수정됨
위로
사용자 정보 보기 비밀 메시지 보내기
유재민



가입: 2013년 10월 2일
올린 글: 11

올리기올려짐: 2013년10월13일 4:49    주제: 음 인용과 함께 답변

트리의 사이즈를 구하는 함수 뿐만 아니라, recursion의 다음 단계에서 사용하는 인자가 subtree밖에 없는 재귀함수에서는 끝나는 것을 보일 필요가 없다는 것인가요? 제 함수가 그런 식으로 짜여져서 실제로 구동할 때는 상위 노드에서부터 dfs 방식으로 노드들을 경유하거든요.
위로
사용자 정보 보기 비밀 메시지 보내기
조성근



가입: 2009년 9월 14일
올린 글: 283

올리기올려짐: 2013년10월14일 12:38    주제: 인용과 함께 답변

숙제4-1에서 "재귀함수의 끝남"을 보이는 방법에 대해 추가 공지합니다. 이미 숙제를 제출하신 분들은 제출된 숙제를 그대로 두시고, 앞으로 숙제를 제출하시는 분들은 가급적 아래의 방법을 사용하시길 바랍니다. 이것은 추천사항입니다.

재귀함수가 끝남을 보이기 위해서 다음 세 가지를 보일 필요가 있습니다.
  1. 재귀함수의 인자에 대한 어떤 순서 정의.
  2. 1에서 정의한 순서에 의한 감소하는 체인이 임의의 인자에서 시작했을 때 항상 유한함.
  3. 모든 재귀 호출에 대해 인자가 감소함.


예) 아래와 같은 factorial 함수가 있을 때,
코드:
(define (fac n)
  (if (eq? n 0) 1
      (* n (fac (- n 1)))))


  1. 정수 n에 대한 순서 ">>"의 정의.
    n >> m iff n > m and m >= 0.
  2. 체인의 유한함.
    Forall n >= 0: n >> n' >> ... >> 0 is finite.
  3. 인자의 감소.
    n >> (- n 1)

다음과 같이 답안을 작성하시기 바랍니다.

코드:
(define (fac n)
  (if (eq? n 0) 1
      (* n (fac (- n 1)))))
; 1. n >> m iff n > m and m >= 0.
; 2. Forall n >= 0: n >> n' >> ... >> 0 is finite.
; 3. n >> (- n 1)


(참고1) tree나 list의 size 표현을 위해서 |tree|, |list|를 사용하셔도 좋습니다.
(참고2) 이 숙제는 조교들이 직접 눈으로 채점할 것이니 형식에 크게 구애받지 않으셔도 좋습니다.


유재인 님,
유재인 씀:
트리의 사이즈를 구하는 함수 뿐만 아니라, recursion의 다음 단계에서 사용하는 인자가 subtree밖에 없는 재귀함수에서는 끝나는 것을 보일 필요가 없다는 것인가요?

아닙니다. 트리의 사이즈를 구하는 함수만 끝나는 것을 보일 필요가 없다는 것입니다.
위로
사용자 정보 보기 비밀 메시지 보내기
이전 글 표시:   
글 쓰기   답변 달기     게시판 인덱스 -> 4190.210 Principles of Programming (Fall 2013) 시간대: GMT + 9 시간(한국)
페이지 11

 
건너뛰기:  
새로운 주제를 올릴 수 없습니다
답글을 올릴 수 없습니다
주제를 수정할 수 없습니다
올린 글을 삭제할 수 없습니다
투표를 할 수 없습니다


Powered by phpBB 2.0.21-7 (Debian) © 2001, 2005 phpBB Group
Translated by kss & drssay