The coding bird

The fibonacci series using memoization

2011-12-16T08:42:00.000-08:00

Another algorithm today...
This is the Fibonacci series implemented with memoization .

int fibonacci(int n){
 int prev=0;
 int next=1;
 int val=0;
 for(int i=2;i<=n;i++){
  val=next+prev;
  prev=next;
  next=val;
 }
 return val;
}

Typically, If you are designing a maths library, you would implement a caching mechanism to avoid reprocessing again. A better way in term of performance would be :

int fibonacci(int n){
 static vector<int> cache(0);
 //check if we have already processed
 if(n<cache.size()){
  cout<<"from cache: ";
  return cache.at(n);
 }
 
 //initial values 
 if(cache.size()==0){
  cache.push_back(0);
  cache.push_back(1);
 }
 
 //we calculate the fibonacci from where the cache end to the number requested
 for(int i=cache.size()-1;i<=n;i++){
  cache.push_back( cache.at(i) + cache.at(i-1) );
 }
 cout<<"Calculated : ";
 return cache.at(n);
}

the cout is embedded for simple debugging.

Matching parenthesis in arithmetic expressions with c++

2011-12-14T13:47:00.000-08:00

This is a simplinstic way of testing if an expression is correctly grouped using stack based method.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main (int argc, char *argv[]){
	vector<char> expr_validator;
	string expression="2[(a-9)/(2-b)]/(x-2)-[(4*(x-8)+4)/(5x+17)]";
	for(int i=0;i<expression.length() ;i++){
		switch(expression[i]){
			case '(':
					expr_validator.push_back(expression[i]);
				break;		
			case ')':
					if('('==expr_validator.back())
						expr_validator.pop_back();
					else
						expr_validator.push_back(expression[i]);
				break;
			case '[':
					expr_validator.push_back(expression[i]);
				break;
			case ']':
					if('['==expr_validator.back())
						expr_validator.pop_back();
					else
					expr_validator.push_back(expression[i]);
				break;					
		}
	}	
	
	if(expr_validator.empty()){
		cout << "Good Expression" << endl;	
	}else {
		cout << "Bad Expression" << endl;
		cout<<	expr_validator.size() ;
	}
	return 0;	
}

About this blog

2011-12-01T13:40:00.001-08:00

Just another blog about c/c++ , Qt , STL, C# Winform ,WPF, PHP Zend framework, CI , Yalamo , and javascrip ...