Data structures 02.3:programming recursive functions

Slides:



Advertisements
Similar presentations
12 장 템플릿 (template) Sung-Min Jung Internet Management Technology Lab. School of Information & Communication Engineering, Sungkyunkwan Univ. 300 Cheoncheon-dong,
Advertisements

YES C 제 1 장 C 언어의 개요 1/34 제 1 장 C 언어의 개요 문봉근. YES C 제 1 장 C 언어의 개요 2/34 제 1 장 C 언어의 개요 1.1 프로그램과 C 언어의 특징 1.2 C 언어의 프로그램 구성 1.3 비주얼 C++ 통합 환경 들어가기.
슬라이드 1~21까지는 각자 복습! 슬라이드 22부터는 수업시간에 복습
Power C++ 제6장 포인터와 문자열.
C++ Espresso 제3장 배열과 포인터.
C++ Espresso 제3장 배열과 포인터.
쉽게 풀어쓴 C언어 Express 제5장 수식과 연산자 C Express Slide 1 (of 34)
2016 ITA 1월 강의 C Programming -4일차- 포인터배열 및 이중포인터 정대진 ( )
C++ Espresso 제1장 기초 사항.
쉽게 풀어쓴 C언어 Express 제11장 포인터 C Express.
C++ Espresso 제2장 제어문과 함수.
Part 10 포인터 ©우균, 창병모 이 슬라이드는 부산대학교 우균이 작성하였습니다. 오류나 수정할 사항 있으면 연락 주세요.
쌍둥이의 탄생 제주 아라중 영재학급 1학년 강나연.
C 프로그래밍.
실전 프로젝트 2 : 숫자야구 숫자 야구를 구현해보자.
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 1 강원대학교 컴퓨터과학전공 문양세.
명품 C++ 13장 예외 처리와 C 언어와의 링크 지정.
2007 1학기 10 함수 활용.
8. 객체와 클래스 (기본).
C++ 프로그래밍 년 2학기 전자정보공학대학 컴퓨터공학부.
C++ Espresso 제9장 다형성.
컴퓨터의 기초 제 4강 - 표준 입출력, 함수의 기초 2006년 4월 10일.
Part 08 함수 ©우균, 창병모 이 슬라이드는 부산대학교 우균이 작성하였습니다. 오류나 수정할 사항 있으면 연락 주세요.
연산자 대입 연산자 산술 연산자 관계 연산자 논리 연산자 비트 연산자 콤마 연산자 축약 연산자 sizeof 연산자
쉽게 풀어쓴 C언어 Express 제17장 동적 메모리와 연결 리스트 C Express.
동적메모리와 연결리스트 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
진로 목표 설정 이 대 성.
C 7장. 배열과 문자열 #include <stdio.h> int main(void) { int num;
Internet Computing KUT Youn-Hee Han
Data structures 01.2: C++ classes 동의대학교 멀티미디어공학과 이광의교수.
Data structures 02.2:mathematical induction 동의대학교 멀티미디어공학과 이광의 교수.
재귀 혹은 귀납 Recursive or Inductive Definition 집합을 정의하는 방법
10장 포인터와 문자열 포인터 기본 배열과 포인터 매개변수 전달방법 포인터와 문자열.
김 정 석 Web Programming 김 정 석
C++ 개요 객체지향 윈도우즈 프로그래밍 한국성서대학교 유일선
제 4주 2014년 1학기 강원대학교 컴퓨터학부 담당교수: 정충교
9장. 동적 프로그래밍Dynamic Programming (DP)
이산수학(Discrete Mathematics)
5장. 상수와 기본 자료형. 5장. 상수와 기본 자료형 5-1 C 언어가 제공하는 기본 자료형 자료형(data type) 기본 자료형 사용자 정의 자료형 int val; "선언할 변수의 특징을 나타내기 위한 키워드" 기본 자료형 기본적으로 제공이 되는 자료형 사용자.
Chapter 3 클래스. 최호성.
컴퓨터 개론 및 실습 Dept. Computer Eng. Hankuk University of Foreign Studies
제5장 생성자와 접근제어 객체 지향 기법을 이해한다. 클래스를 작성할 수 있다. 클래스에서 객체를 생성할 수 있다.
Ⅰ운동과 건강 관리 01 건강 관리와 삶의 질 향상 02 건강과 운동의 관계 이해 03 건강 생활과 운동 환경의 책임 의식.
Ch.03 Dynamic Programming (동적 프로그래밍 or 동적 계획법)
다음 주 과제 3장 읽어오기 숙제 해서 제출하기. 자료구조와 알고리즘, 순환 E304호,
제2장 제어구조와 배열 if-else 문에 대하여 학습한다. 중첩 if-else 문에 대하여 학습한다.
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 년 봄학기
이산수학(Discrete Mathematics)
OpenGL Project Dong-seo Univ Multimedia Engineering.
4. 고급변수 사용 : 포인터와 관련하여 메모리 바라보기
윤성우의 열혈 C 프로그래밍 윤성우 저 열혈강의 C 프로그래밍 개정판 Chapter 09. C언어의 핵심! 함수!
CHAP 2:순환.
2d game pRogramming 1차 발표 이재남.
CHAP 2:순환 순천향대학교 컴퓨터공학과.
Jong Hyun Baek, Dongseo Univ.,
5. 논리적 자료표현 : 구조체.
Android -Data Base : 김성록 GyeongSang Univ. IT.
CHAP 1:자료구조와 알고리즘.
3장,4장 발표 서정우.
4. 시간의 표현 (6장. 시간의 표현).
곡선 처리.
보건소 사업의 문제점 및 발전방향 예방의학 PK A-라 조.
알기쉽게 해설한 데이터구조 고 갑 승 한남대학교
▶서류관리 프로그램 1. 로그인….2 2. 서류등록 … 서류도착 서류스티커발행
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
argc, argv 의 사용방법 #include <stdio.h>
토론의 기술 3 쟁점분석과 입론.
C.
어서와 C언어는 처음이지 제22장.
Presentation transcript:

Data structures 02.3:programming recursive functions 동의대학교 멀티미디어공학과 이광의 교수

Today’s topic 재귀함수의 예와 동작방법 mathematical induction수학적 귀납법 재귀함수의 활용 계승 함수와 그 동작방법 피보나치 함수와 그 동작방법 최소공배수 함수 mathematical induction수학적 귀납법 계승 함수의 증명 피보나치 함수의 증명 최소공배수 함수의 증명 재귀함수의 활용 징검다리 건너기 당근 캐기 거북이 옮기기 Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 1 3 2 Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 방법 1: 1, 2, 3 방법 2: 1, 2 방법 3: 1, 3 방법 4: 2, 3 방법 5: 2 1 3 2 Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 1 3 2 Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 2 6 3 1 7 5 4 Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 건너는 방법은 두 가지로 나눌 수 있다. 마지막으로 7번 거북이를 밟고 지나가는 방법 마지막으로 6번 거북이를 밟고 지나가는 방법 2 6 3 1 7 5 4 Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 건너는 방법은 두 가지로 나눌 수 있다. F(7): 거북이가 7마리 있을 때 방법의 수 마지막으로 7번 거북이를 밟고 지나가는 방법 F(6) 마지막으로 6번 거북이를 밟고 지나가는 방법 F(5) 2 6 3 1 7 5 4 Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 건너는 방법은 두 가지로 나눌 수 있다. F(7): 거북이가 7마리 있을 때 방법의 수 마지막으로 7번 거북이를 밟고 지나가는 방법 F(6) 마지막으로 6번 거북이를 밟고 지나가는 방법 F(5) F(7) = F(6) + F(5) 2 6 3 1 7 5 4 Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 건너는 방법은 두 가지로 나눌 수 있다. F(7): 거북이가 7마리 있을 때 방법의 수 마지막으로 7번 거북이를 밟고 지나가는 방법 F(6) 마지막으로 6번 거북이를 밟고 지나가는 방법 F(5) F(7) = F(6) + F(5) >> F(n) = F(n-1) + F(n-2) 2 6 3 1 7 5 4 Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 건너는 방법은 두 가지로 나눌 수 있다. F(7): 거북이가 7마리 있을 때 방법의 수 마지막으로 7번 거북이를 밟고 지나가는 방법 F(6) 마지막으로 6번 거북이를 밟고 지나가는 방법 F(5) F(7) = F(6) + F(5) >> F(n) = F(n-1) + F(n-2); F(0)= 1; F(1) = 2; 2 6 3 1 7 5 4 Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 건너는 방법은 두 가지로 나눌 수 있다. F(7): 거북이가 7마리 있을 때 방법의 수 마지막으로 7번 거북이를 밟고 지나가는 방법 F(6) 마지막으로 6번 거북이를 밟고 지나가는 방법 F(5) F(7) = F(6) + F(5) >> F(n) = F(n-1) + F(n-2); F(0)= 1; F(1) = 2; 2 6 3 1 7 5 4 int F (int n) { if (n==0) return 1; // return 0 if (n==1) return 2; // return 1 return F (n-1) + F (n-2); } Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 징검다리 건너기: int F(int n) { if (n==0) return 1; if (n==2) return 2; return F(n-1) + F(n-2); } 증명 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 귀납법 기초가 모든 경우에 종료될 수 있도록 충분하다. Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 3 1 1 2 1 1 Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 3 1 1 2 1 1 Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 3 1 1 2 1 1 Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 3 1 1 2 1 1 Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 3 1 1 2 F (n-1,m) 1 1 F (n,m-1) F(n,m) Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 이 수를 C(i,j)라 하자 3 1 1 2 F (n-1,m) 1 1 F (n,m-1) F(n,m) Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 이 수를 C(i,j)라 하자 3 1 1 2 F (n-1,m) 1 1 F (n,m-1) F(n,m) Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 이 수를 C(i,j)라 하자 3 1 int max (int x, int y) { if (x>y) return x; else return y; } int F (int n, int m) { // F(int i, int j) if (n==0||m==0) return 0; return C (n, m) + max (F(n-1,m), F(n,m-1)); 1 2 F (n-1,m) 1 1 F (n,m-1) F(n,m) Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 당근 캐기: int max(int x, int y) { if (x>y) return x; else return y; } Int F(int n, int m) { if (n==0||m==0) return 0; return C(n,m) + max(F(n-1,m), F(n,m-1)); 증명 귀납법 기초: P(0, 0..m), P(0..n, 0) 귀납법 단계: 임의의 자연수 n과 m에 대하여 {P(n-1,m) AND P(n,m-1)} -> P(n, m) 귀납법 기초가 모든 경우에 종료될 수 있도록 충분하다. Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 한 마리인 경우 A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 한 마리인 경우 (수조) A의 (가장 위에 있는) 거북이를 (수조) C로 이동한다. (A->C) A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 한 마리인 경우 (수조) A의 (가장 위에 있는) 거북이를 (수조) C로 이동한다. (A->C) A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 두 마리인 경우 A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 두 마리인 경우 A->B; A->C; B->C; A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 두 마리인 경우 A->B; A->C; B->C; A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 두 마리인 경우 A->B; A->C; B->C; A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 두 마리인 경우 A->B; A->C; B->C; A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 세 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (3, A, B, C); 네 번째 거북이를 이동한다. A->C Move (4, A, C); 세 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (3, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 세 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (3, A, B, C); 네 번째 거북이를 이동한다. A->C Move (4, A, C); 세 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (3, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 세 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (3, A, B, C); 네 번째 거북이를 이동한다. A->C Move (4, A, C); 세 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (3, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 세 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (3, A, B, C); 네 번째 거북이를 이동한다. A->C Move (4, A, C); 세 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (3, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 n-1 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (n-1, A, B, C); n 번째 거북이를 이동한다. A->C Move (n, A, C); n-1 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (n-1, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 n-1 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (n-1, A, B, C); n 번째 거북이를 이동한다. A->C Move (n, A, C); n-1 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (n-1, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 n-1 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (n-1, A, B, C); n 번째 거북이를 이동한다. A->C Move (n, A, C); n-1 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (n-1, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 n-1 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (n-1, A, B, C); n 번째 거북이를 이동한다. A->C Move (n, A, C); n-1 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (n-1, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 n-1 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (n-1, A, B, C); n 번째 거북이를 이동한다. A->C Move (n, A, C); n-1 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (n-1, B, C, A); void Move(int n, char S, char D) { cout << “move turtle” << n << “ from ” << S << “ to ” << D << endl; } int MTs (int n, char S, char D, char M) { if (n>1) MTs (n-1, S, M, D); Move (n, S, D); if (n>1) MTs (n-1, M, D, S); A B C Dept. of Multimedia Engineering, DongEui Univ.

Programming Recursive Functions 거북이 옮기기: void Move(int n, char S, char D) { cout << “move turtle” << n << “ from ” << S << “ to ” << D << endl; } int MTs (int n, char S, char D, char M) { if (n>1) MTs (n-1, S, M, D); Move (n, S, D); if (n>1) MTs (n-1, M, D, S); 증명 귀납법 기초: P(1) <- S, D, M은 중요 변수가 아니다. 실제로는 P(1, A, B, C), P(1, B, A, C), P(1, C, A, B) P(1, A, C, B), P(1, B, C, A), P(1, C, B, A) 모든 경우에 잘 동작한다. 귀납법 단계: n에 대하여 P(n-1) -> P(n) 귀납법 기초가 모든 경우에 종료될 수 있도록 충분하다. Dept. of Multimedia Engineering, DongEui Univ.

You are the one Who makes that happen!!! summaries 재귀함수의 활용 징검다리 건너기 당근 캐기 거북이 옮기기 You are the one Who makes that happen!!! Dept. of Multimedia Engineering, DongEui Univ.