Рисуем новогоднюю ёлку с помощью Си: алгоритм номер 1.

В предыдущем посте я рассказал о задаче, которая меня вдохновила на выращивание хвойных в консоли. Так же был рассмотрен способ отрисовки равнобедренного треугольника.

Теперь пришло время нарисовать первое подобие ёлки.

Постановка задачи

Должно получиться следующее:

   _
  |      X <-------- звезда
  |      *
  |     ***
  |     ***
 10    *****
  |    ***** <------ ёлка
  |   ******* 
  |   *******
  |  *********
  |_ *********
    |----9----|

       рис.1

Всё очень просто: нужно взять за основу алгоритм отрисовки треугольника и удвоить каждую строку: 1, 1, 3, 3, 5, 5...

Высота дерева задаётся пользователем.

Дабы повысить соответствие оригиналу, я хочу поместить на верхушку ёлки "звезду". Ну, вроде тех массивных стеклянных/пластмассовых штуковин, которые часто надевают на верхушку ёлки для усиления праздничного эффекта. За звезду сойдёт английская буква "X" (см. рис.1)

Реализация

Как и в задаче отрисовки треугольника, мне потребуются два цикла - один для перехода на новую строку, другой - для отрисовки каждого ряда звёздочек. Вот первый цикл:

for(i = 0; i < height; i++) {
  // ...
}

С ним не будет особых проблем. А вот над вложенным циклом нужно подумать. Каким образом реализовать удвоение каждой строки? Посмотрим, как будет расти количество звёздочек в строке, в зависимости от номера строки. Как видно из куска кода выше, переменная i изменяется в цикле от 0 до height - 1 (о чём говорит знак "меньше").

  i | кол. звёздочек в строке
  --|------------------------
  0 | 1        X
  1 | 1        *
  2 | 3       ***
  3 | 3       ***
  4 | 5      *****
  5 | 5      *****
  6 | 7     *******
  7 | 7     *******
  8 | 9    *********
  9 | 9    *********
  ...
        рис.2

Из рисунка выше видно, что количество звёздочек увеличивается на 2 на каждой чётной строке. Это даёт подсказку, как можно реализовать алгоритм.

Здесь я хочу сделать небольшое отступление, и посмотреть внимательно на работу алгоритма отрисовки треугольника. Всё, что мне нужно - это знать половину ширины треугольника, а она равна высоте.

for(i = 1; i <= h; i++)
  for(j = 1; j <= (h + i); j++) {
    if(j <= (h - i + 1))
      putchar(' ');
    else
      putchar('*');
    putchar('\n');
  }

Начальное значение счётчиков i, j равно 1, чтобы обеспечить отступ в один дополнительный символ перед каждой строкой.

Нарисуем 3 строку треугольника (i = 3). Пусть высота h равна 5.

h + i = 8;
h - i + 1 = 3;

 |<------------- 8 ------------->|
  _______________________________
 |   |   |   | * | * | * | * | * |
  -------------------------------
             |<----- j > 3 ----->|

             рис.3

Я думаю, из рисунка 3 можно понять работу этого алгоритма.

В алгоритме отрисовки ёлки половину её ширины нужно вычислять отдельно - ведь теперь эта величина не равна высоте, как в случае с отрисовкой треугольника. Однако, не всё так уж и плохо - есть простая формула, о которой я уже говорил в предыдущем посте.

hw = h / 2 - 1          (1)

Создам новую переменную, и присвою ей результат вычисления половины ширины елки, согласно формуле 1.

Теперь вернёмся к проблеме удвоения каждой строки. Поскольку, как уже было сказано выше, количество звёздочек увеличивается на 2 на чётной строке, попробуем сделать вот что.

Я просто разделю i на 2 во всех проверках условий во вложенном цикле. Вот так:

// ...
int hw;
// ...
hw = height / 2 - 1;

for(i = 0; i < height; i++)
  /* Печатаю номер строки в обратном порядке (снизу вверх) */
  printf("%02d\t", height-i);

  for(j = 0; j <= (hw + i / 2); j++) { // <-- здесь
    if(j < (hw - i / 2)) // <-- и здесь
      putchar(' ');
    else
      if(i == 0) // или можно написать: if(!i)
        /* Рисую большую звезду на верхушке ёлки */
        putchar('X');
      else
        putchar('*');

    putchar('\n');
  }
// ...

Если строка нечётная, то hw будет увеличиваться в проверке условия завершения цикла for() и уменьшаться в условии if() - на остаток от деления, т.е. на 1. В результате, количество звёздочек в нечётной строке увеличиться на 2. Если же номер строки - чётный, то никаких изменений не происходит, просто копируется предыдущая строка.

Мне кажется, это потрясающе просто и понятно.