//配属問題2「安定結婚問題の配属シミュレーション」
// 配属問題の部分プログラムNo4「学生ランキング」〜ゼミの学生に対する順位付け
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define Znum 15
#define Snum 150
#define N 1000
struct student
{
int
studentnum;
int
Srandnum;
};
struct zemi
{
int
zeminum;
int
randnum;
};
int main()
{
struct
student B[Snum],tempB;
struct
zemi A[Znum] , tempA;
int
ZR[Znum][Snum],SR[Snum][Znum];
int
D[Snum][Snum],H[Snum][Snum];
int
i,j,n,r,c,h,k,x;
int
RH[Snum][Snum],RD[Snum][Snum];
int P[Snum],SAI[Snum],HDi[Snum];
int
Slist[Snum],Zlist[5];
//Slist[i]は第i希望に所属する学生の人数のカウンタ
//Zlist[i]はゼミにとって所属した学生はどのくらい好ましい人数は何人かを表すカウンタ
//iが小さいほど好ましい学生
for(i=0;i<Snum;i++)Slist[i]=0;
for(i=0;i<5;i++)Zlist[i]=0;
int
onoff;
//乱数データをN回発生させ、シミュレーションを行う。
for(x=0;x<N;x++)
{
for(i=0;i<Snum;i++) {P[i]=Snum;SAI[i]=0;HDi[i]=0;}
for(i=0;i<Snum;i++)
{
for(j=0;j<Snum;j++)
{
RH[i][j]=0;RD[i][j]=0;
}
}
//分野1
for
(i=0;i<5;i++)
{
for
(j=0;j<Snum;j++)
{
B[j].studentnum
= j;
if(j<35)
B[j].Srandnum = rand()%200;
else
if(j<70) B[j].Srandnum = rand()%100;
else
if(j<105) B[j].Srandnum = rand()%50;
else
B[j].Srandnum = 0;
}
//BをB[j].Srandnumについて大きい順に並べ替え
for(j=0;j<Snum-1;j++)
{
for(n=j+1;n<Snum;n++)
{
if(B[j].Srandnum
< B[n].Srandnum)
{tempB=B[n];B[n]=B[j];B[j]=tempB;}
}
}
//配列ZRを作成
for(n=0;n<Snum;n++)
{
ZR[i][n]=B[n].studentnum;
}
}
//分野2
for
(i=5;i<10;i++)
{
for
(j=0;j<Snum;j++)
{
B[j].studentnum
= j;
if(j<35)
B[j].Srandnum = rand()%200;
else
if(j<70) B[j].Srandnum =
rand()%100;
else
if(j<105) B[j].Srandnum = rand()%50;
else
B[j].Srandnum = 0;
}
//BをB[j].Srandnumについて大きい順に並べ替え
for(j=0;j<Snum-1;j++)
{
for(n=j+1;n<Snum;n++)
{
if(B[j].Srandnum
< B[n].Srandnum)
{tempB=B[n];B[n]=B[j];B[j]=tempB;}
}
}
//配列ZRを作成
for(n=0;n<Snum;n++)
{
ZR[i][n]=B[n].studentnum;
}
}
//分野3
for
(i=10;i<Znum;i++)
{
for
(j=0;j<Snum;j++)
{
B[j].studentnum
= j;
if(j<35)
B[j].Srandnum = rand()%200;
else
if(j<70) B[j].Srandnum =
rand()%100;
else
if(j<105) B[j].Srandnum = rand()%50;
else
B[j].Srandnum = 0;
}
//BをB[j].Srandnumについて大きい順に並べ替え
for(j=0;j<Snum-1;j++)
{
for(n=j+1;n<Snum;n++)
{
if(B[j].Srandnum
< B[n].Srandnum)
{tempB=B[n];B[n]=B[j];B[j]=tempB;}
}
}
//配列ZRを作成
for(n=0;n<Snum;n++)
{
ZR[i][n]=B[n].studentnum;
}
}
//150*150の配列Dに拡張
for(j=0;j<Znum;j++)
{
for(i=0;i<Snum;i++)
{
for(n=j*10;n<j*10+10;n++)
{
D[n][i]
= ZR[j][i];
}
}
}
//配属問題部分プログラムNo3「ゼミランキング」〜学生のゼミに対する順位付け
//学籍番号0〜34番について、
//パターン1
for
(i=0;i<35;i++)
{
for
(j=0;j<Znum;j++)
{
A[j].zeminum
= j;
if(j<5)
A[j].randnum = rand()%100;
else
if(j<10) A[j].randnum = rand()%100;
else A[j].randnum
= rand()%100;
}
//AをA[j]->randnumについて大きい順に並べ替え
for(j=0;j<Znum-1;j++)
{
for(n=j+1;n<Znum;n++)
{
if(A[j].randnum
< A[n].randnum)
{tempA=A[n];A[n]=A[j];A[j]=tempA;}
}
//配列SRを作成
for(n=0;n<Znum;n++)
SR[i][n]=A[n].zeminum;
}
}
//学籍番号35〜69番について、
//パターン2
for
(i=35;i<70;i++)
{
for
(j=0;j<Znum;j++)
{
A[j].zeminum
= j;
if
(j<5)
A[j].randnum = rand()%100;
else
if(j<10) A[j].randnum =
rand()%100;
else A[j].randnum
= rand()%100;
}
//AをA[j]->randnumについて大きい順に並べ替え
for(j=0;j<Znum-1;j++)
{
for(n=j+1;n<Znum;n++)
{
if(A[j].randnum
< A[n].randnum)
{tempA=A[n];A[n]=A[j];A[j]=tempA;}
}
//配列SRを作成
for(n=0;n<Znum;n++)
SR[i][n]=A[n].zeminum;
}
}
//学籍番号70〜104番について、
//パターン3
for
(i=70;i<105;i++)
{
for
(j=0;j<Znum;j++)
{
A[j].zeminum
= j;
if(j<5) A[j].randnum =
rand()%100;
else
if(j<10) A[j].randnum = rand()%100;
else A[j].randnum
= rand()%100;
}
//AをA[j]->randnumについて大きい順に並べ替え
for(j=0;j<Znum-1;j++)
{
for(n=j+1;n<Znum;n++)
{
if(A[j].randnum
< A[n].randnum)
{tempA=A[n];A[n]=A[j];A[j]=tempA;}
}
//配列SRを作成
for(n=0;n<Znum;n++)
SR[i][n]=A[n].zeminum;
}
}
//学籍番号105〜150番(ダミー学生)について、
for
(i=105;i<Snum;i++)
{
for
(j=0;j<Znum;j++) A[j].zeminum = j;
//配列SRを作成
for(n=0;n<Znum;n++) SR[i][n]=A[n].zeminum;
}
//150*150の配列Hに拡張する
for(i=0;i<Snum;i++)
{
for(j=0;j<Znum;j++)
{
//定員は10人とする
r
= 0;
for(n=j*10;n<j*10+10;n++)
{
H[i][n]=SR[i][j]*10+r;
r=r+1;
}
}
}
//配属問題部分プログラムNo2「Gale-Shapleyアルゴリズム」〜安定結婚問題アルゴリズム
/*テーブルRH,RDの作成*/
for
(n=0;n<Snum;n++)
{
for
(r=0;r<Snum;r++)
{
RH[n][H[n][r]]
= r;
}
}
for (n=0;n<Snum;n++)
{
for (r=0;r<Snum;r++)
{
RD[n][D[n][r]] = r;
}
}
/*Gale-Shapleyのアルゴリズム*/
for (c=0;c<Snum;c++){
n=0;
h=c;
onoff=0;
while
(onoff == 0){
if(RD[H[h][n]][h] < P[H[h][n]]){
if(P[H[h][n]] == Snum){
P[H[h][n]]
= RD[H[h][n]][h];
onoff = 1;
}
else{
k
=
D[H[h][n]][P[H[h][n]]];
P[H[h][n]] = RD[H[h][n]][h];
n =
RH[k][H[h][n]] + 1;
h = k;
}
}
else{
n=n+1;
}
}
}
//学生はゼミ(ペア)を何番目に好きか?の統計
for(i=0;i<Snum;i++)
{
if(D[i][P[i]]<105) Slist[RH[D[i][P[i]]][i]]
= Slist[RH[D[i][P[i]]][i]] +1;
}
//ゼミはどのくらい好ましい学生を得たかの統計
for(i=0;i<Snum;i++)
{
if(D[i][P[i]]<105)
{
if(RH[D[i][P[i]]][i]<21)
Zlist[0]= Zlist[0] +1;
else
if(RH[D[i][P[i]]][i]<42) Zlist[1] = Zlist[1]+1;
else
if(RH[D[i][P[i]]][i]<63) Zlist[2] = Zlist[2]+1;
else
if(RH[D[i][P[i]]][i]<94) Zlist[3] = Zlist[3]+1;
else Zlist[4]=Zlist[4]+1;
}
}
}
//ゼミを一つのイメージにする
for(i=0;i<Znum;i++)
{
n=0;
for(j=i*10;j<i*10+10;j++) n = n + Slist[j];
printf("%d希望の総数は%d\n,",i+1,n);
}
for(i=0;i<5;i++) printf("ランク%dの学生数->%d人\n",i+1,Zlist[i]);
return 0;
}