Автор оригинала: Catalin Burcea.
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…
Итак, нам нужно напечатать r x 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
На самом деле, у нас есть другой способ, который состоит только из одного для цикла – он использует библиотеку 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 и r , нам нужно напечатать ” *****”, который включен в переменную 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 . Добавляя весь треугольник к переменной result , мы не можем иметь меньше O(N^2) сложности.
Конечно, если бы мы непосредственно печатали символы, у нас была бы постоянная сложность пространства для первых двух примеров. Но в третьем примере используется вспомогательная строка, и сложность пространства будет O(N) .
5. Заключение
В этом уроке мы узнали, как печатать два распространенных типа треугольников в Java.
Во-первых, мы изучили прямоугольный треугольник, который является самым простым типом треугольника, который мы можем напечатать на Java. Затем, мы исследовали два способа построения равнобедренного треугольника. Первый использует только для циклов, а другой использует преимущества метода StringUtils.repeat() и String.substring() и помогает нам писать меньше кода.
Наконец, мы проанализировали сложность времени и пространства для каждого примера.
Как всегда, все примеры можно найти на GitHub .