Задача рисования меток на линейке.

Рассмотрим простую задачу рисования меток на линейке. Каждые ½ дюйма на линейке отмечаются черточкой, каждые ¼ дюйма отмечаются несколько более короткими черточками, 1/8 дюйма – еще более короткими и т. д. Задача состоит в создании программы для рисования этих меток при любом заданном разрешении, при условии, что в нашем распоряжении имеется функция Mark(x,h) для рисования меток высотой h условных единиц в позиции x.

Если требуемое разрешение равно (1/2) ^nдюймов, изменим масштаб, чтобы задача состояла в помещении метки в каждой точке в интервале от 0

До 2^n, за исключением конечных точек. Таким образом, средняя метка должна иметь высоту n условных единиц, метки в середине левой и правой половин должны иметь высоту n-1 условных единиц и т. д. Функция Ruleв примере 2 и использующаяся в программе 2 – простой алгоритм «разделяй и властвуй» для выполнения этой задачи.

Пример 2:

-------------------------------------------------------------------------------------------------------

void Rule (int l, int r, int h)//заголовок ф-ии

{//l-условная абсцисса левой границы линейки

// r-условная абсцисса правой границы линейки 2

// h-высота самой длинной метки

void Mark (int, int);//прототип ф-ии рисования меток

int m=(l+r)/2;//делим линейку пополам

if (h>0)//если высота метки не нулевая, то

{

Rule(l,m,h-1);//вызов ф-ии из самой себя (рекурсия), //сначала работаем в левой части линейки

Mark(m,h);//вызов ф-ии рисования метки

Rule(m,r,h-1);//вызов ф-ии из самой себя (рекурсия), //потом работаем в правой части линейки

}

}

Для рисования меток на линейке мы рисуем метки в левой половине, затем самую длинную метку в середине, а затем метки в правой половине. Эта функция предназначена для использования со значением r-1 равным степени 2 – свойство, сохраняемое в ее рекурсивных вызовах.

-------------------------------------------------------------------------------------------------------

Работа данного алгоритма применительно к небольшому примеру проиллюстрирована на рисунке 3. С точки зрения рекурсии в основе метода лежит следующая идея. Для помещения меток на интервале, последний вначале делится на две половины. Затем создаются метки (более короткие) в левой половине (рекурсивно), помещается длинная метка в середине и рисуются метки (более короткие) в правой половине (рекурсивно). Если говорить об итерации, рисунок 3 иллюстрирует, что с помощью этого метода метки создаются по порядку, слева направо – фокус заключается в вычислении длин интервалов. Дерево рекурсии, приведенное на рисунке, помогает понять вычисление: просматривая его сверху вниз, мы видим, что длина меток уменьшается на 1 для каждого вызова рекурсивной функции. Если просматривать дерево в поперечном направлении, мы получаем метки в том порядке, в каком они рисуются, поскольку для каждого данного узла вначале рисуются метки, связанные с вызовом функции слева, затем метка, связанная с данным узлом, а затем метки, связанные с вызовом функции справа.

Рисунок 3:

-------------------------------------------------------------------------------------------------------