#include<iostream>
#include<time.h>
#include<stdlib.h>
using namespace std;
#define  M  320

int N;
struct Pro
{
	int num,time;
};
void Input(Pro p[M])
{   
	int count=0;
	srand((unsigned)time(0));
	int i=0,nrand=0,n=0;
	int num[1000];
	int page1[1000];
	int offset[1000];
	nrand=rand()%32767;
	n=(float)319*nrand/32767+1;
	for(i=0;i<320;i+=4)
	{
		num[i]=n;
		num[i+1]=num[i]+1;
		nrand=rand()%32767;
		num[i+2]=(float)num[i]*nrand/32767;
		num[i+3]=num[i+2]+1;
		nrand=rand()%32767;
		n=(float)nrand*(318-num[i+2])/32767+num[i+2]+2;
	}
	for(i=0;i<320;i++)
	{
		page1[i]=num[i]/10;
		offset[i]=num[i]%10;
		page1[i]%=32;
	}
	for(i=0;i<320;i++)
	{
		p[i].num=offset[i];
		p[i].time=0;
	}
}

int  Search(int e,Pro *page1  )
{
	int i=0;
	Pro *page=new Pro[N];
	page=page1;
	for(i=0;i<N;i++)
		if(e==page[i].num)
			return i;
	return -1;
}

int Max(Pro *page1)
{
	Pro *page=new Pro[N];
	page=page1;
	int e=page[0].time,i=0;
	while(i<N)//找出離現在時間最長的頁面
	{
		if(e<page[i].time)
			e=page[i].time;
			i++;
	}
    for( i=0;i<N;i++)
		if(e==page[i].time)
			return i;
	
	return -1;
}

int Compfu(Pro *page1,int i,int t,Pro p[M])
{
	Pro *page=new Pro[N];
	page=page1;
	
	int count=0;
	for(int j=i;j<M;j++)
	{
		if(page[t].num==p[j].num )
			break;
		else 
			count++;
	}
	return count;
	
}

int main()
{
    
	cout<<"可用內存頁面數"<<endl;
	cin>>N;	
	Pro p[M];
	Pro *page=new Pro[N];
	char c;
	int m=0,t=0;
	float n=0;
	Input(p);
	int i=0;
	do{
		
		for(i=0;i<N;i++)//初試化頁面基本情況
		{
			page[i].num=0;
			page[i].time=2-i;
		}
        i=0;		
        cout<<"f:FIFO頁面置換"<<endl;
		cout<<"l:LRU頁面置換"<<endl;
		cout<<"o:OPT頁面置換"<<endl;
		cout<<"按其它鍵結束"<<endl;
		cin>>c;
		
		if(c=='f')//FIFO頁面置換
		{
			n=0;
			while(i<m)
			{
				if(Search(p[i].num,page)>=0)
					i++;//找到相同的頁面
				else 
				{  
					if(t==N)
						t=0;
					else 
					{
						n++;//
						page[t].num=p[i].num;
						t++;
					}
				}
			}
			cout<<"缺頁次數："<<n<<"    命中率："<<1-n/m<<endl;      
			
		}
		if(c=='l')//LRU頁面置換
		{    
			n=0;
			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)  				
					i++;
			}
			cout<<"缺頁次數："<<n<<"    命中率："<<1-n/m<<endl; 
			}
			if(c=='o')//OPT頁面置換
			{
				n=0;
				while(i<m)
				{
					if(Search(p[i].num,page)>=0)
						i++;
					else
					{
						int temp=0,cn;
						for(t=0;t<N;t++)
						{
							if(temp<Compfu(page,i,t,p))
							{
								temp=Compfu(page,i,t,p);
								cn=t;
							}
						}
						page[cn]=p[i];
						n++;
						i++;
					}
				}
				cout<<"缺頁次數："<<n<<"    命中率："<<1-n/m<<endl; 
			}		
		}while(c=='f'||c=='l'||c=='o');	
	return 0;
}