#include <iostream>
#include <string.h>
using namespace std;
//========================

//-------------------------------
int **martrix;
 int i,j;
void setm(int m,int n)
{for(i=0;i<n;i++)
{martrix[m][i]=1;
 martrix[i][m]=0;
}
}
//-----------------------------------
char * current;
void print(int n)
{ int p,q;
for(p=0;p<n;p++)
{ for(q=0;q<n;q++)
   {cout<<martrix[p][q]<<" ";}
   cout<<"**"<<current[p];
   cout<<"\n";
}
}
//-----------------------------------
int mini(int *b)
{int i=0;
 int n,m,flag;
 n=0;
 while(b[i]>=0&&b[i]<=9){n++;i++;}
m=b[0];flag=0;
 for(j=1;j<n;j++)
 { if(m>b[j]) {m=b[j];flag=j;}
 }
return flag;
}
//-------------------------------------
void main()
{
 int n;
 char sequence[255];
 cout<<"請輸入分配物理塊數:";
 cin>>n;
 cout<<"請輸入頁面走向序列:";
 cin>>sequence;
 cout<<"*****LRU算法*****"<<endl;

 martrix=new int * [n];
 for( i=0;i<n;i++)
  martrix[i]=new int[n];

 current=new char [n];
 for(i=0;i<n;i++)
  current[i]=' ';
 
 for(i=0;i<n;i++)  //模擬寄存器
  for(j=0;j<n;j++)
   martrix[i][j]=0;

  int k;
  int len=strlen(sequence);
  int flag;
  int f;
  int *total;
  int g;
  int count=0;
  char c;
  total=new int[n];
  for(i=0;i<n;i++)
   total[i]=0;

  for(k=1;k<=len;k++)
{  cout<<endl; 
 cout<<sequence[k-1]<<"要求進入"<<endl;
 if(k<=n) {current[k-1]=sequence[k-1];setm(k-1,n);print(n);cout<<"缺頁"<<endl;count++;}
else 
{     for(i=0;i<n;i++)
       {      if(current[i]==sequence[k-1]) {flag=i; break;}
       }
    if(i==n) { 
             for(f=0;f<n;f++)
                    { for(g=0;g<n;g++)
                           {total[f]+=martrix[f][g];}
            } 
        c=current[mini(total)];
        current[mini(total)]=sequence[k-1];
        setm(mini(total),n);print(n);cout<<"缺頁,置換前一次"<<c<<"的那行"<<endl;
        cout<<endl;
        count++;
               }            
else
{setm(flag,n);print(n);cout<<endl;}
}
for(i=0;i<n;i++)
                  total[i]=0;

}
cout<<"///////////////////////////////////"<<endl;
cout<<"總共有"<<count<<"次缺頁"<<endl;

cout<<"缺頁率："<<count<<"/"<<len<<endl;
cout<<"演示完畢！"<<endl;
}