«1. Введение

В этом уроке мы рассмотрим несколько способов печати треугольника в Java.

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

2. Построение прямоугольного треугольника

Прямоугольный треугольник — самый простой тип треугольника, который мы будем изучать. Давайте быстро взглянем на результат, который мы хотим получить: 

*
**
***
****
*****

Здесь мы замечаем, что треугольник состоит из 5 строк, каждая из которых имеет количество звездочек, равное номеру текущей строки. Конечно, это наблюдение можно обобщить: для каждой строки от 1 до N нужно вывести r звездочек, где r — текущая строка, а N — общее количество строк.

Итак, давайте построим треугольник, используя два цикла for: 

public static String printARightTriangle(int N) {
    StringBuilder result = new StringBuilder();
    for (int r = 1; r <= N; r++) {
        for (int j = 1; j <= r; j++) {
            result.append("*");
        }
        result.append(System.lineSeparator());
    }
    return result.toString();
}

3. Построение равнобедренного треугольника

Теперь давайте посмотрим на форму равнобедренного треугольника: 

    *
   ***
  *****
 *******
*********

Что мы видим в этом случае? Мы замечаем, что помимо звездочек нам также нужно печатать пробелы для каждой строки. Итак, нам нужно выяснить, сколько пробелов и звезд мы должны напечатать для каждой строки. Разумеется, количество пробелов и звездочек зависит от текущей строки.

Во-первых, мы видим, что нам нужно напечатать 4 пробела для первой строки, и по мере того, как мы спускаемся по треугольнику, нам нужно 3 пробела, 2 пробела, 1 пробел и вообще никаких пробелов для последней строки. Обобщая, нам нужно вывести N – r пробелов для каждой строки.

Во-вторых, сравнивая с первым примером, мы понимаем, что здесь нам нужно нечетное количество звезд: 1, 3, 5, 7…

Итак, нам нужно вывести rx 2 – 1 звезд для каждой ряд.

3.1. Использование вложенных циклов for

Основываясь на приведенных выше наблюдениях, давайте создадим наш второй пример: 

public static String printAnIsoscelesTriangle(int N) {
    StringBuilder result = new StringBuilder();
    for (int r = 1; r <= N; r++) {
        for (int sp = 1; sp <= N - r; sp++) {
            result.append(" ");
        }
        for (int c = 1; c <= (r * 2) - 1; c++) {
            result.append("*");
        }
        result.append(System.lineSeparator());
    }
    return result.toString();
}

3.2. Использование одного цикла for

На самом деле, у нас есть другой способ, состоящий только из одного цикла for — он использует библиотеку Apache Commons Lang 3.

Мы собираемся использовать цикл for для перебора строк треугольника, как мы это делали в предыдущих примерах. Затем мы воспользуемся методом StringUtils.repeat(), чтобы сгенерировать необходимые символы для каждой строки: 

public static String printAnIsoscelesTriangleUsingStringUtils(int N) {
    StringBuilder result = new StringBuilder();

    for (int r = 1; r <= N; r++) {
        result.append(StringUtils.repeat(' ', N - r));
        result.append(StringUtils.repeat('*', 2 * r - 1));
        result.append(System.lineSeparator());
    }
    return result.toString();
}

Или мы можем проделать хитрый трюк с методом substring().

Мы можем извлечь приведенные выше методы StringUtils.repeat() для создания вспомогательной строки, а затем применить к ней метод String.substring(). Вспомогательная строка представляет собой конкатенацию максимального количества пробелов и максимального количества звездочек, которые нам нужны для печати строк треугольника.

Глядя на предыдущие примеры, мы замечаем, что нам нужно максимальное количество N – 1 пробелов для первой строки и максимальное количество N x 2 – 1 звездочек для последней строки: 

String helperString = StringUtils.repeat(' ', N - 1) + StringUtils.repeat('*', N * 2 - 1);
// for N = 10, helperString = "    *********"

~ ~~ Например, когда N = 5 и r = 3, нам нужно напечатать « ***** », которое включено в переменную helperString. Все, что нам нужно сделать, это найти правильную формулу для метода substring().

Теперь давайте посмотрим полный пример: 

public static String printAnIsoscelesTriangleUsingSubstring(int N) {
    StringBuilder result = new StringBuilder();
    String helperString = StringUtils.repeat(' ', N - 1) + StringUtils.repeat('*', N * 2 - 1);

    for (int r = 0; r < N; r++) {
        result.append(helperString.substring(r, N + 2 * r));
        result.append(System.lineSeparator());
    }
    return result.toString();
}

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

4. Сложность

Если мы снова взглянем на первый пример, мы заметим внешний цикл и внутренний цикл, каждый из которых имеет максимум N шагов. Следовательно, у нас есть временная сложность O(N^2), где N — количество строк треугольника.

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

В третьем примере, однако, используется только цикл for с N шагами. Но на каждом этапе мы вызываем либо метод StringUtils.repeat(), либо метод substring() вспомогательной строки, каждый из которых имеет сложность O(N). Таким образом, общая временная сложность остается прежней.

Наконец, если мы говорим о вспомогательном пространстве, мы можем быстро понять, что для всех примеров сложность остается в переменной StringBuilder. Добавляя весь треугольник к переменной результата, мы не можем иметь сложность меньше, чем O (N ^ 2).

Конечно, если бы мы печатали символы напрямую, у нас была бы постоянная пространственная сложность для первых двух примеров. Но в третьем примере используется вспомогательная строка, а пространственная сложность будет O(N).

«5. Заключение

В этом уроке мы научились печатать два распространенных типа треугольников в Java.

Во-первых, мы изучили прямоугольный треугольник — самый простой тип треугольника, который мы можем напечатать в Java. Затем мы изучили два способа построения равнобедренного треугольника. Первый использует только циклы for, а второй использует методы StringUtils.repeat() и String.substring() и помогает нам писать меньше кода.

Наконец, мы проанализировали временную и пространственную сложность для каждого примера.

Как всегда, все примеры можно найти на GitHub.