How to resolve the algorithm Zeckendorf number representation step by step in the REXX programming language
How to resolve the algorithm Zeckendorf number representation step by step in the REXX programming language
Table of Contents
Problem Statement
Just as numbers can be represented in a positional notation as sums of multiples of the powers of ten (decimal) or two (binary); all the positive integers can be represented as the sum of one or zero times the distinct members of the Fibonacci series. Recall that the first six distinct Fibonacci numbers are: 1, 2, 3, 5, 8, 13. The decimal number eleven can be written as 013 + 18 + 05 + 13 + 02 + 01 or 010100 in positional notation where the columns represent multiplication by a particular member of the sequence. Leading zeroes are dropped so that 11 decimal becomes 10100. 10100 is not the only way to make 11 from the Fibonacci numbers however; 013 + 18 + 05 + 03 + 12 + 11 or 010011 would also represent decimal 11. For a true Zeckendorf number there is the added restriction that no two consecutive Fibonacci numbers can be used which leads to the former unique solution.
Generate and show here a table of the Zeckendorf number representations of the decimal numbers zero to twenty, in order.
The intention in this task to find the Zeckendorf form of an arbitrary integer. The Zeckendorf form can be iterated by some bit twiddling rather than calculating each value separately but leave that to another separate task.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Zeckendorf number representation step by step in the REXX programming language
Source code in the rexx programming language
/* REXX ***************************************************************
* 11.10.2012 Walter Pachl
**********************************************************************/
fib='13 8 5 3 2 1'
Do i=6 To 1 By -1 /* Prepare Fibonacci Numbers */
Parse Var fib f.i fib /* f.1 ... f.7 */
End
Do n=0 To 20 /* for all numbers in the task */
m=n /* copy of number */
r='' /* result for n */
Do i=6 To 1 By -1 /* loop through numbers */
If m>=f.i Then Do /* f.i must be used */
r=r||1 /* 1 into result */
m=m-f.i /* subtract */
End
Else /* f.i is larger than the rest */
r=r||0 /* 0 into result */
End
r=strip(r,'L','0') /* strip leading zeros */
If r='' Then r='0' /* take care of 0 */
Say right(n,2)': 'right(r,6) /* show result */
End
/*REXX program calculates and displays the first N Zeckendorf numbers. */
numeric digits 100000 /*just in case user gets real ka─razy. */
parse arg N . /*let the user specify the upper limit.*/
if N=='' | N=="," then n=20; w= length(N) /*Not specified? Then use the default.*/
@.1= 1 /*start the array with 1 and 2. */
@.2= 2; do #=3 until #>=N; p= #-1; pp= #-2 /*build a list of Fibonacci numbers. */
@.#= @.p + @.pp /*sum the last two Fibonacci numbers. */
end /*#*/ /* [↑] #: contains a Fibonacci list.*/
do j=0 to N; parse var j x z /*task: process zero ──► N numbers.*/
do k=# by -1 for #; _= @.k /*process all the Fibonacci numbers. */
if x>=_ then do; z= z'1' /*is X>the next Fibonacci #? Append 1.*/
x= x - _ /*subtract this Fibonacci # from index.*/
end
else z= z'0' /*append zero (0) to the Fibonacci #. */
end /*k*/
say ' Zeckendorf' right(j, w) "=" right(z+0, 30) /*display a number.*/
end /*j*/ /*stick a fork in it, we're all done. */
/*REXX program calculates and displays the first N Zeckendorf numbers. */
numeric digits 100000 /*just in case user gets real ka─razy. */
parse arg N . /*let the user specify the upper limit.*/
if N=='' | N=="," then n=20; w= length(N) /*Not specified? Then use the default.*/
z=0 /*the index of a Zeckendorf number. */
do j=0 until z>N; _=x2b( d2x(j) ) /*task: process zero ──► N. */
if pos(11, _) \== 0 then iterate /*are there two consecutive ones (1s) ?*/
say ' Zeckendorf' right(z, w) "=" right(_+0, 30) /*display a number.*/
z= z + 1 /*bump the Zeckendorf number counter.*/
end /*j*/ /*stick a fork in it, we're all done. */
You may also check:How to resolve the algorithm Loops/Infinite step by step in the Wren programming language
You may also check:How to resolve the algorithm Anti-primes step by step in the EMal programming language
You may also check:How to resolve the algorithm Hello world/Graphical step by step in the REBOL programming language
You may also check:How to resolve the algorithm Barnsley fern step by step in the D programming language
You may also check:How to resolve the algorithm Search a list step by step in the MAXScript programming language