1 /* The Great Computer Language Shootout 2 http://shootout.alioth.debian.org/ 3 contributed by Isaac Gouy */ 4 5 function TreeNode(left,right,item){ 6 this.left = left; 7 this.right = right; 8 this.item = item; 9 } 10 11 TreeNode.prototype.itemCheck = function(){ 12 if (this.left==null) return this.item; 13 else return this.item + this.left.itemCheck() - this.right.itemCheck(); 14 } 15 16 function bottomUpTree(item,depth){ 17 if (depth>0){ 18 return new TreeNode( 19 bottomUpTree(2*item-1, depth-1) 20 ,bottomUpTree(2*item, depth-1) 21 ,item 22 ); 23 } 24 else { 25 return new TreeNode(null,null,item); 26 } 27 } 28 29 var ret; 30 31 for ( var n = 4; n <= 7; n += 1 ) { 32 var minDepth = 4; 33 var maxDepth = Math.max(minDepth + 2, n); 34 var stretchDepth = maxDepth + 1; 35 36 var check = bottomUpTree(0,stretchDepth).itemCheck(); 37 38 var longLivedTree = bottomUpTree(0,maxDepth); 39 for (var depth=minDepth; depth<=maxDepth; depth+=2){ 40 var iterations = 1 << (maxDepth - depth + minDepth); 41 42 check = 0; 43 for (var i=1; i<=iterations; i++){ 44 check += bottomUpTree(i,depth).itemCheck(); 45 check += bottomUpTree(-i,depth).itemCheck(); 46 } 47 } 48 49 ret = longLivedTree.itemCheck(); 50 } 51
