khunima
BAN USERMake a ternary tree and do inorder traversal.
#include<iostream>
#include<string>
using namespace std;
struct node
{
string s;
node* left;
node* right;
};
void Insert(node **root,string s)
{
if(*root==NULL)
{
*root=new node;
(*root)->s=s;
(*root)->left=(*root)->right=NULL;
return;
}
if(s>(*root)->s)
Insert(&(*root)->right,s);
else if(s<(*root)->s)
Insert(&(*root)->left,s);
else
return;
}
void display(node *root)
{
if(root)
{
display(root->left);
cout<<root->s<<"\n";
display(root->right);
}
}
int main()
{
string str[5]={"cat","ant","ball","any","boy"};
node *root=NULL;
for(int i=0;i<5;i++)
Insert(&root,str[i]);
display(root);
return 0;
}
If the graph is directed-
1) Add a dummy source to the first node with capacity infinity.
2) Add a dummy sink to the second node with capacity infinity.
3) Give all other nodes capacity 1.
4) Apply ford-fulkerson algorithm, max-flow value will give the minimum number of edges to disconnect the two nodes.Because max-flow is equal to min-cut.
If the graph is undirected.
1) Reduce it to the directed graph.
2) Apply the same procedure as stated above.
Let the matrix is of order MxN.
void func(int x,int y)
{
if(((x>0 || x<M) && (Y>0 || Y<N)))
if(arr[x][y]==1 && arr[x-1][y]==0 && arr[x+1][y]==0 & & arr[x][y+1]==0 &&arr[x][y-1]==0))
{
arr[x-1][y]==1;
arr[x+1][y]==1;
arr[x][y+1]==1;
arr[x][y-1]==1;
}
func(x-1,y);
func(x+1,y);
func(x,y+1);
func(x,y-1);
}
else
return;
First element will be the root and there will be decreasing sequence followed by an increasing sequence. Decreasing sequence will be left subtree and increasing sequence will be right subtree.
Tree(pre[],int start,int end)
{
node *ptr=(node *)alloc(sizeof(node));
ptr->data=pre[start];
for(int i=start+1;i<end;i++)
if(pre[i+1]>pre[i])
break;
ptr->left=Tree(pre,start+1,i)
ptr->right=Tree(pre,i+1,end)
retrun ptr;
}
This is based on divide and conquer approach. If N is even put N/2 coins on both side of the weight balance. One having less weight has the fake coin. Again do the same on N/2 coins until you get 1 coin on each side. One having less weight will be the fake coin.
If N is odd or in some intermediate step of above algo (when N is even and N/2 is odd) , We cannot divide in 2 parts so remove one coin from the N coins now N-1 will be even, divide it and weight it ,if both has same weight then the removed coin is fake coin if not then the (N-1)/2 coins having less weight will have fake coin. Repeat the process until you get fake coin.
This is a permutation problem which can be solved by backtracking.
void permute(char *str, int start, int end)
{
if (start == end)
printf("%s\n", str);
else
{
for (int i = start; i <= end; i++)
{
swap((str+start), (str+i));
permute(str, start+1, end);
swap((str+start), (str+i)); //backtrack
}
}
}
}
- khunima October 24, 2014