Рекурсия в примерах на Visual C++

В этой статье содержится два примера реализации рекурсивных алгоритмов в программном коде на Visual C++. В первом примере показан алгоритм решения задачи о Ханойской башне. Второй пример графически изображает так называемый «Треугольник Серпинского» — одна из разновидностей фракталов, названная по имени его создателя - польского математика Вацлава Серпинского.

Задача о Ханойской башне

Эта задача известна ещё с древних времён, и суть её состоит в следующем: Имеется три стержня, на один из которых насажены диски разных диаметров. Диаметры дисков упорядочены по убыванию, т. е. в самом низу находится диск с наибольшим диаметром, а у каждого последующего диска диаметр меньше предыдущего. Необходимо поочерёдно переставить диски с одного стержня на другой, используя третий стержень как промежуточный. При этом обязательно должно соблюдаться условие, чтобы диски с диаметром большего размера не располагались над дисками с меньшим диаметром.

Посмотреть видео...

Эта задача решается с помощью рекурсии. Кратко этот алгоритм можно описать следующим образом: для перемещения каждого нижестоящего диска нужно сначала переместитьна пустой стержень все вышестоящие диски. Потом переставить очередной диск и сверху на него переместить все вышестоящие диски. Стержень с исходными дисками можно использовать как промежуточный. Вот как это реализовано в виде консольного приложения на Visual C++

#include "stdafx.h"

 

void HanoyTown(int nLevel, char from, char to, char mid)

{

	if (nLevel > 0)

	{

		HanoyTown(nLevel-1, from, mid, to);

		_tprintf(_T("%c ==> %c\n"), from, to);

		HanoyTown(nLevel-1, mid, to, from);

	}

}

 

int _tmain(int argc, _TCHAR* argv[])

{

	HanoyTown(3, 'A', 'B', 'C');

	return 0;

}

В данном примере стержни обозначены буквами A, B и C.Для пирамиды из 3 дисков сценарий их перемещения будет таковым:

A ==> B

A ==> C

B ==> C

A ==> B

C ==> A

C ==> B

A ==> B

А при количестве дисков равном 4, последовательность перестановок будет выглядеть так:

A ==> C
A ==> B
C ==> B
A ==> C
B ==> A
B ==> C
A ==> C
A ==> B
C ==> B
C ==> A
B ==> A
C ==> B
A ==> C
A ==> B
C ==> B

Весь код проекта с данным примером можно загрузить отсюда:

Треугольник Серпинского

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

Так выглядит это изображение в данном примере

Треугольник Серпинского (увеличить)

Рекурсивный алгоритм генерации такой мозайки в примере на Visual C++ реализован в виде функции:

void DrawSerpinskyCover(HDC hdc, int nLevel, int nX, int nY)

{

	if (nLevel > 0)

	{

		int nOffset = 1 << (nLevel-1);

		DrawSerpinskyCover(hdc, nLevel-1, nX, nY);

		DrawSerpinskyCover(hdc, nLevel-1, nX + nOffset, nY);

		DrawSerpinskyCover(hdc, nLevel-1, nX, nY + nOffset);

	} else

	{

		if (hdc != NULL)

		{

			int nLeft = nY * 3 + nX * 6 + 20;

			int nTop = nY * 5 + 20;

			RECT rc = {nLeft, nTop, nLeft+5, nTop+5};

			HBRUSH hBrush = (HBRUSH)::GetStockObject(BLACK_BRUSH);

			::FillRect(hdc, &rc, hBrush);

		}

	}

}

Эта функция вызывается в момент перерисовки окна приложения (оконное сообщение WM_PAINT)

		case WM_PAINT:

			{

				PAINTSTRUCT ps;

				HDC hdc = BeginPaint(hWnd, &ps);

				DrawSerpinskyCover(hdc, 7, 0, 0);

				EndPaint(hWnd, &ps);

			}

			break;

Весь проект с полным кодом данного примера можно загрузить отсюда: