Algorithm - Recursion - 2


 

Algorithm - Recursion - 2

Recursion EX.

Greatest Common Divisor 최대공약수

유클리드 호제법

두 정수 a,b 의 최대공약수 gcd(a,b)

a를 b로 나눈 나머지 r

a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

반복적으로 적용한다.

r이 0이 되었을 때, 나누는 수가 a와 b의 최대공약수이다.

iterator pattern

int gcd_iterator(int a, int b) { int r; do{ r = a % b; a = b; b = r; while( r != 0 ) return a; }

recursive pattern

int gcd_recursive(int a, int b) { if(b == 0)// base case return a; else// recursive step return gcd_recursive(b, a%b); }

Sequential Search

1차원 배열에 n 개의 정수가 주어졌을 때 , 정수 x가 배열에 있는지 검사하라(순차 검색)

iterator pattern

int LinearSearch_iterator(int a[], int n, int value) { int i; for(i=0;i<n;i++) if(a[i] == value) return i; return -1; }

recursive pattern

int LinearSearch_recursive(int a[], int n, int value) { if(n <= 0) // base case return -1; if(a[n-1] == value) // base case return n-1; else return LinearSearch_recursive(a,n-1,value); }

count up/down

n개의 수로부터 카운팅을 하대 출력되는 수가 0으로부터(up) 또는 n으로부터(down) 출력된다. 

count up : 0 1 2 … n-2 n-1 n

count down : n n-1 n-2 … 2 1 0

iterator pattern

int countUp_iterator(int n) { int i; for(i=0;i<=n;i++) cout<<i<<endl; } int countDown_iterator(int n) { int i; for(i=n;i>=0;i--) cout<<i<<endl; }

recursive pattern

int countUp_recursive(int n) { if(n > 0) // base case countUp_recursive(n-1); cout<<n<<endl; } int countDown_recursive(int n) { cout<<n<<endl; if(n > 0) // base case countDown_recursive(n-1); }

String reversal

문자열을 뒤집어 출력한다.

“hello” -> “olleh”

iterator pattern

void printStrReversal_iterator(char str[], int index) { int i; for(i=index-1; i>=0;i--) cout<<str[i]; cout<<endl; }

recursive pattern

void printStrReversal(char str[], int index) { if(str[index] != NULL) { // base case printStrReversal(str,index-1)// recursive step cout<<str[index]; } cout<<endl; }

Palindrome 팰린드롬, 회문

팰린드롬(회문)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말이다.

“기러기", “asdsa” “kkkk”

iterator pattern

int checkPalindrome_iterator(char str[]) { int first = 0; int last = strlen(str); do{ if(str[first] != str[last]) return 0; // not palindrome }while(first <= last) return 1; // palindrome }

recursive pattern

int checkPalindrome_recursive(char str[], int first, int last) { if(last <= first) // base case return 1; // palindrome else if(str[first] != str[last]) return 0; // not palindrome else return checkPalindrome_recursive(str,first+1,last-1); }

십진수 진수 변환 출력하기

주어진 십진수 정수를 다른 진수의 숫자로 변환하여 출력한다.

변환되는 진수의 기수(base)는 2~16의 범위를 가진다.

recursive pattern

void baseConversion(int n, int base) { static baseTable[] = "0123456789abcdedf"; if(n >= base) // base case baseConversion(n/base, base); cout<<baseTable[n%base]); }

Insertion Sorting 삽입 정렬

삽입 정렬은 자료 배열의 모든 요소를 앞에서 부터 차례대로 이미 정렬된 배열 부분과 비교하여,

자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

void insert(int data[], int size, int value) { if(size == 0) data[size] = value; else { if(data[size-1] < value) data[size] = value; else { data[size] = data[size - 1]; insert(data, size-1, value); } } } void insertionSort(int data[], int size) { if(size == 0) // base case return 0; else { insertionSort(data,size-1); insert(data,size-1,data[size-1]); } }

Permutation 순열

순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 조합론에서는 용어 "순열"을 많이 사용하며, 주어진 집합의 원소 또는 그 일부에 대한 배열을 뜻한다.

n개의 서로 다른 문자로 만들어진 스트링이 주어졌을 때, 이 문자열에 속하는 모든 순열(n! 개)을 출력한다.

kjc - kjc kcj jkc jck ckj cjk ( 6가지 )

#include <string> void permuteString(char *str, int begin, int end) { int i; int range = begin - end; if(range == 1) cout<<str<<endl; else { for(i=0;i<range;i++) { swap(&str[begin], &str[begin+i]); // change permutString(str, begin+1, end); swap(&str[begin], &str[begin+i]); // recover } } } void permute(char *str) { permuteString(str, 0, strlen(str)); } void main() { char str[] = "abcd"; permute(str); }