Теория шести рукопожатий
 

Добрый день,

Подскажите пожалуйста мне нужно написать програмку типо Теории шести рукопожатий, то есть я должна создать цепь где каждое из звеньев связано с другими звеньями при чем не только в одном направлении:

друзья Kevin: Mathilde, Sophie, Aaron, Sarah
друзья Joelle: Sarah, Bob, Aaron, Louis
друзья Noah: Pascal, Julie, Mathilde
друзья Matteo: Sophie, Aaron
друзья Stephanie: Bob, Orianne
друзья Lucas: Aaron, Louis
друзья Roger: Julie
Sophie и Julie друзья
Orianne и Mathilde друзья.

Например при вводе каких нибудь двух имен програмка должна показывать связь между ними то есть:
Kevin и Pascal разделены 8 друзьями:
Kevin -> Mathilde -> Noah -> Julie -> Sophie -> Kevin -> Mathilde -> Noah -> Pascal.

структура должна быть подобна этой, при этом свойство друг это должен быть массив содержащий связь с другими друзьями:

var Maillon = function(friend1,name,friend2) {
//if (suiv === undefined)
//suiv = null;
this.name = name;
this.friend1 = friend1;
this.friend2 = friend2;

};

var Liste = function () {
this.tete = null;
this.size = 0;
this.queue = null;
};

Liste.prototype.addFirst = function(name) {
this.tete = new Maillon(name,this.tete);
if (this.size === 0)
this.queue = this.tete;
this.size++;

return this;
};

Я не знаю с чего начать как сделать что бы у каждого звена было по несколько соединений. Нужно ли мне использовать что то типа:var Kevin = new Maillon(friend1,nom,friend2);?
Подскажите пожалуйста где можно найти хоть какую нибудь информацию о том как строятся подобные звенья я нигде в интернете не нашла :(

Ох, не программист я, не знаю хитрых алгоритмов, но вот что у меня получилось:

// Конструктор человека
var Person = function (name) {
    
    var self = this;

    this.name    = name;
    this.friends = {};

    this.AddFriends = function () {
        var max = arguments.length, man;
        while (max--) {
            man = arguments[max];                // Мой друг
            self.friends[man.name] = man;        // Моя связь с другом
            man.friends[self.name] = self;        // Связь друга со мной
        }
    };
};

// Создаём людей
var Kevin     = new Person('Kevin');
var Joelle    = new Person('Joelle');
var Noah      = new Person('Noah');
var Matteo    = new Person('Matteo');
var Stephanie = new Person('Stephanie');
var Lucas     = new Person('Lucas');
var Roger     = new Person('Roger');
var Mathilde  = new Person('Mathilde');    
var Sophie    = new Person('Sophie');
var Aaron     = new Person('Aaron');
var Sarah     = new Person('Sarah');
var Bob       = new Person('Bob');
var Louis     = new Person('Louis');
var Pascal    = new Person('Pascal');
var Julie     = new Person('Julie');
var Orianne   = new Person('Orianne');

// Дружим людей
Kevin.AddFriends(Mathilde, Sophie, Aaron, Sarah);
Joelle.AddFriends(Sarah, Bob, Aaron, Louis);
Noah.AddFriends(Pascal, Julie, Mathilde);
Matteo.AddFriends(Sophie, Aaron);
Stephanie.AddFriends(Bob, Orianne);
Lucas.AddFriends(Aaron, Louis);
Roger.AddFriends(Julie);
Sophie.AddFriends(Julie);
Orianne.AddFriends(Mathilde);

// Функция проверяющая дружбу
var isFriend = function (person1, person2) {
    var viewedPerson = {};
    var chainFriends = [];

    console.log('Ищем связь между "' + person2.name + '" и "' + person1.name + '".');

    function searchFriens(person) {
        var friend;
        viewedPerson[person.name] = true;  // Запоминаем что смотрели друзей этого человека
        chainFriends.push(person.name);    // Добавим чела в цепочку связей
        // Пройдёмся по корешам
        for (var name in person.friends) {
            friend = person.friends[name];
            // Если чел не является сам собой, нужным нам челом и раньше не исследовался
            if (friend !== person1 && friend !== person2 && viewedPerson[friend.name] === undefined) {
                searchFriens(friend);    // Рекурсивный вызов
            } else if (friend === person1) {
                // Ура, это то что нам нужно
                console.log(chainFriends.join(' -> ') + ' -> ' + person1.name);
            }
        }
        chainFriends.slice(chainFriends.length - 1, 1); // Удалим чела из цепочки
    }
    
    searchFriens(person2);
};


// Найдём связь для "Kevin" и "Pascal"
isFriend(Kevin, Pascal);

В консоли получаю такое

Дзен-трансгуманист,
Интересно. Где узнал про него? Порекомендуй почитать что нибудь по алгоритмам.

Добрый день, спасибо вам большое, что помогли я бы то такого не додумалась, я только начинаю программировать, прочитала в задании что циклы использовать для поиска друзей нельзя, а чем еще можно заменить цикл?

forEach
Метод arr.forEach(callback[, thisArg]) вызывает функцию callback для каждого элемента массива.

filter
Метод arr.filter(callback[, thisArg]) создаёт новый массив, в который войдут только те элементы arr, для которых вызов callback(item, i, arr) возвратит true.

map
Метод arr.map(callback[, thisArg]) создаёт новый массив, который будет состоять из результатов вызова callback(item, i, arr) для каждого элемента arr.

every/some
Метод arr.every(callback[, thisArg]) возвращает true, если вызов callback вернёт true для каждого элемента arr.

Метод arr.some(callback[, thisArg]) возвращает true, если вызов callback вернёт true для какого-нибудь элемента arr.

reduce/reduceRight
Метод arr.reduce(reduceCallback[, initialValue]) применяет функцию reduceCallback по очереди к каждому элементу массива слева направо, сохраняя при этом промежуточный результат.


http://learn.javascript.ru/array-methods#foreach

в общем тот же цикл но реализован по другому.
В общем цикл можно заменить правильным алгоритмом, но есть задачи в которых циклы нужны по любому ( как эта), чем меньше циклов тем лучше.

а если например вводишь имя через prompt которого нет в списке как его добавить? а потом и его друзей? мне нужно вызвать функцию Person а затем Person.addFriends? для этих имен?
У меня почему то не получается ввести имена через prompt, если я их ввожу в функции isFriend то они становятся undefined.

ага, там строка по тому что, а ф-я ждёт объекты

var name  = prompt('sina pona?');
var friend = window[name];

все равно выдает ошибку: "TypeError: Cannot read property 'Kevin" of undefined"

код в студию!

Tim, строка 63 во 2 посте
в той песочнице свои законы
var viewedPerson = {};

print(viewedPerson["Kevin"]===undefined);

cannot read the undefined variable undefined


var viewedPerson = {};

print(viewedPerson["Kevin"]===void(0));

true

или ещё == null можно но не === null
в остальном ок.

рони,
print? дык это печать на принтере. мб alert?


как так то? :blink:
http://javascript.ru/undefined

Tim,
print да это типа замена алерт -- повторю с вашим кодом всё в порядке, а вот с песочницей где студентам необходимо запускать код есть вопросы - http://codeboot.org/
https://github.com/feeley/codeboot -- но это уже не к вам, просто инфа для Угумс,

http://javascript.ru/node/4119
подтверждение
http://es5.javascript.ru/x15.1.html#x15.1.1

к чему это? с какого места читать?

ну вы совсем меня уже за новичка держите :)

Добрый день, спасибо всем кто мне помогает без вас я бы ничего не сделала. :thanks:
prompt работает без проблем, но у меня есть еще один вопросик:help: не подскажите как можно сделать что бы например выводилась только самая маленькая связь и заодно считала сколько друзей их разделяет?

Например программка выводит:
Ищем связь между "Pascal" и "Kevin".

Pascal -> Noah -> Mathilde -> Kevin
Pascal -> Noah -> Mathilde -> Orianne -> Stephanie -> Bob -> Joelle -> Louis -> Lucas -> Aaron -> Kevin
Pascal -> Noah -> Mathilde -> Orianne -> Stephanie -> Bob -> Joelle -> Louis -> Lucas -> Aaron -> Matteo -> Sophie -> Kevin
Pascal -> Noah -> Mathilde -> Orianne -> Stephanie -> Bob -> Joelle -> Louis -> Lucas -> Aaron -> Matteo -> Sophie -> Julie -> Roger -> Sarah -> Kevin

а нужно, что бы выводила:
Pascal -> Noah -> Mathilde -> Kevin
Pascal и Kevin разделены двумя друзьями

Если кто знает как это делается подскажите пожалуйста очень нужно:(

Дзен-трансгуманист приводил модифицированный в соответствии с волновым алгоритмом скрипт. Он, если не ошибаюсь, как раз это и делает.

foundPath.join(' -> ') - тут мы склеиваем цепочку друзей, те массив
а свойство length - это его длина, т.е. кол-во друзей в цепочке

и да, советую изучить как работает код, иначе это палево

[quote=Tim;266202]Дзен-трансгуманист приводил модифицированный в соответствии с волновым алгоритмом скрипт. Он, если не ошибаюсь, как раз это и делает.

Боюсь, что нужно с рекурсией как Вы сделали
if (friend !== person1 && friend !== person2 && viewedPerson[friend.name] === undefined) { searchFriens(friend); // Рекурсивный вызов
но при этом чтобы одну строчку всего выводила программка:help:

это к тому, что приведённая ниже цитата была оттуда

я лишь указал на противоречие в двух разных источниках одного не малоизвестного автора ;)

хотя-я ... хм ... неиспользование возможности "Цитата выделенного" при дате регистрации 4-годичной давности заставляет задуматься :)

Я тоже всегда называю их глобальными переменными ибо к ним можно обратиться не упоминая объект в котором они находятся. Но всегда помню что это не переменные.

Я больше забочусь о том что сам о себе думаю. Но всё равно спасибо. Приятно знать что о тебе кто то думает. :)

вона куда тебя твоя фантазия понесла, её полёт становится всё более непредсказуемым :)

Надеюсь ты прав. Мне это сейчас не лишним будет.

bes,
Расскажи свою версию тогда. О чём ты там задумался.

контекст был такой:

ты говоришь
я, судя по тому, что ты не используешь возможность "цитата выделенного" (то есть очевидно ты выделяешь текст, копируешь его, вставляешь в область ввода, затем обрамляешь bb-тегами quote (как минимум, 4 действия, если, конечно, не переписываешь это всё вручную :haha: ), когда можно было выделить и нажать "цитата выделенного" (2 действия) ) отвечаю
это означает, что я задумался, что для не новичка ты выполняешь слишком много действий по созданию цитат, хотя вроде как утверждаешь, что не новичок (на такие мелочи вроде как жалко своего времени)

на что ты отвечаешь
то есть, если учесть, что ты понял контекст (очевидно, что это было не так), начинаешь фантазировать о любви к ближнему своему, вот и вся история о задумывании

как сказал один русский богатырь в не малоизвестном мультике: "я понятно объясняю?" :)

bes,
Ну так объясняй чего хочешь яснее. А то троллишь меня несколько дней уже. То undefined не работает у тебя, то ещё чего.

Да, не использую и не буду. Привык так с самого начала. Я даже не задумываюсь над этим, всё на автомате.

ну опять ты фантазируешь, где это у меня не работал undefined

ну давай на этом и завершим наш диалог, чё воду переливать из пустого в порожнее

true

ну почти всё :)
хочется ещё ответить на это
привычка не самый лучший друг в этой области ;)

возможно

Я забываю про эту хрень. Даже не понял про что ты сначала. Так что иногда легче оставить привычки чем переучиваться, тем более что профита не так много.

профит в том, что сразу становится понятно с кем ты разговариваешь (на чью реплику отвечаешь) + сообщения бывает удаляют, а цитата с указанием чья остаётся