Форум на Исходниках.RU

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