На вечеринке тусуется N человек, и каждый может знать или не знать другого (если A знает B, из этого не следует, что B знает A). Кто кого знает, задается матрицей NxN, в ячейке хранится соответственно 0 или 1. А еще на вечеринке может быть или не быть знаменитость. Знаменитость - это человек, который никого не знает, но его знают все. Задача - найти знаменитость, или сказать, что её нет.
Минимальное количество человек на вечеринке
Максимальное количество человек на вечеринке
Точное количество человек на вечеринке если указано занчение, то поля «минимальное» и «максимальное» не учитываются
Матрица каждый раз генерируется произвольного размера (по умолчанию, минимум - 3х3, максимум - 26х26 (это обусловлено английским алфавитом, буквы которого участвуют в наименовании строк/столбцов)). В связи с этим, вероятность, что среди «гостей» окажется знаменитость очень мала. Поэтому рекомендуется установить размерность матрицы, например, 5х5 (для наглядности) и «устроить вечеринку» несколько раз.
Принято, что строки - это субъекты (те, КТО знает кого-то), а столбцы - это объекты (те, КОГО знает кто-то).
На пересечении строки и столбца с одинаковыми индексами (например, «A») в ячейке устанавливается «1»: из условия - признак того, что человек знает, как бы, сам себя. Поэтому матрица является единичной.
Условием того, что на вечеринке присутствует знаменитость является наличие строки со всеми нулями, кроме ячейки с одинаковыми индексами (см. абзац выше), и столбца, с тем же индексом, со всеми единицами.
// задаются переменные и начальные значения
var N = Math.round(Math.random()*Nmax), // количество человек на вечеринке
people = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'], // условное обозначение людей
Nmin = 3, // минимальное количество человек
Nmax = people.length, // максимальное количество человек
NN = new Array(), // квадратная единичная матрица
i,j,ji,s; // переменные для счетчиков
// генерируется количество человек, но не меньше заданного минимума
while(N < Nmin){N = Math.round(Math.random()*Nmax);}
// случайным образом устанавливаются знакомства
for(i=0;i < N;i++){
NN[i] = new Array();
for(j=0;j < N;j++){
if(i == j){NN[i][j] = 1;}
else{NN[i][j] = Math.round(Math.random());}
}
}
// теперь знакомства проверяются (необходимо обнаружить человека,
// который никого не знает (кроме себя - математически), но его знают все)
for(i=0;i < N;i++){
s = 0;
for(j=0;j < N;j++){ // сумма чисел в строке
s = s + NN[i][j];
}
if(s == 1){ // ситуация, при которой человек никого не знает
s = 0;
for(ji=0;ji < N;ji++){ // сумма чисел в столбце
s = s + NN[ji][i];
}
if(s == N){ // ситуация, при которой человека знают все
people[i];
}
}
}
