재 귀적 응용

1, 하노이 타 워 문제
하노이 타 워 문 제 는 A, B, C 세 개의 기둥 이 있 고 기둥 마다 약간의 접 시 를 입 을 수 있다 는 것 이다.현재 A 기둥 위 에는 4 개의 접시 가 있 는데 위 에서 아래로 갈수 록 커진다.모든 접 시 를 B 를 중간 으로 C 기둥 으로 옮 겨 야 한다.규칙 은 매번 한 접시 만 움 직 일 수 있 고 접 시 는 자신 보다 큰 접시 에 만 놓 을 수 있다 는 것 이다.이 제 는 이동 하 는 모든 과정 을 인쇄 하 기 를 바 랍 니 다.먼저 이 문 제 를 자세히 고려 한 후에 알 수 있 듯 이 모든 단계 의 이동 은 고정 적 이 고 분기 문제 가 존재 하지 않 는 다.이 문 제 를 해결 하려 면 반드시 아래 의 절 차 를 거 쳐 야 한다. 그렇지 않 으 면 A 위의 맨 아래 에 있 는 접 시 는 이동 할 수 없다. 1. n - 1 접 시 를 A 에서 B 로 이동 하고 C 를 중간 기둥 으로 사용한다.2. 가장 큰 접 시 를 A 에서 C 로 옮 깁 니 다.3. n - 1 접 시 를 B 에서 C 로 옮 기 고 A 를 중간 기둥 으로 사용한다.다음은 코드.관찰 을 통 해 코드 가 위의 분석 결 과 를 완전히 반영 한 것 을 알 수 있다.

public class Testing {

	static int dick = 3;

	public static void main(String[] args) {
		Testing.doTower(dick, 'A', 'B', 'C');
	}

	private static void doTower(int topN, char from, char inter, char to) {

		if (topN == 1) {
			System.out.println("Move disk " + topN + " from tower " + from + " to tower " + to);
		} else {

			doTower(topN - 1, from, to, inter);
			System.out.println("Move disk " + topN + " from tower " + from + " to tower " + to);
			doTower(topN - 1, inter, from, to);
		}
	}
}

여기 서 우 리 는 알고리즘 을 써 서 A 의 모든 접 시 를 B 를 통 해 C 위 에 올 려 놓 았 다 고 말 할 수 없다.이렇게 재 귀 하면 끝 날 조건 이 없 기 때문이다.그래서 매번 돌아 올 때마다 꼭
topN-1。
다시 한 번 문 제 를 푸 는 과정 을 돌 이 켜 보면 n 층 hanio 를 완성 하 는 횟수 를 H (n) 로 설정 합 니 다.재 귀 를 이용 하여 문 제 를 해결 할 때 는 반드시 다음 절 차 를 완성 해 야 한다.
1. H (n) 와 H (n - 1) 의 관 계 를 찾 아야 한다. 즉, 이른바 전달 공식 이다.예 를 들 어 hanio 탑 문제 의 전달 공식 은 다음 과 같다.
H(n) = H(n-1) + 1 + H(n-1)
한 문제 가 전달 공식 을 찾 지 못 하면 전달 을 이용 해 해결 할 수 없다.
2. 종료 조건 이 있어 야 합 니 다.예 를 들 어 hanio 문제 의 끝 조건 은 접시 가 1 개 일 때 A 에서 C 로 간단하게 이동 하면 된다 는 것 이다.
2, 제곱
x 의 y 자 를 계산 하 다.예 를 들 어 2 의 8 제곱 을 계산한다.통상 적 인 방법 은 8 개 2 를 곱 하 는 것 이다.
private static int power(int x, int y){         if (y == 1){             return x;         }         else{             x = x * power(x,y-1);
            System.out.println("1");  //이러한 재 귀 는 아무런 장점 이 없다 는 말 을 통 해 알 수 있 듯 이 재 귀 는 Y - 1 회 운행 되 었 다. 직접 순환 과 곱 하 는 것 과 다 르 지 않다.            return x;         }     }
사실 우 리 는 연산 예 를 들 어 2 의 8 제곱 을 연산 할 때 먼저 2 * 2 를 계산 한 다음 에 재 귀 를 이용 하여 이 과정 을 가속 화 할 수 있다.
일반 알고리즘: 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 는 8 회 곱 해 야 합 니 다.
개선 알고리즘: (2 * 2) ^ 2) ^ 2 는 3 번 만 곱 하면 됩 니 다. 즉, 2 를 밑 으로 8 의 대수 입 니 다.
private static int power(int x, int y){         if (y == 1){             return x;         }         else{             if (y%2 == 0){                 x = power (x * x, y / 2); / / 사실 여 기 는 2 의 8 제곱 은 4 의 4 제곱 과 같다 고 이해 할 수 있다.                System.out.println("1");                 return x;             }             else{                 x = x * power (x, y - 1); / y 가 홀수 일 때 일반 알고리즘 으로 한 번 계산 해 야 합 니 다. 그 다음 y - 1 은 짝수 입 니 다.                System.out.println("1");  //결국 우 리 는 이 알고리즘 이 logY 회 만 실행 해 야 한 다 는 것 을 알 수 있 기 때문에 효율 이 훨씬 높다.                return x;             }         }     }
우 리 는 심지어 사용 할 수 있다.
if(y%3 == 0){             System.out.println("b");             return power(x*x*x,y/3);         }
진행 을 더욱 가속 화하 다.
3，merge sort
merge 정렬 의 사상 은 배열 을 두 개의 작은 질서 있 는 배열 로 나 눈 다음 에 이 두 개의 질서 있 는 배열 을 합 쳐 정렬 된 전체 배열 을 얻 는 것 이다.
그러면 어떻게 두 개의 작은 질서 있 는 배열 을 얻 을 수 있 습 니까? 바로 각 그룹 을 두 개의 더 작은 질서 있 는 배열 로 나 누고 merge 를 하 는 것 입 니 다. 이렇게 순환 적 으로 나 누 면 배열 에 하나의 요소 만 남 을 때 까지 그룹 을 나 눌 필요 가 없고 질서 있 는 배열 이 되 었 습 니 다.
여기 서 재 귀 를 써 야 한 다 는 것 은 분명 하 다.
우선, 재 귀적 이지 않 을 때 두 개의 질서 있 는 배열 을 어떻게 함께 합 니까?
public class mergeSort {     public static void main(String[] args) {         int[] a = {2,5,8,35,78,99,102,103,201};         int[] b = {5,7,17,32};         System.out.println(mergeSort(a,b) );     }          private static ArrayList mergeSort(int[] a, int[] b){         ArrayList c = new ArrayList();         int aInd=0;         int bInd=0;         int cInd=0;                   while(aInd < a.length && bInd < b.length){              if (a[aInd] > b[bInd]){                  c.add(cInd++, b[bInd++]);              }              else{                  c.add(cInd++,a[aInd++]);              }          }                   while(aInd == a.length && bInd < b.length){              c.add(cInd++,b[bInd++]);          }                   while(bInd == b.length && aInd < a.length){              c.add(cInd++,a[aInd++]);          }                  return c;     } }
다음은 merge sort 의 전체 코드 입 니 다.
public class mergeSort {          public static void main(String[] args) {         int[] initial = {5,2,7,8,102,45,36,22,201,43};         recSort(initial);     }    
/ recsort 의 임 무 는 배열 을 두 개의 더 작은 배열 로 나 누 는 것 입 니 다.    private static int[] recSort(int[] initial){                  int[] begin;         int[] end;                  if ( initial.length == 1 ){             return initial; / 배열 이 마지막 으로 하나의 요소 만 있 을 때 더 이상 구분 할 필요 가 없습니다. 이것 이 기본 값 조건 입 니 다.        }         else{             begin = Arrays.copyOfRange(initial, 0, initial.length/2);  //begin 배열 은 배열 의 앞부분 을 대표 합 니 다.            end = Arrays. copyOfRange (initial, initial. length / 2, initial. length); / end 배열 은 배열 의 후반 부 를 대표 합 니 다.                     begin = recsort (begin); / begin 을 재 귀적 으로 recsort 로 구분 합 니 다.            end = recSort(end);                                  return mergeSort(begin, end);
/ / 이 returen 은 매우 중요 합 니 다. recsort 가 맨 안쪽 으로 순환 할 때 mergeSort 는 스 택 에서 begin 과 end 를 꺼 내 합병 하기 시작 합 니 다.
/ / 동시에 합 친 결 과 는 다음 mergeSort 재 귀적 호출 의 입력 매개 변수 입 니 다.
/ / 즉, 예 를 들 어 지난번 합병 결과 [2, 5] [7, 8, 102] 이 두 개의 서 수 는 다음 mergeSort 의 입력 매개 변수 로 구성 된다.
/ / 이 예 가 재 미 있 는 점 은: 우 리 는 recSort 방법 을 사용 하여 배열 을 최 내층 으로 나 누고, mergeSort 방법 을 사용 하여 최 내층 에서 최 외층 으로 재 귀 합 니 다. 이 두 가지 방법 은 공동으로 재 귀 호출 을 완 료 했 습 니 다.        }     }    
/ / mergeSort 방법 은 앞 과 완전히 일치 합 니 다. 어떻게 호출 하 느 냐 가 관건 입 니 다.    private static int[] mergeSort(int[] a, int[] b){         int[] c = new int[a.length + b.length];         int aInd=0;         int bInd=0;         int cInd=0;                   while(aInd < a.length && bInd < b.length){              if (a[aInd] > b[bInd]){                  c[cInd++] = b[bInd++];              }              else{                  c[cInd++] = a[aInd++];              }          }                   while(aInd == a.length && bInd < b.length){              c[cInd++] = b[bInd++];          }                   while(bInd == b.length && aInd < a.length){              c[cInd++] = a[aInd++];          }                   System.out.println(Arrays.toString(c));         return c;     } }
4, 가방 문제
가방 문 제 는 5 가지 무게 의 물체, 1kg, 2kg, 5kg, 10kg, 20kg 등 여러 가지 형태 가 있다. 현재 가방 에 하나 이상 을 넣 어 총 무 게 를 25kg 으로 만든다.
한 물체 가 한 번 만 나타 날 수 있 습 니 다. 가능 한 조합 을 찾 은 후 reture 로 돌아 가 false 로 돌아 가 는 것 을 찾 지 못 했 습 니 다.
가방 문 제 는 트 리 검색 문제 로 모든 가능성 을 한 번 씩 시도 할 수 밖 에 없습니다. 코드 가 복잡 해서 다른 스티커 에 넣 었 습 니 다.
5, 확률 문제
알파벳 5 개 (A, B, C, D, E) 중 3 개 를 선택 하면 몇 가지 조합 이 있 는 지 알 수 있다. 배열 이 아 닌 조합 이 므 로 ABC 와 ACB 는 같은 조합 이다.
재 귀적 인 해결 방법 은 바로 문제 의 중간 상 태 를 찾 는 것 이기 때문에 여기 서 우 리 는 고려 할 수 있다.
5 글자 중 3 자 를 고 르 는 조합 은 = A 로 시작 하 는 모든 조합 + A 로 시작 하 는 모든 조합 이 아니다
이 / 가
(5,3) = (4,2) + (4,3)
즉 f (n, k) = f (n - 1, k - 1) + f (n - 1, k)
기본 값 조건 은:
(i, 1) - k 가 1 일 때 i 가지 가능성 이 있 습 니 다. 예 를 들 어 3 글자 중 1 개 를 고 르 면 3 가지 가능 한 조합 이 있 습 니 다.
(i, j) - i 와 j 가 같 을 때 1 가지 가능성 이 있 습 니 다. 예 를 들 어 3 글자 중에서 3 자 모 를 고 르 면 한 가지 조합 만 있 습 니 다.
코드 가 매우 간단 합 니 다:
public class Testing {     public static void main(String arg[]){         System.out.println(selector1(5,3));     }          public static int selector1(int i, int j){         if(j == 1){             return i;         }         if(i == j){             return 1;         }                 return selector1(i-1,j-1)+selector1(i-1,j);     } }