Fibonacci n-step number sequences: Difference between revisions
m (typo in task description) |
(→Tcl: Added implementation) |
||
Line 50: | Line 50: | ||
[1, 1, 2, 4, 8, 16, 32, 64, 127, 253] |
[1, 1, 2, 4, 8, 16, 32, 64, 127, 253] |
||
>>> </lang> |
>>> </lang> |
||
=={{header|Tcl}}== |
|||
{{works with|Tcl|8.6}} |
|||
<lang tcl>package require Tcl 8.6 |
|||
proc fibber {args} { |
|||
coroutine fib[incr ::fibs]=[join $args ","] apply {fn { |
|||
set n [info coroutine] |
|||
foreach f $fn { |
|||
if {![yield $n]} return |
|||
set n $f |
|||
} |
|||
while {[yield $n]} { |
|||
set fn [linsert [lreplace $fn 0 0] end [set n [+ {*}$fn]]] |
|||
} |
|||
} ::tcl::mathop} $args |
|||
} |
|||
proc print10 cr { |
|||
for {set i 1} {$i <= 10} {incr i} { |
|||
lappend out [$cr true] |
|||
} |
|||
puts \[[join [lappend out ...] ", "]\] |
|||
$cr false |
|||
} |
|||
puts "FIBONACCI" |
|||
print10 [fibber 1 1] |
|||
puts "TRIBONACCI" |
|||
print10 [fibber 1 1 2] |
|||
puts "TETRANACCI" |
|||
print10 [fibber 1 1 2 4] |
|||
puts "LUCAS" |
|||
print10 [fibber 2 1]</lang> |
|||
{{out}} |
|||
<pre> |
|||
FIBONACCI |
|||
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...] |
|||
TRIBONACCI |
|||
[1, 1, 2, 4, 7, 13, 24, 44, 81, 149, ...] |
|||
TETRANACCI |
|||
[1, 1, 2, 4, 8, 15, 29, 56, 108, 208, ...] |
|||
LUCAS |
|||
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76, ...] |
|||
</pre> |
Revision as of 23:02, 24 May 2012
These number series are an expansion of the ordinary Fibonacci sequence where:
- For n = 2 we have the Fibonacci sequence; with initial values [1, 1] and
- For n = 3 we have the tribonacci sequence; with initial values [1, 1, 2] and
- For n = 4 we have the tetranacci sequence; with initial values [1, 1, 2, 4] and
... - For general n>2 we have the Fibonacci n-step sequence - ; with initial values of the first n values of the (n-1)'th Fibonacci n-step sequence ; and k'th value of this n'th sequence being
Allied sequences can be generated where the initial values are changed. The Lucas series sums the two preceeding values like the fibonacci series for n==2 but has the values [2, 1] as its initial values.
The task is to:
- Write a function to generate Fibonacci n-step number sequences given its initial values and assuming the number of initial values determines how many previous values are summed to make the next number of the series.
- Use this to print and show here the first ten members of the Fibo/tribo/tetra-nacci and Lucas sequences.
- C.f
Python
<lang python>>>> def fiblike(start): addnum = len(start) def fibber(n): try: return fibber.memo[n] except: ans = sum(fibber(i) for i in range(n-addnum, n)) fibber.memo.append(ans) return ans fibber.memo = start[:] return fibber
>>> fibo = fiblike([1,1]) >>> [fibo(i) for i in range(10)] [1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> lucas = fiblike([2,1]) >>> [lucas(i) for i in range(10)] [2, 1, 3, 4, 7, 11, 18, 29, 47, 76] >>> f3= fiblike([1,1,2]) # tribo- >>> [f3(i) for i in range(10)] [1, 1, 2, 4, 7, 13, 24, 44, 81, 149] >>> f4 = fiblike([1,1,2,4]) # tetra- >>> [f4(i) for i in range(10)] [1, 1, 2, 4, 8, 15, 29, 56, 108, 208] >>> f5 = fiblike([1,1,2,4,8]) # penta- >>> [f5(i) for i in range(10)] [1, 1, 2, 4, 8, 16, 31, 61, 120, 236] >>> f6 = fiblike([1,1,2,4,8,16]) # hexa- >>> [f6(i) for i in range(10)] [1, 1, 2, 4, 8, 16, 32, 63, 125, 248] >>> f7 = fiblike([1,1,2,4,8,16,32]) # hepta >>> [f7(i) for i in range(10)] [1, 1, 2, 4, 8, 16, 32, 64, 127, 253] >>> </lang>
Tcl
<lang tcl>package require Tcl 8.6
proc fibber {args} {
coroutine fib[incr ::fibs]=[join $args ","] apply {fn {
set n [info coroutine] foreach f $fn { if {![yield $n]} return set n $f } while {[yield $n]} { set fn [linsert [lreplace $fn 0 0] end [set n [+ {*}$fn]]] }
} ::tcl::mathop} $args
}
proc print10 cr {
for {set i 1} {$i <= 10} {incr i} {
lappend out [$cr true]
} puts \[[join [lappend out ...] ", "]\] $cr false
} puts "FIBONACCI" print10 [fibber 1 1] puts "TRIBONACCI" print10 [fibber 1 1 2] puts "TETRANACCI" print10 [fibber 1 1 2 4] puts "LUCAS" print10 [fibber 2 1]</lang>
- Output:
FIBONACCI [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...] TRIBONACCI [1, 1, 2, 4, 7, 13, 24, 44, 81, 149, ...] TETRANACCI [1, 1, 2, 4, 8, 15, 29, 56, 108, 208, ...] LUCAS [2, 1, 3, 4, 7, 11, 18, 29, 47, 76, ...]