#include <iostream>
#include <string.h>
#include <unistd.h>
#include <stdio.h>
using namespace std ;
#define min(a,b) ( (a) < (b) ? (a) : (b))
void print_memo(int a[]){
cout << endl ;
cout << "and printing the whole memo table " <<endl ;
for(int i = 0 ; i < 11 ; i++){
cout << " " << a[i] ;
}
cout << endl <<endl ;
}
int memo[10+1] ;
void reset_memo(){
cout <<endl ;
cout << "RESETTING MEMO" <<endl ;
for(int i = 0 ; i < 11 ; i++){
memo[i] = -1 ;
}
}
int getMinSteps ( int n ){
cout << "======current n : "<< n << " ========================"<<endl <<endl ;
cout << "entering the function" <<endl ;
if ( n == 1 ){ cout << "HITTHING THIS CASE n = 1" <<endl ; return 0;
} // base case
if( memo[n] != -1 ){
cout << "critical : found -1" <<endl;
return memo[n];
} // we have solved it already :)
int r = 1 + getMinSteps( n - 1 ); // '-1' step . 'r' will contain the optimal answer finally
cout << "after step 1 r is " << r <<endl <<endl <<endl ;
if( n%2 == 0 ){cout << "this n: " << n<< " is div by 2 and r we checking " << r <<endl ;
cout << " STEP 2: " << "min of " << r << " and 1 + f(" <<(n/2) << ")" <<endl ;
r = min( r , 1 + getMinSteps( n / 2 ) ) ;} // '/2' step
if( n%3 == 0 ){cout << "this n: " << n<< " is div by 3 and r we checking "<< r <<endl ;
cout << " STEP 3: " << "min of " << r << " and 1 + f(" <<(n/3) << ")" <<endl ;
r = min( r , 1 + getMinSteps( n / 3 ) ) ;
} // '/3' step
cout <<endl ;
cout << "R ADDED : " <<r <<endl <<endl ;
memo[n] = r ; // save the result. If you forget this step, then its same as plain recursion.
cout << "memo cell filled: memo[ " << n << " ] with " << r <<endl ;
print_memo(memo) ;
cout << endl;
return r;
}
int main(){
int n ;
int res = 0 ;
reset_memo() ;
while(true){
cout << endl <<endl ;
cout << "enter next number" <<endl ;
cin >> n ;
if( n == -1 ) {cout << "THE END " <<endl ; break ;}
else{
cout << "******************************************"<<endl <<endl <<endl;
res = getMinSteps(n) ;
cout << "******************************************"<<endl <<endl <<endl;
reset_memo() ;
}
}
}
