#include<iostream.h>
int fact(int n)
{
 if(n==0||n==1)
	return(1);
 else
	return(n*n-1*fact(n-2));
}

// tedaade kole avaamele avvale yek adad
int PrimeFactorNum(int n)
{
 int i;
 i=1;
 while(++i<=n)
 {
	if(n%i==0)
	  return(1+PrimeFactorNum(n/i));
 }
 return(0);  // when n=1 or less
}

int fibunatchi(int n)
{
  if(n<=2)
	 return(1);
  else
	 return(fibunatchi(n-1)+fibunatchi(n-2));
}

// chap vaarooneye yek araaye (dar morede reshte haa ham ghabel anjaam ast
void printreverse(int a[],int first)
{
 printreverse(a,first+1);
 cout<<a[first];
 return;
}

// sorting an array(method 1)
void sort1(int a[],int first,int last)
{
  int i,n;
  if(last>first)
	 sort1(a,first,last-1);
  n=a[last];
  for(i=last;i>first&&a[i-1]>n;i--)
	 a[i]=a[i-1];
  a[i]=n;
}

//napsack problem: is there a subset of a[] which sum is equal to n?
// the idea is we say either the last elemnt is in the subset or it is not
// if the last element is not the subset we try to make n by a subset of a[first]..a[last]
// if last element is in the subset then we try to make n-a[last] by a subset of a[first]..a[last]
int napsack(int a[],int first,int last,int n)
{
 if(first==last)
	return(a[first]==n);
 return(napsack(a,first,last-1,n)||napsack(a,first,last-1,n-a[last]));
}

// napsack with writing the subset members
int napsack1(int a[],int first,int last,int n)
{
 if(first==last)
	if(a[first]==n)
	{
	  cout<<' '<<n<<' ';
	  return(1);
	}
	else
	  return(0);
 if(napsack1(a,first,last-1,n))
	return(1);
 else if(napsack1(a,first,last-1,n-a[last]))
 {
	cout<<' '<<a[last]<<' ';
	return(1);
 }
 else
	return(0);
}


// tavajoh: manzoor az reshte yek araaye az char ast
// tavajoh2: manzoor az zir reshte tedadi az anaasor araaye kenaare ham ast

// toole bozorg tarin zirreshte yek reshte ke az vasat be to taraf motaghaaren ast
// maslan 1 4 6 4 1 motagharen ast
int BigSubstring(char s[],int first,int last)
{
 int i,match,n1,n2;
 match=1;
 for(i=first;i<=last;i++)
	if(s[i]!=s[last-(i-first)])
	  match=0;
 if(match)
	return(last-first+1);
 n1=BigSubstring(s,first,last-1);
 n2=BigSubstring(s,first+1,last);
 if(n1>n2)
	return(n1);
 else
	return(n2);
}


// yek araaye az adaad darim, ayaa baa gozaashtan + yaa * beyne
// aanhaa mitavaan n raa ijaad kard, baa farze inke amaale riaazi taghadom nadaarand va
int CanMake(int a[],int first,int last,int n)
{
 int answer;
 if(first==last)
	return(a[first]==n);
 answer=CanMake(a,first+1,last,n-a[first]);
 if(n%a[first]==0)
	answer=answer||CanMake(a,first+1,last,n/a[first]);
 return(answer);
}

// m matrise mojaaverate yek graph (VertexNum=tedaade ra~s haa) ast,
// toole kootah tarin masir az rase n1 be n2, va -1 agar masir vojood nadaarad
// PassedVertexes is initially all zero, used inside the function to show
// the vertexes which are passed in the path
const VertexNum=3;
int PassedVertexes[]={0,0,0};
int ShortestPathLen(int m[][VertexNum],int n1,int n2)
{
 int i,MinPathLen,l;
 if(n1==n2)
	return(0);
 PassedVertexes[n1]=1; // passing the node n1 and try going to other nodes
 MinPathLen=VertexNum; // longest possible path len is VertexNum-1
 for(i=0;i<VertexNum;i++)
	if(!PassedVertexes[i]&&m[n1][i])
	{
	 l=ShortestPathLen(m,i,n2);
	 if(l>=0&&l<MinPathLen)
		MinPathLen=l;
	}
 PassedVertexes[n1]=0; // back tracking in the path
 if(MinPathLen==VertexNum)
	return(-1);
 else
	return(1+MinPathLen);
}

void main()
{
  int m[VertexNum][VertexNum]={{1,0,1},
										 {0,1,1},
										 {1,1,1}};
  int a[6]={5,4,3,7,2,2};
  char s[11]="abaffgffaa";
  sort1(a,0,5);
  cout<<PrimeFactorNum(20);
  napsack1(a,0,5,1);
  napsack1(a,0,5,15);
  cout<<'\n'<<BigSubstring(s,0,9);
  cout<<'\n'<<ShortestPathLen(m,0,1);
}