streamalism.org

1. Inleiding

In deze zelfstudie gaan we verschillende manieren onderzoeken om een ​​driehoek in Java af te drukken.

Er zijn natuurlijk veel soorten driehoeken. Hier, we gaan er maar een paar onderzoeken: rechter en gelijkbenige driehoeken.

2. Bouwen aan een rechthoekige driehoek

De rechthoekige driehoek is het eenvoudigste type driehoek dat we gaan bestuderen. Laten we snel kijken naar de output die we willen verkrijgen:

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

Hier zien we dat de driehoek bestaat uit 5 rijen, elk met een aantal sterren dat gelijk is aan het huidige rijnummer. Deze observatie kan natuurlijk worden gegeneraliseerd: voor elke rij van 1 tot N, we moeten afdrukken r sterren, waar r is de huidige rij en N is het totale aantal rijen.

Laten we dus de driehoek bouwen met twee voor lussen:

openbare statische String printARightTriangle (int N) {StringBuilder resultaat = nieuwe 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. Het bouwen van een gelijkbenige driehoek

Laten we nu eens kijken naar de vorm van een gelijkbenige driehoek:

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

Wat zien we in dit geval? We merken dat, Naast de sterren moeten we ook enkele spaties voor elke rij afdrukken. We moeten dus uitzoeken hoeveel spaties en sterren we voor elke rij moeten afdrukken. Het aantal spaties en sterren hangt natuurlijk af van de huidige rij.

Ten eerste zien we dat we 4 spaties voor de eerste rij moeten afdrukken, en als we de driehoek omlaag gaan, hebben we 3 spaties, 2 spaties, 1 spatie en helemaal geen spaties nodig voor de laatste rij. Generaliseren, we moeten afdrukken N - r spaties voor elke rij.

Ten tweede, in vergelijking met het eerste voorbeeld, realiseren we ons dat we hier een oneven aantal sterren nodig hebben: 1, 3, 5, 7 ...

Zo, we moeten afdrukken r x 2-1 sterren voor elke rij.

3.1. Met behulp van Genest voor Loops

Laten we op basis van de bovenstaande observaties ons tweede voorbeeld maken:

openbare statische String printAnIsoscelesTriangle (int N) {StringBuilder resultaat = nieuwe 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. Met behulp van een enkele voor Lus

Eigenlijk hebben we dat op een andere manier bestaat slechts uit een enkele voor loop - het gebruikt de Apache Commons Lang 3-bibliotheek.

We gaan de for-lus gebruiken om de rijen van de driehoek te herhalen, zoals we in de vorige voorbeelden hebben gedaan. Vervolgens gebruiken we de StringUtils.repeat () methode om de benodigde karakters voor elke rij te genereren:

openbare statische String printAnIsoscelesTriangleUsingStringUtils (int N) {StringBuilder resultaat = nieuwe 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 (); }

Of we kunnen een leuke truc doen met de deelstring () methode.

We kunnen het StringUtils.repeat () methoden hierboven om een ​​helperstring te bouwen en vervolgens de String.substring () methode erop. De hulpstring is een aaneenschakeling van het maximale aantal spaties en het maximale aantal sterren dat we nodig hebben om de rijen van de driehoek af te drukken.

Als we naar de voorgaande voorbeelden kijken, merken we dat we er een maximaal aantal nodig hebben N - 1 spaties voor de eerste rij en een maximum aantal N x 2-1 sterren voor de laatste rij:

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

Bijvoorbeeld wanneer N = 5 en r = 3, moeten we "*****" afdrukken, die is opgenomen in het helperString variabele. Het enige wat we hoeven te doen is de juiste formule voor de deelstring () methode.

Laten we nu het volledige voorbeeld bekijken:

openbare statische String printAnIsoscelesTriangleUsingSubstring (int N) {StringBuilder resultaat = nieuwe 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 (); }

Evenzo kunnen we met net wat meer werk de driehoek ondersteboven laten afdrukken.

4. Complexiteit

Als we het eerste voorbeeld nog eens bekijken, zien we een buitenste lus en een binnenste lus met elk een maximum van N stappen. Daarom hebben we O (N ^ 2) tijdcomplexiteit, waar N is het aantal rijen van de driehoek.

Het tweede voorbeeld is vergelijkbaar - het enige verschil is dat we twee binnenste lussen hebben, die opeenvolgend zijn en de tijdcomplexiteit niet vergroten.

Het derde voorbeeld gebruikt echter alleen een voor loop met N stappen. Maar bij elke stap noemen we ofwel de StringUtils.repeat () methode of de deelstring () methode op de helper string, elk met AAN) complexiteit. De algehele tijdcomplexiteit blijft dus hetzelfde.

Ten slotte, als we het hebben over de hulpruimte, kunnen we ons snel realiseren dat, voor alle voorbeelden, de complexiteit in de StringBuilder variabele. Door de hele driehoek toe te voegen aan de resultaat variabele, we kunnen niet minder hebben dan O (N ^ 2) complexiteit.

Als we de tekens rechtstreeks zouden afdrukken, zouden we natuurlijk een constante ruimtecomplexiteit hebben voor de eerste twee voorbeelden. Maar het derde voorbeeld gebruikt de helper-string en de ruimtecomplexiteit zou zijn AAN).

5. Conclusie

In deze zelfstudie hebben we geleerd hoe u twee veelvoorkomende soorten driehoeken in Java kunt afdrukken.

Eerste, we hebben de rechthoekige driehoek bestudeerd, het eenvoudigste type driehoek dat we in Java kunnen afdrukken. Dan, we hebben twee manieren onderzocht om een ​​gelijkbenige driehoek te bouwen. De eerste gebruikt alleen voor loops en de andere maakt gebruik van de StringUtils.repeat () en de String.substring () methode en helpt ons minder code te schrijven.

Ten slotte hebben we voor elk voorbeeld de complexiteit van tijd en ruimte geanalyseerd.

Zoals altijd zijn alle voorbeelden te vinden op GitHub.