Ханой++

[esperanto]

решение есть в журнале квант

иди в яндекс пиши квант ханойские и вперед

[Trurl]

Цитата Visitor, 15.09.03, 10:46:49

Дык дайте сам алгоритм, который без вот етих "procedure SHTRAF"

сам алгоритм: Procedure Choose_Shag

[Trurl]

Цитата esperanto, 15.09.03, 10:57:23

решение есть в журнале квант

Спасибо.

[Visitor]

Насколько я смог разобраться в ChooseShag -- да, в точности то же решение, что получилось у меня:

Отличие от "классического" только в одном: перед тем, как переместить какой-либо диск, проверяем, надо ли его вообще перемещать.

Вот еще вариант решения (массив с состояниями стержней только для того, чтобы было удобнее смотреть на состояние етой ханойской башни, вообще-то он и добрая половина кода не нужны ):

<br>#include <stdio.h><br>#include <stdlib.h><br><br>/*****************************************************************<br>* Входные данные: строка вида 1232131211131... -- номера стержней,<br>* на которые помещается очередной диск.<br>* Диски кладутся на стержни, начиная с самого большого, и<br>* заканчивая самым маленьким. Цифра строки показывает, на какой<br>* стержень класть очередной диск.<br>* Программа ищет оптимальный алгоритм перемещения всех дисков на<br>* стрежень №1<br>*****************************************************************/<br><br>int aces[3][1000];<br>int ndisks;<br><br>/*****************************************************************<br>* В массиве aces[][] хранится текущее состояние стержней (номера<br>* дисков, которые на них лежат). Самый большой диск обозначен<br>* номером 1, самый маленький -- N (число дисков).<br>* Нижнему диску на стержне соответствует первый элемент массива<br>*****************************************************************/<br><br>/* Ввод начального состояния стержней */<br>void read_initial_state();<br><br>/* Найти алгоритм перемещения диска i и всех меньших дисков на<br>стержень ato. Функция выполняет перемещение (изменяет состояние<br>aces[][]; кроме того, функция выводит на екран ето перемещение в<br>виде "(i) afrom->ato", где i -- номер диска, afrom -- номер<br>стержня, с которого перемещается диск, ato -- номер стержня, на<br>который перемещается диск */<br>void find_and_do_move(int, int);<br><br>int main(int argc, char* argv[])<br>{<br>      memset(aces, 0, sizeof(aces));<br>      read_initial_state();<br>      if(ndisks < 1)<br>      {<br>            puts("Дайте хотя бы один диск!\n");<br>            return 1;<br>      }<br>      find_and_do_move(1, 0);<br>      return 0;<br>}<br><br>void read_initial_state()<br>{<br>      char buf[1000];<br>      int *pace;<br><br>      char *pbuf = buf;<br><br>      memset(buf, 0, sizeof(buf));<br>      fgets(buf, sizeof(buf)-1, stdin);<br>      ndisks = 0;<br><br>      while(*pbuf)<br>      {<br>            if((*pbuf >= '1') && (*pbuf <= '3'))<br>            {<br>                  ndisks++;<br>                  pace = aces[*pbuf-'1'];<br>                  while(*pace) pace++;<br>                  *pace = ndisks;<br>            }<br>            pbuf++;<br>      }<br>}<br><br>void find_and_do_move(int i, int ato)<br>{<br>      int a, p;<br>      /* Найти номер стержня, на котором лежит диск №i */<br>      for(a=0; a<3; a++)<br>            for(p=0; aces[a][p] != 0; p++)<br>                  if(aces[a][p] == i) goto l_found;<br>l_found:<br><br>      /* Номер стержня в a, позиция на стержне в p */<br><br><br>      if(i == ndisks) /* Самый маленький диск сразу перемещаем */<br>      {<br>            /* Вот етот "лишний" оператор if и является отличием от<br>            "классического" решения */<br>            if(a != ato) /* Смысл: "нужно ли вообще перемещать етот диск?" */<br>            {<br>                  aces[a][p] = 0; /* Сняли диск */<br>                  for(p=0; aces[ato][p] != 0; p++); /* Нашли, куда его положить */<br>                  aces[ato][p] = i; /* И положили */<br>                  printf("(\%i) \%i->\%i\n", i, a+1, ato+1); /* И напечатали */<br>            }<br>            return;<br>      }<br><br>      /* Вот етот "лишний" оператор if и является отличием от<br>      "классического" решения */<br>      if(a != ato) /* Смысл: "нужно ли вообще перемещать етот диск?" */<br>      {<br>            /* НЕ самый маленький перемещаем более сложным способом */<br><br>            /* Сначала переместим все меньшие диски на третий стержень */<br>            find_and_do_move(i+1, 3-a-ato);<br><br>            /* Теперь перемещаем диск i */<br>            aces[a][p] = 0; /* Сняли диск */<br>            for(p=0; aces[ato][p] != 0; p++); /* Нашли, куда его положить */<br>            aces[ato][p] = i; /* И положили */<br>            printf("(\%i) \%i->\%i\n", i, a+1, ato+1); /* И напечатали */<br><br>      }<br><br>      /* Здесь диск i уже лежит на нужном месте */<br><br>      /* Теперь складываем все меньшие диски на наш диск i */<br>      find_and_do_move(i+1, ato);<br>}<br>