在线测评网站怎么做,小辉seo,如何进行网站调试,贵阳市城乡建设学校网站7-2 银行家算法–申请资源 (30 分)#xff08;思路详解#xff09;Come 乖宝宝们
一#xff1a;前言
这道题需要用到前面的一道题 安全性检查 算法知识#xff0c;所以强烈建议先看前面那道题 7-1 银行家算法–安全性检查 (20 分)
二#xff1a;题目
输入N个进程(N思路详解Come 乖宝宝们
一前言
这道题需要用到前面的一道题 安全性检查 算法知识所以强烈建议先看前面那道题 7-1 银行家算法–安全性检查 (20 分)
二题目
输入N个进程(N100)以及M类资源M100初始化各种资源的总数T0时刻资源的分配情况。例如 假定系统中有5个进程{P0P1P2P3P4}和三类资源{A,B,C}各种资源的数量分别为10、5、7在T0时刻的资源分配 输入申请资源的进程以及申请各类资源的数目判断是否分配。若分配输出”可以找到安全序列可以分配。“并输出分配后的系统状态。若不分配输出”找不到安全序列不予分配。“并输出当前系统状态。
输入格式: 第一行输入进程数量N第二行输入资源类数M第三行输入M类资源个类资源的总数以下N行分别输入每个进程的名字该进程对M类资源的最大需求以及已分配资源。最后一行输入申请进程的名字和申请各类资源的数目。
输出格式: 若分配输出”可以找到安全序列可以分配。“并输出分配后的系统状态。
若不分配给出不分配的原因
1.若输入的进程的名字不正确输出”查无此进程。“并输出当前系统状态。
2.若申请的资源数目大于最大需求输出”需求不合理不予分配。“并输出当前系统状态。
3.若申请的资源数目大于剩余资源输出”剩余资源不足不予分配。“并输出当前系统状态。
4.若找不到安全序列输出”找不到安全序列不予分配。“并输出当前系统状态。
输入样例1: 在这里给出一组输入。例如
5
3
10 5 7
P0 7 5 3 0 1 0
P1 3 2 2 2 0 0
P2 9 0 2 3 0 2
P3 2 2 2 2 1 1
P4 4 3 2 0 0 2
P1 1 0 2
结尾无空行输出样例1: 在这里给出相应的输出。例如
可以找到安全序列可以分配。
name max allocation need available
P0 7 5 3 | 0 1 0 | 7 4 3 | 2 3 0
P1 3 2 2 | 3 0 2 | 0 2 0 |
P2 9 0 2 | 3 0 2 | 6 0 0 |
P3 2 2 2 | 2 1 1 | 0 1 1 |
P4 4 3 2 | 0 0 2 | 4 3 0 |
结尾无空行输入样例2: 在这里给出一组输入。例如
5
3
10 5 7
P0 7 5 3 0 1 0
P1 3 2 2 2 0 0
P2 9 0 2 3 0 2
P3 2 2 2 2 1 1
P4 4 3 2 0 0 2
P5 1 0 2结尾无空行 输出样例2: 在这里给出相应的输出。例如
查无此进程。
name max allocation need available
P0 7 5 3 | 0 1 0 | 7 4 3 | 3 3 2
P1 3 2 2 | 2 0 0 | 1 2 2 |
P2 9 0 2 | 3 0 2 | 6 0 0 |
P3 2 2 2 | 2 1 1 | 0 1 1 |
P4 4 3 2 | 0 0 2 | 4 3 0 |结尾无空行
三思路
思路 1.我相信如果我们AC出来前面安全性检查那到题那么这道题也会很快做出来 2.前面所求的 need 和 Avaliable是 跟这道题一样的 3.那么接下来我们就是判断 requst 和 need 和 avaliable之间的关系 其中requset 就是 一个进程p1 申请的资源量 1: 如果这个进程名输入错了 那就输出 查无此进程 2: 如果上诉条件满足那判断 request 和 Max 关系 request Max 就欧克 否则 出输出”需求不合理不予分配。“并输出当前系统状态。 3:如果上诉条件满足那就判断 request 和 avaliable之间的关系 request avaliable 就欧克 否则 剩余资源不足不予分配。“并输出当前系统状态 4:当上诉条件均满足的话 那么 相应的进程的 allocation 和 need 要做出变化 而且其 系统可利用的资源 avaliable也要做出相应的变化 5:接下来就是 判断在当前的avaliable下 是否是安全状态也就是安全性检查 如果找到一条安全序列输出 “可以找到安全序列可以分配。“并输出分配后的系统状态。 如果找不到就输出”找不到安全序列不予分配。“并输出当前系统状态。
四坑
需要注意的是当资源分配完成后如果找不到安全序列的话那么需要注意的是 将分配给该进程的资源给收回来 也就是 该进程的need 和 allocation回到 原来的值 同时 还有 avaliable也需要回归到原来的值
五:上码
/**思路1.我相信如果我们AC出来前面安全性检查那到题那么这道题也会很快做出来2.前面所求的 need 和 Avaliable是 跟这道题一样的3.那么接下来我们就是判断 requst 和 need 和 avaliable之间的关系其中requset 就是 一个进程p1 申请的资源量 1: 如果这个进程名输入错了 那就输出 查无此进程2: 如果上诉条件满足那判断 request 和 Max 关系 request Max 就欧克否则 出输出”需求不合理不予分配。“并输出当前系统状态。 3:如果上诉条件满足那就判断 request 和 avaliable之间的关系 request avaliable 就欧克否则 剩余资源不足不予分配。“并输出当前系统状态4:当上诉条件均满足的话 那么 相应的进程的 allocation 和 need 要做出变化而且其 系统可利用的资源 avaliable也要做出相应的变化5:接下来就是 判断在当前的avaliable下 是否是安全状态也就是安全性检查如果找到一条安全序列输出 “可以找到安全序列可以分配。“并输出分配后的系统状态。 如果找不到就输出”找不到安全序列不予分配。“并输出当前系统状态。
**/#includebits/stdc.h
using namespace std;int N,M;
string str;
vectorintv1;//用于存放各种的资源总量
vectorintv2;//用于代表申请资源的进程申请的 资源量
vectorintv3;//用于记录最初的avaliable struct Node{string processName; int a[100];//Maxint b[100];//allocation int c[100];//needbool finish;
} node[1000];//用于判断是否有该进程
bool judgeExit(string str){for(int i 0; i N; i){if(str node[i].processName){return true;}}return false;
}//用于计算此时的request 和 need
bool requestNeed(){int count 0;for(int i 0; i N; i){int count 0;if(str node[i].processName){for(int j 0; j M; j){if(v2[j] node[i].c[j]){//请求量 小于 need count;}} }if(count M){return true;}}return false;}
//用判断申请的资源数目是否大于剩余资源
bool requestAvaliable(){int count 0;for(int j 0; j M; j){if(v2[j] v1[j]){ //请求量 小于 avaliabale count;}} if(count M){return true;}return false;}//判断当前的安全状态
bool isSafe(){int cnt 0; for(int i 0; i N; i){int count 0;for(int j 0; j M; j){if(node[i].c[j] v1[j]){count;}else{break;//只要有一个不合适就 break 出去 } }if(node[i].finish false count M) {//count M说明剩余的各个资源总量大于该进程的所需要的 for(int j 0; j M; j){v1[j] node[i].b[j];//那么此时剩余的资源总量为原来的加上 该进程释放其占有的资源} node[i].finish true; cnt;//记录完成进程的个数 // cout node[i].processName ;//此处牛逼之处在于 只要我们找到满足条件的就从-1开始继续寻找满足条件的 i -1; } }if(cnt N){return true;}return false;
} //用于输出此时系统的状态
void state(){int flag 0;cout name max allocation need available endl;for(int i 0; i N; i){cout node[i].processName ;for(int j 0; j M; j){cout node[i].a[j] ; } cout | ;for(int j 0; j M; j){cout node[i].b[j] ; }cout | ;for(int j 0; j M; j){cout node[i].c[j] ; }cout |;if(flag 0){for(int j 0; j M; j){if(j 0)cout v3[j];elsecout v3[j] ; } flag 1; } cout endl; }
}int main(){cin N M;for(int i 0; i M; i){int nums;cin nums;v1.push_back(nums); } for(int i 0; i N; i){cin node[i].processName;//输入Max for(int j 0; j M; j){cin node[i].a[j]; }//输入allovation for(int j 0; j M; j){cin node[i].b[j];v1[j] - node[i].b[j];//这里是每次减去分配的资源 那么剩下的最后就是 available }//计算needfor(int j 0; j M; j){node[i].c[j] node[i].a[j] - node[i].b[j];} node[i].finish false;}cin str;for(int i 0; i M; i){int temp;cin temp;v2.push_back(temp);} //将最初的avaliable记录下来 for(int i 0; i M; i){v3.push_back(v1[i]);} if(judgeExit(str) false){cout 查无此进程。 endl;state();}else if(requestNeed() false){cout 需求不合理不予分配。 endl;state();}else if(requestAvaliable() false) {cout 剩余资源不足不予分配。 endl;state();}//此时开始将申请的资源赋值给该进程同时进行安全检测 else if(judgeExit(str) true requestNeed() true requestAvaliable() true){for(int i 0; i N; i){if(str node[i].processName){for(int j 0; j M; j){node[i].b[j] v2[j];//这里是更新 该进程的allocation node[i].c[j] - v2[j];//这里是更新 该进程的needv1[j] - v2[j]; //这里是更新 该进程的avaliable v3[j] - v2[j];//存放 最初 avaliable的 }} } if(isSafe() true){cout 可以找到安全序列可以分配。 endl;state();}else{cout 找不到安全序列不予分配。 endl;//如果不满足条件的话 需要将原来 进程的的资源分配形式输出来 for(int i 0; i N; i){if(str node[i].processName){for(int j 0; j M; j){node[i].b[j] - v2[j];//这里是更新 该进程的allocation node[i].c[j] v2[j];//这里是更新 该进程的needv1[j] v2[j]; //这里是更新 该进程的avaliable v3[j] v2[j];//存放 最初 avaliable的 }} } state();} }} //5
//3
//10 5 7
//P0 7 5 3 0 1 0
//P1 3 2 2 2 0 0
//P2 9 0 2 3 0 2
//P3 2 2 2 2 1 1
//P4 4 3 2 0 0 2
//P1 2 2 2//name max allocation need available
//P0 7 5 3 | 0 1 0 | 7 4 3 | 3 3 2
//P1 3 2 2 | 2 0 0 | 1 2 2 |
//P2 9 0 2 | 3 0 2 | 6 0 0 |
//P3 2 2 2 | 2 1 1 | 0 1 1 |
//P4 4 3 2 | 0 0 2 | 4 3 0 |
//找到安全序列处于安全状态。//5
//3
//10 5 7
//P0 7 5 3 0 1 0
//P1 3 2 2 2 0 0
//P2 9 0 2 3 0 2
//P3 2 2 2 2 1 1
//P4 4 3 2 0 0 2
//P0 0 1 0 宝宝们 加油呀 我们共勉 活得坦然 走的自信 坚持热爱 不负初心
