資料構造02:在貴
再帰アルゴリズム
アルゴリズム自体が定義するアルゴリズム
非再帰アルゴリズムと比較
さぎょうげんり
保存された再帰呼び出しに関連する変数の保存/復元
→コンピュータによる自動実行
メリットとデメリット
回帰要素
Alg Factorial(n)
input integer n
output factorial of integer n
1. if(n==1) {base case}
return 1
2. else {recursion case}
return n*Factorial(n-1)基本ルール
次のルールを守らないと、再帰的に問題を解決できません.
ルールを守らないと、次の問題が発生する可能性があります.
ハノイタワー
原版の移出は杭から杭への出力として表現される.
#include <stdio.h>
void move(int n, char from, char to){
printf("n=%d\tmove from %c to %c\n", n, from, to);
}
void hanoi(int n, char from, char aux, char to){
if(n==1){
move(n, from, to);
} else {
hanoi(n-1, from, to, aux);
move(n, from, to);
hanoi(n-1, aux, from, to);
}
}
int main(){
int n;
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
return 0;
}hanoi関数を再帰的に呼び出す.この関数の再帰的なインスタンスを表示するには、次の手順に従います.
次のセクション1〜3を再帰的に呼び出すことによって、問題全体を解決する.
파트1. from말뚝의 위쪽 n-1개를 aux말뚝으로 옮긴다.
파트2. from말뚝의 가장 아래(가장 큰) 1개를 to말뚝으로 옮긴다.
파트3. aux말뚝에 있는 n-1개 전부를 to 말뚝으로 옮긴다.n=1 move from A to C 파트1
n=2 move from A to B 파트1
n=1 move from C to B 파트1
n=3 move from A to C ---파트2
n=1 move from B to A ------파트3
n=2 move from B to C ------파트3
n=1 move from A to C ------파트3Reference
この問題について(資料構造02:在貴), 我々は、より多くの情報をここで見つけました https://velog.io/@yiwonjin/자료구조-02-재귀テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol