Гуманитарные основы комбинаторных алгоритмов - Иван Гаврюшин

Скачать книгу

стиль немного напоминает bash, но код выглядит довольно понятным:

      $x=’a’;

      $z=$a [0];

      while (1) {

      $x.=$z;

      $z=$ {$z} [0];

      if ($z == ’f’) {$x.=$z; break;}

      }

      И так, мы получили первый путь x=abdef.

      Можем вывести его на экран и заняться непосредственно самим алгоритмом, так как все, что было выше, – это только подготовительная часть. По идее от нее можно было бы избавиться, но я ее оставляю и публикую, чтобы был лучше понятен ход мысли.

      Выводим на экран первый путь и запускаем первую функцию.

      print $x;

      print '<br>»;

      search_el ($x,$a,$b,$c,$d,$e);

      Сам алгоритм фактически сводится к двум циклам, которые вынесены в отдельные функции. Первая функция принимает полученный ранее первый путь x. Далее в цикле осуществляется обход x справа налево. Мы ищем два элемента, один из которых будет работать в качестве указателя на массив, другой (правый, тут только стоит помнить, что массив перевернут) в качестве указателя на элемент массива. С помощью array_search найдем ключ элемента и проверим, есть ли что-нибудь в данном массиве после него. Если есть, то заменим элемент на найденный, но перед этим отрежем хвост (для этого нужен substr). Замену можно организовать и по другому:

      function search_el ($x, $a, $b, $c, $d, $e)

      {

      $j = strlen ($x);

      while ($j!= 0)

      {

      $j – ;

      if (isset ($ {$x [$j – 1]}))

      $key = array_search ($x [$j], $ {$x [$j – 1]}); if ($ {$x [$j – 1]} [$key +1]!= «»)

      {

      $x = substr ($x, 0, $j);

      $x.= $ {$x [$j – 1]} [$key +1];

      new_way_search ($x, $a, $b, $c, $d, $e); break;

      }

      }

      }

      Условие с isset нужно, чтобы интерпретатор не выбрасывал

      предупреждение. К самому алгоритму оно отношения не имеет. Если никаких элементов в массивах найдено не было, то алгоритм завершится, но если все-таки чудо свершилось, то переходим в новую функцию, суть которой крайне проста – дописать хвост к x, вывести на экран и… «дорисовать восьмерку» или петлю – вернуться в функцию, из которой мы пришли, но уже с новым значением x:

      function new_way_search ($x, $a, $b, $c, $d, $e)

      {

      $z = $x [strlen ($x) – 1];

      $z = $ {$z} [0];

      while (1)

      {

      $x.= $z;

      if ($x [strlen ($x) – 1] == ’f’) break;

      if ($z == ’f’)

      {

      $x.= $z;

      break;

      }

      $z = $ {$z} [0];

      }

      echo $x;

      echo '<br />»;

      search_el ($x, $a, $b, $c, $d, $e);

      }

      Результат работы алгоритма для графа, что на рисунке выше:

      abdef

      abdf

      abef

      abf

      acdef

      acdf

      acef

      acf

      adef

      adf

      Дополнение

      В качестве дополнения приведу описание полученного алгоритма более кратко: ребра ориентированного графа выписаны в отдельные массивы в порядке возрастания. Т.е. вершины графа и рёбра упорядочены. Это обязательное условие. До начала алгоритма находим первый путь, который с учетом первого условия будет с наименьшими именами вершин. Способ нахождения не особенно важен.

      Описание для проверки на бумаге

      На входе

Скачать книгу