Anonymous user
Pascal's triangle: Difference between revisions
add Tcl
(Add Factor) |
(add Tcl) |
||
Line 621:
end
</lang>
=={{header|Tcl}}==
===Summing from Previous Rows===
<lang tcl>proc pascal_iterative n {
if {$n < 1} {error "undefined behaviour for n < 1"}
set row [list 1]
lappend rows $row
set i 1
while {[incr i] <= $n} {
set prev $row
set row [list 1]
for {set j 1} {$j < [llength $prev]} {incr j} {
lappend row [expr {[lindex $prev [expr {$j - 1}]] + [lindex $prev $j]}]
}
lappend row 1
lappend rows $row
}
return $rows
}
puts [join [pascal_iterative 6] \n]</lang>
<pre>1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1</pre>
===Using binary coefficients===
{{trans|BASIC}}
<lang tcl>proc pascal_coefficients n {
if {$n < 1} {error "undefined behaviour for n < 1"}
for {set i 0} {$i < $n} {incr i} {
set c 1
set row [list $c]
for {set j 0} {$j < $i} {incr j} {
set c [expr {$c * ($i - $j) / ($j + 1)}]
lappend row $c
}
lappend rows $row
}
return $rows
}
puts [join [pascal_coefficients 6] \n]</lang>
===Combinations===
{{trans|Java}}, however thanks to Tcl 8.5's arbitrary precision integer arithmetic, this solution is not limited to a couple of dozen rows. Uses a caching factorial calculator to improve performance.
<lang tcl>package require Tcl 8.5
proc pascal_combinations n {
if {$n < 1} {error "undefined behaviour for n < 1"}
for {set i 0} {$i < $n} {incr i} {
set row [list]
for {set j 0} {$j <= $i} {incr j} {
lappend row [C $i $j]
}
lappend rows $row
}
return $rows
}
proc C {n k} {
expr {[ifact $n] / ([ifact $k] * [ifact [expr {$n - $k}]])}
}
set fact_cache {1 1}
proc ifact n {
global fact_cache
if {$n < [llength $fact_cache]} {
return [lindex $fact_cache $n]
}
set i [expr {[llength $fact_cache] - 1}]
set sum [lindex $fact_cache $i]
while {$i < $n} {
incr i
set sum [expr {$sum * $i}]
lappend fact_cache $sum
}
return $sum
}
puts [join [pascal_combinations 6] \n]</lang>
===Comparing Performance===
<lang tcl>set n 100
puts "calculate $n rows:"
foreach proc {pascal_iterative pascal_coefficients pascal_combinations} {
puts "$proc: [time [list $proc $n] 100]"
}</lang>
outputs
<pre>calculate 100 rows:
pascal_iterative: 2800.14 microseconds per iteration
pascal_coefficients: 8760.98 microseconds per iteration
pascal_combinations: 38176.66 microseconds per iteration</pre>
=={{header|Vedit macro language}}==
| |||