The Fibonacci series :
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …
begins with a 0 and 1 and has the property that each subsequent Fibonacci number is
the sum of the previous two Fibonnacci numbers
fib(n) =
0 if n = 0
1, if n = 1
fib(n-1) + fib(n-2), if n > 1
• A Fibonnacci number, fib(n), can be expressed mathematically
fib(n) =
0 if n = 0
1, if n = 1
fib(n-1) + fib(n-2), if n > 1
1. Recusive Method to tackle the problem:
int fibonacci(int n){
if( n <= 1) return n; else return (fibonacci(n-1) + fibonacci(n-2)); } Complexity Analysis: the O-notation for fibonacci(n) is O(2^n), for example, if n = 20, that will result in one millions of function calls.
2. Iterative Mehod to tackle the problem:
int fibonacci(int n) {
int f1 = 0;
int f2 = 1;
int f;
if(n <=1)
return n;
for(int i = 2, i <= n; i++)
{
f = f1 + f2;
f1 = f2;
f2 = f;
}
return f;
}
Complexity Analysis: the O-notation for this method is O(n). So it is much more efficient than the recusive method!
3. Non-recursive Methold by using array
//use an array to hold the previous two values
int fibonacci2(const unsigned& n){
if(n <= 1)
return n;
unsigned* fib_a = (unsigned*) malloc((n+1)*sizeof(unsigned));
unsigned result;
fib_a[0]= 0;
fib_a[1] = 1;
for(unsigned i = 2; i <= n; i++){
fib_a[i] = fib_a[i-1] + fib_a[i-2];
}
result = fib_a[n];
free(fib_a);
return result;
}
The Complexity Analysis: the O-notation for this method is O(n), though it is a little more efficient than the previous one, it cosume more memory.
how to calculate an intger's factorial?
Factorial Explanation :
- The product of the positive integers from 1 to n inclusive is called
“n factorial”, usually denoted by n!
n! = n*(n-1)*(n-2)…3*2*1
int factorial(int n){
if ( n > = 1) //base case
return 1;
else
return n*factorial(n-1); //recursive case
}
- The product of the positive integers from 1 to n inclusive is called
“n factorial”, usually denoted by n!
n! = n*(n-1)*(n-2)…3*2*1
int factorial(int n){
if ( n > = 1) //base case
return 1;
else
return n*factorial(n-1); //recursive case
}
Binary Search Tree
1. Data structure organized as trees will prove valuable for a range of applications, especially for problems of information retrieval.
2. A binary tree is either empty,ot it consists of one node called root together with two binary trees called left subtree and the right subtree of the root.
3. Three ways to traverse the binary tree: (1) preorder: (root, left, right) (2)Inorder: (left, root, right) (3) postorder: (left, right, root)
4. Express Tree: An expression tree is built up from the simple operands and operators of an expression by placing the simple operands as the leaves of a binary tree and the operators as interior nodes.
5. The binary tree is used to implement the binary search tree and binary heap.
6. The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only a node (the root) has a height of zero.
7. The size of a node is the number of descendants it has including itself.
8. The Binary Search Tree (BST): the BST is a binary tree with the following property, any node in the tree, is greater than any nodes in its left tree and less or equal to every item in its right subtree.
9. An inorder traverse of the BST will process the items in increasing order.
10. The insertion and searching are efficient with BST, provided that the BST is close to being ballanced. A binary tree is called balanced if for any node in the tree, the number of nodes in its left subtree is approximately same as in its right subtree.
11. When inserting a new node into BST we always insert the new node as a leaf node.
12. The nodes' values in BST must be unique, doesn't allow to insert a duplicate node.
13. For any BST, the smallest value is at the left-most node, the biggest value is at the right-most node.
template
int binaryTree::size()
//return the number of nodes in the binay tree
{
int count =0;
recursiveSize(root, count);
return count;
}
template
void binaryTree::recursiveSize(treeNode* subTree, int& count)
//use recursive method to get the num of nodes in the binary tree
//traverse the tree in pre-order
{
if(subTree != NULL) {
count++;
recursiveSize(subTree->left, count);
recursiveSize(subTree-right, count);
}
}
template
int binaryTree::height()
//return -1 if the tree is empty, return 1 if the tree is root tree
{
int height;
if(root == NULL)
return -1;
recursiveHeight(root, height);
return height;
}
template
void binaryTree::recursiveHeight(treeNode* subTree, int& height)
//get the heights for the left and right subtree, then add 1 to the max of them
{
int lh, rh;
if( subTree == NULL) {
height = -1;
}
else {
recursiveHeight(subTree->left, lh);
recursiveHeight(subTree->right, rh);
height = ( (lh > rh)?lh:rh ) + 1;
}
}
TreeNode* TreeNode::clone()
{
if (TreeNode* tmp = new TreeNode)
{
tmp->ascii = ascii;
if (left) tmp->left = left->clone();
if (right) tmp->right = right->clone();
return tmp;
}
return 0;
}
2. A binary tree is either empty,ot it consists of one node called root together with two binary trees called left subtree and the right subtree of the root.
3. Three ways to traverse the binary tree: (1) preorder: (root, left, right) (2)Inorder: (left, root, right) (3) postorder: (left, right, root)
4. Express Tree: An expression tree is built up from the simple operands and operators of an expression by placing the simple operands as the leaves of a binary tree and the operators as interior nodes.
5. The binary tree is used to implement the binary search tree and binary heap.
6. The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only a node (the root) has a height of zero.
7. The size of a node is the number of descendants it has including itself.
8. The Binary Search Tree (BST): the BST is a binary tree with the following property, any node in the tree, is greater than any nodes in its left tree and less or equal to every item in its right subtree.
9. An inorder traverse of the BST will process the items in increasing order.
10. The insertion and searching are efficient with BST, provided that the BST is close to being ballanced. A binary tree is called balanced if for any node in the tree, the number of nodes in its left subtree is approximately same as in its right subtree.
11. When inserting a new node into BST we always insert the new node as a leaf node.
12. The nodes' values in BST must be unique, doesn't allow to insert a duplicate node.
13. For any BST, the smallest value is at the left-most node, the biggest value is at the right-most node.
template
int binaryTree::size()
//return the number of nodes in the binay tree
{
int count =0;
recursiveSize(root, count);
return count;
}
template
void binaryTree::recursiveSize(treeNode
//use recursive method to get the num of nodes in the binary tree
//traverse the tree in pre-order
{
if(subTree != NULL) {
count++;
recursiveSize(subTree->left, count);
recursiveSize(subTree-right, count);
}
}
template
int binaryTree::height()
//return -1 if the tree is empty, return 1 if the tree is root tree
{
int height;
if(root == NULL)
return -1;
recursiveHeight(root, height);
return height;
}
template
void binaryTree::recursiveHeight(treeNode
//get the heights for the left and right subtree, then add 1 to the max of them
{
int lh, rh;
if( subTree == NULL) {
height = -1;
}
else {
recursiveHeight(subTree->left, lh);
recursiveHeight(subTree->right, rh);
height = ( (lh > rh)?lh:rh ) + 1;
}
}
TreeNode* TreeNode::clone()
{
if (TreeNode* tmp = new TreeNode)
{
tmp->ascii = ascii;
if (left) tmp->left = left->clone();
if (right) tmp->right = right->clone();
return tmp;
}
return 0;
}
Swap data between two arrays
You are given two arrays
int Array1[n], Array2[n];
Each array contains numbers which are half even and half odd. Write C code that will return two arrays one having only even numbers and other having only odd numbers. You are not allowed to use additional data structures like hash,array etc but can use temp variables. The solution should have O(n) complexity.
int array1[20] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 }; int array2[20] = { 21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40};
//array1 will contain even. array2 will contain odd.
i= 0; j = 0;
while( i < 20 && j < 20 ){
while(i<20 && array[i]%2 == 0)
i++;
while(j<20 && array[j]%2 == 1)
j++;
//swap only when i < 20 && j < 20 cause there is a possibilty that one could be over before the other.
if( i<20 && j<20)
{ //swap contents of i and j
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++; j++;
}
}
int Array1[n], Array2[n];
Each array contains numbers which are half even and half odd. Write C code that will return two arrays one having only even numbers and other having only odd numbers. You are not allowed to use additional data structures like hash,array etc but can use temp variables. The solution should have O(n) complexity.
int array1[20] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 }; int array2[20] = { 21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40};
//array1 will contain even. array2 will contain odd.
i= 0; j = 0;
while( i < 20 && j < 20 ){
while(i<20 && array[i]%2 == 0)
i++;
while(j<20 && array[j]%2 == 1)
j++;
//swap only when i < 20 && j < 20 cause there is a possibilty that one could be over before the other.
if( i<20 && j<20)
{ //swap contents of i and j
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++; j++;
}
}
How to join the leafes of the binary tree?
Given a binary tree, how would you join the nodes at each level, left to right.
Say there are 5 nodes at level three, link all of them from left to right.
Say there are 5 nodes at level three, link all of them from left to right.
Subscribe to:
Posts (Atom)