#include <iostream>
using namespace std;

int AVAILABLE[5];          /*可用資源數(shù)組*/
int MAX[10][5];            /*最大需求矩陣*/
int ALLOCATION[10][5];     /*分配矩陣*/
int NEED[10][5];           /*進(jìn)程需求矩陣*/
int need1[10][5] ;          //手工輸入需求矩陣
int REQUEST[10][5];        /*進(jìn)程需要資源數(shù)*/
int total[5];
int totalAllocation[5];
bool FINISH[10];           /*系統(tǒng)是否有足夠的資源分配*/
int p[10];                 /*記錄序列*/
int m,n;                   /*m個進(jìn)程,n個資源*/

void Init();
bool IsSafe();
void Bank();


void Init()                /*初始化算法*/
{
    int i,j;
    cout<<"請輸入進(jìn)程的數(shù)目:";
    cin>>m;
    cout<<"請輸入資源的種類:";
    cin>>n;
    cout<<"請輸入每個進(jìn)程最多所需的各資源數(shù),按照"<<m<<"x"<<n<<"矩陣輸入"<<endl;
    for(i=0;i<m;i++)
	{ cout<<"p"<<i<<" ";
      for(j=0;j<n;j++)
       
	  cin>>MAX[i][j];}
    cout<<"請輸入每個進(jìn)程已分配的各資源數(shù),也按照"<<m<<"x"<<n<<"矩陣輸入"<<endl;
    for(i=0;i<m;i++)
    {   cout<<"p"<<i<<" ";
        for(j=0;j<n;j++)
        {   
            cin>>ALLOCATION[i][j];
            NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];
            if(NEED[i][j]<0)
            {
                cout<<"您輸入的第"<<i+1<<"個進(jìn)程所擁有的第"<<j+1<<"個資源數(shù)錯誤,請重新輸入:"<<endl;
                j--;
                continue;
            }
        }
    }
loop: cout<<"請輸入need1矩陣"<<endl;
      for(i=0;i<m;i++){
          for(j=0;j<n;j++)
          {
             cin>>need1[i][j];
            
           }
       }
      for(i=0;i<m;i++){
          for(j=0;j<n;j++)
          {
        if(need1[i][j]>NEED[i][j])
		{ cout<<"輸入有錯,請重新輸入："<<endl;    
		    goto  loop ;
		}
                                                  //	continue;
              }
       }




    cout<<"請輸入各個資源共有的數(shù)目:"<<endl;
    for(j=0;j<n;j++)
    {
        cin>>total[j];
    }

   for(j=0;j<n;j++){
        for(i=0;i<m;i++)
     {totalAllocation[j]+=ALLOCATION[i][j];}
    AVAILABLE[j]=total[j]-totalAllocation[j];   

   }
   cout<<"系統(tǒng)可利用資源";
   for(j=0;j<n;j++)

   {
	   cout<<" "<<AVAILABLE[j];
	   
   }

    cout<<endl;

   }

void Bank()                /*銀行家算法*/
{
    int i,num,q;         
    char again;

    while(1)
    {
loop1:  cout<<"請輸入要申請資源的進(jìn)程號(從0開始)"<<endl;
        cin>>num;
        cout<<"請輸入進(jìn)程所請求的各資源的數(shù)量"<<endl;
        for(i=0;i<n;i++)               
        {
            cin>>REQUEST[num][i];
        }
   



        for(i=0;i<n;i++)
        {
            if(REQUEST[num][i]>NEED[num][i])
            {
                cout<<"您輸入的請求數(shù)超過進(jìn)程的需求量!請重新輸入!"<<endl;
               goto loop1;
            }
            if(REQUEST[num][i]>AVAILABLE[i])
            {
                cout<<"您輸入的請求數(shù)超過系統(tǒng)有的資源數(shù)!請重新輸入!"<<endl;
                goto loop1;
            }
    	else
            cout<<"Request"<<num<<"(";
		    for(i=0;i<n;i++)
				cout<<REQUEST[num][i]<<",";
			cout<<")<=Need"<<num<<"(";
			for(i=0;i<n;i++)
				cout<<NEED[num][i]<<",";
			cout<<")"<<endl;
            cout<<"Request"<<num<<"(";
		    for(i=0;i<n;i++)
				cout<<REQUEST[num][i]<<",";
			cout<<")<=AVAILABLE"<<"(";
			for(i=0;i<n;i++)
				cout<<AVAILABLE[i]<<",";
			cout<<")";

        }
        for(i=0;i<n;i++)
        {
            AVAILABLE[i]-=REQUEST[num][i];
            ALLOCATION[num][i]+=REQUEST[num][i];
            NEED[num][i]-=REQUEST[num][i];
        }
        if(IsSafe())
        {
            cout<<"同意分配請求!"<<endl;
             for(i=0;i<m;i++)
			 {
                FINISH[i]=false;
			 }
			 cout<<"當(dāng)前可利用資源";
            for(i=0;i<n;i++)
		   cout<<AVAILABLE[i]<<" ";
			cout<<endl;
             cout<<"當(dāng)前各進(jìn)程需要資源："<<endl;
       for(i=0;i<m;i++)
	   { for(q=0;q<n;q++)
	   {cout<<NEED[i][q];}
         cout<<endl;
	   }
            cout<<"您還想再次請求分配嗎?是請按y/n,否請按其它鍵"<<endl;
            cin>>again;
          
        if(again=='y'||again=='Y')
        {   
		  	 
            continue;      //跳到while繼續(xù)執(zhí)行銀行家算法
        }
        break;
        }
        else
        {
            cout<<"您的請求被拒絕!"<<endl;
            for(i=0;i<n;i++)
            {
                AVAILABLE[i]+=REQUEST[num][i];
                ALLOCATION[num][i]-=REQUEST[num][i];
                NEED[num][i]+=REQUEST[num][i];
            }
        }
        for(i=0;i<m;i++)
        {
            FINISH[i]=false;
        }

     }
}

bool IsSafe()                        //安全性檢查算法
{
    int i,j,k,l=0;
    int Work[5];                    /*可利用資源數(shù)*/
    for(i=0;i<n;i++)
    Work[i]=AVAILABLE[i];
    for(i=0;i<m;i++)               //先初始化均為false
    {
        FINISH[i]=false;
    }
    for(i=0;i<m;i++)
	{    
        if(FINISH[i]==true)
        {
            continue;
        }
        else
        {
            for(j=0;j<n;j++)
            {
                if(NEED[i][j]>Work[j])  //需要資源大于可利用資源
                {
                    break;
                }
            }
            if(j==n)
            { 
                FINISH[i]=true;
                for(k=0;k<n;k++)
                {
                    Work[k]+=ALLOCATION[i][k];     //可利用資源相加
                }
                p[l++]=i;
                i=-1;     //重新從進(jìn)程0開始循環(huán)，已加入的則跳過
            }
            else
            {
                continue; 
            }
        }
        if(l==m)
        {
            cout<<"系統(tǒng)是安全的"<<endl;
            cout<<"安全序列:"<<endl;
            for(i=0;i<l;i++)
            {
                cout<<p[i];
                if(i!=l-1)
                {
                    cout<<"-->";
                }
            }
            cout<<""<<endl;
            return true;
        }
    }
    cout<<"系統(tǒng)是不安全的"<<endl;
    return false;
} 

int main()
{
    Init();
    IsSafe();
    Bank();
}