Java 재귀 알고리즘 활용 분석

저자：Eve Cole 업데이트 시간：2024-11-18 19:24:01

재귀 알고리즘은 자신을 직접 또는 간접적으로 호출하는 알고리즘입니다. 컴퓨터 프로그래밍에서 재귀 알고리즘은 대규모 문제를 해결하는 데 매우 효과적이며 종종 알고리즘 설명을 간결하고 이해하기 쉽게 만듭니다.

질문 1: 숫자 열의 규칙은 다음과 같습니다: 1, 1, 2, 3, 5, 8, 13, 21, 34. 30번째 숫자는 무엇입니까? 재귀를 사용하여 구현

다음과 같이 코드 코드를 복사합니다 .

공개 클래스 피보나치 시퀀스 {
공개 정적 무효 메인(문자열[] 인수){
System.out.println(Fribonacci(9));

}
공개 정적 int Fribonacci(int n){
만약(n<=2)
1을 반환합니다.
또 다른
프리보나치(n-1)+프리보나치(n-2)를 반환합니다.

}
}

질문 2: 하노이 타워 문제

하노이 타워(하노이 타워라고도 함)는 실제로 인도의 고대 전설입니다.

세상을 창조한 신(중국의 판구와 비슷한 신)인 범천이 절에 세 개의 다이아몬드 막대를 남겼는데, 첫 번째 것은 64개의 둥근 금 조각으로 덮여 있었고, 가장 큰 것은 바닥에 있었고 나머지는 A보다 작은 막대기를 차곡차곡 쌓아서 절에 있는 스님이 막대기 하나하나를 하나씩 옮겨가며 보조용으로 쓸 수 있다고 규정되어 있는데, 움직일 수 있는 막대기는 하나만 가능하다. , 큰 것은 작은 것 위에 놓일 수 없습니다. 계산 결과는 매우 무섭습니다(원반이 이동한 횟수): 18446744073709551615. 스님들이 평생을 바쳐도 금원반의 이동을 완료하는 것은 불가능합니다.

요구 사항: 첫 번째 기둥에 n개의 디스크가 있음을 나타내는 양의 정수 n을 입력합니다. "t를 x에서 y로 이동" 형식으로 일련의 작업을 출력합니다. 각 작업에는 한 줄이 있습니다. 이는 x열의 t 번호가 붙은 디스크를 y열로 이동하는 것을 의미합니다. 열에는 A, B, C 번호가 매겨져 있습니다. 최소한의 작업으로 모든 플레이트를 A열에서 C열로 옮겨야 합니다.

다음과 같이 코드 코드를 복사합니다 .

공개 클래스 하니오 {
공개 정적 무효 메인(문자열[] 인수){
정수 i=3;
char a ='A',b='B',c='C';
하니오(i,a,b,c);
}
공개 정적 무효 hanio(int n,char a,char b,char c){
만약(n==1)
System.out.println("플레이트 "+n+"를 "+a+"에서 "+c"로 이동);
또 다른{
hanio(n-1,a,c,b);//b를 사용하여 위의 n-1개 플레이트를 a에서 c로 이동합니다.
System.out.println("플레이트 "+n+"를 "+a+"에서 "+c"로 이동);//그런 다음 n을 직접 c로 이동합니다.
hanio(n-1,b,a,c);//a를 사용하여 b의 n-1개 플레이트를 c로 이동합니다.
}
}
}