intackermann_loop(int m,int n){int mm = m, nn = n;while(mm!=0){if(nn ==0) nn =1;else nn =ackermann_loop(mm,nn-1); mm--;printf("nn : %d \n",nn); }return nn+1;}
2차원 배열로 구현했을 때는 범위를 지정해주지 않으면 계속해서 범위를 초과하는 문제발생했다.
int A[100][100];intackermann_loop(int m,int n){for(int i =0;i<=m;i++){for(int j =0; j<=50; j++){if(i==0)A[i][j]=n+1;elseif(j==0)A[i][j]=A[i-1][j];else{int tmp = A[i][j-1]; A[i][j] = A[i-1][tmp]; } } }return A[m][n];}
또 규칙을 찾아서 구현하는 방법도 있다.
intAcker_nonrecursive3(int m,int n)int i;int val=2;if(m==0) return n+1;if(m==1) return n+2;if(m==2) return2*n+3;if(m==3) { // return pow(2, n+3) -3; 또는 아래 for loop 으로 for(i=1; i<n+3; i++) val *=2;return val -3; }if(m==4){for(i=1; i< n+3; i++) val *=val;return val=val-3; }}
완전 탐색
완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미한다.
재귀 호출은 가능한 방법을 전부 만들어 보는 알고리즘으로 완전 탐색(Exhaustive Search)이라 볼 수 있다.
어떤 문제를 완전 탐색으로 해결하기 위해서 필요한 과정은 대략 다음과 같다.
완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고, 이들을 모두 제한 시간안에 생성할 수 있을지 가늠해보고 적용해야한다.
가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다. 각각의 선택은 답의 후보를 만드는 과정의 한 조각이다.
그중 한 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.
조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로 basecase로 선택해 처리한다.