1. Въведение
В този урок ще проучим няколко начина за отпечатване на триъгълник в Java.
Естествено има много видове триъгълници. Тук ще изследваме само няколко от тях: правоъгълен и равнобедрен триъгълник.
2. Изграждане на правоъгълен триъгълник
Правоъгълният триъгълник е най-простият тип триъгълник, който ще изучаваме. Нека да разгледаме бързо резултата, който искаме да получим:
* ** *** **** *****Тук забелязваме, че триъгълникът е направен от 5 реда, всеки от които има брой звезди, равен на номера на текущия ред. Разбира се, това наблюдение може да бъде обобщено: за всеки ред от 1 до N трябва да отпечатаме r звезди, където r е текущият ред, а N е общият брой редове.
И така, нека изградим триъгълника, като използваме две за цикли:
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. Използване на Nested for Loops
Въз основа на горните наблюдения, нека създадем втория си пример:
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 = 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. След това проучихме два начина за изграждане на равнобедрен триъгълник. Първият използва само за цикли, а другият се възползва от метода StringUtils.repeat () и String.substring () и ни помага да напишем по-малко код.
И накрая, ние анализирахме сложността във времето и пространството за всеки пример.
Както винаги, всички примери могат да бъдат намерени в GitHub.