Sierpinski triangle: Difference between revisions
Content added Content deleted
(Added PicoLisp) |
(Replaced content with ' * * * * * * how to print the above triangle') |
||
Line 1: | Line 1: | ||
{{task|Fractals}} |
|||
* |
|||
Produce an ASCII representation of a Sierpinski triangle of order N. For example, the Sierpinski triangle of order 4 should look like this: |
|||
* * |
|||
<pre> |
|||
* * * |
|||
* |
|||
* * |
|||
* * |
|||
* * * * |
|||
* * |
|||
* * * * |
|||
* * * * |
|||
* * * * * * * * |
|||
* * |
|||
* * * * |
|||
* * * * |
|||
* * * * * * * * |
|||
* * * * |
|||
* * * * * * * * |
|||
* * * * * * * * |
|||
* * * * * * * * * * * * * * * * |
|||
</pre> |
|||
how to print the above triangle |
|||
See also [[Sierpinski carpet]] |
|||
=={{header|Ada}}== |
|||
This Ada example creates a string of the binary value for each line, converting the '0' values to spaces. |
|||
<lang ada>with Ada.Text_Io; use Ada.Text_Io; |
|||
with Ada.Strings.Fixed; |
|||
with Interfaces; use Interfaces; |
|||
procedure Sieteri_Triangles is |
|||
subtype Practical_Order is Unsigned_32 range 0..4; |
|||
function Pow(X : Unsigned_32; N : Unsigned_32) return Unsigned_32 is |
|||
begin |
|||
if N = 0 then |
|||
return 1; |
|||
else |
|||
return X * Pow(X, N - 1); |
|||
end if; |
|||
end Pow; |
|||
procedure Print(Item : Unsigned_32) is |
|||
use Ada.Strings.Fixed; |
|||
package Ord_Io is new Ada.Text_Io.Modular_Io(Unsigned_32); |
|||
use Ord_Io; |
|||
Temp : String(1..36) := (others => ' '); |
|||
First : Positive; |
|||
Last : Positive; |
|||
begin |
|||
Put(To => Temp, Item => Item, Base => 2); |
|||
First := Index(Temp, "#") + 1; |
|||
Last := Index(Temp(First..Temp'Last), "#") - 1; |
|||
for I in reverse First..Last loop |
|||
if Temp(I) = '0' then |
|||
Put(' '); |
|||
else |
|||
Put(Temp(I)); |
|||
end if; |
|||
end loop; |
|||
New_Line; |
|||
end Print; |
|||
procedure Sierpinski (N : Practical_Order) is |
|||
Size : Unsigned_32 := Pow(2, N); |
|||
V : Unsigned_32 := Pow(2, Size); |
|||
begin |
|||
for I in 0..Size - 1 loop |
|||
Print(V); |
|||
V := Shift_Left(V, 1) xor Shift_Right(V,1); |
|||
end loop; |
|||
end Sierpinski; |
|||
begin |
|||
for N in Practical_Order loop |
|||
Sierpinski(N); |
|||
end loop; |
|||
end Sieteri_Triangles;</lang> |
|||
=={{header|ALGOL 68}}== |
|||
{{trans|python}} |
|||
{{works with|ALGOL 68|Standard - no extensions to language used}} |
|||
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}} |
|||
<!-- {{does not work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386 - test missing transput}} --> |
|||
<lang algol68>PROC sierpinski = (INT n)[]STRING: ( |
|||
FLEX[0]STRING d := "*"; |
|||
FOR i TO n DO |
|||
[UPB d * 2]STRING next; |
|||
STRING sp := " " * (2 ** (i-1)); |
|||
FOR x TO UPB d DO |
|||
STRING dx = d[x]; |
|||
next[x] := sp+dx+sp; |
|||
next[UPB d+x] := dx+" "+dx |
|||
OD; |
|||
d := next |
|||
OD; |
|||
d |
|||
); |
|||
printf(($gl$,sierpinski(4)))</lang> |
|||
=={{header|AutoHotkey}}== |
|||
ahk [http://www.autohotkey.com/forum/viewtopic.php?t=44657&postdays=0&postorder=asc&start=150 discussion] |
|||
<lang autohotkey>Loop 6 |
|||
MsgBox % Triangle(A_Index) |
|||
Triangle(n,x=0,y=1) { ; Triangle(n) -> string of dots and spaces of Sierpinski triangle |
|||
Static t, l ; put chars in a static string |
|||
If (x < 1) { ; when called with one parameter |
|||
l := 2*x := 1<<(n-1) ; - compute location, string size |
|||
VarSetCapacity(t,l*x,32) ; - allocate memory filled with spaces |
|||
Loop %x% |
|||
NumPut(13,t,A_Index*l-1,"char") ; - new lines in the end of rows |
|||
} |
|||
If (n = 1) ; at the bottom of recursion |
|||
Return t, NumPut(46,t,x-1+(y-1)*l,"char") ; - write "." (better at proportional fonts) |
|||
u := 1<<(n-2) |
|||
Triangle(n-1,x,y) ; draw smaller triangle here |
|||
Triangle(n-1,x-u,y+u) ; smaller triangle down-left |
|||
Triangle(n-1,x+u,y+u) ; smaller triangle down right |
|||
Return t |
|||
}</lang> |
|||
=={{header|BASIC}}== |
|||
{{works with|FreeBASIC}} |
|||
{{works with|RapidQ}} |
|||
<lang freebasic>SUB triangle (x AS Integer, y AS Integer, length AS Integer, n AS Integer) |
|||
IF n = 0 THEN |
|||
LOCATE y,x: PRINT "*"; |
|||
ELSE |
|||
triangle (x, y+length, length/2, n-1) |
|||
triangle (x+length, y, length/2, n-1) |
|||
triangle (x+length*2, y+length, length/2, n-1) |
|||
END IF |
|||
END SUB |
|||
CLS |
|||
triangle 1,1,16,5</lang> |
|||
Note: The total height of the triangle is 2 * parameter ''length''. It should be power of two so that the pattern matches evenly with the character cells. Value 16 will thus create pattern of 32 lines. |
|||
=={{header|C}}== |
|||
This solution uses a cellular automaton (''rule 90'') with a proper initial status. |
|||
<lang c>#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <stdbool.h> |
|||
#include <string.h> |
|||
#ifndef _POSIX_C_SOURCE |
|||
char *strdup(const char *s) |
|||
{ |
|||
int l = strlen(s); |
|||
char *r = malloc(l+1); |
|||
memcpy(r, s, l+1); |
|||
return r; |
|||
} |
|||
#endif |
|||
#define truth(X) ((X)=='*'?true:false) |
|||
void rule_90(char *evstr) |
|||
{ |
|||
int i; |
|||
int l = strlen(evstr); |
|||
bool s[3]; |
|||
char *cp = strdup(evstr); |
|||
for(i=0;i < l; i++) { |
|||
s[1] = truth(cp[i]); |
|||
s[0] = (i-1) < 0 ? false : truth(cp[i-1]); |
|||
s[2] = (i+1) < l ? truth(cp[i+1]) : false; |
|||
if ( (s[0] && !s[2]) || (!s[0] && s[2]) ) { |
|||
evstr[i] = '*'; |
|||
} else { |
|||
evstr[i] = ' '; |
|||
} |
|||
} |
|||
free(cp); |
|||
}</lang> |
|||
<lang c>void sierpinski_triangle(int n) |
|||
{ |
|||
int i; |
|||
int l = 1<<(n+1); |
|||
char *b = malloc(l+1); |
|||
memset(b, ' ', l); |
|||
b[l] = 0; |
|||
b[l>>1] = '*'; |
|||
printf("%s\n", b); |
|||
for(i=0; i < l/2-1;i++) { |
|||
rule_90(b); |
|||
printf("%s\n", b); |
|||
} |
|||
free(b); |
|||
}</lang> |
|||
<lang c>int main() |
|||
{ |
|||
sierpinski_triangle(4); |
|||
return EXIT_SUCCESS; |
|||
}</lang> |
|||
=={{header|C sharp|C#}}== |
|||
<lang csharp>using System; |
|||
using System.Collections; |
|||
namespace RosettaCode { |
|||
class SierpinskiTriangle { |
|||
int len; |
|||
BitArray b; |
|||
public SierpinskiTriangle(int n) { |
|||
if (n < 1) { |
|||
throw new ArgumentOutOfRangeException("Order must be greater than zero"); |
|||
} |
|||
len = 1 << (n+1); |
|||
b = new BitArray(len+1, false); |
|||
b[len>>1] = true; |
|||
} |
|||
public void Display() { |
|||
for (int j = 0; j < len / 2; j++) { |
|||
for (int i = 0; i < b.Count; i++) { |
|||
Console.Write("{0}", b[i] ? "*" : " "); |
|||
} |
|||
Console.WriteLine(); |
|||
NextGen(); |
|||
} |
|||
} |
|||
private void NextGen() { |
|||
BitArray next = new BitArray(b.Count, false); |
|||
for (int i = 0; i < b.Count; i++) { |
|||
if (b[i]) { |
|||
next[i - 1] = next[i - 1] ^ true; |
|||
next[i + 1] = next[i + 1] ^ true; |
|||
} |
|||
} |
|||
b = next; |
|||
} |
|||
} |
|||
}</lang> |
|||
<lang csharp>namespace RosettaCode { |
|||
class Program { |
|||
static void Main(string[] args) { |
|||
SierpinskiTriangle t = new SierpinskiTriangle(4); |
|||
t.Display(); |
|||
} |
|||
} |
|||
}</lang> |
|||
{{trans|OCaml}} |
|||
{{works with|C sharp|C#|3.0+}} |
|||
<lang csharp>using System; |
|||
using System.Collections.Generic; |
|||
using System.Linq; |
|||
class Program |
|||
{ |
|||
public static List<String> Sierpinski(int n) |
|||
{ |
|||
var lines = new List<string> { "*" }; |
|||
string space = " "; |
|||
for (int i = 0; i < n; i++) |
|||
{ |
|||
lines = lines.Select(x => space + x + space) |
|||
.Concat(lines.Select(x => x + " " + x)).ToList(); |
|||
space += space; |
|||
} |
|||
return lines; |
|||
} |
|||
static void Main(string[] args) |
|||
{ |
|||
foreach (string s in Sierpinski(4)) |
|||
Console.WriteLine(s); |
|||
} |
|||
}</lang> |
|||
=={{header|Clojure}}== |
|||
'''Translation of''': Ada and Common Lisp, with a touch of Clojure's sequence handling. |
|||
<lang clojure>(ns example |
|||
(:require [clojure.contrib.math :as math])) |
|||
; Length of integer in binary |
|||
; (copied from a private multimethod in clojure.contrib.math) |
|||
(defmulti #^{:private true} integer-length class) |
|||
(defmethod integer-length java.lang.Integer [n] |
|||
(count (Integer/toBinaryString n))) |
|||
(defmethod integer-length java.lang.Long [n] |
|||
(count (Long/toBinaryString n))) |
|||
(defmethod integer-length java.math.BigInteger [n] |
|||
(count (.toString n 2))) |
|||
(defn sierpinski-triangle [order] |
|||
(loop [size (math/expt 2 order) |
|||
v (math/expt 2 (- size 1))] |
|||
(when (pos? size) |
|||
(println |
|||
(apply str (map #(if (bit-test v %) "*" " ") |
|||
(range (integer-length v))))) |
|||
(recur |
|||
(dec size) |
|||
(bit-xor (bit-shift-left v 1) (bit-shift-right v 1)))))) |
|||
(sierpinski-triangle 4) |
|||
</lang> |
|||
=={{header|Common Lisp}}== |
|||
<lang lisp>(defun print-sierpinski (order) |
|||
(loop with size = (expt 2 order) |
|||
repeat size |
|||
for v = (expt 2 (1- size)) then (logxor (ash v -1) (ash v 1)) |
|||
do (fresh-line) |
|||
(loop for i below (integer-length v) |
|||
do (princ (if (logbitp i v) "*" " ")))))</lang> |
|||
Printing each row could also be done by printing the integer in base 2 and replacing zeroes with spaces: <tt>(princ (substitute #\Space #\0 (format nil "~%~2,vR" (1- (* 2 size)) v)))</tt> |
|||
Replacing the iteration with <tt>for v = 1 then (logxor v (ash v 1))</tt> produces a "right" triangle instead of an "equilateral" one. |
|||
=={{header|D}}== |
|||
Adapted from Java version (this version is slower than the Python one). |
|||
<lang d>import std.stdio, std.string; |
|||
string[] sierpinski(int n) { |
|||
string[] parts = ["*"]; |
|||
string space = " "; |
|||
for (int i; i < n; i++) { |
|||
string[] parts2; |
|||
foreach (x; parts) |
|||
parts2 ~= space ~ x ~ space; |
|||
foreach (x; parts) |
|||
parts2 ~= x ~ " " ~ x; |
|||
parts = parts2; |
|||
space ~= space; |
|||
} |
|||
return parts; |
|||
} |
|||
void main() { |
|||
writefln(sierpinski(4).join("\n")); |
|||
}</lang> |
|||
That sierpinski() function can run at compile time too, so with a compile-time join it can compute the whole result at compile-time: |
|||
<lang d>string[] sierpinski(int n) { |
|||
string[] parts = ["*"]; |
|||
string space = " "; |
|||
for (int i; i < n; i++) { |
|||
string[] parts2; |
|||
foreach (x; parts) |
|||
parts2 ~= space ~ x ~ space; |
|||
foreach (x; parts) |
|||
parts2 ~= x ~ " " ~ x; |
|||
parts = parts2; |
|||
space ~= space; |
|||
} |
|||
return parts; |
|||
} |
|||
string joinCT(string[] parts, char sep) { |
|||
string result; |
|||
if (parts.length) { |
|||
foreach (part; parts[0 .. $-1]) { |
|||
result ~= part; |
|||
result ~= sep; |
|||
} |
|||
result ~= parts[$-1]; |
|||
} |
|||
return result; |
|||
} |
|||
pragma(msg, sierpinski(4).joinCT('\n')); |
|||
void main() {}</lang> |
|||
=={{header|E}}== |
|||
<lang e>def printSierpinski(order, out) { |
|||
def size := 2**order |
|||
for y in (0..!size).descending() { |
|||
out.print(" " * y) |
|||
for x in 0..!(size-y) { |
|||
out.print((x & y).isZero().pick("* ", " ")) |
|||
} |
|||
out.println() |
|||
} |
|||
}</lang> |
|||
<lang e>? printSierpinski(4, stdout)</lang> |
|||
Non-ASCII version (quality of results will depend greatly on text renderer): |
|||
<lang e>def printSierpinski(order, out) { |
|||
def size := 2**order |
|||
for y in (0..!size).descending() { |
|||
out.print(" " * y) |
|||
for x in 0..!(size-y) { |
|||
out.print((x & y).isZero().pick("◢◣", " ")) |
|||
} |
|||
out.println() |
|||
} |
|||
}</lang> |
|||
=={{header|Erlang}}== |
|||
{{trans|OCaml}} |
|||
<lang erlang> |
|||
-module(sierpinski). |
|||
-export([triangle/1]). |
|||
triangle(N) -> |
|||
F = fun(X) -> io:format("~s~n",[X]) end, |
|||
lists:foreach(F, triangle(N, ["*"], " ")). |
|||
triangle(0, Down, _) -> Down; |
|||
triangle(N, Down, Sp) -> |
|||
NewDown = [Sp++X++Sp || X<-Down]++[X++" "++X || X <- Down], |
|||
triangle(N-1, NewDown, Sp++Sp). |
|||
</lang> |
|||
=={{header|F Sharp|F#}}== |
|||
<lang fsharp>let sierpinski n = |
|||
let rec loop down space n = |
|||
if n = 0 then |
|||
down |
|||
else |
|||
loop (List.map (fun x -> space + x + space) down @ |
|||
List.map (fun x -> x + " " + x) down) |
|||
(space + space) |
|||
(n - 1) |
|||
in loop ["*"] " " n |
|||
let () = |
|||
List.iter (fun (i:string) -> System.Console.WriteLine(i)) (sierpinski 4)</lang> |
|||
=={{header|FALSE}}== |
|||
<lang false>[[$][$1&["*"]?$~1&[" "]?2/]#%" |
|||
"]s: { stars } |
|||
[$@$@|@@&~&]x: { xor } |
|||
[1\[$][1-\2*\]#%]e: { 2^n } |
|||
[e;!1\[$][\$s;!$2*x;!\1-]#%%]t: |
|||
4t;!</lang> |
|||
=={{header|Factor}}== |
|||
{{trans|OCaml}} |
|||
<lang factor>USING: io kernel math sequences ; |
|||
IN: sierpinski |
|||
: iterate-triangle ( triange spaces -- triangle' ) |
|||
[ [ dup surround ] curry map ] |
|||
[ drop [ dup " " glue ] map ] 2bi append ; |
|||
: (sierpinski) ( triangle spaces n -- triangle' ) |
|||
dup 0 = [ 2drop "\n" join ] [ |
|||
[ |
|||
[ iterate-triangle ] |
|||
[ nip dup append ] 2bi |
|||
] dip 1 - (sierpinski) |
|||
] if ; |
|||
: sierpinski ( n -- ) |
|||
[ { "*" } " " ] dip (sierpinski) print ;</lang> |
|||
=={{header|Forth}}== |
|||
<lang forth>: stars ( mask -- ) |
|||
begin |
|||
dup 1 and if [char] * else bl then emit |
|||
1 rshift dup |
|||
while space repeat drop ; |
|||
: triangle ( order -- ) |
|||
1 swap lshift ( 2^order ) |
|||
1 over 0 do |
|||
cr over i - spaces dup stars |
|||
dup 2* xor |
|||
loop 2drop ; |
|||
5 triangle</lang> |
|||
=={{header|Haskell}}== |
|||
<lang haskell>sierpinski 0 = ["*"] |
|||
sierpinski (n+1) = map ((space ++) . (++ space)) down |
|||
++ map (unwords . replicate 2) down |
|||
where down = sierpinski n |
|||
space = replicate (2^n) ' ' |
|||
printSierpinski = mapM_ putStrLn . sierpinski</lang> |
|||
=={{header|HaXe}}== |
|||
{{trans|JavaScript}} |
|||
<lang HaXe>class Main |
|||
{ |
|||
static function main() |
|||
{ |
|||
triangle(3); |
|||
} |
|||
static inline function println(str) { |
|||
Lib.println(str); |
|||
} |
|||
static inline var SPACE = ' '; |
|||
static inline var STAR = '*'; |
|||
static function triangle(o) { |
|||
var n = 1 << o; |
|||
var line = new Array<String>(); |
|||
for (i in 0...(n*2)) line[i] = SPACE; |
|||
line[n] = '*'; |
|||
for (i in 0...n) { |
|||
println(line.join('')); |
|||
var u ='*'; |
|||
var start = n - i; |
|||
var end = n + i + 1; |
|||
var t = SPACE; |
|||
for (j in start...end) { |
|||
t = (line[j-1] == line[j+1] ? SPACE : STAR); |
|||
line[j-1] = u; |
|||
u = t; |
|||
} |
|||
line[n+i] = t; |
|||
line[n+i+1] = STAR; |
|||
} |
|||
} |
|||
}</lang> |
|||
=={{header|IDL}}== |
|||
The only 'special' thing here is that the math is done in a byte array, filled with the numbers 32 and 42 and then output through a "<tt>string(array)</tt>" which prints the ascii representation of each individual element in the array. |
|||
<lang idl>pro sierp,n |
|||
s = (t = bytarr(3+2^(n+1))+32b) |
|||
t[2^n+1] = 42b |
|||
for lines = 1,2^n do begin |
|||
print,string( (s = t) ) |
|||
for i=1,n_elements(t)-2 do if s[i-1] eq s[i+1] then t[i]=32b else t[i]=42b |
|||
end |
|||
end</lang> |
|||
=={{header|J}}== |
|||
There are any number of succinct ways to produce this in J. Here's one that exploits self-similarity: |
|||
<lang j> |._31]\,(,.~,])^:4,:'* '</lang> |
|||
Here's one that leverages the relationship between Sierpinski's and Pascal's triangles: |
|||
<lang j> ' *'{~'1'=(-|."_1[:":2|!/~)i.-16</lang> |
|||
=={{header|Java}}== |
|||
{{trans|JavaScript}} |
|||
<lang java>public static void triangle(int n){ |
|||
n= 1 << n; |
|||
StringBuilder line= new StringBuilder(); //use a "mutable String" |
|||
char t= 0; |
|||
char u= 0; // avoid warnings |
|||
for(int i= 0;i <= 2 * n;++i) |
|||
line.append(" "); //start empty |
|||
line.setCharAt(n, '*'); //with the top point of the triangle |
|||
for(int i= 0;i < n;++i){ |
|||
System.out.println(line); |
|||
u= '*'; |
|||
for(int j= n - i;j < n + i + 1;++j){ |
|||
t= (line.charAt(j - 1) == line.charAt(j + 1) ? ' ' : '*'); |
|||
line.setCharAt(j - 1, u); |
|||
u= t; |
|||
} |
|||
line.setCharAt(n + i, t); |
|||
line.setCharAt(n + i + 1, '*'); |
|||
} |
|||
}</lang> |
|||
{{trans|Haskell}} |
|||
{{works with|Java|1.5+}} |
|||
<lang java>import java.util.*; |
|||
public class Sierpinski |
|||
{ |
|||
public static List<String> sierpinski(int n) |
|||
{ |
|||
List<String> down = Arrays.asList("*"); |
|||
String space = " "; |
|||
for (int i = 0; i < n; i++) { |
|||
List<String> newDown = new ArrayList<String>(); |
|||
for (String x : down) |
|||
newDown.add(space + x + space); |
|||
for (String x : down) |
|||
newDown.add(x + " " + x); |
|||
down = newDown; |
|||
space += space; |
|||
} |
|||
return down; |
|||
} |
|||
public static void main(String[] args) |
|||
{ |
|||
for (String x : sierpinski(4)) |
|||
System.out.println(x); |
|||
} |
|||
}</lang> |
|||
=={{header|JavaScript}}== |
|||
<lang javascript>function triangle(o) { |
|||
var n = 1<<o, line = new Array(2*n), i,j,t,u; |
|||
for (i=0; i<line.length; ++i) line[i] = ' '; |
|||
line[n] = '*'; |
|||
for (i=0; i<n; ++i) { |
|||
document.write(line.join('')+"\n"); |
|||
u ='*'; |
|||
for(j=n-i; j<n+i+1; ++j) { |
|||
t = (line[j-1] == line[j+1] ? ' ' : '*'); |
|||
line[j-1] = u; |
|||
u = t; |
|||
} |
|||
line[n+i] = t; |
|||
line[n+i+1] = '*'; |
|||
} |
|||
} |
|||
document.write("<pre>\n"); |
|||
triangle(6); |
|||
document.write("</pre>");</lang> |
|||
=={{header|Logo}}== |
|||
This will draw a graphical Sierpinski gasket using turtle graphics. |
|||
<lang logo>to sierpinski :n :length |
|||
if :n = 0 [stop] |
|||
repeat 3 [sierpinski :n-1 :length/2 fd :length rt 120] |
|||
end |
|||
seth 30 sierpinski 5 200</lang> |
|||
=={{header|Mathematica}}== |
|||
Cellular automaton (rule 90) based solution: |
|||
<lang mathematica>n=4;Grid[CellularAutomaton[90,{{1},0},2^n-1]/.{0->" ",1->"*"},ItemSize->All]</lang> |
|||
=={{header|OCaml}}== |
|||
<lang ocaml>let sierpinski n = |
|||
let rec loop down space n = |
|||
if n = 0 then |
|||
down |
|||
else |
|||
loop (List.map (fun x -> space ^ x ^ space) down @ |
|||
List.map (fun x -> x ^ " " ^ x) down) |
|||
(space ^ space) |
|||
(n - 1) |
|||
in loop ["*"] " " n |
|||
let () = |
|||
List.iter print_endline (sierpinski 4)</lang> |
|||
=={{header|Oz}}== |
|||
<lang oz>declare |
|||
fun {NextTriangle Triangle} |
|||
Sp = {Spaces {Length Triangle}} |
|||
in |
|||
{Flatten |
|||
[{Map Triangle fun {$ X} Sp#X#Sp end} |
|||
{Map Triangle fun {$ X} X#" "#X end} |
|||
]} |
|||
end |
|||
fun {Spaces N} if N == 0 then nil else & |{Spaces N-1} end end |
|||
fun lazy {Iterate F X} |
|||
X|{Iterate F {F X}} |
|||
end |
|||
SierpinskiTriangles = {Iterate NextTriangle ["*"]} |
|||
in |
|||
{ForAll {Nth SierpinskiTriangles 5} System.showInfo}</lang> |
|||
=={{header|Pascal}}== |
|||
{{trans|C}} |
|||
{{works with|Free Pascal}} |
|||
<lang pascal>program Sierpinski; |
|||
function ipow(b, n : Integer) : Integer; |
|||
var |
|||
i : Integer; |
|||
begin |
|||
ipow := 1; |
|||
for i := 1 to n do |
|||
ipow := ipow * b |
|||
end; |
|||
function truth(a : Char) : Boolean; |
|||
begin |
|||
if a = '*' then |
|||
truth := true |
|||
else |
|||
truth := false |
|||
end;</lang> |
|||
<lang pascal>function rule_90(ev : String) : String; |
|||
var |
|||
l, i : Integer; |
|||
cp : String; |
|||
s : Array[0..1] of Boolean; |
|||
begin |
|||
l := length(ev); |
|||
cp := copy(ev, 1, l); |
|||
for i := 1 to l do begin |
|||
if (i-1) < 1 then |
|||
s[0] := false |
|||
else |
|||
s[0] := truth(ev[i-1]); |
|||
if (i+1) > l then |
|||
s[1] := false |
|||
else |
|||
s[1] := truth(ev[i+1]); |
|||
if ( (s[0] and not s[1]) or (s[1] and not s[0]) ) then |
|||
cp[i] := '*' |
|||
else |
|||
cp[i] := ' '; |
|||
end; |
|||
rule_90 := cp |
|||
end; |
|||
procedure triangle(n : Integer); |
|||
var |
|||
i, l : Integer; |
|||
b : String; |
|||
begin |
|||
l := ipow(2, n+1); |
|||
b := ' '; |
|||
for i := 1 to l do |
|||
b := concat(b, ' '); |
|||
b[round(l/2)] := '*'; |
|||
writeln(b); |
|||
for i := 1 to (round(l/2)-1) do begin |
|||
b := rule_90(b); |
|||
writeln(b) |
|||
end |
|||
end;</lang> |
|||
<lang pascal>begin |
|||
triangle(4) |
|||
end.</lang> |
|||
=={{header|Perl}}== |
|||
<lang perl>sub sierpinski { |
|||
my ($n) = @_; |
|||
my @down = '*'; |
|||
my $space = ' '; |
|||
foreach (1..$n) { |
|||
@down = (map("$space$_$space", @down), map("$_ $_", @down)); |
|||
$space = "$space$space"; |
|||
} |
|||
return @down; |
|||
} |
|||
print "$_\n" foreach sierpinski 4;</lang> |
|||
=={{header|PL/I}}== |
|||
<lang PL/I> |
|||
sierpinski: procedure options (main); /* 2010-03-30 */ |
|||
declare t (79,79) char (1); |
|||
declare (i, j, k) fixed binary; |
|||
declare (y, xs, ys, xll, xrr, ixrr, limit) fixed binary; |
|||
t = ' '; |
|||
xs = 40; ys = 1; |
|||
/* Make initial triangle */ |
|||
call make_triangle (xs, ys); |
|||
y = ys + 4; |
|||
xll = xs-4; xrr = xs+4; |
|||
do k = 1 to 3; |
|||
limit = 0; |
|||
do forever; |
|||
ixrr = xrr; |
|||
do i = xll to xll+limit by 8; |
|||
if t(y-1, i) = ' ' then |
|||
do; |
|||
call make_triangle (i, y); |
|||
if t(y+3,i-5) = '*' then |
|||
t(y+3,i-4), t(y+3,ixrr+4) = '*'; |
|||
call make_triangle (ixrr, y); |
|||
end; |
|||
ixrr = ixrr - 8; |
|||
end; |
|||
xll = xll - 4; xrr = xrr + 4; |
|||
y = y + 4; |
|||
limit = limit + 8; |
|||
if xll+limit > xs-1 then leave; |
|||
end; |
|||
t(y-1,xs) = '*'; |
|||
end; |
|||
/* Finished generation; now print the Sierpinski triangle. */ |
|||
put edit (t) (skip, (hbound(t,2)) a); |
|||
make_triangle: procedure (x, y); |
|||
declare (x, y) fixed binary; |
|||
declare i fixed binary; |
|||
do i = 0 to 3; |
|||
t(y+i, x-i), t(y+i, x+i) = '*'; |
|||
end; |
|||
do i = x-2 to x+2; /* The base of the triangle. */ |
|||
t(y+3, i) = '*'; |
|||
end; |
|||
end make_triangle; |
|||
end sierpinski; |
|||
</lang> |
|||
=={{header|PicoLisp}}== |
|||
{{trans|Python}} |
|||
<lang PicoLisp>(de sierpinski (N) |
|||
(let (D '("*") S " ") |
|||
(do N |
|||
(setq |
|||
D (conc |
|||
(mapcar '((X) (pack S X S)) D) |
|||
(mapcar '((X) (pack X " " X)) D) ) |
|||
S (pack S S) ) ) |
|||
D ) ) |
|||
(mapc prinl (sierpinski 4))</lang> |
|||
=={{header|Pop11}}== |
|||
Solution using line buffer in an integer array oline, 0 represents ' ' |
|||
(space), 1 represents '*' (star). |
|||
<lang pop11>define triangle(n); |
|||
lvars k = 2**n, j, l, oline, nline; |
|||
initv(2*k+3) -> oline; |
|||
initv(2*k+3) -> nline; |
|||
for l from 1 to 2*k+3 do 0 -> oline(l) ; endfor; |
|||
1 -> oline(k+2); |
|||
0 -> nline(1); |
|||
0 -> nline(2*k+3); |
|||
for j from 1 to k do |
|||
for l from 1 to 2*k+3 do |
|||
printf(if oline(l) = 0 then ' ' else '*' endif); |
|||
endfor; |
|||
printf('\n'); |
|||
for l from 2 to 2*k+2 do |
|||
(oline(l-1) + oline(l+1)) rem 2 -> nline(l); |
|||
endfor; |
|||
(oline, nline) -> (nline, oline); |
|||
endfor; |
|||
enddefine; |
|||
triangle(4);</lang> |
|||
Alternative solution, keeping all triangle as list of strings |
|||
<lang pop11>define triangle2(n); |
|||
lvars acc = ['*'], spaces = ' ', j; |
|||
for j from 1 to n do |
|||
maplist(acc, procedure(x); spaces >< x >< spaces ; endprocedure) |
|||
<> maplist(acc, procedure(x); x >< ' ' >< x ; endprocedure) -> acc; |
|||
spaces >< spaces -> spaces; |
|||
endfor; |
|||
applist(acc, procedure(x); printf(x, '%p\n'); endprocedure); |
|||
enddefine; |
|||
triangle2(4);</lang> |
|||
=={{header|PowerShell}}== |
|||
{{Trans|JavaScript}} |
|||
<lang powershell>function triangle($o) { |
|||
$n = [Math]::Pow(2, $o) |
|||
$line = ,' '*(2*$n+1) |
|||
$line[$n] = '█' |
|||
$OFS = '' |
|||
for ($i = 0; $i -lt $n; $i++) { |
|||
Write-Host $line |
|||
$u = '█' |
|||
for ($j = $n - $i; $j -lt $n + $i + 1; $j++) { |
|||
if ($line[$j-1] -eq $line[$j+1]) { |
|||
$t = ' ' |
|||
} else { |
|||
$t = '█' |
|||
} |
|||
$line[$j-1] = $u |
|||
$u = $t |
|||
} |
|||
$line[$n+$i] = $t |
|||
$line[$n+$i+1] = '█' |
|||
} |
|||
}</lang> |
|||
=={{header|PureBasic}}== |
|||
<lang PureBasic>Procedure Triangle (X,Y, Length, N) |
|||
If N = 0 |
|||
DrawText( Y,X, "*",#Blue) |
|||
Else |
|||
Triangle (X+Length, Y, Length/2, N-1) |
|||
Triangle (X, Y+Length, Length/2, N-1) |
|||
Triangle (X+Length, Y+Length*2, Length/2, N-1) |
|||
EndIf |
|||
EndProcedure |
|||
OpenWindow(0, 100, 100,700,500 ,"Sierpinski triangle", #PB_Window_SystemMenu |1) |
|||
StartDrawing(WindowOutput(0)) |
|||
DrawingMode(#PB_2DDrawing_Transparent ) |
|||
Triangle(10,10,120,5) |
|||
Repeat |
|||
Until WaitWindowEvent()=#PB_Event_CloseWindow |
|||
End</lang> |
|||
=={{header|Python}}== |
|||
<lang python>def sierpinski(n): |
|||
d = ["*"] |
|||
for i in xrange(n): |
|||
sp = " " * (2 ** i) |
|||
d = [sp+x+sp for x in d] + [x+" "+x for x in d] |
|||
return d |
|||
print "\n".join(sierpinski(4))</lang> |
|||
=={{header|Ruby}}== |
|||
From the command line: |
|||
<lang ruby>ruby -le'16.times{|y|print" "*(15-y),(0..y).map{|x|~y&x>0?" ":" *"}}'</lang> |
|||
or, {{trans|Python}} |
|||
<lang ruby>def sierpinski_triangle(n) |
|||
triangle = ["*"] |
|||
n.times do |i| |
|||
sp = " " * (2**i) |
|||
triangle = triangle.collect {|x| sp + x + sp} + \ |
|||
triangle.collect {|x| x + " " + x} |
|||
end |
|||
triangle.join("\n") |
|||
end |
|||
puts sierpinski_triangle(4)</lang> |
|||
=={{header|Scala}}== |
|||
The Ruby command-line version (on Windows): |
|||
<lang scala>scala -e "for(y<-0 to 15){println(\" \"*(15-y)++(0 to y).map(x=>if((~y&x)>0)\" \"else\" *\")mkString)}"</lang> |
|||
The Forth version: |
|||
<lang scala>def sierpinski(n: Int) { |
|||
def star(n: Long) = if ((n & 1L) == 1L) "*" else " " |
|||
def stars(n: Long): String = if (n == 0L) "" else star(n) + " " + stars(n >> 1) |
|||
def spaces(n: Int) = " " * n |
|||
((1 << n) - 1 to 0 by -1).foldLeft(1L) { |
|||
case (bitmap, remainingLines) => |
|||
println(spaces(remainingLines) + stars(bitmap)) |
|||
(bitmap << 1) ^ bitmap |
|||
} |
|||
}</lang> |
|||
The Haskell version: |
|||
<lang scala>def printSierpinski(n: Int) { |
|||
def sierpinski(n: Int): List[String] = { |
|||
lazy val down = sierpinski(n - 1) |
|||
lazy val space = " " * (1 << (n - 1)) |
|||
n match { |
|||
case 0 => List("*") |
|||
case _ => (down map (space + _ + space)) ::: |
|||
(down map (List.fill(2)(_) mkString " ")) |
|||
} |
|||
} |
|||
sierpinski(n) foreach println |
|||
}</lang> |
|||
=={{header|Scheme}}== |
|||
{{trans|Haskell}} |
|||
<lang scheme>(define (sierpinski n) |
|||
(for-each |
|||
(lambda (x) (display (list->string x)) (newline)) |
|||
(let loop ((acc (list (list #\*))) (spaces (list #\ )) (n n)) |
|||
(if (zero? n) |
|||
acc |
|||
(loop |
|||
(append |
|||
(map (lambda (x) (append spaces x spaces)) acc) |
|||
(map (lambda (x) (append x (list #\ ) x)) acc)) |
|||
(append spaces spaces) |
|||
(- n 1))))))</lang> |
|||
=={{header|Seed7}}== |
|||
<lang seed7>$ include "seed7_05.s7i"; |
|||
const func array string: sierpinski (in integer: n) is func |
|||
result |
|||
var array string: parts is 1 times "*"; |
|||
local |
|||
var integer: i is 0; |
|||
var string: space is " "; |
|||
var array string: parts2 is 0 times ""; |
|||
var string: x is ""; |
|||
begin |
|||
for i range 1 to n do |
|||
parts2 := 0 times ""; |
|||
for x range parts do |
|||
parts2 &:= [] (space & x & space); |
|||
end for; |
|||
for x range parts do |
|||
parts2 &:= [] (x & " " & x); |
|||
end for; |
|||
parts := parts2; |
|||
space &:= space; |
|||
end for; |
|||
end func; |
|||
const proc: main is func |
|||
begin |
|||
writeln(join(sierpinski(4), "\n")); |
|||
end func;</lang> |
|||
=={{header|Tcl}}== |
|||
{{trans|Perl}} |
|||
<lang tcl>package require Tcl 8.5 |
|||
proc map {lambda list} { |
|||
foreach elem $list { |
|||
lappend result [apply $lambda $elem] |
|||
} |
|||
return $result |
|||
} |
|||
proc sierpinski_triangle n { |
|||
set down [list *] |
|||
set space " " |
|||
for {set i 1} {$i <= $n} {incr i} { |
|||
set down [concat \ |
|||
[map [subst -nocommands {x {expr {"$space[set x]$space"}}}] $down] \ |
|||
[map {x {expr {"$x $x"}}} $down] \ |
|||
] |
|||
append space $space |
|||
} |
|||
return [join $down \n] |
|||
} |
|||
puts [sierpinski_triangle 4]</lang> |
|||
=={{header|Ursala}}== |
|||
the straightforward recursive solution |
|||
<lang Ursala>#import nat |
|||
triangle = ~&a^?\<<&>>! ^|RNSiDlrTSPxSxNiCK9xSx4NiCSplrTSPT/~& predecessor</lang> |
|||
the cheeky cellular automaton solution |
|||
<lang Ursala>#import std |
|||
#import nat |
|||
rule = -$<0,&,0,0,&,0,0,0>@rSS zipp0*ziD iota8 |
|||
evolve "n" = @iNC ~&x+ rep"n" ^C\~& @h rule*+ swin3+ :/0+ --<0> |
|||
sierpinski = iota; --<&>@NS; iota; ^H/evolve@z @NS ^T/~& :/&</lang> |
|||
an example of each (converting from booleans to characters) |
|||
<lang Ursala>#show+ |
|||
examples = mat0 ~&?(`*!,` !)*** <sierpinski3,triangle4></lang> |
|||
output: |
|||
<pre style="height:30ex;overflow:scroll;"> |
|||
* |
|||
* * |
|||
* * |
|||
* * * * |
|||
* * |
|||
* * * * |
|||
* * * * |
|||
* * * * * * * * |
|||
* |
|||
* * |
|||
* * |
|||
* * * * |
|||
* * |
|||
* * * * |
|||
* * * * |
|||
* * * * * * * * |
|||
* * |
|||
* * * * |
|||
* * * * |
|||
* * * * * * * * |
|||
* * * * |
|||
* * * * * * * * |
|||
* * * * * * * * |
|||
* * * * * * * * * * * * * * * * |
|||
</pre> |
|||
=={{header|Vedit macro language}}== |
|||
===Iterative=== |
|||
{{trans|JavaScript}} |
|||
The macro writes the fractal into an edit buffer where it can be viewed and saved to file if required. |
|||
This allows creating images larger than screen, the size is only limited by free disk space. |
|||
<lang vedit>#3 = 16 // size (height) of the triangle |
|||
Buf_Switch(Buf_Free) // Open a new buffer for output |
|||
Ins_Char(' ', COUNT, #3*2+2) // fill first line with spaces |
|||
Ins_Newline |
|||
Line(-1) Goto_Col(#3) |
|||
Ins_Char('*', OVERWRITE) // the top of triangle |
|||
for (#10=0; #10 < #3-1; #10++) { |
|||
BOL Reg_Copy(9,1) Reg_Ins(9) // duplicate the line |
|||
#20 = '*' |
|||
for (#11 = #3-#10; #11 < #3+#10+1; #11++) { |
|||
Goto_Col(#11-1) |
|||
if (Cur_Char==Cur_Char(2)) { #21=' ' } else { #21='*' } |
|||
Ins_Char(#20, OVERWRITE) |
|||
#20 = #21 |
|||
} |
|||
Ins_Char(#21, OVERWRITE) |
|||
Ins_Char('*', OVERWRITE) |
|||
}</lang> |
|||
===Recursive=== |
|||
{{trans|BASIC}} |
|||
Vedit macro language does not have recursive functions, so some pushing and popping is needed to implement recursion. |
|||
<lang vedit>#1 = 1 // x |
|||
#2 = 1 // y |
|||
#3 = 16 // length (height of the triangle / 2) |
|||
#4 = 5 // depth of recursion |
|||
Buf_Switch(Buf_Free) // Open a new buffer for output |
|||
Ins_Newline(#3*2) // Create as many empty lines as needed |
|||
Call("Triangle") // Draw the triangle |
|||
BOF |
|||
Return |
|||
:Triangle: |
|||
if (#4 == 0) { |
|||
Goto_Line(#2) |
|||
EOL Ins_Char(' ', COUNT, #1-Cur_Col+1) // add spaces if needed |
|||
Goto_Col(#1) |
|||
Ins_Char('*', OVERWRITE) |
|||
} else { |
|||
Num_Push(1,4) |
|||
#2 += #3; #3 /= 2; #4--; Call("Triangle") |
|||
Num_Pop(1,4) |
|||
Num_Push(1,4) |
|||
#1 += #3; #3 /= 2; #4--; Call("Triangle") |
|||
Num_Pop(1,4) |
|||
Num_Push(1,4) |
|||
#1 += 2*#3; #2 += #3; #3 /= 2; #4--; Call("Triangle") |
|||
Num_Pop(1,4) |
|||
} |
|||
Return</lang> |
Revision as of 11:12, 17 June 2010
* * * * * *
how to print the above triangle