Печать отношений между членами

Question

Печать отношений между членами

У меня есть университетский проект, в котором я должен напечатать отношения между студентами в разных классах уровень за уровнем. Идея в том, что если Джон и Крис учатся в одном классе, они друзья первого уровня, если Крис учится с Матем в одном классе, то Джон и Мат — друзья второго уровня. Я исследовал проблему и нашел такие алгоритмы, как этот, но моя главная проблема заключается в том, что я использую объекты в качестве входных данных:

<?php
class Student {

private $id = null;
private $classes = [];

public function __construct($id) {
$this->id = $id;
}

public function getId() {
return $this->id;
}

public function getClasses() {
return $this->classes;
}

public function addClass(UClass $class) {
array_push($this->classes, $class);
}

}

class UClass {

private $id = null;
private $students= [];

public function __construct($id) {
$this->id = $id;
}

public function getId() {
return $this->id;
}

public function getStudents() {
return $this->students;
}

public function addStudent(Student $student) {
array_push($this->students, $student);
$student->addClass($this);
}

}

function getRelations(Student $start_student, &$tree = array(), $level = 2, &$visited) {
foreach ($start_student>Classes() as $class) {
foreach ($class->Students() as $student) {
if($start_student->getId() != $student->getId() && !is_int(array_search($student->getId(), $visited))) {
$tree[$level][] = $student->getId();
array_push($visited, $student->getId());
getRelations($student, $tree, $level+1, $visited);
}
}
}
}

$class = new UClass(1);
$class2 = new UClass(2);
$class3 = new UClass(3);

$student = new Student(1);
$student2 = new Student(2);
$student3 = new Student(3);
$student4 = new Student(4);
$student5 = new Student(5);
$student6 = new Student(6);

$class->addStudent($student);
$class->addStudent($student2);
$class->addStudent($student4);

$class2->addStudentr($student2);
$class2->addStudent($student4);
$class2->addStudent($student5);

$class3->addStudent($student4);
$class3->addStudent($student5);
$class3->addStudent($student6);

$tree[1][] = $student->getId();
$visited = array($student->getId());
getRelations($student, $tree, 2, $visited);
print_r($tree);

Я застрял в написании функции getRelations (), которая должна создать массив, что-то вроде

Array ( [1] => Array ( [0] => 1 ) [2] => Array ( [0] => 2 [1] => 4 ) [3] => Array ( [0] => 5 [1] => 6 ) )

но я не могу понять рекурсию правильно (или, возможно, весь алгоритм). Любая помощь будет оценена.

2

algorithm binary-tree oop php

Решение

Другие решения

Я пришел с этой функцией (не уверен, что это лучшее решение, но он работает с объектами класса)

function print_students(Student $start_student, &$tree = array(), $lvl = 1) {
if (!$start_student) {
return;
}
$tree[$lvl][] = $start_student->getId();
$q = array();
array_push($q, $start_student);
$visited = array($start_student->getId());

while (count($q)) {
$lvl++;
$lvl_students = array();
foreach ($q as $current_student) {
foreach ($current_student->getClasses() as $class) {
foreach ($class->getStudents() as $student) {
if (!is_int(array_search($student->getId(), $visited))) {
array_push($lvl_students, $student);
array_push($visited, $student->getId());
$tree[$lvl][] = $student->getId();
}
}
}
}
$q = $lvl_students;
}
}

0

Источник

Accepted Answer

Логика в вашей рекурсивной процедуре неверна. Пример:

Допустим, вы вводите процедуру для некоторого уровня А, и на самом деле есть 2 студента, которые могут найти соединение на этом уровне.

Вы справляетесь с первым, назначаете правильный уровень А, отмечаете его как «посещенный».

Затем, прежде чем перейти ко второму, вы обрабатываете уровень A + 1 для первого ученика. Где-то в его «цепочке» вы также можете найти второго ученика, который ждал, чтобы его обработали на уровне А. Однако теперь ему назначается более высокий уровень A + n, и затем он помечается как посещенный.

Затем, когда рекурсия для student1 закончена, вы продолжаете со второй. Однако его уже «посетили» …

(Кстати, я не совсем понимаю (но мой php слабый …), почему ваш первый вызов GetRelations указывает level = 2.)

В любом случае, чтобы понять вашу логику, нет необходимости в рекурсии.

Добавить свойство «уровень» для каждого студента. Поместите всех студентов также в общую коллекцию «население».

Затем для выбранного «startStudent» задайте себе уровень = 0, всем остальным студентам уровень = -1.

Итерируйте уровни и попробуйте заполнить уровни дружбы, пока не останется ничего сделать. Мой php практически не существует, поэтому я пытаюсь использовать псевдокод.

  for(int level=0; ; level++) // no terminating condition here
{
int countHandled = 0;
for each (student in population.students)
{
if (student.level==level)
{
for each (class in student.classes)
{
for each (student in class.students)
{
if(student.level==-1)
{
student.level = level+1;
countHandled++;
}
}
}
}
}
if(countHandled==0)
break;
}

Надеюсь, что это помогает вам. Конечно, вы все равно должны заполнить дерево / печатные материалы; мой вклад касается только логики правильного назначения уровней.

0