streamalism.org

1. Úvod

V tomto výučbe preskúmame niekoľko spôsobov, ako tlačiť trojuholník v prostredí Java.

Existuje samozrejme veľa druhov trojuholníkov. Tu, preskúmame iba pár z nich: pravý a rovnoramenný trojuholník.

2. Budovanie pravého trojuholníka

Pravý trojuholník je najjednoduchší typ trojuholníka, ktorý budeme študovať. Poďme sa rýchlo pozrieť na výstup, ktorý chceme získať:

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

Tu si všimneme, že trojuholník je tvorený 5 radmi, z ktorých každý má počet hviezdičiek rovný aktuálnemu číslu radu. Toto pozorovanie možno samozrejme zovšeobecniť: pre každý riadok od 1 do N, musíme tlačiť r hviezdy, kde r je aktuálny riadok a N je celkový počet riadkov.

Vytvorme teda trojuholník pomocou dvoch pre slučky:

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

3. Budovanie rovnoramenného trojuholníka

Teraz sa pozrime na formu rovnoramenného trojuholníka:

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

Čo vidíme v tomto prípade? Všimli sme si, že okrem hviezd musíme pre každý riadok vytlačiť aj nejaké medzery. Musíme teda prísť na to, koľko medzier a hviezd musíme pre každý riadok vytlačiť. Počet medzier a hviezd samozrejme závisí od aktuálneho riadku.

Najprv vidíme, že musíme vytlačiť 4 medzery pre prvý riadok a keď sa dostaneme nadol trojuholníka, potrebujeme 3 medzery, 2 medzery, 1 medzeru a pre posledný riadok vôbec žiadne medzery. Zovšeobecňujeme, musíme tlačiť N - r medzery pre každý riadok.

Po druhé, v porovnaní s prvým príkladom si uvedomíme, že tu potrebujeme nepárny počet hviezd: 1, 3, 5, 7 ...

Takže musíme tlačiť r x 2 - 1 hviezdičky pre každý riadok.

3.1. Pomocou vnoreného pre Slučky

Na základe vyššie uvedených pozorovaní vytvoríme náš druhý príklad:

public static String printAnIsoscelesTriangle (int N) {StringBuilder result = new StringBuilder (); pre (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 ()); } vratit vysledok.toString (); }

3.2. Používanie singla pre Slučka

Vlastne máme iný spôsob sa skladá iba z jediného pre slučka - využíva knižnicu Apache Commons Lang 3.

Smyčku for použijeme na iteráciu nad riadkami trojuholníka, ako sme to urobili v predchádzajúcich príkladoch. Potom použijeme StringUtils.repeat () metóda na vygenerovanie potrebných znakov pre každý riadok:

public static String printAnIsoscelesTriangleUsingStringUtils (int N) {StringBuilder result = new StringBuilder (); pre (int r = 1; r <= N; r ++) {result.append (StringUtils.repeat ('', N - r)); result.append (StringUtils.repeat ('*', 2 * r - 1)); result.append (System.lineSeparator ()); } vratit vysledok.toString (); }

Alebo môžeme urobiť šikovný trik s the podreťazec () metóda.

Môžeme extrahovať StringUtils.repeat () vyššie uvedenými metódami vytvoriť pomocný reťazec a potom použiť String.substring () metóda na to. Pomocný reťazec je zreťazenie maximálneho počtu medzier a maximálneho počtu hviezdičiek, ktoré potrebujeme na vytlačenie riadkov trojuholníka.

Pri pohľade na predchádzajúce príklady si všimneme, že potrebujeme maximálny počet N - 1 medzery pre prvý riadok a maximálny počet N x 2 - 1 hviezdičky v poslednom riadku:

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

Napríklad kedy N = 5 a r = 3, musíme vytlačiť „*****“, ktorý je zahrnutý v helperString premenná. Všetko, čo musíme urobiť, je nájsť správny vzorec pre podreťazec () metóda.

Teraz sa pozrime na úplný príklad:

public static String printAnIsoscelesTriangleUsingSubstring (int N) {StringBuilder result = new StringBuilder (); String helperString = StringUtils.repeat ('', N - 1) + StringUtils.repeat ('*', N * 2 - 1); pre (int r = 0; r <N; r ++) {result.append (helperString.substring (r, N + 2 * r)); result.append (System.lineSeparator ()); } vratit vysledok.toString (); }

Podobne, s trochou viac práce, by sme mohli urobiť tlač trojuholníka naopak.

4. Zložitosť

Ak sa pozrieme znova na prvý príklad, všimneme si, že každá vonkajšia slučka a vnútorná slučka majú maximum N krokov. Preto máme O (N ^ 2) časová zložitosť, kde N je počet riadkov trojuholníka.

Druhý príklad je podobný - jediný rozdiel je v tom, že máme dve vnútorné slučky, ktoré sú postupné a nezvyšujú časovú zložitosť.

Tretí príklad však používa iba a pre slučka s N krokov. Ale na každom kroku voláme buď StringUtils.repeat () metóda alebo podreťazec () metóda na pomocnom reťazci, pričom každý má O (N) zložitosť. Celková časová zložitosť teda zostáva rovnaká.

Nakoniec, ak hovoríme o pomocnom priestore, môžeme si rýchlo uvedomiť, že pre všetky príklady zostáva zložitosť v StringBuilder premenná. Pridaním celého trojuholníka k výsledok premenná, nemôžeme mať menej ako O (N ^ 2) zložitosť.

Keby sme priamo tlačili znaky, mali by sme samozrejme konštantnú priestorovú zložitosť pre prvé dva príklady. Tretí príklad ale používa pomocný reťazec a zložitosť priestoru by bola O (N).

5. Záver

V tomto tutoriáli sme sa naučili, ako tlačiť dva bežné typy trojuholníkov v Jave.

Najprv, študovali sme pravý trojuholník, čo je najjednoduchší typ trojuholníka, ktorý môžeme vytlačiť v Jave. Potom, preskúmali sme dva spôsoby stavby rovnoramenného trojuholníka. Prvý používa iba pre slučky a druhá využíva výhody StringUtils.repeat () a String.substring () metóda a pomáha nám písať menej kódu.

Nakoniec sme pre každý príklad analyzovali časovú a priestorovú zložitosť.

Ako vždy, všetky príklady nájdete na GitHub.