Ce n'est pas une question de devoirs, en fait je le fais pour m'amuser.Faire une "classe parfaite"
Voici le problème:
J'ai une salle de classe avec une « largeur » spécifiée (chaises), et je dois placer tous les étudiants donc il n'y a pas de conversation dans la salle de classe.
Il y a une conversation si un élève est à côté de l'autre. (Diagonales comptent)
Pour cet exemple, la largeur de la salle de classe est de 3. Disons que nous avons quelques étudiants: Matheus, Gabriel et Ravi, ils se parlent tous, maintenant nous avons les autres étudiants, A, B, C, D, E, F.
Une solution pour le problème ci-dessus serait:
|---------|--------|---------|
| Gabriel | A | Matheus |
|---------|--------|---------|
| B | C | D |
|---------|--------|---------|
| Ravi | E | F |
|---------|--------|---------|
Mon code actuel est, mais pour une raison quelconque, il bloque le navigateur (boucle infinie):
/*
Class Classroom
*/
function Classroom($width){
$width=$width||6;
var self=this;
var alunos=[];
self.addClassmate=function($classmate){
alunos.push($classmate);
}
self.createClassroom=function(){
var mapa=[];
var width=$width;
var height=Math.ceil(alunos.length/width);
for(var i=0;i<width;++i){
mapa[i]=[];
}
// Shuffle the array
alunos.sort(function(a,b){
return 0.5 - Math.random();
});
var i=0;
var px=width;
var py=height;
// Fill the array
while(px--){
while(py--){
if(i<alunos.length){
mapa[px][py]=alunos[i];
}else{
mapa[px][py]=new Student('---');
}
++i;
}
py=height;
}
function changePosition(px,py){
var dx=Math.floor(Math.random()*width);
var dy=Math.floor(Math.random()*height);
var me=mapa[px][py];
var other=mapa[dx][dy];
mapa[dx][dy]=me;
mapa[px][py]=other;
alert('lol');
checkChairs();
}
// DO IT
function checkChairs(){
for(var px=0;px<width;++px){
for(var py=0;py<height;++py){
var me=mapa[px][py];
var leftCorner = px==0;
var rightCorner = px==width-1;
var topCorner = py==0;
var bottomCorner = py==height-1;
if(!leftCorner){
if(mapa[px-1][py].hasRelationWith(me)){
changePosition(px,py);
return;
}
if(!topCorner){
if(mapa[px-1][py-1].hasRelationWith(me)){
changePosition(px,py);
return;
}
}
if(!bottomCorner){
if(mapa[px-1][py+1].hasRelationWith(me)){
return;
}
}
}
if(!rightCorner){
if(mapa[px+1][py].hasRelationWith(me)){
changePosition(px,py);
return;
}
if(!topCorner){
if(mapa[px+1][py-1].hasRelationWith(me)){
changePosition(px,py);
return;
}
}
if(!bottomCorner){
if(mapa[px+1][py+1].hasRelationWith(me)){
changePosition(px,py);
return;
}
}
}
if(!topCorner){
if(mapa[px][py-1].hasRelationWith(me)){
changePosition(px,py);
return;
}
}
if(!bottomCorner){
if(mapa[px][py+1].hasRelationWith(me)){
changePosition(px,py);
return;
}
}
}
}
}
checkChairs();
return mapa;
}
}
/*
Class Student
*/
function Student($name){
var self=this;
var name=$name;
var relation=[];
self.addRelationWith=function($classmate,$mutual){
$mutual=$mutual||true;
if(self.hasRelationWith($classmate)) return;
relation.push($classmate);
if($mutual){
$classmate.addRelationWith(self, false);
}
}
self.hasRelationWith=function($classmate){
var i=relation.length;
while(i--){
if(relation[i]==$classmate){
return true;
}
}
return false;
}
self.getName=function(){
return name;
}
self.toString=function(){
return '[Student '+self.getName()+']';
}
}
var s=new Classroom(3);
var Matheus=new Student('Matheus');
var Gabriel=new Student('Gabriel');
var Ravi=new Student('Ravi');
Matheus.addRelationWith(Gabriel);
Matheus.addRelationWith(Ravi);
Gabriel.addRelationWith(Ravi);
s.addClassmate(Matheus);
s.addClassmate(Gabriel);
s.addClassmate(Ravi);
s.addClassmate('A');
s.addClassmate('B');
s.addClassmate('C');
s.addClassmate('D');
s.addClassmate('E');
s.addClassmate('F');
alert(s.createClassroom());
(L'exemple que j'ai donné dans ce message est à la fin du code)
Puis-je suggérer un autre algorithme? Tout d'abord, placez un élève dans un coin (un endroit avec seulement trois voisins, en comptant la diagonale). Ensuite, marquez tous les sièges "à côté" de l'étudiant comme remplis. Maintenant, placez un élève dans un autre "coin" des sièges non remplis. Si aucun coin n'est disponible, choisissez un endroit avec le nombre minimal de voisins. Répétez jusqu'à ce que tous les élèves ont été placés. – Borealid
Bonne idée, je vais mettre en œuvre cet algorithme quand j'ai le temps, merci! –