streamalism.org

1. Uvod

U ovom uputstvu istražit ćemo nekoliko načina za ispis trokuta na Javi.

Postoje, naravno, mnoge vrste trokuta. Ovdje, istražit ćemo samo njih nekoliko: pravokutni i jednakokračni trokut.

2. Izgradnja pravokutnog trokuta

Pravokutni je trokut najjednostavniji tip trokuta koji ćemo proučavati. Kratko ćemo pogledati izlaz koji želimo dobiti:

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

Ovdje primjećujemo da je trokut napravljen od 5 redaka, a svaki ima broj zvijezda jednak broju trenutnog reda. Naravno, ovo se zapažanje može generalizirati: za svaki red od 1 do N, moramo tiskati r zvijezde, gdje r je trenutni redak i N je ukupan broj redaka.

Dakle, izgradimo trokut pomoću dva za petlje:

javni statički niz printARightTriangle (int N) {StringBuilder rezultat = novi StringBuilder (); for (int r = 1; r <= N; r ++) {for (int j = 1; j <= r; j ++) {result.append ("*"); } result.append (System.lineSeparator ()); } vratiti rezultat.toString (); }

3. Izgradnja jednakokračnog trokuta

Pogledajmo sada oblik jednakokračnog trokuta:

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

Što vidimo u ovom slučaju? Primjećujemo da, osim zvijezda, za svaki red moramo ispisati i neke razmake. Dakle, moramo shvatiti koliko prostora i zvijezda moramo ispisati za svaki red. Naravno, broj razmaka i zvijezda ovisi o trenutnom redu.

Prvo, vidimo da trebamo ispisati 4 razmaka za prvi redak, a kako se spuštamo trokut, trebaju nam 3 razmaka, 2 razmaka, 1 razmak i uopće nema razmaka za posljednji redak. Općenito, moramo tiskati N - r razmaci za svaki red.

Drugo, uspoređujući s prvim primjerom, shvaćamo da nam ovdje treba neparan broj zvijezda: 1, 3, 5, 7 ...

Tako, moramo tiskati r x 2 - 1 zvjezdice za svaki red.

3.1. Korištenje ugniježđenog za Petlje

Na temelju gornjih zapažanja, kreirajmo naš drugi primjer:

javni statički String printAnIsoscelesTriangle (int N) {StringBuilder rezultat = novi StringBuilder (); for (int r = 1; r <= N; r ++) {for (int sp = 1; sp <= N - r; sp ++) {result.append (""); } za (int c = 1; c <= (r * 2) - 1; c ++) {result.append ("*"); } result.append (System.lineSeparator ()); } vratiti rezultat.toString (); }

3.2. Korištenje singla za Petlja

Zapravo imamo i drugi način sastoji se samo od jednog za petlja - koristi biblioteku Apache Commons Lang 3.

Upotrijebit ćemo petlju for za prelazak preko redova trokuta kao što smo to činili u prethodnim primjerima. Zatim ćemo upotrijebiti StringUtils.repeat () metoda kako bi se generirali potrebni znakovi za svaki redak:

javni statički niz printAnIsoscelesTriangleUsingStringUtils (int N) {StringBuilder rezultat = novi 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 ()); } vratiti rezultat.toString (); }

Ili, možemo napraviti fin trik the podniz () metoda.

Možemo izvući StringUtils.repeat () gore navedene metode za izgradnju pomoćnog niza, a zatim primjenu String.substring () metoda na njemu. Pomoćni niz je spajanje maksimalnog broja razmaka i maksimalnog broja zvjezdica koji su nam potrebni za ispis redaka trokuta.

Gledajući prethodne primjere, primjećujemo da nam treba maksimalan broj N - 1 prostora za prvi red i maksimalan broj N x 2 - 1 zvijezde za zadnji red:

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

Na primjer, kada N = 5 i r = 3, moramo ispisati "*****", koji je uključen u helperString varijabilna. Sve što trebamo učiniti je pronaći pravu formulu za podniz () metoda.

Pogledajmo sada cjelovit primjer:

javni statički niz printAnIsoscelesTriangleUsingSubstring (int N) {StringBuilder rezultat = novi StringBuilder (); String helperString = StringUtils.repeat ('', N - 1) + StringUtils.repeat ('*', N * 2 - 1); za (int r = 0; r <N; r ++) {result.append (helperString.substring (r, N + 2 * r)); result.append (System.lineSeparator ()); } vratiti rezultat.toString (); }

Slično tome, sa samo malo više posla, mogli bismo ispisati trokut naopako.

4. Složenost

Ako ponovno pogledamo prvi primjer, primjećujemo vanjsku i unutarnju petlju od kojih svaka ima najviše N stepenice. Stoga imamo O (N ^ 2) složenost vremena, gdje N je broj redaka trokuta.

Sličan je i drugi primjer - jedina je razlika što imamo dvije unutarnje petlje koje su sekvencijalne i ne povećavaju vremensku složenost.

Treći primjer, međutim, koristi samo a za petlja sa N stepenice. Ali, na svakom koraku zovemo bilo StringUtils.repeat () metoda ili podniz () metoda na pomoćnom nizu, svaki ima NA) složenost. Dakle, ukupna vremenska složenost ostaje ista.

Napokon, ako govorimo o pomoćnom prostoru, možemo brzo shvatiti da, za sve primjere, složenost ostaje u StringBuilder varijabilna. Dodavanjem cijelog trokuta na proizlaziti varijabla, ne možemo imati manje od O (N ^ 2) složenost.

Naravno, ako bismo izravno ispisali znakove, imali bismo stalnu složenost prostora za prva dva primjera. Ali, treći primjer koristi pomoćni niz i složenost prostora bi bila NA).

5. Zaključak

U ovom uputstvu naučili smo kako ispisati dvije uobičajene vrste trokuta u Javi.

Prvi, proučavali smo pravokutni trokut, što je najjednostavniji tip trokuta koji možemo ispisati na Javi. Zatim, istražili smo dva načina izgradnje jednakokračnog trokuta. Prvi koristi samo za petlje, a druga iskorištava StringUtils.repeat () i String.substring () metoda i pomaže nam da napišemo manje koda.

Na kraju smo analizirali vremensku i prostornu složenost za svaki primjer.

Kao i uvijek, svi se primjeri mogu naći na GitHubu.