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 .