Главная » Алгоритмы » Ханойские башни

0

Имеется 3 стержня: А, В и С. На стержень А нанизано п дисков так, что диск с меньшим диаметром всегда лежит поверх диска с большим. Говоря другими словами, на стержне А пирамида из дисков, сужающаяся вверх. Требуется переместить все диски на стержень В. Стержень С можно исполь­зовать в качестве вспомогательного. Основное условие состоит в том, что диск с большим диаметром не должен находиться поверх диска с меньшим.

Как это сделать? Предположим, что мы умеем перекладывать пирамиду из n—1 дисков. Как, мы не знаем, но умеем. Тогда нам нужно переместить первые n—1 дисков с А на С. Затем перенести самое большое кольцо с А на В. Оно окажется внизу. Затем n—1 дисков нужно переместить с С на В. Го­тово. Мы только задали закон развития алгоритма. Как он будет выполнять­ся в действительности — очень любопытно посмотреть по распечатке ре­зультата. Если дисков много, задача получается очень головоломной.

#include <stdio.h>

void Ring(int n, char a, char b, char c)

{

if(n <= 0) return;

Ring(n-l,a,c,b);

printf("диск %d %c -> %c \n", n,a,b);

Ring(n-l,c,b,a); }

//основная программа

int main(void) {

Ring(3,’a’,’ b’ ,’ c’ ) ;

return 0; //код завершения программы }

Мы вызываем функцию Ring, чтобы переложить только 3 кольца. Если уве­личить это число, то процедура перекладывания будет очень замысловатой.

Директивой #include в программу включен заголовочный файл <stdio.h>. Он содержит стандартные библиотеки ввода/вывода языка С, и описание функции printf находится именно в нем. Текст программы поступит снача­ла на вход препроцессора языка С. Он просмотрит данный файл и вставит программный код файла stdio.h точно в то место, где он объявлен директи­вой #inciude. Препроцессору все равно, какой файл вставить в это место. Было бы указано его название, и был бы он на диске в доступном каталоге.

Когда код программы поступит на вход компилятора, он будет значительно больше приведенного, но это уас не волнует, в данном случае. Компилятор при трансляции кода делает один проход, поэтому он должен встретить предварительное описание функции printf перед тем, как вызов данной функции встретится в программе. Иначе компилятор не будет знать, что это за функция, и каков у нее список аргументов. Наша небольшая программа содержится в файле с расширением с. При трансляции кода компилятором получится объектный файл с расширением obj. Он должен быть связан компоновщиком (например, link) с другими объектными файлами, если они есть в проекте. В результате мы получим выполняемый файл с расши­рением ехе, который и является исполняемой программой. В нашем случае компоновщик должен будет найти библиотечный объектный файл (name.obj или name.lib) и взять оттуда сам код функции printf. В файле stdio.h содер­жится только ее предварительное (forward) описание. Мы можем и не вклю­чать файл stdio.h, а написать в начале программы:

extern printf(…);

Сигнатуру функции printf можно посмотреть в вашем файле stdio.h. Это обычный текстовый файл. Сигнатура функции printf непростая, и лучше оставить все это на совести разработчиков компилятора.

В проекте может быть несколько файлов с расширением с. Компилятор для каждого создаст свой объектный файл. Единственное, что нужно помнить, что это функция main является точкой начала исполнения программы, и она должна быть одна в каком-либо файле. В каком — безразлично.

Зачем нужно много файлов? Это очень удобно. Некоторые файлы могут со­держать пользовательские библиотечные функции, и их можно включать в разные проекты. Как вызвать из одного файла функцию, содержащуюся в другом? Для этого нужно воспользоваться директивой extern. Если мы хо­тим ограничить область видимости некоторой функции одним файлом (или переменной), мы должны перед ее сигнатурой написать ключевое слово static. В нашем примере функция Ring и основная функция main были в одном файле. Давайте поместим функцию Ring в отдельный файл. Тогда основной файл программы будет содержать только функцию main. Перед использованием функции Ring нужно написать:

extern Ring(int n,char a, char b, char с);

Когда компилятор встретит это описание, он ничего не будет знать об уст­ройстве функции Ring, потому что каждый файл компилируется отдельно. Он будет только знать сигнатуру данной функции, чтобы осуществить ее вызов. При этом компилятору не важны названия аргументов, важен их тип и порядок. Мы могли бы написать:

extern Rint(int,char,char,char);

Компоновщик после компиляции установит необходимые связи. Если он не найдет функцию Ring ни в одном файле проекта, он сообщит об ошибке компоновки. Директива extern может использоваться и для объявления внешних переменных. Мы можем написать в одном файле:

extern int dummy;

А сама переменная dummy будет находиться в другом файле.

int dummy = 0;

Каждый раз использовать директиву extern не всегда удобно. У нас может быть большой проект и много файлов. Мы можем собрать все внешние объявления (extern) в одном или нескольких файлах с расширением h и включить их директивой #include. Давайте создадим для нашего случая простой файл (*.h) и включим туда описание внешней функции Ring.

//файл MyHeader.h #idndef MY HEADER

#define MY_HEADER

extern Ring(int,char,char,char);

#endif

Файл main.c тогда будет выглядеть так:

#include "MyHeader.h"

int main(void) {

Ring (3,’ a’,’ b’,’ c’) ;

return 0;

}

Сама функция Ring будет находиться в третьем файле с расширением с, на­звание которого совершенно не важно. Обратите внимание, что в файле MyHeader.h содержится только описание функции Ring. В каком она фай­ле — не указано. В одном из файлов проекта. Директиву extern можно опустить для описания внешней функции в файле (*.h). Это подразумевает­ся. В языке С значком # начинаются директивы препроцессора. Это не компилятор, это отдельная программа, которая совершает предварительную обработку текста программы. Компилятор не встретит в программе уже ни одной директивы, начинающейся значком #. В нашем файле MyHeader.h есть несколько директив препроцессора. Их можно опустить, и тогда файл будет выглядеть:

///////////////////////////////////

void Foo(int,char,char,char);

///////////////////////////////////

Зачем они нужны? Дело в том, что данный файл может быть включен в текст программы несколько раз. Как это может быть? Допустим, у нас не­сколько заголовочных файлов (*.h). В один файл может быть включен дру­гой заголовочный файл, а потом оба, по ошибке, включены в третий заго­ловочный файл. Это происходит довольно часто. Как этого избежать? Для этого мы используем директиву препроцессора, проверяющую условие. Она аналогична оператору if языка программирования, только пишется #if, например:

?    директива #ifdef — если определена;

?    директива #ifndef — если не определена;

?    директива #define вводит константу (символическое имя препроцессора). В нашем случае мы написали:

#define MY HEADER my_header — это вымышленное символическое имя препроцессора. Если файл MyHeader.h был включен препроцессором хоть один раз при трансля­ции кода для конкретного файла, то это имя препроцессор запомнил. Если встретится повторное включение файла MyHeader.h, то препроцессор про­верит условие:

iifndef MY_HEADER

Так как оно ложно, весь текст до директивы #endif будет пропущен, и по­вторного включения файла MyHeader.h не произойдет. Мы должны пони­мать, что препроцессору все равно, что включать и сколько раз. Если мы напишем 10 раз #inciude "MyHeader.h" и не примем мер, то препроцессор включит этот файл 10 раз в место, указанное директивой #inciude. Ошибку выдаст компилятор. Он 10 раз встретит предварительное описание функции Ring и откажется дальше компилировать. Если разобраться, в этом нет ни­чего сложного. Это обычные макросы. Нам может быть неудобно много раз выписывать один и тот же код, и мы можем его оформить в виде макроса. Потом в тексте программы, вместо того чтобы нудно выписывать одно и то же, мы можем просто написать имя макроса, и препроцессор расширит его нужным кодом. Например, у нас есть массив из 10-ти чисел, и нам нужно его много раз обнулять или присваивать какие-либо значения. Мы можем написать один раз макрос, а потом использовать в программе имя макроса, например:

//инициализация массива data[10]

#define INIT_ARRAY \

data[0] = 1; data[l] = 2;\ data[3] = 4;   data[9] = 512;

Содержимое файла (*.h) вставляется точно так же препроцессором, и мы должны написать в этом файле то, что хотим видеть в этом месте програм­мы. Как некоторый рекурсивный казус, мы можем включить в файл MyHeader.h в самом конце сам этот файл #include "MyHeader.h". Что про­изойдет? Конечно, препроцессор должен заметить ошибку, иначе он будет расширять файл MeHeader.h самим собой, пока хватит памяти, или впадет в бесконечный цикл.

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии