#include<iostream.h>
#define  M  40
struct Q
{
	int num,time;
};


/************輸入頁面個數與頁面號************/
int Input(int m,Q p[M])
{   
	cout<<"請輸入頁數：";
	do
	{
		cin>>m;
		if(m>M)cout<<"數目太多，請重試"<<endl;
	    else break;
	}while(1);
    cout<<endl<<"請輸入各頁面號"<<endl;
   	for(int i=0;i<m;i++)
	{
		cin>>p[i].num;
		p[i].time=0;
	}
	return m;
}

/**********顯示置換的情況**************/
void print(Q page[3])
{
	for(int i=0;i<3;i++)cout<<page[i].num<<"  ";
	cout<<endl;
}

/***********尋找指定元在固定頁中的位置***********/
int  Search(int e,Q page[3]  )
{
  for(int i=0;i<3;i++)if(e==page[i].num)return i;
  return -1;
}

/*************尋找最大時間元在 固定頁中的位置***************/
int Max(Q page[3])
{
	int e=page[0].time,i=0;
     while(i<3)
	{
		 if(e<page[i].time)e=page[i].time;
		 i++;
	}
    for( i=0;i<3;i++)if(e==page[i].time)return i;

  return -1;
}

/*********************固定分配局部置換主函數*******************/
int main()
{
    Q p[M], page[3];
	 char c;
     int m=0,t=0;
	 float n=0;
	m=Input(m,p);

 
  do{

       for(int i=0;i<3;i++)
		  {
		  page[i].num=p[i].num;
          page[i].time=2-i;
		  }
        i=3; 
       cout<<"開始時";
	   print(page);
        
      cout<<"若FIFO頁面置換則輸入f,若LRU頁面置換則輸入l,否則輸入其他鍵：";
	  cin>>c;
	  
     if(c=='f')//FIFO頁面置換
	 {
		
		 cout<<"頁面置換情況:   "<<endl;
        while(i<m)
	   {
		if(Search(p[i].num,page)>=0)i++;
		else 
		{  
			if(t==3)t=0;
		    else 
			{
				n++;
			page[t].num=p[i].num;
			print(page);
			t++;
			}
		}
	   }
       cout<<"缺頁次數："<<n<<"    缺頁率："<<n/(n+3)<<endl;      

	 }
     if(c=='l')//LRU頁面置換
	 {    n=0;
		 cout<<"頁面置換情況:   "<<endl; 
		 while(i<m)
		 {    
			int k;
		    k=t=Search(p[i].num,page);
			if(t>=0)
			
			  page[t].time=0;
			  
           
              else
			{  
				  n++; 
			  t=Max(page);
		
			  page[t].num=p[i].num;
              page[t].time=0;
              }
			  if(t==0){page[t+1].time++;page[t+2].time++;}
			  if(t==1){page[2].time++;page[0].time++;}
              if(t==2){page[1].time++;page[0].time++;}
            if(k==-1)   print(page);
              
	          
		 	 i++;
		 }
     cout<<"缺頁次數："<<n<<"    缺頁率："<<n/(n+3)<<endl; 
	 }
  
	}while(c=='f'||c=='l');
 
 

	return 0;
}