求n个数的全排列,n不定。用c语言。用于银行家算法中求安全序列

在求安全序列中需要遍历所有的可能,从中找到一条可行的安全序列。这个遍历该怎么做??
谢谢
最新回答
姐↗就是女汉子

2024-11-07 01:02:16

好久没用c了,所以代码可能要用到伪代码
先定义a[maxn]
用子函数递归
void p(int x)
{
if (n == x+1)
{
//foreach a print
//输出数组a
}
for (int i=1 to n)
{
a[x] = i;
p(x+1);
a[x] = 0;
}
}
主函数main调用p(n)
会坚持

2024-11-07 00:34:05

源代码:
#include<stdio.h>
#include<stdlib.h>
#defineN 100
#defineM 100
intavailable[M];
intmax[N][M];
intallocation[N][M];
intneed[N][M];
intn,m;

intv[N];
intflag_security=0;
/*
all_security函数为银行家算法的子算法:安全性算法
@work 系统可提供给进程继续运行的所需的各类资源数目,含m个元素
@num 进行试探性分配时,已得到资源分配的进程个数 为num-1
@s 存放已得到资源分配的进程个数,当num-1==n时即得到一个安全序列。
*/
voidall_security(int work[],int num,int s[]){
int i,j;
if(num==n+1){
flag_security=1;
int j;
printf("安全序列:");
for(j=1;j<num;j++)
printf("%d ",s[j]-1);
printf("\n");
}
int flag_error=0;
for(i=1;i<=n;i++){ //注意回溯时,同层节点的控制
flag_error=0; //之前flag_error声明在for外,导致剪枝失败
for(j=1;j<=m;j++){
if(need[i][j]>work[j]){
flag_error=1;
break;
}
}
if(!v[i]&&!flag_error){
v[i]=1;
s[num]=i;
int work2[M];
for(j=1;j<=m;j++){
work2[j]=work[j];
}
for(j=1;j<=m;j++){
work2[j]+=allocation[i][j];
}
all_security(work2,++num,s);
num--;
v[i]=0;
}
}
}
/*
bank为银行家算法
@pid 进程的pid,范围在0 ~ n-1
@request 进程pid的资源请求向量
@return 若可分配资源给进程pid,则return 1,否则return 0
*/
intbank(int pid,int request[]){
int i,j;
for(i=1;i<=m;i++){
if(request[i]>need[pid][i]){
printf("error:进程%d请求的资源数量>所需的资源数量!\n",pid-1);
exit(0);
}
if(request[i]>available[i]){
printf("error:系统无足够资源,进程%d等待中。。。\n",pid-1);
return 0;
}
}
for(i=1;i<=m;i++){
available[i]-=request[i];
allocation[pid][i]+=request[i];
need[pid][i]-=request[i];
}
int work[M];
for(j=1;j<=m;j++){
work[j]=available[j];
}
int s[N];
for(i=0;i<=n;i++){
v[i]=0;
}
flag_security=0;
all_security(work,1,s);
if(!flag_security){
printf("error:系统执行安全性算法,结果为此次资源分配后系统不处于安全状态!\n");
available[i]+=request[i];
allocation[pid][i]-=request[i];
need[pid][i]+=request[i];
return 0;
}
return 1;
}

intmain(){
int s[10];
int i,j,pid,request[M];;
printf("输入进程数和资源种类数:\n");
scanf("%d%d",&n,&m);

printf("输入各类资源的可分配资源数向量available:\n");
for(i=1;i<=m;i++){
scanf("%d",&available[i]);
}
printf("输入各个进程所需最大资源数量(矩阵max:行为进程,列为资源量):\n");
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%d",&max[i][j]);
}
}
printf("输入各个进程已分配的各类资源的数量(矩阵allocation:行为进程,列为资源量):\n");
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%d",&allocation[i][j]);
}
}
printf("输入各个进程还需要各类资源的数量(矩阵need:行为进程,列为资源量):\n");
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%d",&need[i][j]);
}
}
int work[M];
printf("\n\n输出系统当前时刻的可利用资源向量:\n");
for(j=1;j<=m;j++){
work[j]=available[j];
printf("%d ",available[j]);
}
printf("\n");
printf("输出当前时刻n个进程的还需要资源矩阵\n");
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
printf("%d ",need[i][j]);
}
printf("\n");
}
for(j=1;j<=m;j++){
work[j]=available[j];
}
all_security(work,1,s);
if(flag_security){
printf("\n此刻t0处于安全状态!\n\n");
} else{
printf("\n此刻t0处于不安全状态,接下来可能会发生死锁!程序关闭\n\n");
return 0;
}

printf("请输入请求进程标志pid(0~n-1):\n");
while(~scanf("%d",&pid)){
printf("请输入请求进程%d的资源请求向量:\n",pid);
for(i=1;i<=m;i++){
scanf("%d",&request[i]);
}
printf("输出系统当前时刻的可利用资源向量:\n");
for(j=1;j<=m;j++){
work[j]=available[j];
printf("%d ",available[j]);
}
printf("\n\n");
printf("输出当前时刻n个进程的还需要资源矩阵\n");
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
printf("%d",need[i][j]);
}
printf("\n");
}
int flag_request=bank(pid+1,request);
if(flag_request){
printf("进程%d请求资源成功!\n\n",pid);
}else{
printf("进程%d请求资源失败!\n\n",pid);
}
printf("请输入进程标志pid(0~n-1):\n");
}
return 0;
}