Sierpinski triangle: Difference between revisions
(→{{header|Forth}}: more compact representation allows larger order) |
(Java version based on JS version) |
||
Line 151: | Line 151: | ||
' *'{~'1'=(-|."_1[:":2|!/~)i.-16 |
' *'{~'1'=(-|."_1[:":2|!/~)i.-16 |
||
=={{header|Java}}== |
|||
<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, '*'); |
|||
} |
|||
}</java> |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
Revision as of 22:28, 14 March 2008
You are encouraged to solve this task according to the task description, using any language you may know.
Produce an ASCII representation of a Sierpinski triangle of order N. For example, the Sierpinski triangle of order 4 should look like this:
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Ada
This Ada example creates a string of the binary value for each line, converting the '0' values to spaces. <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;</ada>
Common 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) "*" " ")))))
Printing each row could also be done by printing the integer in base 2 and replacing zeroes with spaces: (princ (substitute #\Space #\0 (format nil "~%~2,vR" (1- (* 2 size)) v)))
Replacing the iteration with for v = 1 then (logxor v (ash v 1))
produces a "right" triangle instead of an "equilateral" one.
D
Translated from Lisp examples. <d>module sierpinski ; import std.stdio ;
long ipow(int x, int n) { return n > 0 ? x*ipow(x, n-1) : 1 ; }
void sietri(uint n) {
if(n > 5) return writefln("integer bit size limited : n should not be larger than 5") ; long size = ipow(2,n) ; long v = ipow(2, size) ; for(int i = 0 ; i < size ; i++) { for(int j = 0; j <v.sizeof*8 ; j++ ) writef(ipow(2,j) & v ? "*" : " ") ; writefln() ; v = (v << 1) ^ (v >> 1) ; }
}
void main() {
for(int n = 0; n < 5 ; n++) sietri(n) ;
}</d>
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
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
J
There are any number of succinct ways to produce this in J. Here's one that exploits self-similarity:
|._31]\,(,.~,])^:4,:'* '
Here's one that leverages the relationship between Sierpinski's and Pascal's triangles:
' *'{~'1'=(-|."_1[:":2|!/~)i.-16
Java
<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, '*'); } }</java>
JavaScript
<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("
\n"); triangle(6); document.write("
");
</javascript>
Scheme
As the Haskell.
(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))))))